Quantum Adiabatic Evolution Algorithms versus Simulated Annealing

Abstract

We explain why quantum adiabatic evolution and simulated annealing perform similarly in certain examples of searching for the minimum of a cost function of n bits. In these examples each bit is treated symmetrically so the cost function depends only on the Hamming weight of the n bits. We also give two examples, closely related to these, where the similarity breaks down in that the quantum adiabatic algorithm succeeds in polynomial time whereas simulated annealing requires exponential time.

16pp., 10 EPS figures, using BoxedEPS macros and LaTeX. Email correspondence to E. Farhi <[email protected]>

Cited by in corpus (39)

• A Quantum Approximate Optimization Algorithm
• Adiabatic Quantum Computing
• NP-complete Problems and Physical Reality
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum search by measurement
• An Elementary Proof of the Quantum Adiabatic Theorem
• A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Prospects and challenges of quantum finance
• Adiabatic optimization versus diffusion Monte Carlo
• Scalable Superconducting Architecture for Adiabatic Quantum Computation
• Charged particle tracking with quantum annealing-inspired optimization
• Period Finding with Adiabatic Quantum Computation
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Quantum Annealing - Foundations and Frontiers
• Practical designs for permutation symmetric problem Hamiltonians on hypercubes
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• Continuous-Time Quantum Algorithms for Unstructured Problems
• Quantum Adiabatic Algorithm and Large Spin Tunnelling
• Quantum Computing by Cooling
• How Fast Can Quantum Annealers Count?
• Tunneling through high energy barriers in simulated quantum annealing
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
• Realizable Quantum Adiabatic Search
• On models of nonlinear evolution paths in adiabatic quantum algorithms
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
• Polynomial Time Algorithms for Estimating Spectra of Adiabatic Hamiltonians
• The Detectability Lemma and Quantum Gap Amplification
• The Fundamental Gap for a Class of Schrödinger Operators on Path and Hypercube Graphs
• The performance of the quantum adiabatic algorithm on spike Hamiltonians
• Quantum Adiabatic Evolution for Global Optimization in Big Data
• Ising formulations of routing optimization problems
• Maritime Just-in-time navigation with Quantum algorithms
• Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem
• Simulated Quantum Annealing is Efficient on the Spike Hamiltonian
• Statistical Analysis of Quantum Annealing