Extreme Quantum Advantage for Rare-Event Sampling
arXiv:1707.09553 · doi:10.1103/PhysRevX.8.011025
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 (4)
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