Quantum Metropolis Sampling

Abstract

The original motivation to build a quantum computer came from Feynman who envisaged a machine capable of simulating generic quantum mechanical systems, a task that is believed to be intractable for classical computers. Such a machine would have a wide range of applications in the simulation of many-body quantum physics, including condensed matter physics, chemistry, and high energy physics. Part of Feynman's challenge was met by Lloyd who showed how to approximately decompose the time-evolution operator of interacting quantum particles into a short sequence of elementary gates, suitable for operation on a quantum computer. However, this left open the problem of how to simulate the equilibrium and static properties of quantum systems. This requires the preparation of ground and Gibbs states on a quantum computer. For classical systems, this problem is solved by the ubiquitous Metropolis algorithm, a method that basically acquired a monopoly for the simulation of interacting particles. Here, we demonstrate how to implement a quantum version of the Metropolis algorithm on a quantum computer. This algorithm permits to sample directly from the eigenstates of the Hamiltonian and thus evades the sign problem present in classical simulations. A small scale implementation of this algorithm can already be achieved with today's technology

revised version

References in corpus (9)

• Simulated Quantum Computation of Molecular Energies
• Ab-initio Determination of Light Hadron Masses
• Realization of the quantum Toffoli gate with trapped ions
• The power of quantum systems on a line
• Quantum Simulations of Classical Annealing Processes
• The ${\chi }^2$-divergence and Mixing times of quantum Markov processes
• Quantum NP - A Survey
• A quantum version of Wielandt's inequality
• Quantum Algorithm for Molecular Properties and Geometry Optimization

Cited by in corpus (201)

