Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes
arXiv:1704.04231 · doi:10.1038/s41534-018-0064-4
Abstract
Continuous-time stochastic processes pervade everyday experience, and the simulation of models of these processes is of great utility. Classical models of systems operating in continuous-time must typically track an unbounded amount of information about past behaviour, even for relatively simple models, enforcing limits on precision due to the finite memory of the machine. However, quantum machines can require less information about the past than even their optimal classical counterparts to simulate the future of discrete-time processes, and we demonstrate that this advantage extends to the continuous-time regime. Moreover, we show that this reduction in the memory requirement can be unboundedly large, allowing for arbitrary precision even with a finite quantum memory. We provide a systematic method for finding superior quantum constructions, and a protocol for analogue simulation of continuous-time renewal processes with a quantum machine.
arXiv comment13 pages, 8 figures, title changed from original version
References in corpus (24)
- Computational Mechanics: Pattern and Prediction, Structure and Simplicity
- Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
- Time's Barbed Arrow: Irreversibility, Crypticity, and Stored Information
- Statistical Complexity of Simple 1D Spin Systems
- Anatomy of a Bit: Information in a Time Series Observation
- Highly Efficient Source for Indistinguishable Photons of Controlled Shape
- Multipartite Entangled Spatial Modes of Ultracold Atoms Generated and Controlled by Quantum Measurement
- The Computational Structure of Spike Trains
- Experimental quantum processing enhancement in modelling stochastic processes
- Inferring hidden Markov models from noisy time sequences: a method to alleviate degeneracy in molecular dynamics
- 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
- Driven-dissipative many-body pairing states for cold fermionic atoms in an optical lattice
- Many-body state engineering using measurements and fixed unitary dynamics
- Quantum control of spin-correlations in ultracold lattice gases
- Informational and Causal Architecture of Continuous-time Renewal and Hidden Semi-Markov Processes
- Informational and Causal Architecture of Discrete-Time Renewal Processes
- Using quantum theory to reduce the complexity of input-output processes
- Thermodynamics of complexity and pattern manipulation
- Synchronization and Control in Intrinsic and Designed Computation: An Information-Theoretic Analysis of Competing Models of Stochastic Computation
- Unbounded memory advantage in stochastic simulation using quantum mechanics
- The classical-quantum divergence of complexity in modelling spin chains
- Information Anatomy of Stochastic Equilibria
Cited by in corpus (25)
- A practical, unitary simulator for non-Markovian complex processes
- Extreme dimensionality reduction with quantum modelling
- Optimal stochastic modelling with unitary quantum dynamics
- Matrix Product States for Quantum Stochastic Modelling
- Causal Asymmetry in a Quantum World
- Memory compression and thermal efficiency of quantum implementations of non-deterministic hidden Markov models
- Single-shot quantum memory advantage in the simulation of stochastic processes
- Quantum adaptive agents with efficient long-term memories
- Memory-efficient tracking of complex temporal and symbolic dynamics with quantum simulators
- Temporal correlations in the simplest measurement sequences
- Robust inference of memory structure for efficient quantum modelling of stochastic processes
- Implementing quantum dimensionality reduction for non-Markovian stochastic simulation
- Quantifying Non-Markovianity in Open Quantum Dynamics
- Ticking-clock performance enhanced by nonclassical temporal correlations
- Quantum coarse-graining for extreme dimension reduction in modelling stochastic temporal dynamics
- Measures of distinguishability between stochastic processes
- Reconstructing Non-Markovian Open Quantum Evolution From Multi-time Measurements
- Quantum Encoding and Analysis on Continuous Time Stochastic Process with Financial Applications
- Quantum Communication Networks Enhanced by Distributed Quantum Memories
- Surveying structural complexity in quantum many-body systems
- Embedding memory-efficient stochastic simulators as quantum trajectories
- 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
- Quantum Dimension Reduction of Hidden Markov Models