A Quantum-Quantum Metropolis Algorithm
arXiv:1011.1468 · doi:10.1073/pnas.1111758109
Abstract
Recently, the idea of classical Metropolis sampling through Markov chains has been generalized for quantum Hamiltonians. However, the underlying Markov chain of this algorithm is still classical in nature. Due to Szegedy's method, the Markov chains of classical Hamiltonians can achieve a quadratic quantum speedup in the eigenvalue gap of the corresponding transition matrix. A natural question to ask is whether Szegedy's quantum speedup is merely a consequence of employing classical Hamiltonians, where the eigenstates simply coincide with the computational basis, making cloning of the classical information possible. We solve this problem by introducing a quantum version of the method of Markov-chain quantization combined with the quantum simulated annealing (QSA) procedure, and describe explicitly a novel quantum Metropolis algorithm, which exhibits a quadratic quantum speedup in the eigenvalue gap of the corresponding Metropolis Markov chain for any quantum Hamiltonian. This result provides a complete generalization of the classical Metropolis method to the quantum domain.
7 pages
References in corpus (14)
- Quantum phase transition from a superfluid to a Mott insulator in a gas of ultracold atoms
- Simulated Quantum Computation of Molecular Energies
- Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
- Simulation of Electronic Structure Hamiltonians Using Quantum Computers
- Polynomial-time quantum algorithm for the simulation of chemical dynamics
- Simulating chemistry using quantum computers
- Quantum Metropolis Sampling
- Quantum Simulations of Classical Annealing Processes
- Speed-up via Quantum Sampling
- Preparing thermal states of quantum systems by dimension reduction
- Solving Quantum Ground-State Problems with Nuclear Magnetic Resonance
- Quantum computing applied to calculations of molecular energies: CH2 benchmark
- Quantum algorithms for classical lattice models
- Simulation of Classical Thermal States on a Quantum Computer: A Transfer Matrix Approach
Cited by in corpus (95)
- Quantum Machine Learning
- A variational eigenvalue solver on a quantum processor
- Quantum Chemistry in the Age of Quantum Computing
- Quantum algorithms for quantum chemistry and quantum materials science
- Quantum optimization using variational algorithms on near-term quantum devices
- Quantum speedup of Monte Carlo methods
- From transistor to trapped-ion computers for quantum chemistry
- Quantum speedup for active learning agents
- Tomography and Generative Data Modeling via Quantum Boltzmann Training
- Quantum Computation of Finite-Temperature Static and Dynamical Properties of Spin Systems Using Quantum Imaginary Time Evolution
- Quantum Algorithm for Spectral Measurement with Lower Gate Count
- Digital quantum simulation of molecular vibrations
- Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information
- Variational Quantum Boltzmann Machines
- 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
- Rapid adiabatic preparation of injective PEPS and Gibbs states
- Demon-like Algorithmic Quantum Cooling and its Realization with Quantum Optics
- Universal simulation of Markovian open quantum systems
- Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
- Solving Quantum Ground-State Problems with Nuclear Magnetic Resonance
- Single-ancilla ground state preparation via Lindbladians
- Digital Quantum Simulation of the Statistical Mechanics of a Frustrated Magnet
- QFold: Quantum Walks and Deep Learning to Solve Protein Folding
- Robust quantum compilation and circuit optimisation via energy minimisation
- Quantum enhancements for deep reinforcement learning in large spaces
- Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
- Optimizing qubit resources for quantum chemistry simulations in second quantization on a quantum computer
- Toward Quantum Computing Phase Diagrams of Gauge Theories with Thermal Pure Quantum States
- Quantum Walks
- Introduction to Quantum Algorithms for Physics and Chemistry
- Machine learning \& artificial intelligence in the quantum domain
- Predicting Gibbs-State Expectation Values with Pure Thermal Shadows
- Quantum computing for chemistry and physics applications from a Monte Carlo perspective
- Quantum Simulation of Chiral Phase Transitions
- Artificial quantum thermal bath: Engineering temperature for a many-body quantum system
- Quantum many-body systems in thermal equilibrium
- Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
- Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer
- Generative training of quantum Boltzmann machines with hidden units
- Quantum Sampling Algorithms for Near-Term Devices
- Faster quantum and classical SDP approximations for quadratic binary optimization
- Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
- Hardware-efficient quantum algorithm for the simulation of open-system dynamics and thermalisation
- Superdiffusive quantum stochastic walk definable of arbitrary directed graph
- Efficient simulation of sparse Markovian quantum dynamics
- Quantum rejection sampling
- Error Bounds for Variational Quantum Time Evolution
- Finding a marked node on any graph by continuous-time quantum walk
- Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems
- Resource estimate for quantum many-body ground-state preparation on a quantum computer
- Variational Gibbs State Preparation on NISQ devices
- Fragmented imaginary-time evolution for early-stage quantum signal processors
- Szegedy Walk Unitaries for Quantum Maps
- Adaptive variational quantum minimally entangled typical thermal states for finite temperature simulations
- Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
- Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
- Quantum Speed-ups for Semidefinite Programming
- Minimal Effective Gibbs Ansatz (MEGA): A simple protocol for extracting an accurate thermal representation for quantum simulation
- Faster quantum mixing for slowly evolving sequences of Markov chains
- Bootstrap Embedding on a Quantum Computer
- Quantum computation of thermal averages in the presence of a sign problem
- Nitrogen-Vacancy Center as Open-Quantum-System Simulator
- 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
- Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
- Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm
- 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
- Reachability Analysis of Quantum Markov Decision Processes
- Quantum algorithm for estimating volumes of convex bodies
- Fast and robust quantum state tomography from few basis measurements
- Quantum algorithm for spectral projection by measuring an ancilla iteratively
- Estimating Gibbs partition function with quantumClifford sampling
- Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
- Kernel-Function Based Quantum Algorithms for Finite Temperature Quantum Simulation
- Estimating molecular thermal averages with the quantum equation of motion and informationally complete measurements
- Quantum-enhanced Markov Chain Monte Carlo for systems larger than your Quantum Computer
- Metropolis-style random sampling of quantum gates for the estimation of low-energy observables
- 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
- Perfect Sampling for Quantum Gibbs States
- Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
- Quantum Bayesian Inference with Renormalization for Gravitational Waves
- Provably Efficient Simulation of 1D Long-Range Interacting Systems at Any Temperature
- Quantum Lower Bounds by Sample-to-Query Lifting
- Quantum Generative Training Using Rényi Divergences
- Quantum Algorithm for Testing Graph Completeness
- Quantum Machine Learning For Classical Data
- Variational Quantum Algorithms for Gibbs State Preparation
- Stability of universal properties against perturbations of the Markov Chain Monte Carlo algorithm
- Quasi-adiabatic thermal ensemble preparation in the thermodynamic limit