## Abstract

Computer simulation of observable phenomena is an indispensable tool for engineering new technology, understanding the natural world, and studying human society. However, the most interesting systems are often so complex that simulating their future behavior demands storing immense amounts of information regarding how they have behaved in the past. For increasingly complex systems, simulation becomes increasingly difficult and is ultimately constrained by resources such as computer memory. Recent theoretical work shows that quantum theory can reduce this memory requirement beyond ultimate classical limits, as measured by a process’ statistical complexity, *C*. We experimentally demonstrate this quantum advantage in simulating stochastic processes. Our quantum implementation observes a memory requirement of *C*_{q} = 0.05 ± 0.01, far below the ultimate classical limit of *C* = 1. Scaling up this technique would substantially reduce the memory required in simulations of more complex systems.

- quantum information
- complexity
- Quantum Optics
- stochastic simulation
- quantum measurement

## INTRODUCTION

What new tasks can be enhanced by quantum information science? It is a matter of practical importance and fundamental interest to find new additions to the impressive list of known quantum information benefits that include the exponential speedup provided by Shor’s factorization algorithm (*1*) and by algorithms for simulating quantum systems (*2*), the physically guaranteed security of quantum key distribution (*3*), and the sensitivity advantages in using certain quantum states for metrology (*4*, *5*). Here, we experimentally demonstrate a fundamentally new quantum advantage (*6*): Quantum information processing can reduce the memory required to simulate a stochastically evolving classical system by encoding information in nonorthogonal quantum states. Limitations on memory availability are a key consideration in computer simulation—a ubiquitous tool in modern society (*7*)—as the state space grows exponentially with the size of the system.

Our work is of particular relevance to the field of complexity theory. Therefore, the phenomena that people seek to understand, such as neural networks or the dynamics of the stock market, consist of a vast myriad of interacting components, whose internal details are too complex or inaccessible for one to model their behavior from first principles. In such cases, the system is instead typically regarded as a black box such that one has access only to some observable output. The task is then to isolate key indicators of future behavior from these data—and these data alone—without any knowledge of the system’s internal mechanism. It is possible to imagine that many different models of this type could be constructed for a given process. Of these, simpler models—those that store less data without sacrificing predictive accuracy—then represent a better understanding of exactly what observations in the past matter for the future. Our experimental work aims to demonstrate that, in taking this motivation to its ultimate conclusion, quantum effects can provide a powerful resource for simplifying models.

Our technique is fundamentally different from quantum data compression (*8*, *9*). That protocol is concerned with preserving all input data and thus encodes orthogonal signal states into orthogonal encoded states. In contrast, our work is concerned with more efficient ways of discarding useless data (in the sense of being useless for future prediction), by encoding classically distinct states as nonorthogonal quantum states, and processing them coherently.

To demonstrate the quantum advantage provided for this kind of simulation task, we need to quantify the minimum amount of memory (that is, stored information) required to simulate a process. Mathematically, we can characterize the observable behavior of a dynamical process by a joint probability distribution , where and represent random variables that govern the observed behavior of the process in the past and future, respectively. A simulator, implementing a model for the process, operates by storing information about within some physical system *S* such that, for each instance of the process with a particular past , it can be set to a particular state that allows for the reproduction of expected future statistics, that is, generating a random variable sampled from .

The complexity of the simplest simulator—the one for which *S* has minimal entropy—is regarded as an intrinsic property of the process being simulated, capturing the bare minimum information one must store to replicate the statistics of the process (*10*, *11*). In complexity theory, the minimal entropy of *S* is known as the statistical complexity *C*. The most complex processes reside between complete randomness (maximum system entropy) and complete order (zero system entropy) (*12*). At each extremity, the entropy of the simulator is zero: *C* = 0. The statistical complexity has been applied to a wide range of problems, including self-organization (*13*), the onset of chaos (*14*), and the complexity of a protein configuration space (*15*).

## RESULTS

The statistical complexity of a stochastic process can be determined by dividing the set of all possible pasts into equivalences classes such that all members of a given class yield coinciding future predictions. The implementation of such a model can replicate future statistics by recording only the equivalence class *s* that belongs to. In the literature, these equivalence classes are known as causal states (*14*); thus, causal states encode the information that is required to be stored. The complexity of such a simulator is then given by its entropy (*16*)(1)where the sum is taken over all causal states *s* ∈ *S*, and *℘*_{s} is the probability that lies in *s*. This representation turns out be classically optimal (*14*)—no classical model can simulate a stochastic process by storing less memory than *C*_{c}. Thus, *C*_{c} coincides with the statistical complexity.

