Temporal correlations in the simplest measurement sequences

Lucas B. Vieira; Costantino Budroni

doi:10.22331/q-2022-01-18-623

Temporal correlations in the simplest measurement sequences

Lucas B. Vieira¹ and Costantino Budroni^1,2

¹Institute for Quantum Optics and Quantum Information (IQOQI), Austrian Academy of Sciences, Boltzmanngasse 3, 1090 Vienna, Austria
²Faculty of Physics, University of Vienna, Boltzmanngasse 5, 1090 Vienna, Austria

Published:	2022-01-18, volume 6, page 623
Eprint:	arXiv:2104.02467v2
Doi:	https://doi.org/10.22331/q-2022-01-18-623
Citation:	Quantum 6, 623 (2022).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We investigate temporal correlations in the simplest measurement scenario, i.e., that of a physical system on which the same measurement is performed at different times, producing a sequence of dichotomic outcomes. The resource for generating such sequences is the internal dimension, or $memory$, of the system. We characterize the minimum memory requirements for sequences to be obtained deterministically, and numerically investigate the probabilistic behavior below this memory threshold, in both classical and quantum scenarios. A particular class of sequences is found to offer an upper-bound for all other sequences, which suggests a nontrivial universal upper-bound of $1/e$ for the classical probability of realization of any sequence below this memory threshold. We further present evidence that no such nontrivial bound exists in the quantum case.

Featured image: (a) Schematic representation of the generation of temporal correlations. Results of the numerical optimization: (b) classical probabilities (black dots), conjectured upper bound (red lines), and universal bound (purple line), sorted by increasing conjecture upper bound; (c) obtained classical and quantum optimal models sorted by quantum advantage.

Popular summary

An information processing task can be thought of as sequential operations, possibly conditioned on inputs, producing an output at each step. As these operations occur one at a time, outputs are correlated in time. From a quantum mechanical perspective, these operations can be interpreted as measurements of some properties of a physical system. Any such operation on a physical system modifies (or store information in) it, but up to a limit, given by its internal memory.

Here, we consider the simplest form of temporal correlations: A single finite-dimensional system subjected to the same two-outcome (0 or 1) measurement at different times, producing a binary sequence. We investigate the minimal dimension d necessary to generate a sequence with certainty, which we call its deterministic complexity (DC), and provide an efficient algorithm to compute it. This quantity is central to investigating quantum advantages, since a difference between classical and quantum temporal correlations may arise only below this threshold, for d < DC, when sequences can only be produced probabilistically.

In this scenario, we numerically optimize probabilities for a large number of sequences, confined to various memory sizes, for classical and quantum models. Our results suggest that the probability of each sequence, for any d < DC, can be upper bounded by a directly computable expression associated with the probability of a special sequence, called one-tick sequence, with the same DC and same dimension. If proven, this conjecture would imply a universal classical bound of 1/e for the probabilistic realization of any sequence. We introduce a method to optimize quantum models that shows a quantum advantage for the vast majority of sequences and dimensions considered. Finally, we show that a universal (nontrivial) bound does not exist for quantum models.

► BibTeX data

