Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
arXiv:2109.03007 · doi:10.1103/PhysRevA.104.032602
Abstract
Drawing independent samples from a probability distribution is an important computational problem with applications in Monte Carlo algorithms, machine learning, and statistical physics. The problem can in principle be solved on a quantum computer by preparing a quantum state that encodes the entire probability distribution followed by a projective measurement. We investigate the complexity of adiabatically preparing such quantum states for the Gibbs distributions of various classical models including the Ising chain, hard-sphere models on different graphs, and a model encoding the unstructured search problem. By constructing a parent Hamiltonian, whose ground state is the desired quantum state, we relate the asymptotic scaling of the state preparation time to the nature of transitions between distinct quantum phases. These insights enable us to identify adiabatic paths that achieve a quantum speedup over classical Markov chain algorithms. In addition, we show that parent Hamiltonians for the problem of sampling from independent sets on certain graphs can be naturally realized with neutral atoms interacting via highly excited Rydberg states.
arXiv commentCompanion paper of arXiv:2005.14059
References in corpus (44)
- 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 many-body scars
- 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
- Grover's quantum searching algorithm is optimal
- Quantum Search by Local Adiabatic Evolution
- Criticality, the area law, and the computational power of PEPS
- Schrieffer-Wolff transformation for quantum many-body systems
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- 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
- The problem of equilibration and the computation of correlation functions on a quantum computer
- Thermalization in Nature and on a Quantum Computer
- Majorana zero modes in a quantum Ising chain with longer-ranged interactions
- Quantum Simulations of Classical Annealing Processes
- Quantum Adiabatic Brachistochrone
- A Quantum-Quantum Metropolis Algorithm
- Variational Thermal Quantum Simulation via Thermofield Double States
- Quantum Spin Ice and dimer models with Rydberg atoms
- 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
- Product Spectrum Ansatz and the Simplicity of Thermal States
- Preparing thermal states of quantum systems by dimension reduction
- Liquid ground state, gap and excited states of a strongly correlated spin chain
- Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
- Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays
- Quantum Sampling Algorithms for Near-Term Devices
- Simulation of Classical Thermal States on a Quantum Computer: A Transfer Matrix Approach
- Fast Quantum Methods for Optimization
- Renormalization Group Circuits for Gapless States
- Computational complexity of the Rydberg blockade in two dimensions
Cited by in corpus (8)
- Quantum-enhanced Markov chain Monte Carlo
- Quantum Sampling Algorithms for Near-Term Devices
- The topology of data hides in quantum thermal states
- 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
- Optimal sampling of tensor networks targeting wave function's fast decaying tails
- Exploring Quantum Bootstrap Sampling for AQP Error Assessment: A Pilot Study