The Power of Adiabatic Quantum Computation with No Sign Problem

Abstract

We show a superpolynomial oracle separation between the power of adiabatic quantum computation with no sign problem and the power of classical computation.

22 pages, 2 figures; v2 final version in Quantum

References in corpus (5)

• Universal computation by quantum walk
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Adiabatic optimization versus diffusion Monte Carlo
• On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm
• The Short Path Algorithm Applied to a Toy Model

Cited by in corpus (17)

• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Digitized-Counterdiabatic Quantum Optimization
• Prospects and challenges of quantum finance
• Automated Design of Pulse Sequences for Magnetic Resonance Fingerprinting using Physics-Inspired Optimization
• An energetic perspective on rapid quenches in quantum annealing
• Accelerated Quantum Monte Carlo with Probabilistic Computers
• Diagonal Catalysts in Quantum Adiabatic Optimization
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Lefschetz Thimble Quantum Monte Carlo for Spin Systems
• How to experimentally evaluate the adiabatic condition for quantum annealing
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
• Simultaneous Stoquasticity
• Limits of Short-Time Evolution of Local Hamiltonians
• Simulated Quantum Annealing is Efficient on the Spike Hamiltonian
• Degeneracy Engineering for Classical and Quantum Annealing: A Case Study of Sparse Linear Regression in Collider Physics