Naïvely, one might expect such optimal models to waste no information—any information they store should be of relevance to the future. Surprisingly, this is not so. Classical models are almost always inefficient. Even in very simple processes, the statistical complexity *C*_{c} is usually strictly greater than , the mutual information between past and future outputs (*10*). Some information stored within a simulator is simply wasted. This surprising wastefulness of even the provably most efficient classical models can be very significant for more complex systems and contributes to an unavoidable energy cost in stochastic simulation (*17*, *18*).

Quantum information processing can drastically reduce this waste. It has been theoretically demonstrated that, for any process whose optimal classical model satisfies *C*_{c} > *E*, there exists a quantum model that requires a smaller memory, *C*_{q} < *C*_{c} (*6*). Quantum models assign each causal state *s* a corresponding quantum causal state . The amount of memory required to retain is then given by the von Neumann entropy *C*_{q} = − Tr[ρ log_{2} ρ], where represents the mixed state of the associated quantum memory that takes on state with probability *℘*_{s}, and Tr[⋅] denotes the matrix trace. Quantum models then derive their advantage in not requiring the states to be mutually orthogonal, without sacrificing their capacity to replicate desired future statistical behavior. This nonorthogonality ensures that *C*_{q} < *C*_{c}, allowing quantum models to save additional memory over their classical counterparts (*16*). This implies that when simulating *N* instances of such stochastic processes in parallel, quantum compression allows one to store all necessary past information within *NC*_{q} qubits in the asymptotic limit of large *N*, whereas classical simulators will necessitate the use of *NC*_{c} bits.

We experimentally demonstrate these ideas by modeling a specific, simple, stochastic process. It applies to many different physical systems, one of which is illustrated in Fig. 1A: a pair of binary switches. At each time step *j*, one of the switches is chosen at random and flipped with probability *P*. The system then outputs 0 if the switches are aligned and 1 if they are anti-aligned. The obvious (perhaps naïve) model keeps track of the state of both switches, resulting in a memory of entropy 2. However, we may optimize this classical model by observing that the parity of the switches corresponds to the causal states of the system (any past histories for coinciding switch parity have statistically identical futures). Thus, to simulate its statistics, we need to only store a single binary value, *s*, that takes on 0 and 1 with equiprobability. A potential representation of the simplest model for the switches in Fig. 1A is illustrated in Fig. 1B, which uses antiparallel red and blue vectors to represent the two causal states.

Figure 2A summarizes how the dynamics of this process are completely captured by transitions between the two causal states. For a single flip probability *P*, the steady-state occupation probabilities *℘*_{0} and *℘*_{1} for the two causal states coincide due to symmetry. Thus, this process, in general, has a statistical complexity of *C*_{c} = 1. The only exception is *P* = 0.5, because each output bit is then completely random (uncorrelated with earlier output bits), so that no memory of previous outcomes is required. Because the *P* = 0.5 protocol can be run without a memory, its theoretical *C*_{c} is 0, consistent with 0 bits of memory. [However, note that if the protocol is run with a single bit of (unnecessary) memory, that bit will be maximally mixed on average and the memory will have ; see results below.]

Figure 1C provides a conceptual representation of the quantum causal states. The quantum model makes use of a nonorthogonal encoding such that each of the two values of *s* is assigned to a corresponding quantum state , namely(2)(3)Here, |0〉 and |1〉 are the logical basis states of a qubit. The quantum-enhanced model saves further memory by sacrificing absolute knowledge of switch parity—it distinguishes the two possible immediate pasts only to the extent required to generate correct future statistics. The storage of in a physical system *S*, rather than the classical states *s*, results in a reduced simulator entropy of(4)where(5)represents the state of *S* averaged over possible causal states, and is the Pauli operator. The coherence in Eq. 5 comes from the nonorthogonality, which guarantees reduced complexity *C*_{q} < *C*_{c} for any *P* (except *P* = 0.5, where *C*_{q} = *C*_{c} = 0). For *P* close to 0.5, *C*_{q} can be arbitrarily small, whereas *C*_{c} = 1.

Figure 1 (D and E) shows classical and quantum logical circuits, respectively, that implement these models. The operation of the circuits is explained in detail in the caption, but the key point is that the (*j* + 1)^{th} simulation step (going from discrete time *t*_{j} to *t*_{j + 1}, say) involves taking the memory as input, applying the probabilistic operation, and generating a classical output *x*_{j + 1}. In the classical case, the probability *P* of a flip is inserted externally, but in the quantum case, it comes from the intrinsic randomness of quantum measurements on nonorthogonal states. In either scenario, the resulting predictive model can faithfully replicate future statistical behavior. That is, when initialized in the appropriate (quantum) causal states at time *t*, the future outputs are statistically indistinguishable and align with that of the original process being modeled.

### Experimental implementation

