Speed-up via Quantum Sampling
arXiv:0804.4259 · doi:10.1103/PhysRevA.78.042336
Abstract
The Markov Chain Monte Carlo method is at the heart of efficient approximation schemes for a wide range of problems in combinatorial enumeration and statistical physics. It is therefore very natural and important to determine whether quantum computers can speed-up classical mixing processes based on Markov chains. To this end, we present a new quantum algorithm, making it possible to prepare a quantum sample, i.e., a coherent version of the stationary distribution of a reversible Markov chain. Our algorithm has a significantly better running time than that of a previous algorithm based on adiabatic state generation. We also show that our methods provide a speed-up over a recently proposed method for obtaining ground states of (classical) Hamiltonians.
8 pages, fixed some minor typos
References in corpus (6)
Cited by in corpus (59)
- Simulation of Electronic Structure Hamiltonians Using Quantum Computers
- Simulating chemistry using quantum computers
- Quantum speedup of Monte Carlo methods
- Quantum computing for finance
- Quantum speedup for active learning agents
- A Quantum-Quantum Metropolis Algorithm
- Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
- Quantum-enhanced Markov chain Monte Carlo
- Rapid adiabatic preparation of injective PEPS and Gibbs states
- Quantum Speed-up for Approximating Partition Functions
- QFold: Quantum Walks and Deep Learning to Solve Protein Folding
- Quantum enhancements for deep reinforcement learning in large spaces
- Quantum walk approach to simulating parton showers
- Quantum Walks
- Introduction to Quantum Algorithms for Physics and Chemistry
- Spectral Gap Amplification
- Quantum Computing for Fusion Energy Science Applications
- Extreme Quantum Advantage for Rare-Event Sampling
- Quantum Sampling Algorithms for Near-Term Devices
- Simulation of Classical Thermal States on a Quantum Computer: A Transfer Matrix Approach
- Quantum Enhanced Inference in Markov Logic Networks
- How fast do quantum walks mix?
- Collider Events on a Quantum Computer
- Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
- Faster quantum mixing for slowly evolving sequences of Markov chains
- Bootstrap Embedding on a Quantum Computer
- Analog quantum algorithms for the mixing of Markov chains
- Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
- Improved Bounds for Eigenpath Traversal
- Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
- Optimal quantum algorithm for Gibbs state preparation
- Quantum-to-Quantum Bernoulli Factory
- Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
- Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm
- Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
- Fast quantum algorithms for traversing paths of eigenstates
- Small quantum computers and large classical data sets
- A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
- Quantum algorithm for estimating volumes of convex bodies
- Code Generator for Quantum Simulated Annealing
- Use of a Quantum Computer to do Importance and Metropolis-Hastings Sampling of a Classical Bayesian Network
- Quantum sampling for the Euclidean path integral of lattice gauge theory
- Quantum algorithm for exact Monte Carlo sampling
- Quantum Gibbs Sampling Using Szegedy Operators
- Quantum-assisted variational Monte Carlo
- Efficient Circuits for Quantum Walks
- GPGPU based simulations for one and two dimensional quantum walks
- Cosine series quantum sampling method with applications in signal and image processing
- Preparing Many Copies of a Quantum State in the Black-Box Model
- Sensitivity of Quantum Walks with Perturbation
- End-to-End Protocol for High-Quality QAOA Parameters with Few Shots
- Ising models and topological codes: classical algorithms and quantum simulation
- Faster quantum mixing of Markov chains in non-regular graph with fewer qubits
- Quantized Markov Chain Couplings that Prepare Qsamples
- Quantum Chebyshev's Inequality and Applications
- Exploring Quantum Bootstrap Sampling for AQP Error Assessment: A Pilot Study
- Leveraging Analog Neutral Atom Quantum Computers for Diversified Pricing in Hybrid Column Generation Frameworks
- On Quantum Perceptron Learning via Quantum Search