Extreme Quantum Advantage for Rare-Event Sampling

Abstract

We introduce a quantum algorithm for efficient biased sampling of the rare events generated by classical memoryful stochastic processes. We show that this quantum algorithm gives an extreme advantage over known classical biased sampling algorithms in terms of the memory resources required. The quantum memory advantage ranges from polynomial to exponential and when sampling the rare equilibrium configurations of spin systems the quantum advantage diverges.

11 pages, 9 figures; http://csc.ucdavis.edu/~cmg/compmech/pubs/eqafbs.htm

References in corpus (22)

• Quantum algorithm for solving linear systems of equations
• An efficient, multiple range random walk algorithm to calculate the density of states
• The large deviation approach to statistical mechanics
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Computational Mechanics: Pattern and Prediction, Structure and Simplicity
• First-order dynamical phase transition in models of glasses: an approach based on ensembles of histories
• Thermodynamic formalism for systems with Markov dynamics
• Nonequilibrium Markov processes conditioned on large deviations
• Thermodynamics of Quantum Jump Trajectories
• Large deviations and ensembles of trajectories in stochastic models
• Nonequilibrium microcanonical and canonical ensembles and their equivalence
• Speed-up via Quantum Sampling
• Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
• Chaotic properties of systems with Markov dynamics
• 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
• Communication tasks with infinite quantum-classical separation
• Unbounded memory advantage in stochastic simulation using quantum mechanics
• How Hidden are Hidden Processes? A Primer on Crypticity and Entropy Convergence
• The Markov Memory for Generating Rare Events
• Externally driven one-dimensional Ising model

Cited by in corpus (16)

• 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
• 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
• An Experimental Quantum Bernoulli Factory
• Quantum coarse-graining for extreme dimension reduction in modelling stochastic temporal dynamics
• Measures of distinguishability between stochastic processes
• Thermodynamically-Efficient Local Computation and the Inefficiency of Quantum Memory Compression
• Quantum-inspired identification of complex cellular automata
• Error-tolerant witnessing of divergences in classical and quantum statistical complexity
• Strict advantage of complex quantum theory in a communication task
• Quantum Dimension Reduction of Hidden Markov Models