Dimensional Quantum Memory Advantage in the Simulation of Stochastic Processes

Stochastic processes underlie a vast range of natural and social phenomena. Some processes such as atomic decay feature intrinsic randomness, whereas other complex processes, e.g., traffic congestion, are effectively probabilistic because we cannot track all relevant variables. To simulate a stochastic system’s future behavior, information about its past must be stored, and thus memory is a key resource. Quantum information processing promises a memory advantage for stochastic simulation. Here, we report the first experimental demonstration that a quantum stochastic simulator can encode the required information in fewer dimensions than any classical simulator, thereby achieving a quantum advantage in minimal memory requirements using an individual simulator. This advantage is in contrast to recent proof-of-concept experiments, where the memory saving would only become accessible in the limit of a large number of parallel simulations. In those examples, the minimal memory registers of individual quantum simulators had the same dimensionality as their classical counterparts. Our photonic experiment thus establishes the potential of new, practical resource savings in the simulation of complex systems.

Popular Summary

We experimentally demonstrate a way of simulating time-series data (a so-called stochastic process) using quantum physics to reduce the size of the required computer memory. Our fundamental result demonstrates a reduction in the size (or dimensionality) of the memory system beyond classical limits.

Simulating the behavior of stochastic processes, such as weather patterns and traffic congestion, is a crucial tool in science and technology. These stochastic simulators work by dividing time into discrete steps and projecting what will happen in the future, based on the information available from past steps. Quantum information processors offer the power to store past information in memory states that are not completely distinguishable from one another while still being able to achieve accurate simulation results. Surprisingly, the fact that the states cannot be fully distinguished makes things better, not worse: A quantum simulator needs a smaller memory than its best classical counterpart.

Our quantum simulator uses photons—single particles of light—as its memory. In this experiment, we send this photon memory into a processor especially designed to manipulate the photon’s quantum state. Then, we perform a series of measurements to retrieve the simulation result. While our experiment is based on an example that allows us to run a three-state classical processor inside a single two-level quantum system, it is theoretically known that the improvement can be extended to large-scale problems and to a variety of stochastic processes.

The ease and efficiency of using these new quantum simulators opens the path to more complicated simulators with smaller memory storage requirements.

Figure 1

The stochastic process and its simulation. (a) The simplest classical simulator for the process can be represented by a directed graph. Here, the three nodes $S_1$, $S_2$, and $S_3$ represent internal states of the machine. Each edge between two nodes, $S_j$ and $S_k$, labeled $r|T_{jk}$, represents the probability $T_{jk}$ that the machine emits output $r$ and transitions from state $S_j$ to state $S_k$. To generate correct conditional futures, one first initializes the machine in state $S_i$ depending on the value of the last output (0, 1, or 2). Iterating the machine can then generate correct conditional future statistics. Mathematically, the probabilities $T_{jk}$ make up the transition matrix, whose eigenvalues form the probability distribution of the causal states, called the stationary distribution $\{p_i{\}}_{i=0,1,2}$. (b) Dynamically, a simulator can be considered to consist of a memory (upper arm) that transfers information between time steps and sequentially interacts with a blank tape (lower arm) at each time step.

Figure 2

Conceptual diagram of a simulation step. (a) The quantum processor ($W$) accepts a memory qubit and uses an ancilla. (We use wavy lines to denote quantum objects, with the number of lines in parallel indicating the dimensionality.) In the processor, the qubit undergoes a fan-out operation $F$ to a qutrit space. The ancilla contains no information, and its preparation $P$ is fixed. Then, a unitary operation $U$ acts on the qutrit and ancilla, outputting an entangled state of the memory qubit and a qutrit. A projective measurement of the qutrit provides the output of the simulation step and collapses the memory qubit to the appropriate state for the next step. (b) The classical simulator requires a three-dimensional memory system. The irreversible operation $W$ acts on the memory system to generate the classical output and the next memory state. (c) The experimental realization of the circuit in diagram (a) using linear optics gates requires an ancilla qubit (Photon 2) and its herald (Photon 1). Following the fan-out operation $F(p,q)$ on the memory qubit, we implement a gate, C-NOT 1, which performs a nondestructive measurement (NDM). Then, the unitary operation $U$ is performed by an additional two gates, C-NOT 2 and C-rotation. The preparation $P(q)$ of the memory system (Photon 3), the fan-out operation $F(p,q)$, and the single qubit rotation $R(q)$ depend on the stochastic process parameters $p$ and $q$ as indicated.

Figure 3

Experimental setup. Single photons are generated from SPDC events. The herald photon from Source 1 is sent straight to a heralding detector. The polarization of the memory system is used to encode the relevant causal state in a qubit, using a half-wave plate (HWP). Ancillas are prepared in a fixed polarization using HWPs. To implement the fanning out from the memory qubit to a qutrit, a HWP and polarizing beam splitters (PBSs) are used. Each of the C-NOT 1 and C-NOT 2 gates is implemented using a HWP and a PBS. The C-rotation gate is realized via HWPs and partially polarizing beam splitters (PPBSs). In order to vary the relative delay between the single-photon wave packets, an automated translation stage is used to move one of the couplers. Classical readout is performed via projective measurements on the path modes of the qutrit, which collapses the memory state to the appropriate causal state. To verify the memory qubit, its state is reconstructed via quantum state tomography. A telecom bandpass filter is used in the tomography arm in order to spectrally filter the SPDC photons and maximize the visibility of the quantum interference. $P$ stands for state preparation, SMF for single-mode fiber, QWP for quarter-wave plate, GT for Glan-Taylor prism, and FPC for fiber polarization controller. For more details, see Appendix pp2.

Figure 4

Statistical complexity of the classical and quantum simulators. (a) The theoretically calculated statistical complexity. The pale grey surface depicts $C_{\mu }$, while the pale orange surface shows $C_Q$. The transparent plane marks the value $C=1$. The yellow, purple, green, and cyan cuts illustrate specific cross sections, which are experimentally probed and shown in panels (b), (c), (d), and (e), respectively. The red projection on the floor illustrates the $(p,q)$ values for which $C_{\mu }\ge 1$. (b)–(e) The quantum simulator is used to investigate several sets of processes with different values of $p$ and $q$. The entropy of the reconstructed stationary states (see Appendix pp3) determines the quantum statistical complexity (red dots). The black and blue curves represent the theoretical $C_{\mu }$ and $C_Q$, respectively. The plots demonstrate a considerable memory advantage for the i.i.d. case. Furthermore, the grey shaded areas mark processes where the complexity $C_{\mu }$ of the classical simulator exceeds one bit, while the quantum simulation runs with only one memory qubit. Uncertainties are estimated from the Poissonian distribution of photon counts.