Unbounded memory advantage in stochastic simulation using quantum mechanics
arXiv:1609.04408 · doi:10.1088/1367-2630/aa82df
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.
arXiv commentMinor clarifications to prior version
References in corpus (15)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Algorithms Revisited
- Computational Mechanics: Pattern and Prediction, Structure and Simplicity
- The thermodynamics of prediction
- Quantifying Self-Organization with Optimal Predictors
- Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
- Time's Barbed Arrow: Irreversibility, Crypticity, and Stored Information
- The Computational Structure of Spike Trains
- Experimental quantum processing enhancement in modelling stochastic processes
- Complexity analysis of the stock market
- A Closed-Form Shave from Occam's Quantum Razor: Exact Results for Quantum Compression
- The application of computational mechanics to the analysis of geomagnetic data
- Thermodynamics of complexity and pattern manipulation
- The classical-quantum divergence of complexity in modelling spin chains
- Information-theoretic bound on the energy cost of stochastic simulation
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