Single-shot quantum memory advantage in the simulation of stochastic processes

Abstract

Stochastic processes underlie a vast range of natural and social phenomena. Some processes such as atomic decay feature intrinsic randomness, whereas other complex processes, e.g. traffic congestion, are effectively probabilistic because we cannot track all relevant variables. To simulate a stochastic system's future behaviour, information about its past must be stored and thus memory is a key resource. Quantum information processing promises a memory advantage for stochastic simulation that has been validated in recent proof-of-concept experiments. Yet, in all past works, the memory saving would only become accessible in the limit of a large number of parallel simulations, because the memory registers of individual quantum simulators had the same dimensionality as their classical counterparts. Here, we report the first experimental demonstration that a quantum stochastic simulator can encode the relevant information in fewer dimensions than any classical simulator, thereby achieving a quantum memory advantage even for an individual simulator. Our photonic experiment thus establishes the potential of a new, practical resource saving in the simulation of complex systems.

References in corpus (22)

• Computational Mechanics: Pattern and Prediction, Structure and Simplicity
• Demonstration of a simple entangling optical gate and its use in Bell-state analysis
• Measuring a photonic qubit without destroying it
• Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
• Time's Barbed Arrow: Irreversibility, Crypticity, and Stored Information
• Experimental Realization of a Quantum Autoencoder: The Compression of Qutrits via Machine Learning
• Quantum Non-demolition Measurements on Qubits
• Efficient and pure femtosecond-pulse-length source of polarization-entangled photons
• Conclusive experimental demonstration of one-way Einstein-Podolsky-Rosen steering
• A practical, unitary simulator for non-Markovian complex processes
• Computational Mechanics of Input-Output Processes: Structured transformations and the $\epsilon$-transducer
• Experimental quantum processing enhancement in modelling stochastic processes
• A Closed-Form Shave from Occam's Quantum Razor: Exact Results for Quantum Compression
• Optimal stochastic modelling with unitary quantum dynamics
• Optimal classical simulation of state-independent quantum contextuality
• Thermodynamical cost of some interpretations of quantum theory
• Extreme Quantum Advantage for Rare-Event Sampling
• Using quantum theory to reduce the complexity of input-output processes
• Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes
• The classical-quantum divergence of complexity in modelling spin chains
• Causal Asymmetry in a Quantum World
• Interfering trajectories in experimental quantum-enhanced stochastic simulation

Cited by in corpus (13)

• Extreme dimensionality reduction with quantum modelling
• Quantum advantage in simulating stochastic processes
• Digital Discovery of 100 diverse Quantum Experiments with PyTheus
• Broadband polarization insensitivity and high detection efficiency in high-fill-factor superconducting microwire single-photon detectors
• Memory compression and thermal efficiency of quantum implementations of non-deterministic hidden Markov models
• Quantum adaptive agents with efficient long-term memories
• Robust inference of memory structure for efficient quantum modelling of stochastic processes
• Quantum coarse-graining for extreme dimension reduction in modelling stochastic temporal dynamics
• Capturing long-range memory structures with tree-geometry process tensors
• Quantum-embeddable stochastic matrices
• Embedding memory-efficient stochastic simulators as quantum trajectories
• Error-tolerant witnessing of divergences in classical and quantum statistical complexity
• Quantum Dimension Reduction of Hidden Markov Models