Extreme Quantum Advantage for Rare-Event Sampling

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.

• Publication year

  2017

• Venue

  arXiv.org

• Publication date

  2017-07-29

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1103/PhysRevX.8.011025arXiv 1707.09553
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Practical Unitary Simulator for Non-Markovian Complex Processes.

  2017cited by this paper
• Extreme Quantum Advantage when Simulating Classical Systems with Long-Range Interaction

  2017cited by this paper
• The ambiguity of simplicity in quantum and classical simulation

  2017cited by this paper
• Minimum memory for generating rare events.

  2016cited by this paper
• Experimentally modeling stochastic processes with less memory by the use of a quantum processor

  2016cited by this paper
• Establishing quantum advantage

  2016cited by this paper
• Extreme Quantum Advantage when Simulating Strongly Coupled Classical Systems

  2016cited by this paper
• Provably unbounded memory advantage in stochastic simulation using quantum mechanics

  2016cited by this paper
• Thermodynamics of complexity and pattern manipulation.

  2015cited by this paper
• Occam’s Quantum Strop: Synchronizing and Compressing Classical Cryptic Processes via a Quantum Channel

  2015influential reference
• A Closed-Form Shave from Occam's Quantum Razor: Exact Results for Quantum Compression

  2015influential reference
• Nonequilibrium Markov Processes Conditioned on Large Deviations

  2014cited by this paper
• Communication Tasks with Infinite Quantum-Classical Separation.

  2014cited by this paper
• Nonequilibrium Markov Processes Conditioned on Large Deviations

  2014cited by this paper
• Markov chains and mixing times

  2013cited by this paper
• Nonequilibrium microcanonical and canonical ensembles and their equivalence.

  2013cited by this paper
• Exponential Bounds for Convergence of Entropy Rate Approximations in Hidden Markov Models Satisfying a Path-Mergeability Condition

  2012cited by this paper
• Externally driven one-dimensional Ising model

  2012cited by this paper
• I and J

  2012cited by this paper
• How Hidden are Hidden Processes? A Primer on Crypticity and Entropy Convergence

  2011cited by this paper
• Large Deviations and Applications

  2011cited by this paper
• Quantum mechanics can reduce the complexity of classical models

  2011influential reference
• Information Theory and Statistics

  2011cited by this paper
• Between order and chaos

  2011cited by this paper
• The computational complexity of linear optics

  2010cited by this paper
• Dynamic Order-Disorder in Atomistic Models of Structural Glass Formers

  2009cited by this paper
• Thermodynamics of quantum jump trajectories.

  2009cited by this paper
• Large deviations and ensembles of trajectories in stochastic models

  2009cited by this paper
• Information Theory and Network Coding

  2008cited by this paper
• First-order dynamical phase transition in models of glasses: an approach based on ensembles of histories

  2008cited by this paper
• Speedup via quantum sampling

  2008cited by this paper
• Quantum Walk Based Search Algorithms

  2008cited by this paper
• The large deviation approach to statistical mechanics

  2008cited by this paper
• Quantum algorithm for linear systems of equations.

  2008cited by this paper
• Study Design and Statistical Analysis: A Practical Guide for Clinicians.

  2007cited by this paper
• Thermodynamic Formalism for Systems with Markov Dynamics

  2006cited by this paper
• Simulation

  2006cited by this paper
• A Mathematical Theory of Communication

  2006cited by this paper
• Chaotic properties of systems with Markov dynamics.

  2005cited by this paper
• Analyticity of Entropy Rate of Hidden Markov Chains

  2005cited by this paper
• Elements of Information Theory

  2005cited by this paper
• Understanding molecular simulation : from algorithms to applications. 2nd ed.

  2002cited by this paper
• Regularities unseen, randomness observed: levels of entropy convergence.

  2001cited by this paper
• Efficient, multiple-range random walk algorithm to calculate the density of states.

  2000cited by this paper
• Comment on "Efficient, multiple-range random walk algorithm to calculate the density of states"

  2000cited by this paper
• Computational Mechanics: Pattern and Prediction, Structure and Simplicity

  1999cited by this paper
• Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and Eigenvectors

  1998cited by this paper
• The quantum communication complexity of sampling

  1998cited by this paper
• Theory and algorithms for hidden Markov models and generalized hidden Markov models

  1998cited by this paper
• Molecular modelling: Principles and applications

  1997cited by this paper
• Understanding molecular simulation: from algorithms to applications

  1996cited by this paper
• A fast quantum mechanical algorithm for database search

  1996cited by this paper
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

  1995cited by this paper
• Fluctuation Spectroscopy

  1993cited by this paper
• Probability: Theory and Examples

  1993cited by this paper
• THE weighted histogram analysis method for free‐energy calculations on biomolecules. I. The method

  1992cited by this paper
• Inferring statistical complexity.

  1989cited by this paper
• A tutorial on hidden Markov models and selected applications in speech recognition

  1989cited by this paper
• Fast, Rigorous Factorization and Discrete Logarithm Algorithms

  1987cited by this paper
• An introduction to hidden Markov models

  1986cited by this paper
• Sanov Property, Generalized $I$-Projection and a Conditional Limit Theorem

  1984cited by this paper
• Exactly solved models in statistical mechanics

  1982cited by this paper
• Maximum entropy and conditional probability

  1981cited by this paper
• Nonphysical sampling distributions in Monte Carlo free-energy estimation: Umbrella sampling

  1977cited by this paper
• Markov Chains

  1972cited by this paper
• Lectures on Gas Theory

  1964cited by this paper
• A Convexity Property in the Theory of Random Variables Defined on a Finite Markov Chain

  1961cited by this paper
• The Individual Ergodic Theorem of Information Theory

  1957cited by this paper
• The Basic Theorems of Information Theory

  1953cited by this paper

• Provable superior accuracy in machine learned quantum models

  2021cites this paper
• Memory compression and thermal efficiency of quantum implementations of non-deterministic hidden Markov models

  2021cites this paper
• Quantum-enhanced analysis of discrete stochastic processes

  2020cites this paper
• Thermodynamically-Efficient Local Computation: Classical and quantum information reservoirs and generators

  2020cites this paper
• Thermodynamically-efficient local computation and the inefficiency of quantum memory compression

  2020cites this paper
• Understanding sequential measurements in psi-epistemic ontological models

  2019influential citation
• Quantum-inspired memory-enhanced stochastic algorithms

  2019influential citation
• Measures of distinguishability between stochastic processes.

  2019cites this paper
• Dimensional Quantum Memory Advantage in the Simulation of Stochastic Processes

  2018cites this paper
• Memory-efficient tracking of complex temporal and symbolic dynamics with quantum simulators

  2018cites this paper
• Strong and Weak Optimizations in Classical and Quantum Models of Stochastic Processes

  2018cites this paper
• Matrix Product States for Quantum Stochastic Modeling.

  2018cites this paper
• Optimal stochastic modeling with unitary quantum dynamics

  2018cites this paper
• An experimental quantum Bernoulli factory

  2018cites this paper
• Surveying Structural Complexity in Quantum Many-Body Systems

  2018cites this paper
• Error-tolerant witnessing of divergences in classical and quantum statistical complexity

  2017cites this paper
• Classical and Quantum Factors of Channels

  2017cites this paper
• Practical Unitary Simulator for Non-Markovian Complex Processes.

  2017cites this paper
• The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications

  2017cites this paper