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.
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.
Abstract How much information do we need about a process’ past to faithfully simulate its future? The statistical complexity is a prominent quantifier of structure for stochastic processes. Quantum machines, however, can simulate classical stochastic processes while storing significantly less information than their optimal classical counterparts. This implies qualitative divergences between classical and quantum statistical complexity. Here, we develop error-tolerant techniques to witness such divergences, enabling us to account for the inevitable imperfections in realising quantum stochastic simulators with present-day quantum technology. We apply these tools to experimentally verify the quantum memory advantage in simulating an Ising spin chain, even when accounting for experimental distortion. This then leads us to observe a recently conjectured effect, the ambiguity of simplicity—the notion that the relative complexity of two different processes can depend on whether we model the process using classical or quantum means of information processing.
The modelling of stochastic processes is ubiquitous throughout the natural and social sciences. An ideal model produces the correct statistical output without any unnecessary complexity. This minimal-complexity criterion is important conceptually, entailing the least number of causes of effects (Occam's razor), and practically, entailing the least stored information in the simulation. Here, we experimentally compare classical and quantum information encodings in simulating an Ising spin chain, showing that quantum encodings perform better and redefine our understanding of what is complex. We experimentally observe a recently conjectured effect, the ambiguity of simplicity. Specifically, we simulate Ising chains at different temperatures, A and B, such that classical encodings require fewer resources to model A than B, while quantum encodings are simpler for B than A. This challenges the perspective that relative complexity is contained solely in the configuration of the system being modelled. Our error-tolerant techniques account for inevitable imperfections in realising quantum simulators, thus providing the technological milestone needed to simulate increasingly complex stochastic processes.
Statistical complexity measures are distinctive tools that can detect significant physical phenomena. Many of these phenomena occur in such a way that they leave signatures that can be interpreted as changes in the state of the system, which can be read as statistical complexity through these measures, measured on a scale of order and disorder. We investigate the classical statistical complexity measure (CSCM) defined by López-Ruiz et al. and apply it to a simple model of discrete time evolution, characterized by finite Markov chains in dimension 2, for stochastic and bistochastic evolutions. Additionally, we introduce a quantum version for measuring statistical complexity: the quantum statistical complexity measure (QSCM), in the context of quantum information theory, and use it as a signaling function for quantum correlation transitions, measured on a scale of order and disorder. We consider the possibility that such transitions characterize intriguing physical phenomena, such as quantum phase transitions or sudden variations in correlation distributions. Our measure is applied to two analytically solvable Hamiltonian models: the one-dimensional quantum Ising model in the reduced single-particle state, and the Heisenberg chain XXZ of spin-1/2 in the state reduced by two particles. We analyze the measurement behavior in quantum phase transitions for finite system sizes and in the thermodynamic limit using the Bethe ansatz technique. We conclude that the quantum statistical complexity measure can serve as a signaling function of correlation transitions and distinguish quantum phase transitions, due to the abruptness that physical quantities experience at these transition points and the way in which the reduced states of these critical systems change within a scale of order and disorder.
We investigate the role of a statistical complexity measure to assign equilibration in isolated quantum systems. While unitary dynamics preserve global purity, expectation values of observables often exhibit equilibration-like behavior, raising the question of whether a measure of complexity can track this process. In addition to examining observable equilibration, we extend our analysis to study how the complexity of the quantum states evolves, providing insight into the transition from initial coherence to equilibrium. We define a classical statistical complexity measure based on observable entropy and deviation from equilibrium, which captures the dynamical progression towards equilibration and effectively distinguishes between complex and non-complex trajectories. In particular, our measure is sensitive to non-complex dynamics. Such dynamics include the quasi-periodic behavior exhibited by low-dimensional initial states, where the system explores a limited region of Hilbert space while preserving coherence. Numerical simulations of an Ising-like non-integrable Hamiltonian spin-chain model support these findings. Our work provides new insight into the emergence of equilibrium behavior from unitary dynamics and advances complexity as a meaningful tool in the study of the emergence of classicality in microscopic systems.
Classical stochastic processes can be generated by quantum simulators instead of the more standard classical ones, such as hidden Markov models. One reason for using quantum simulators has recently come to the fore: they generally require less memory than their classical counterparts. Here, we examine this quantum advantage for strongly coupled spin systems-in particular, the Dyson one-dimensional Ising spin chain with variable interaction length. We find that the advantage scales with both interaction range and temperature, growing without bound as interaction range increases. In particular, simulating Dyson's original spin chain with the most memory-efficient classical algorithm known requires infinite memory, while a quantum simulator requires only finite memory. Thus, quantum systems can very efficiently simulate strongly coupled one-dimensional classical spin systems.
We introduce a quantum version for the statistical complexity measure, in the context of quantum information theory, and use it as a signaling function of quantum order-disorder transitions. We discuss the possibility for such transitions to characterize interesting physical phenomena, as quantum phase transitions, or abrupt variations in correlation distributions. We apply our measure on two exactly solvable Hamiltonian models: the 1D-Quantum Ising Model (in the single-particle reduced state), and on Heisenberg XXZ spin-1/2 chain (in the two-particle reduced state). We analyze its behavior across quantum phase transitions for finite system sizes, as well as in the thermodynamic limit by using Bethe Ansatz technique.