• Quantum Machine Learning
• A variational eigenvalue solver on a quantum processor
• Quantum Simulation
• Quantum Chemistry in the Age of Quantum Computing
• Quantum algorithms for quantum chemistry and quantum materials science
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Quantum optimization using variational algorithms on near-term quantum devices
• Variational ansatz-based quantum simulation of imaginary time evolution
• Quantum machine learning: a classical perspective
• Simulating chemistry using quantum computers
• Quantum speedup of Monte Carlo methods
• Quantum Simulation for High Energy Physics
• Can One Trust Quantum Simulators?
• Solving strongly correlated electron models on a quantum computer
• From transistor to trapped-ion computers for quantum chemistry
• Thermalization in Nature and on a Quantum Computer
• Quantum speedup for active learning agents
• Work measurement as a generalized quantum measurement
• Challenges and Opportunities in Quantum Optimization
• A Quantum-Quantum Metropolis Algorithm
• Variational Thermal Quantum Simulation via Thermofield Double States
• Quantum logarithmic Sobolev inequalities and rapid mixing
• The ${\chi }^2$-divergence and Mixing times of quantum Markov processes
• Quantum circuits cannot control unknown operations
• Quantum Computation of Finite-Temperature Static and Dynamical Properties of Spin Systems Using Quantum Imaginary Time Evolution
• Quantum algorithm for simulating the dynamics of an open quantum system
• Algorithms for quantum simulation at finite energies
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Quantum simulation of non-equilibrium dynamics and thermalization in the Schwinger model
• Linear Response on a Quantum Computer
• Quantum Inference on Bayesian Networks
• Digital quantum simulation of molecular vibrations
• Variational Quantum Boltzmann Machines
• Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information
• Quantum Computing for Molecular Biology
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Simulating Quantum Materials with Digital Quantum Computers
• Quantum Analog-Digital Conversion
• 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
• Variational preparation of finite-temperature states on a quantum computer
• Universal simulation of Markovian open quantum systems
• Scaling of variational quantum circuit depth for condensed matter systems
• Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
• Quantum Computing with black-box Subroutines
• Single-ancilla ground state preparation via Lindbladians
• Digital Quantum Simulation of the Statistical Mechanics of a Frustrated Magnet
• Rapid mixing implies exponential decay of correlations
• QFold: Quantum Walks and Deep Learning to Solve Protein Folding
• Robust quantum compilation and circuit optimisation via energy minimisation
• Simulating Quantum Fields with Cavity QED
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Toward Quantum Computing Phase Diagrams of Gauge Theories with Thermal Pure Quantum States
• Quantum enhancements for deep reinforcement learning in large spaces
• Hypercontractivity of quasi-free quantum semigroups
• Preparing projected entangled pair states on a quantum computer
• Simulating hydrodynamics on noisy intermediate-scale quantum devices with random circuits
• Quantum Walks
• Introduction to Quantum Algorithms for Physics and Chemistry
• Polymer Physics by Quantum Computing
• Thermal State Preparation via Rounding Promises
• Rapid thermalization of spin chain commuting Hamiltonians
• Machine learning \& artificial intelligence in the quantum domain
• Lattice Renormalization of Quantum Simulations
• Quantum computing for chemistry and physics applications from a Monte Carlo perspective
• Provable Quantum Advantage in Randomness Processing
• Approximating many-body quantum states with quantum circuits and measurements
• Quantum Simulation of Chiral Phase Transitions
• Engineered thermalization and cooling of quantum many-body systems
• Spectral convergence bounds for classical and quantum Markov processes
• Artificial quantum thermal bath: Engineering temperature for a many-body quantum system
• Bayesian Quantum Multiphase Estimation Algorithm
• Diagonal quantum circuits: their computational power and applications
• Programmable Quantum Annealers as Noisy Gibbs Samplers
• Quantum many-body systems in thermal equilibrium
• Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Quantum Sampling Algorithms for Near-Term Devices
• A method to efficiently simulate the thermodynamical properties of the Fermi-Hubbard model on a quantum computer
• Perturbation Bounds for Quantum Markov Processes and their Fixed Points
• Faster quantum and classical SDP approximations for quadratic binary optimization
• Hardware-efficient quantum algorithm for the simulation of open-system dynamics and thermalisation
• Lanczos recursion on a quantum computer for the Green's function and ground state
• Combinatorial Optimization on Gate Model Quantum Computers: A Survey
• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• Quantum Enhanced Inference in Markov Logic Networks
• Superdiffusive quantum stochastic walk definable of arbitrary directed graph
• Efficient simulation of sparse Markovian quantum dynamics
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• On the Sample Complexity of Quantum Boltzmann Machine Learning
• Quantum rejection sampling
• Probing finite-temperature observables in quantum simulators of spin systems with short-time dynamics
• Finding a marked node on any graph by continuous-time quantum walk
• Error Bounds for Variational Quantum Time Evolution
• Toward Automatic Verification of Quantum Programs
• Dynamical maps, quantum detailed balance and Petz recovery map
• Variational Gibbs State Preparation on NISQ devices
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• A Comparison of Quantum Walk Implementations on NISQ Computers
• Continuous-variable assisted thermal quantum simulation
• Szegedy Walk Unitaries for Quantum Maps
• Adaptive variational quantum minimally entangled typical thermal states for finite temperature simulations
• Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Quantum Speed-ups for Semidefinite Programming
• Faster quantum mixing for slowly evolving sequences of Markov chains
• Explainable AI using expressive Boolean formulas
• Designing open quantum systems with known steady states: Davies generators and beyond
• Exact stabilization of entangled states in finite time by dissipative quantum circuits
• A Silicon Surface Code Architecture Resilient Against Leakage Errors
• Quantum computation of thermal averages in the presence of a sign problem
• Quantum algorithm for universal implementation of projective measurement of energy
• Quantum algorithms for scientific computing
• Observation of a finite-energy phase transition in a one-dimensional quantum simulator
• Certified algorithms for equilibrium states of local quantum Hamiltonians
• Local minima in quantum systems
• Rapid quantum ground state preparation via dissipative dynamics
• Variational quantum Gibbs state preparation with a truncated Taylor series
• A variational quantum algorithm for Hamiltonian diagonalization
• Variational Approach to Quantum State Tomography based on Maximal Entropy Formalism
• Double-bracket quantum algorithms for diagonalization
• Dissipative Preparation of Many-Body Quantum States: Towards Practical Quantum Advantage
• Controlled quantum operations and combs, and their applications to universal controllization of divisible unitary operations
• Optimal quantum algorithm for Gibbs state preparation
• Exponential Decay of Matrix $\Phi$-Entropies on Markov Semigroups with Applications to Dynamical Evolutions of Quantum Ensembles
• Thermal variational quantum simulation on a superconducting quantum processor
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
• Quantum Algorithm for Preparing Thermal Gibbs States - Detailed Analysis
• Density functionals and Kohn-Sham potentials with minimal wavefunction preparations on a quantum computer
• Dissipative variational quantum algorithms for Gibbs state preparation
• Estimation of general Hamiltonian parameters via controlled energy measurements
• Uniqueness regime for Markov dynamics on quantum lattice spin systems
• Why now is the right time to study quantum computing
• Robust Extraction of Thermal Observables from State Sampling and Real-Time Dynamics on Quantum Computers
• Calculating the many-body density of states on a digital quantum computer
• A QUBO model of the RNA folding problem optimized by variational hybrid quantum annealing
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• Reachability Analysis of Quantum Markov Decision Processes
• Quantum algorithm for estimating volumes of convex bodies
• A constructive commutative quantum Lovasz Local Lemma, and beyond
• Fast and robust quantum state tomography from few basis measurements
• Quantum self-learning Monte Carlo with quantum Fourier transform sampler
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• From decay of correlations to locality and stability of the Gibbs state
• Chern-Simons theory encoded on a spin chain
• Contractivity properties of a quantum diffusion semigroup
• Mixing Time of Open Quantum Systems via Hypocoercivity
• Quantum algorithm for spectral projection by measuring an ancilla iteratively
• Estimating Gibbs partition function with quantumClifford sampling
• Efficient Bayesian phase estimation using mixed priors
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• Solving Quantum Statistical Mechanics with Variational Autoregressive Networks and Quantum Circuits
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Entanglement Properties of SU(2) Gauge Theory
• Kernel-Function Based Quantum Algorithms for Finite Temperature Quantum Simulation
• Estimating molecular thermal averages with the quantum equation of motion and informationally complete measurements
• Metropolis-style random sampling of quantum gates for the estimation of low-energy observables
• Quantum-enhanced Markov Chain Monte Carlo for systems larger than your Quantum Computer
• Practical sampling schemes for quantum phase estimation
• Solving Free Fermion Problems on a Quantum Computer
• Lindblad engineering for quantum Gibbs state preparation under the eigenstate thermalization hypothesis
• Quantum-assisted variational Monte Carlo
• Thermal state preparation by repeated interactions at and beyond the Lindblad limit
• Combinatorial summation of Feynman diagrams: Equation of state of the 2D SU(N) Hubbard model
• Topological obstructions to quantum computation with unitary oracles
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Perfect Sampling for Quantum Gibbs States
• Readout Error Mitigation for Mid-Circuit Measurements and Feedforward
• Some Error Analysis for the Quantum Phase Estimation Algorithms
• Sequential Strong Measurements and Heat Vision
• Generation of Thermofield Double States and Critical Ground States with a Quantum Computer
• Use of Quantum Sampling to Calculate Mean Values of Observables and Partition Function of a Quantum System
• Quantum Bayesian Inference with Renormalization for Gravitational Waves
• Quantum Lower Bounds by Sample-to-Query Lifting
• Unifying Collisional Models and the Monte Carlo Metropolis Method: Algorithms for Dynamics of Open Quantum Systems
• Quantum Computing Beyond Ground State Electronic Structure: A Review of Progress Toward Quantum Chemistry Out of the Ground State
• Provably Efficient Simulation of 1D Long-Range Interacting Systems at Any Temperature
• Optimal Coherent Quantum Phase Estimation via Tapering
• Quantized Markov Chain Couplings that Prepare Qsamples
• Calculating potential energy surfaces with quantum computers by measuring only the density along adiabatic transitions
• Block Lanczos method for excited states on a quantum computer
• Alternating Projections Methods for Discrete-time Stabilization of Quantum States
• Towards self-correcting quantum codes for neutral atom arrays
• Variational Quantum Algorithms for Gibbs State Preparation
• Simple and efficient end-to-end quantum thermal and ground state preparation
• Gibbs state sampling via cluster expansions
• Efficient and simple Gibbs state preparation of the 2D toric code via duality to classical Ising chains
• Quasi-adiabatic thermal ensemble preparation in the thermodynamic limit
• Modeling Time-Dependent Systems using Dynamic Quantum Bayesian Networks
• One, Two, Three: One empirical evaluation of a two-copy shadow tomography scheme with triple efficiency
• Strictly incoherent operations for one-qubit systems
• Stability of universal properties against perturbations of the Markov Chain Monte Carlo algorithm
• Variational quantum simulation of the quantum critical regime
• Quantum Markov chain Monte Carlo method with programmable quantum simulators
• Quantum Phase Estimation Algorithm with Gaussian Spin States
• Markovian Statistics on Evolving Systems
• Two Variations of Quantum Phase Estimation for Reducing Circuit Error Rates: Application to the Harrow--Hassidim--Lloyd Algorithm