We implemented the quantum switch model using a photonic quantum logic circuit. We compared it with the theoretical classical bound and a classical switch model that we also implemented with a photonic circuit. Figure 1 (F and G) shows the mapping of the conceptual models onto what we realized experimentally. Experimentally processing either classical states (classical model) or quantum states (quantum model) required a CNOT gate, as well as two single photons—one to encode the state of the model and one to facilitate readout. We used a linear optics controlled-Z (CZ) gate (Fig. 3) with local unitary operations, and spontaneous parametric downconversion for photon generation, to realize these (see Materials and Methods).

In the classical circuit, the causal states are encoded in orthogonal logical photon polarization states, the equivalent of classical bits. The CNOT gate performs a classical XOR (exclusive-OR) operation, mapping the system state (after the probabilistic operation) onto a meter bit, which is read out via a destructive projective measurement to provide the (*j* + 1)^{th} data value of the model output.

In the quantum circuit, the relevant quantum causal states are encoded in nonorthogonal photon polarization states, as per Eqs. 2 and 3. The CNOT gate produces an entangled state between the model state and a meter qubit. The probability of a flip is determined by the degree of orthogonality of the causal states. Destructive projective measurement of the first qubit after the CNOT gate produces a classical output, which is the (*j* + 1)^{th} data value of the model output, and the corresponding collapse of the quantum state on the other photon implements the probabilistic operation on the model qubit for the next time step.

To verify the statistical complexity of the simulation, we measure the entropy of the model register via quantum state tomography at the end of the time-step circuit. This requires a destructive measurement of the photonic memory (qu)bit and, consequently, repreparation using classical logic. This is a slight practical difference from the theoretical circuits of Fig. 1 (D and E) and is necessary only for the sake of verifying the information storage requirements of the quantum model.

Experimental determinations of the statistical complexity, for both classical and quantum models, are shown in Fig. 4A, where they are compared with theoretical predictions. We collected data for various values of *P* ranging from 0 to 1 at intervals of 0.1. For a wide range of *P* values, , as predicted by theory. Small imperfections in arise due to slight imperfections in the operation of the CNOT gate and preparation of the input states. Figure 4B shows theoretical and experimental single-qubit density matrices, for the symmetric case where *P* = 0.8, and provides a good example of the strong agreement between theory and experiment.

The classical scenario for this model uses orthogonal logical states, which are invariant with *P*. Experimentally, this leads to a single data point for the classical symmetric case because the statistics are independent of *P*. Experimental imperfections, as discussed, led to a measured value of , very slightly less than the predicted value of unity (Fig. 4A). The imperfections, at the ≲ 0.1 % level, bias the equilibrium statistics. Note that measuring a value of less unity does not imply that the classical bound of unity is incorrect but rather that our slightly imperfect experiment implements a classical model of a slightly different process, one with a statistical complexity marginally less than 1. In principle, the same effect could cause the quantum statistical complexity to be lower than that of the expected process. In our experiment, we used careful characterization of the experimental circuit, state preparations, and measurements to ensure that the implemented model was very close to the desired model. Because we implemented our classical protocol with 1 bit of memory at *P* = 0.5, we observe *C*_{c}(0.5) ≈ 1, as discussed previously. However, no memory is required, in principle, for either the classical or quantum simulation at *P* = 0.5; hence, there is no quantum advantage in theory for this special case.

Our setup can also be generalized to model a class of more general stochastic processes, including the case where probabilities of transitioning between the two causal states do not coincide (see Fig. 2B). This is the case, for example, when the probability of flipping a switch depends on its current parity. Although the causal states of such a process remain unchanged, this generalization does affect the transition probabilities between the two causal states and, thus, their equilibrium distribution. In general, *℘*_{1} ≠ *℘*_{2}, and thus, *C*_{c} ≠ 1 (see Materials and Methods for details).

We experimentally tested one such case, where *P*_{←} = 0.3 and *P*_{→} = 0.9. The experimental implementation is the same as before, except that the states and are no longer symmetrically distributed around . The experimentally determined entropy for the quantum model is *S*_{q} = 0.19 ± 0.01, much lower than the equivalent case for the classical model *S*_{c} = 0.818 ± 0.001. Note that these values are slightly in excess of the theoretically predicted values of 0.12 and 0.81, respectively, which we attribute to a combination of slightly imperfect state preparation and slightly imperfect CNOT gate operation.

## DISCUSSION

In complexity theory, the statistical complexity of a stochastic process is considered as an intrinsic quantifier of its structure, representing the ultimate limit in the amount of memory required to optimally simulate its future statistics. Here, we have experimentally demonstrated that this limit can be surpassed with quantum processing. Stochastic processes permeate quantitative science, modeling diverse phenomena from neural networks to financial markets. In complexity theory, the construction of the simplest such models that replicate their observation behavior has played an important role in understanding their hidden structure. Our results present a proof of principle that these existing methods can be enhanced through quantum technology. Recent theoretical work indicates that quantum models can be further improved for non-Markovian processes (*19*), and our technology could be adapted to realizing these designs.

