Quantum algorithm for exact Monte Carlo sampling
arXiv:1003.1862 · doi:10.1103/PhysRevLett.104.250502
Abstract
We build a quantum algorithm which uses the Grover quantum search procedure in order to sample the exact equilibrium distribution of a wide range of classical statistical mechanics systems. The algorithm is based on recently developed exact Monte Carlo sampling methods, and yields a polynomial gain compared to classical procedures.
4 pages, 1 figure, discussion added
References in corpus (8)
- Glassy dynamics of kinetically constrained models
- Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
- Quantum Simulations of Classical Annealing Processes
- Speed-up via Quantum Sampling
- On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
- Renormalization group approach to exact sampling
- Quantum Computing of Poincare Recurrences and Periodic Orbits
- Quantum computing of semiclassical formulas