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.
Companion paper of arXiv:2005.14059
References in corpus (13)
- 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
- Criticality, the area law, and the computational power of PEPS
- Competing density-wave orders in a one-dimensional hard-boson model
- One-Dimensional Symmetry Protected Topological Phases and their Transitions
- Quantum Simulations of Classical Annealing Processes
- Quantum Adiabatic Brachistochrone
- Speed-up via Quantum Sampling
- A Quantum Approach to Classical Statistical Mechanics
- Phase transitions and localizable entanglement in cluster-state spin chains with Ising couplings and local fields
- Preparing thermal states of quantum systems by dimension reduction
- Fast Quantum Methods for Optimization