Quantum Sampling Algorithms for Near-Term Devices
arXiv:2005.14059 · doi:10.1103/PhysRevLett.127.100504
Abstract
Efficient sampling from a classical Gibbs distribution is an important computational problem with applications ranging from statistical physics over Monte Carlo and optimization algorithms to machine learning. We introduce a family of quantum algorithms that provide unbiased samples by preparing a state encoding the entire Gibbs distribution. We show that this approach leads to a speedup over a classical Markov chain algorithm for several examples including the Ising model and sampling from weighted independent sets of two different graphs. Our approach connects computational complexity with phase transitions, providing a physical interpretation of quantum speedup. Moreover, it opens the door to exploring potentially useful sampling algorithms on near-term quantum devices as the algorithm for sampling from independent sets on certain graphs can be naturally implemented using Rydberg atom arrays.
References in corpus (34)
- Community detection in graphs
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Probing many-body dynamics on a 51-atom quantum simulator
- Quantum computational advantage using photons
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Realizing quantum Ising models in tunable two-dimensional arrays of single Rydberg atoms
- Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
- Criticality, the area law, and the computational power of PEPS
- Quantum Metropolis Sampling
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Competing density-wave orders in a one-dimensional hard-boson model
- One-Dimensional Symmetry Protected Topological Phases and their Transitions
- Thermalization in Nature and on a Quantum Computer
- The problem of equilibration and the computation of correlation functions on a quantum computer
- Majorana zero modes in a quantum Ising chain with longer-ranged interactions
- Quantum Simulations of Classical Annealing Processes
- A Quantum-Quantum Metropolis Algorithm
- Perfect Sampling with Unitary Tensor Networks
- From quantum mechanics to classical statistical physics: generalized Rokhsar-Kivelson Hamiltonians and the "Stochastic Matrix Form" decomposition
- Speed-up via Quantum Sampling
- Simulating Ising Spin Glasses on a Quantum Computer
- From classical to quantum dynamics at Rokhsar-Kivelson points
- A Quantum Approach to Classical Statistical Mechanics
- Topological order in 1D Cluster state protected by symmetry
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Phase transitions and localizable entanglement in cluster-state spin chains with Ising couplings and local fields
- Rapid adiabatic preparation of injective PEPS and Gibbs states
- Preparing thermal states of quantum systems by dimension reduction
- Liquid ground state, gap and excited states of a strongly correlated spin chain
- Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays
- Simulation of Classical Thermal States on a Quantum Computer: A Transfer Matrix Approach
- Fast Quantum Methods for Optimization
- Renormalization Group Circuits for Gapless States
- Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
Cited by in corpus (17)
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Challenges and Opportunities in Quantum Optimization
- Quantum-enhanced Markov chain Monte Carlo
- Quantum computing for chemistry and physics applications from a Monte Carlo perspective
- Number Partitioning with Grover's Algorithm in Central Spin Systems
- Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
- Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
- Digital-analog quantum learning on Rydberg atom arrays
- Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
- Quantum sampling for the Euclidean path integral of lattice gauge theory
- Quantum-assisted variational Monte Carlo
- Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
- Machine-learning-inspired quantum control in many-body dynamics
- Robust projective measurements through measuring code-inspired observables
- Quantum Annealing Algorithms for Estimating Ising Partition Functions
- All-to-all connectivity of Rydberg-atom-based quantum processors with messenger qubits