Quantum Simulations of Classical Annealing Processes

Abstract

We describe a quantum algorithm that solves combinatorial optimization problems by quantum simulation of a classical simulated annealing process. Our algorithm exploits quantum walks and the quantum Zeno effect induced by evolution randomization. It requires order $1/\sqrt{\delta }$ steps to find an optimal solution with bounded error probability, where $\delta$ is the minimum spectral gap of the stochastic matrices used in the classical annealing process. This is a quadratic improvement over the order $1/\delta$ steps required by the latter.

4 pages - 1 figure. This work differs from arXiv:0712.1008 in that the quantum Zeno effect is implemented via randomization in the evolution

References in corpus (7)

• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum random walks - an introductory overview
• Theory of Quantum Annealing of an Ising Spin Glass
• Optimal Quantum Measurements of Expectation Values of Observables
• A Quantum Approach to Classical Statistical Mechanics
• Quantum search by measurement

Cited by in corpus (100)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum machine learning: a classical perspective
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Simulating chemistry using quantum computers
• Quantum speedup of Monte Carlo methods
• Quantum Metropolis Sampling
• Quantum computing for finance
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Quantum speedup for active learning agents
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum Machine Learning for Chemistry and Physics
• A Quantum-Quantum Metropolis Algorithm
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Speed-up via Quantum Sampling
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Preparing ground states of quantum many-body systems on a quantum computer
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Magic-state resource theory for the ground state of the transverse-field Ising model
• Quantum-enhanced Markov chain Monte Carlo
• Rapid adiabatic preparation of injective PEPS and Gibbs states
• Preparing thermal states of quantum systems by dimension reduction
• Quadratic speedup for spatial search by continuous-time quantum walk
• Nonstabilizerness determining the hardness of direct fidelity estimation
• High Performance Emulation of Quantum Circuits
• Quantum Speed-up for Approximating Partition Functions
• Necessary Condition for the Quantum Adiabatic Approximation
• QFold: Quantum Walks and Deep Learning to Solve Protein Folding
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Quantum enhancements for deep reinforcement learning in large spaces
• A Variational Quantum Algorithm for Preparing Quantum Gibbs States
• Quantum walk approach to simulating parton showers
• Introduction to Quantum Algorithms for Physics and Chemistry
• Quantum Walks
• Rapid thermalization of spin chain commuting Hamiltonians
• Spectral Gap Amplification
• Constrained Optimization via Quantum Zeno Dynamics
• Radio frequency reflectometry in silicon-based quantum dots
• Quantum Computing for Fusion Energy Science Applications
• Quantum algorithms for estimating quantum entropies
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Quantum Sampling Algorithms for Near-Term Devices
• Simulation of Classical Thermal States on a Quantum Computer: A Transfer Matrix Approach
• Quantum Enhanced Inference in Markov Logic Networks
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• Quantum rejection sampling
• All optical Controlled-NOT quantum gate based on an exciton-polariton circuit
• Collider Events on a Quantum Computer
• Variational Gibbs State Preparation on NISQ devices
• Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems
• Asymptotic entanglement in 1D quantum walks with a time-dependent coined
• Szegedy Walk Unitaries for Quantum Maps
• Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
• Quantum Language Processing
• Faster quantum mixing for slowly evolving sequences of Markov chains
• Fast Quantum Methods for Optimization
• Improved Bounds for Eigenpath Traversal
• Variational quantum Gibbs state preparation with a truncated Taylor series
• Complexity of quantum state verification in the quantum linear systems problem
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Magnetic gradient free two axis control of a valley spin qubit in SiGe
• Variational Approach to Quantum State Tomography based on Maximal Entropy Formalism
• Speedup of the Quantum Adiabatic Algorithm using Delocalization Catalysis
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians
• Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm
• Dissipative variational quantum algorithms for Gibbs state preparation
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Fast quantum algorithms for traversing paths of eigenstates
• Collective dynamics of phase-repulsive oscillators solves graph coloring problem
• Zeno subspace in quantum-walk dynamics
• Quantum algorithm for estimating volumes of convex bodies
• Optimal exploration of random walks with local bias on networks
• Quantum algorithm for spectral projection by measuring an ancilla iteratively
• Construction of non-convex polynomial loss functions for training a binary classifier with quantum annealing
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• Discretely-observable continuous time quantum walks on Möbius strips and other exotic structures in 3D integrated photonics
• Quantum search in many-body interacting system with long-range interaction
• Quantum sampling for the Euclidean path integral of lattice gauge theory
• Quantum algorithm for exact Monte Carlo sampling
• Efficient Circuits for Quantum Walks
• Quantum Zeno approach for molecular energies with maximum commuting initialHamiltonians
• Quantum-assisted variational Monte Carlo
• Preparing Many Copies of a Quantum State in the Black-Box Model
• Sensitivity of Quantum Walks with Perturbation
• End-to-End Protocol for High-Quality QAOA Parameters with Few Shots
• Faster quantum mixing of Markov chains in non-regular graph with fewer qubits
• Disorder-free localisation in continuous-time quantum walks : Role of symmetries
• Variational Quantum Algorithms for Gibbs State Preparation
• Gibbs state sampling via cluster expansions
• Q-CHOP: Quantum constrained Hamiltonian optimization
• Towards establishing a connection between two-level quantum systems and physical spaces
• Quantum Simulation of the Unruh Temperature via the Thermal Properties of Virtually Evolving Bose-Einstein Condensates
• Monte Carlo Quantum Computing
• Resonant Coupling Parameter Estimation with Superconducting Qubits
• Expanding the reach of quantum optimization with fermionic embeddings
• Quantum Speedups for Multiproposal MCMC