Practical Unitary Simulator for Non-Markovian Complex Processes

Stochastic processes are as ubiquitous throughout the quantitative sciences as they are notorious for being difficult to simulate and predict. In this Letter, we propose a unitary quantum simulator for discrete-time stochastic processes which requires less internal memory than any classical analogue throughout the simulation. The simulator’s internal memory requirements equal those of the best previous quantum models. However, in contrast to previous models, it only requires a (small) finite-dimensional Hilbert space. Moreover, since the simulator operates unitarily throughout, it avoids any unnecessary information loss. We provide a stepwise construction for simulators for a large class of stochastic processes hence directly opening the possibility for experimental implementations with current platforms for quantum computation. The results are illustrated for an example process.

Figure 1

A stochastic process (a), a general simulator (b), and a $q$ simulator (c) generally all retain some memory about the past (brown dotted lines) between each symbol emission. (a) A stochastic process is a bi-infinite string of random variables, $\dots ,X_{-2},X_{-1},X_0,X_1,X_2,\dots$. We picture it here as “emitting” symbols $x_t$ at discrete times $t$. (b) The process’ simulator equally emits symbols $x_t$ at times $t$. Its output is statistically indistinguishable from the process itself. (c) A $q$ simulator is a specific type of simulator which uses quantum memory, initialized in state $|{\sigma }_i⟩$ with probability ${\pi }_i$ (top register) and a sequentially repeated unitary interaction with one or multiple symbol registers. It may be thought of as a “black box” (represented in grey) which takes states $|0⟩$ as input and returns output states whose measurement statistics in the computational basis are indistinguishable from the process itself. The physical system which supplies the blank $|0⟩$ states can be reused at each step.

Figure 2

Memory requirement $C_q$ for simulation of the upset-gambler process with $p=0.7$ and $q=0.8$. The solid red line shows the classical complexity $C_{\mu }\approx 0.98$. The blue dots represent the memory ${\tilde{C}}_q(L)$ required by previous models. $L$ corresponds to the number of future symbols stored at a time and, hence, equivalently, the number of qubits required for the simulator’s internal memory [see Eqs. (15) and (16)]. ${\tilde{C}}_q(L)$ is always lower bounded by $C_q\approx 0.10$ which it reaches asymptotically for $L\to \infty$. The $q$ simulator operates at $C_q$ throughout (green dashed line).For an illustration of the process’ full parameter range, see Supplemental Material B of Ref. [28].