Tunneling and Speedup in Quantum Optimization for Permutation-Symmetric Problems

2015/11/12 by Siddharth Muthukrishnan, Tameem Albash, Daniel A. Lidar · 85 citations
Computer Science · Physics and Astronomy · #Adiabatic process #Computer science #Diabatic #Parallel computing #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum and electron transport phenomena #Quantum annealing #Quantum computer #Quantum mechanics #Quantum tunnelling #Speedup #Statistical physics #quant-ph

paper · pdf · doi:10.1103/physrevx.6.031010

published in Physical Review X 6(3) (American Physical Society) · 21 pages and 12 figures; subsumes arXiv:1505.01249

arxiv created 2015/11/12 · openalex publication_date 2016/07/21 · arxiv updated 2016/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

It is commonly believed that quantum tunneling is necessary for a quantum speedup in quantum annealing, but a theoretical demonstration shows that quantum tunneling is not always the most efficient way to yield a quantum speedup.

Citations

• When Diabatic Trumps Adiabatic in Quantum Optimization
• Colloquium: Quantum annealing and analog quantum computation
• Quantum Ising Phases and Transitions in Transverse Ising Models
• Quantum Annealing in the Transverse Ising Model
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Equation of State Calculations by Fast Computing Machines
• Bounds for the adiabatic approximation with applications to quantum computation
• Monte Carlo sampling methods using Markov chains and their applications
• A variable order Runge-Kutta method for initial value problems with rapidly varying right-hand sides
• Quantum Search by Local Adiabatic Evolution

Cited by

• Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Effective Gaps Are Not Effective: Quasipolynomial Classical Simulation of Obstructed Stoquastic Hamiltonians
• Optimally Stopped Optimization

Related

• Tunneling through high energy barriers in simulated quantum annealing
• When Diabatic Trumps Adiabatic in Quantum Optimization
• What is the Computational Value of Finite Range Tunneling?
• Quantization-based Optimization with Perspective of Quantum Mechanics
• Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA