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.
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.
 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).
 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).
 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.
 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).
 N. Miklin, J. J. Borkała, and M. Pawłowski, Semi-device-independent self-testing of unsharp measurements, Phys. Rev. Research 2, 033014 (2020).
 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).
 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).
 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).
 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).
 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).
 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).
 C. Emary, N. Lambert, and F. Nori, Leggett–Garg inequalities, Rep. Prog. Phys. 77, 016001 (2014).
 J. S. Bell, On the Einstein-Podolsky-Rosen paradox, Physics 1, 195 10.1103/PhysicsPhysiqueFizika.1.195 (1964).
 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).
 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).
 T. Fritz, Quantum correlations in the temporal clauser–horne–shimony–holt (chsh) scenario, New J. Phys. 12, 083055 (2010).
 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).
 C. Budroni, G. Vitagliano, and M. P. Woods, Ticking-clock performance enhanced by nonclassical temporal correlations, Phys. Rev. Research 3, 033051 (2021).
 A. Paz, Introduction to probabilistic automata (Academic Press, 1971).
 J. Shallit and M.-W. Wang, Automatic complexity of strings, Journal of Automata, Language and Combinatorics 6, 537 (2001).
 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).
 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).
 C. Budroni, T. Moroder, M. Kleinmann, and O. Gühne, Bounding temporal quantum correlations, Phys. Rev. Lett. 111, 020403 (2013).
 C. Budroni and C. Emary, Temporal quantum correlations and Leggett-Garg inequalities in multilevel systems, Phys. Rev. Lett. 113, 050401 (2014).
 A. Sohbi, D. Markham, J. Kim, and M. T. Quintino, Certifying dimension of quantum systems by sequential projective measurements, Quantum 5, 472 (2021).
 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).
 J. Bowles, F. Baccari, and A. Salavrakos, Bounding sets of sequential quantum correlations and device-independent randomness certification, Quantum 4, 344 (2020).
 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.
 J.-P. Allouche and J. Shallit, Automatic sequences: theory, applications, generalizations (Cambridge University Press, 2003).
 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).
 C. R. Shalizi and J. P. Crutchfield, Computational mechanics: Pattern and prediction, structure and simplicity, Journal of statistical physics 104, 817 (2001).
 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).
 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).
 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.
 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).
 Costantino Budroni, Giuseppe Vitagliano, and Mischa P. Woods, "Ticking-clock performance enhanced by nonclassical temporal correlations", Physical Review Research 3 3, 033051 (2021).
 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).
The above citations are from Crossref's cited-by service (last updated successfully 2022-10-05 04:39:29) and SAO/NASA ADS (last updated successfully 2022-10-05 04:39:30). 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.