@article{Vieira2022temporal,
  doi = {10.22331/q-2022-01-18-623},
  url = {https://doi.org/10.22331/q-2022-01-18-623},
  title = {Temporal correlations in the simplest measurement sequences},
  author = {Vieira, Lucas B. and Budroni, Costantino},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {623},
  month = jan,
  year = {2022}
}

► References

[1] M. Markiewicz, A. Przysieżna, S. Brierley, and T. Paterek, Genuinely multipoint temporal quantum correlations and universal measurement-based quantum computing, Phys. Rev. A 89, 062319 (2014).
https://doi.org/10.1103/PhysRevA.89.062319

[2] M. Zurel, C. Okay, and R. Raussendorf, Hidden variable model for universal quantum computation with magic states on qubits, Phys. Rev. Lett. 125, 260404 (2020).
https://doi.org/10.1103/PhysRevLett.125.260404

[3] S. Wiesner, Conjugate coding, ACM Sigact News 15, 78 (1983).
https://doi.org/10.1145/1008908.1008920

[4] A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and a lower bound for 1-way quantum automata, in Proceedings of the thirty-first annual ACM symposium on Theory of computing (1999) pp. 376–383.
https://doi.org/10.1145/301250.301347

[5] A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and quantum finite automata, Journal of the ACM (JACM) 49, 496 (2002).
https://doi.org/10.1145/581771.581773

[6] J. Bowles, N. Brunner, and M. Pawłowski, Testing dimension and nonclassicality in communication networks, Phys. Rev. A 92, 022351 (2015).
https://doi.org/10.1103/PhysRevA.92.022351

[7] E. A. Aguilar, M. Farkas, D. Martínez, M. Alvarado, J. Cariñe, G. B. Xavier, J. F. Barra, G. Cañas, M. Pawłowski, and G. Lima, Certifying an irreducible 1024-dimensional photonic state using refined dimension witnesses, Phys. Rev. Lett. 120, 230503 (2018).
https://doi.org/10.1103/PhysRevLett.120.230503

[8] N. Miklin, J. J. Borkała, and M. Pawłowski, Semi-device-independent self-testing of unsharp measurements, Phys. Rev. Research 2, 033014 (2020).
https://doi.org/10.1103/PhysRevResearch.2.033014

[9] M. Kleinmann, O. Gühne, J. R. Portillo, J. Åke Larsson, and A. Cabello, Memory cost of quantum contextuality, New J. Phys. 13, 113011 (2011).
https://doi.org/10.1088/1367-2630/13/11/113011

[10] G. Fagundes and M. Kleinmann, Memory cost for simulating all quantum correlations from the peres–mermin scenario, J. Phys. A 50, 325302 (2017).
https://doi.org/10.1088/1751-8121/aa7ab3

[11] A. J. P. Garner, Q. Liu, J. Thompson, V. Vedral, and M. Gu, Provably unbounded memory advantage in stochastic simulation using quantum mechanics, New J. Phys. 19, 103009 (2017).
https://doi.org/10.1088/1367-2630/aa82df

[12] T. J. Elliott and M. Gu, Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes, npj Quantum Information 4, 1 (2018).
https://doi.org/10.1038/s41534-018-0064-4

[13] T. J. Elliott, C. Yang, F. C. Binder, A. J. P. Garner, J. Thompson, and M. Gu, Extreme dimensionality reduction with quantum modeling, Phys. Rev. Lett. 125, 260501 (2020).
https://doi.org/10.1103/PhysRevLett.125.260501

[14] C. Spee, Certifying the purity of quantum states with temporal correlations, Phys. Rev. A 102, 012420 (2020).
https://doi.org/10.1103/PhysRevA.102.012420

[15] P. Erker, M. T. Mitchison, R. Silva, M. P. Woods, N. Brunner, and M. Huber, Autonomous quantum clocks: Does thermodynamics limit our ability to measure time?, Phys. Rev. X 7, 031022 (2017).
https://doi.org/10.1103/PhysRevX.7.031022

[16] M. P. Woods, R. Silva, G. Pütz, S. Stupar, and R. Renner, Quantum clocks are more accurate than classical ones, arXiv (2018), arXiv:1806.00491 [quant-ph].
arXiv:1806.00491

[17] M. P. Woods, Autonomous Ticking Clocks from Axiomatic Principles, Quantum 5, 381 (2021).
https://doi.org/10.22331/q-2021-01-17-381

[18] E. Schwarzhans, M. P. E. Lock, P. Erker, N. Friis, and M. Huber, Autonomous temporal probability concentration: Clockworks and the second law of thermodynamics, Phys. Rev. X 11, 011046 (2021).
https://doi.org/10.1103/PhysRevX.11.011046

[19] A. J. Leggett and A. Garg, Quantum mechanics versus macroscopic realism: Is the flux there when nobody looks?, Phys. Rev. Lett. 54, 857 (1985).
https://doi.org/10.1103/PhysRevLett.54.857

[20] C. Emary, N. Lambert, and F. Nori, Leggett–Garg inequalities, Rep. Prog. Phys. 77, 016001 (2014).
https://doi.org/10.1088/0034-4885/77/1/016001

[21] J. S. Bell, On the Einstein-Podolsky-Rosen paradox, Physics 1, 195 10.1103/PhysicsPhysiqueFizika.1.195 (1964).
https://doi.org/10.1103/PhysicsPhysiqueFizika.1.195

[22] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Bell nonlocality, Rev. Mod. Phys. 86, 419 (2014).
https://doi.org/10.1103/RevModPhys.86.419

[23] M. M. Wilde and A. Mizel, Addressing the clumsiness loophole in a Leggett-Garg test of macrorealism, Found. Phys. 42, 256 (2012).
https://doi.org/10.1007/s10701-011-9598-4

[24] C. Budroni, G. Vitagliano, G. Colangelo, R. J. Sewell, O. Gühne, G. Tóth, and M. W. Mitchell, Quantum nondemolition measurement enables macroscopic leggett-garg tests, Phys. Rev. Lett. 115, 200403 (2015).
https://doi.org/10.1103/PhysRevLett.115.200403

[25] J. J. Halliwell, Leggett-Garg inequalities and no-signaling in time: A quasiprobability approach, Phys. Rev. A 93, 022123 (2016).
https://doi.org/10.1103/PhysRevA.93.022123

[26] G. C. Knee, K. Kakuyanagi, M.-C. Yeh, Y. Matsuzaki, H. Toida, H. Yamaguchi, S. Saito, A. J. Leggett, and W. J. Munro, A strict experimental test of macroscopic realism in a superconducting flux qubit, Nat. Commun. 7, 13253 (2016).
https://doi.org/10.1038/ncomms13253

[27] C. Emary, Ambiguous measurements, signaling, and violations of Leggett-Garg inequalities, Phys. Rev. A 96, 042102 (2017).
https://doi.org/10.1103/PhysRevA.96.042102

[28] R. Uola, G. Vitagliano, and C. Budroni, Leggett-Garg macrorealism and the quantum nondisturbance conditions, Phys. Rev. A 100, 042117 (2019).
https://doi.org/10.1103/PhysRevA.100.042117

[29] C. Budroni, G. Fagundes, and M. Kleinmann, Memory cost of temporal correlations, New J. Phys. 21, 093018 (2019).
https://doi.org/10.1088/1367-2630/ab3cb4

[30] T. Fritz, Quantum correlations in the temporal clauser–horne–shimony–holt (chsh) scenario, New J. Phys. 12, 083055 (2010).
https://doi.org/10.1088/1367-2630/12/8/083055

[31] J. Hoffmann, C. Spee, O. Gühne, and C. Budroni, Structure of temporal correlations of a qubit, New J. Phys. 20, 102001 (2018).
https://doi.org/10.1088/1367-2630/aae87f

[32] C. Spee, H. Siebeneich, T. F. Gloger, P. Kaufmann, M. Johanning, M. Kleinmann, C. Wunderlich, and O. Gühne, Genuine temporal correlations can certify the quantum dimension, New J. Phys. 22, 023028 (2020a).
https://doi.org/10.1088/1367-2630/ab6d42

[33] C. Spee, C. Budroni, and O. Gühne, Simulating extremal temporal correlations, New Journal of Physics 22, 103037 (2020b).
https://doi.org/10.1088/1367-2630/abb899

[34] Y. Mao, C. Spee, Z.-P. Xu, and O. Gühne, Structure of dimension-bounded temporal correlations, arXiv (2020), arXiv:2005.13964 [quant-ph].
arXiv:2005.13964

[35] C. Budroni, G. Vitagliano, and M. P. Woods, Ticking-clock performance enhanced by nonclassical temporal correlations, Phys. Rev. Research 3, 033051 (2021).
https://doi.org/10.1103/PhysRevResearch.3.033051

[36] M. O. Rabin, Probabilistic automata, Information and Control 6, 230 (1963).
https://doi.org/10.1016/S0019-9958(63)90290-0

[37] A. Paz, Introduction to probabilistic automata (Academic Press, 1971).

[38] J. Shallit and M.-W. Wang, Automatic complexity of strings, Journal of Automata, Language and Combinatorics 6, 537 (2001).

[39] G. Kirchmair, F. Zähringer, R. Gerritsma, M. Kleinmann, O. Gühne, A. Cabello, R. Blatt, and C. F. Roos, State-independent experimental test of quantum contextuality, Nature (London) 460, 494 (2009).
https://doi.org/10.1038/nature08172

[40] O. Gühne, M. Kleinmann, A. Cabello, J.-Å. Larsson, G. Kirchmair, F. Zähringer, R. Gerritsma, and C. F. Roos, Compatibility and noncontextuality for sequential measurements, Phys. Rev. A 81, 022121 (2010).
https://doi.org/10.1103/PhysRevA.81.022121

[41] C. Budroni, A. Cabello, O. Gühne, M. Kleinmann, and J.-Å. Larsson, Quantum Contextuality, arXiv (2021), arXiv:2102.13036 [quant-ph].
arXiv:2102.13036

[42] C. Budroni, T. Moroder, M. Kleinmann, and O. Gühne, Bounding temporal quantum correlations, Phys. Rev. Lett. 111, 020403 (2013).
https://doi.org/10.1103/PhysRevLett.111.020403

[43] C. Budroni and C. Emary, Temporal quantum correlations and Leggett-Garg inequalities in multilevel systems, Phys. Rev. Lett. 113, 050401 (2014).
https://doi.org/10.1103/PhysRevLett.113.050401

[44] G. Schild and C. Emary, Maximum violations of the quantum-witness equality, Phys. Rev. A 92, 032101 (2015).
https://doi.org/10.1103/PhysRevA.92.032101

[45] M. Ringbauer and R. Chaves, Probing the non-classicality of temporal correlations, Quantum 1, 35 (2017).
https://doi.org/10.22331/q-2017-11-25-35

[46] A. Sohbi, D. Markham, J. Kim, and M. T. Quintino, Certifying dimension of quantum systems by sequential projective measurements, Quantum 5, 472 (2021).
https://doi.org/10.22331/q-2021-06-10-472

[47] R. Gallego, L. E. Würflinger, R. Chaves, A. Acín, and M. Navascués, Nonlocality in sequential correlation scenarios, New Journal of Physics 16, 033037 (2014).
https://doi.org/10.1088/1367-2630/16/3/033037

[48] C. Spee, Signaling between time steps prohibits nonlocality beyond hidden nonlocality, arXiv (2020), arXiv:2011.12774 [quant-ph].
https://doi.org/10.1088/1751-8121/ac2aea
arXiv:2011.12774

[49] J. Bowles, F. Baccari, and A. Salavrakos, Bounding sets of sequential quantum correlations and device-independent randomness certification, Quantum 4, 344 (2020).
https://doi.org/10.22331/q-2020-10-19-344

[50] C. Nicaud, Average state complexity of operations on unary automata, in Mathematical Foundations of Computer Science 1999, edited by M. Kutyłowski, L. Pacholski, and T. Wierzbicki (Springer Berlin Heidelberg, Berlin, Heidelberg, 1999) pp. 231–240.
https://doi.org/10.1007/3-540-48340-3_21

[51] J.-P. Allouche and J. Shallit, Automatic sequences: theory, applications, generalizations (Cambridge University Press, 2003).

[52] M. Holzer and M. Kutrib, Nondeterministic finite automata — recent results on the descriptional and computational complexity, International Journal of Foundations of Computer Science 20, 563 (2009).
https://doi.org/10.1142/S0129054109006747

[53] C. R. Shalizi and J. P. Crutchfield, Computational mechanics: Pattern and prediction, structure and simplicity, Journal of statistical physics 104, 817 (2001).
https://doi.org/10.1023/A:1010388907793

[54] D. P. Kingma and J. Ba, Adam: A Method for Stochastic Optimization, arXiv (2014), arXiv:1412.6980 [cs.LG].
arXiv:1412.6980

[55] Online repository containing the code used for the optimizations and the data obtained as a result. https://github.com/1ucasvb-research/TCSMS.
https://github.com/1ucasvb-research/TCSMS

[56] M. L. Almeida, J.-D. Bancal, N. Brunner, A. Acín, N. Gisin, and S. Pironio, Guess your neighbor's input: A multipartite nonlocal game with no quantum advantage, Phys. Rev. Lett. 104, 230404 (2010).
https://doi.org/10.1103/PhysRevLett.104.230404

[57] M. Domaratzki, D. Kisman, and J. Shallit, On the number of distinct languages accepted by finite automata with n states, Journal of Automata, Languages and Combinatorics 7, 469 (2002).

[58] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, Pytorch: An imperative style, high-performance deep learning library, in Advances in Neural Information Processing Systems 32 (Curran Associates, Inc., 2019) pp. 8024–8035.

Cited by

[1] Lorenzo Catani, Ricardo Faleiro, Pierre-Emmanuel Emeriau, Shane Mansfield, and Anna Pappa, "Connecting xor and xor * games", Physical Review A 109 1, 012427 (2024).

[2] Kawthar Al Rasbi, Lewis A. Clark, and Almut Beige, "Quantum physics cannot be captured by classical linear hidden variable theories even in the absence of entanglement", Frontiers in Physics 12, 1325239 (2024).

[3] Lucas B. Vieira, Simon Milz, Giuseppe Vitagliano, and Costantino Budroni, "Witnessing environment dimension through temporal correlations", Quantum 8, 1224 (2024).

[4] Wan-Guan Chang, Chia-Yi Ju, Guang-Yin Chen, Yueh-Nan Chen, and Huan-Yu Ku, "Visually quantifying single-qubit quantum memory", Physical Review Research 6 2, 023035 (2024).

[5] Mirjam Weilenmann, Costantino Budroni, and Miguel Navascués, "Optimization of Time-Ordered Processes in the Finite and Asymptotic Regimes", PRX Quantum 5 2, 020351 (2024).

[6] Huan-Yu Ku, Josef Kadlec, Antonín Černoch, Marco Túlio Quintino, Wenbin Zhou, Karel Lemr, Neill Lambert, Adam Miranowicz, Shin-Liang Chen, Franco Nori, and Yueh-Nan Chen, "Quantifying Quantumness of Channels Without Entanglement", PRX Quantum 3 2, 020338 (2022).

[7] Moritz F. Richter, Andrea Smirne, Walter T. Strunz, and Dario Egloff, "Classical Invasive Description of Informationally‐Complete Quantum Processes", Annalen der Physik 536 4, 2300304 (2024).

[8] Giuseppe Vitagliano and Costantino Budroni, "Leggett-Garg macrorealism and temporal correlations", Physical Review A 107 4, 040101 (2023).

[9] Costantino Budroni, Adán Cabello, Otfried Gühne, Matthias Kleinmann, and Jan-Åke Larsson, "Kochen-Specker contextuality", Reviews of Modern Physics 94 4, 045007 (2022).

[10] Feng-Jui Chan, Yi-Te Huang, Jhen-Dong Lin, Huan-Yu Ku, Jui-Sheng Chen, Hong-Bin Chen, and Yueh-Nan Chen, "Maxwell's two-demon engine under pure dephasing noise", Physical Review A 106 5, 052201 (2022).

[11] Costantino Budroni, Giuseppe Vitagliano, and Mischa P. Woods, "Ticking-clock performance enhanced by nonclassical temporal correlations", Physical Review Research 3 3, 033051 (2021).

[12] Huan-Yu Ku, Hao-Cheng Weng, Yen-An Shih, Po-Chen Kuo, Neill Lambert, Franco Nori, Chih-Sung Chuu, and Yueh-Nan Chen, "Hidden nonmacrorealism: Reviving the Leggett-Garg inequality with stochastic operations", Physical Review Research 3 4, 043083 (2021).

[13] SeungYeop Baik, Sicheol Sung, and Yo-Sub Han, "A Framework for Quantum Finite-State Languages with Density Mapping", arXiv:2407.02776, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-08-31 23:55:46) and SAO/NASA ADS (last updated successfully 2024-08-31 23:55:47). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.