The minimal memory required to model a given stochastic process - known as the statistical complexity - is a widely adopted quantifier of structure in complexity science. Here, we ask if quantum mechanics can fundamentally change the qualitative behaviour of this measure. We study this question in the context of the classical Ising spin chain. In this system, the statistical complexity is known to grow monotonically with temperature. We evaluate the spin chain's quantum mechanical statistical complexity by explicitly constructing its provably simplest quantum model, and demonstrate that this measure exhibits drastically different behaviour: it rises to a maximum at some finite temperature then tends back towards zero for higher temperatures. This demonstrates how complexity, as captured by the amount of memory required to model a process, can exhibit radically different behaviour when quantum processing is allowed.
We apply this measure to the Ising spin chain – a series of magnetically interacting spins that can each be aligned in one of two directions. The classical statistical complexity of an Ising spin chain only ever increases with temperature. On the other hand, the quantum statistical complexity rises to a maximum at some finite temperature then tends back towards zero for higher temperatures. This difference in the qualitative behaviour of complexity measures shows us that when we also consider quantum perspectives, our conclusions about “What is complex?” may be drastically changed.
 J. P. Crutchfield and K. Young, Physical Review Letters 63, 105 (1989).
 J. P. Crutchfield, Physica D: Nonlinear Phenomena 75, 11 (1994).
 C. R. Shalizi and J. P. Crutchfield, Journal of statistical physics 104, 817 (2001).
 C. R. Shalizi et al., Ph.D. thesis, University of Wisconsin-Madison (2001).
 C. R. Shalizi and K. L. Shalizi, in Proceedings of the 20th conference on Uncertainty in artificial intelligence (AUAI Press, 2004), pp. 504-511.
 D. Kelly, M. Dillingham, A. Hudson, and K. Wiesner, PloS one 7, e29703 (2012).
 N. Perry and P.-M. Binder, Physical Review E 60, 459 (1999).
 J. E. Hanson and J. P. Crutchfield, Physica D: Nonlinear Phenomena 103, 169 (1997).
 W. Gonçalves, R. Pinto, J. Sartorelli, and M. De Oliveira, Physica A: Statistical Mechanics and its Applications 257, 385 (1998).
 P. Tino and M. Koteles, IEEE Transactions on Neural Networks 10, 284 (1999).
 J. Crutchfield and D. Feldman, Physical Review E 55, 1239R (1997).
 M. Gu, K. Wiesner, E. Rieper, and V. Vedral, Nature communications 3, 762 (2012).
 R. Tan, D. R. Terno, J. Thompson, V. Vedral, and M. Gu, The European Physical Journal Plus 129, 1 (2014).
 J. Mahoney, C. Aghamohammadi, and J. Crutchfield, Scientific Reports 6 (2016).
 P. M. Riechers, J. R. Mahoney, C. Aghamohammadi, and J. P. Crutchfield, Phys. Rev. A 93 (2015).
 M. S. Palsson, M. Gu, J. Ho, H. M. Wiseman, and G. J. Pryde, Science Advances, 3.2, e1601302 (2017).
 D. P. Feldman, Ph.D. thesis, University of California, Davis (1998).
 J. M. Yeomans, Statistical mechanics of phase transitions (Clarendon Press, 1992).
 R. Jozsa and J. Schlienz, Physical Review A 62, 012301 (2000).
 E. Schneidman, M. J. Berry, R. Segev, and W. Bialek, Nature 440, 1007 (2006).
 T. L. Hill, The Journal of Chemical Physics 30, 383 (1959).
 B. Simon and R. B. Griffiths, Communications in Mathematical Physics 33, 145 (1973).
 S. Torquato, Physical biology 8, 015017 (2011).
 C. R. Shalizi, K. L. Shalizi, and R. Haslinger, Physical review letters 93, 118701 (2004).
 J. P. Crutchfield, C. J. Ellison, R. G. James, and J. R. Mahoney, Chaos 30, 3 (2010).
 N. Barnett and J. P. Crutchfield, Journal of Statistical Physics 161, 404 (2015).
 M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information (Cambridge university press, 2010).
 C. Aghamohammadi, J. R. Mahoney and J. P. Crutchfield, Physics Letters A 381, 1223-1227 (2017).
 C. Aghamohammadi, J. R. Mahoney and J. P. Crutchfield, arXiv:1609.03650v2.
 A. J. P. Garner, Q. Liu, J. Thompson, V. Vedral and M. Gu, arXiv:1609.04408.
 T.J. Elliott, M. Gu, arXiv:1704.04231.
 J. Thompson, A. J. P. Garner, V. Vedral and M. Gu, npj Quantum Information 3, 6 (2017).
 Thomas J. Elliott, Mile Gu, "Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes", npj Quantum Information 4, 18 (2018).
 Andrew J P Garner, Qing Liu, Jayne Thompson, Vlatko Vedral, mile Gu, "Provably unbounded memory advantage in stochastic simulation using quantum mechanics", New Journal of Physics 19, 103009 (2017).
(The above data is from Crossref's cited-by service. Unfortunately not all publishers provide suitable and complete citation data so that some citing works or bibliographic details may be missing.)
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.