In the short term, it will be possible to implement simulations with few-qubit systems, in line with the current state of the art in quantum computer logic. As realizable quantum processor circuits increase in scale, it will be possible to implement this for large numbers of qubits, in one or more of the scalable platforms [including, but not limited to, optics, spins in solids (*20*), trapped ions (*21*), and superconductors (*22*)]. We note that the particular optical gate presented here is not suitable for scaling to large circuits in its current form, but optical quantum logic is scalable with more sophisticated implementations (*23*–*25*).

Because the amount of information classical models waste often scales with the complexity of the processes they model, the adoption of our methods could have significant potential in simplifying more complex simulations. This highlights not only quantum theory’s relevance in understanding the microscopic world but also its importance in studying the complex macroscopic systems that are characteristic of everyday life.

## MATERIALS AND METHODS

### Photon source and CNOT gate

A source of polarization-unentangled photon pairs was realized using type I spontaneous parametric downconversion in bismuth triborate (BiBO). The source produced photon pairs at 820 nm when pumped with a 410-nm, continuous-wave, 60-mW diode laser. The classical or quantum logic was implemented by constructing a linear optics CNOT gate as shown in Fig. 3. [In practice, the CNOT gate was realized using a CZ gate (*26*) and Hadamard rotations, which were incorporated into the settings of the wave plates before and after the gate.] To determine how well the CNOT gate was operating (*27*), we attempted to generate a maximally entangled state from separable inputs, with the resultant 2-qubit density matrix reconstructed via quantum state tomography. The fidelity of the state produced by the CNOT gate with the desired maximally entangled state was measured to be 0.97 ± 0.01.

### Classical XOR gate

The classical XOR gate, used to implement the model with classical causal states, can be implemented using a quantum CNOT gate (as above) and orthogonal logical photon polarization states as bits. Because of experimental contingencies, we collected the classical data using a different (but nominally identical in layout and component type) CNOT gate to the one used for the quantum data collection and at a later time.

### Asymmetric two-switch process

In the main text, we studied the special case of the two-switch process, where the probability of flipping a switch did not depend on the state of the two switches. We can generalize this model by assuming that a switch is flipped with probability *P*_{→} when the switches align, or *P*_{←} otherwise (Fig. 2B). The resulting system will still have two causal states, *s* = {0, 1}, corresponding to the parity of the two switches. However, the two causal states no longer occur with equiprobability and instead satisfy *℘*_{0}*P*_{→} = *℘*_{1}*P*_{←}. Thus, *C*_{c} ⩽ 1, with equality when *P*_{→} = *P*_{←}. The quantum model causal states for the general model are given by(6)(7)

The statistical complexity is given by the von Neumann entropy of . The quantum circuit to realize this quantum model is the same as that in Fig. 1F, except that we must replace the controlled- (CNOT) operation with a controlled-*Û* (CU) gate, where *Û* is the operator such that . In practice, , where is a rotation around the *y* axis of the Bloch sphere. Thus, the rotation can be implemented by HWPs in the meter arm before and after the CNOT gate—we incorporated these rotations into the settings of the state preparation and measurement wave plates. However, the asymmetry of settings, when implemented with experimental components, lead to a slight degradation in the performance of the CU gate compared with the CNOT case.

This is an open-access article distributed under the terms of the Creative Commons Attribution-NonCommercial license, which permits use, distribution, and reproduction in any medium, so long as the resultant use is **not** for commercial advantage and provided the original work is properly cited.

## REFERENCES AND NOTES

**Acknowledgments:**

**Funding:**This research was funded, in part, by the Australian Research Council (project no. DP160101911) and the Australian Research Council Centre of Excellence for Quantum Computation and Communication Technology (project no. CE110001027). M.G. is financially supported by the John Templeton Foundation Grant 53914 “Occam’s quantum mechanical razor: Can quantum theory admit the simplest understanding of reality?” and the National Research Foundation NRF-Fellowship (reference no. NRF-NRFF2016-02).

**Author contributions:**M.S.P. performed the experiment and data analysis, with contributions from J.H. and with assistance from G.J.P. The theoretical and experimental conceptualization was developed by M.G., H.M.W., and G.J.P.

**Competing interests:**The authors declare that they have no competing interests.

**Data and materials availability:**All data needed to evaluate the conclusions in the paper are present in the paper. Additional data related to this paper may be requested from the authors.

- Copyright © 2017, The Authors