Unbounded memory advantage in stochastic simulation using quantum mechanics

Abstract

Simulating the stochastic evolution of real quantities on a digital computer requires a trade-off between the precision to which these quantities are approximated, and the memory required to store them. The statistical accuracy of the simulation is thus generally limited by the internal memory available to the simulator. Here, using tools from computational mechanics, we show that quantum processors with a fixed finite memory can simulate stochastic processes of real variables to arbitrarily high precision. This demonstrates a provable, unbounded memory advantage that a quantum simulator can exhibit over its best possible classical counterpart.

Minor clarifications to prior version

References in corpus (5)

• The thermodynamics of prediction
• Experimental quantum processing enhancement in modelling stochastic processes
• A Closed-Form Shave from Occam's Quantum Razor: Exact Results for Quantum Compression
• Thermodynamics of complexity and pattern manipulation
• The classical-quantum divergence of complexity in modelling spin chains

Cited by in corpus (24)

• Quantum stochastic processes and quantum non-Markovian phenomena
• A practical, unitary simulator for non-Markovian complex processes
• Extreme dimensionality reduction with quantum modelling
• Optimal stochastic modelling with unitary quantum dynamics
• Extreme Quantum Advantage for Rare-Event Sampling
• Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes
• Matrix Product States for Quantum Stochastic Modelling
• Causal Asymmetry in a Quantum World
• Memory cost of temporal correlations
• Memory compression and thermal efficiency of quantum implementations of non-deterministic hidden Markov models
• Strong and Weak Optimizations in Classical and Quantum Models of Stochastic Processes
• Temporal correlations in the simplest measurement sequences
• Robust inference of memory structure for efficient quantum modelling of stochastic processes
• Simulating extremal temporal correlations
• Ticking-clock performance enhanced by nonclassical temporal correlations
• Quantum coarse-graining for extreme dimension reduction in modelling stochastic temporal dynamics
• Quantum thermodynamic advantage in work extraction from steerable quantum correlations
• Embedding memory-efficient stochastic simulators as quantum trajectories
• Surveying structural complexity in quantum many-body systems
• Error-tolerant witnessing of divergences in classical and quantum statistical complexity
• Quantum-inspired identification of complex cellular automata
• Optimisation of time-ordered processes in the finite and asymptotic regime
• One-shot information-theoretical approaches to fluctuation theorems
• Quantum Dimension Reduction of Hidden Markov Models