Quantum Sampling Algorithms for Near-Term Devices

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 (15)

• 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
• Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
• 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
• 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
• 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