Stochastic processes are a keen interest of study across most scientific disciplines. Manifest in economic markets, biological evolution, the weather, crystal formation, and numerous other phenomena, they are ubiquitous in nature but often hard to simulate and predict.
Reflecting this difficulty of simulation, the complexity of a stochastic process is quantified in terms of the memory requirements of a machine that optimally predicts the process (a so-called ‘ε-machine’) [1]. Interestingly, it has recently been shown how quantum encoding can reduce such complexity for discrete-time, stochastic processes [2] as well as a certain type of continuous-time processes. Moreover, this quantum reduction of complexity may in fact become unbounded: There are processes which are simulable with a fixed number of memory quantum bits (qubits) while the number of classical bits required for the same simulation diverges to infinity.
Building on these results we establish a practical link between the quantum complexity of stochastic processes and their simulation in practice by giving a constructive description of a quantum simulator [3]. Our framework avoids unnecessary information loss during the simulation and opens up the possibility of practical implementation in state-of-the art quantum laboratories. The construction is generic and fully harnesses the complexity reduction due to quantum encoding, as is reflected by the quantum simulator’s reduced memory requirements.
The results will be illustrated for an example process and supported by experimental data.
