Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy

Abstract

Quantum annealing (QA) is a method for solving combinatorial optimization problems. We can estimate the computational time for QA using the adiabatic condition. The adiabatic condition consists of two parts: an energy gap and a transition matrix. Most past studies have focused on the relationship between the energy gap and computational time. The success probability of QA is considered to decrease exponentially owing to the exponentially decreasing energy gap at the first-order phase-transition point. In this study, through a detailed analysis of the relationship between the energy gap, transition matrix, and computational cost during QA, we propose a general method for constructing counterintuitive models wherein QA with a constant annealing time fails despite a constant energy gap, based on polynomial energy. We assume that the energy of the total Hamiltonian is at most $\Theta (L)$, where $L$ is the number of qubits. In our formalism, we choose a known model that exhibits an exponentially small energy gap during QA, and modify the model by adding a specific penalty term to the Hamiltonian. In the modified model, the transition matrix in the adiabatic condition becomes exponentially large as the number of qubits increases, while the energy gap remains constant. Moreover, we achieve a quadratic speedup, for which the upper bound for improvement in the adiabatic condition is determined by the polynomial energy. As examples, we consider the adiabatic Grover search and the $p$-spin model. In these cases, with the addition of the penalty term, although the success probability of QA on the modified models becomes exponentially small despite a constant energy gap; we can achieve a success probability considerably higher than that of conventional QA. Moreover, we numerically show the scaling of the computational cost is quadratically improved compared to the conventional QA.

13 pages, 9 figures

References in corpus (41)

• Quantum Mechanics helps in searching for a needle in a haystack
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Adiabatic Quantum Computing
• Shortcuts to adiabaticity: concepts, methods, and applications
• Statistical mechanics and dynamics of solvable models with long-range interactions
• The maximum speed of dynamical evolution
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing and Analog Quantum Computation
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Quantum Search by Local Adiabatic Evolution
• Quantum speed limits: from Heisenberg's uncertainty principle to optimal quantum control
• Mathematical Foundation of Quantum Annealing
• Bounds for the adiabatic approximation with applications to quantum computation
• Undecidability of the Spectral Gap (short version)
• Anderson localization casts clouds over adiabatic quantum optimization
• Energy-time uncertainty relation for driven quantum systems
• Quantum versus Classical Annealing of Ising Spin Glasses
• Consistency of the Adiabatic Theorem
• First order phase transition in the Quantum Adiabatic Algorithm
• Quantum annealing with antiferromagnetic fluctuations
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• On quantum mean-field models and their quantum annealing
• Controlling and exploring quantum systems by algebraic expression of adiabatic gauge potential
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Quantum phase transitions in fully connected spin models: an entanglement perspective
• Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
• A new perturbative approach to the adiabatic approximation
• Performance Evaluation of Adiabatic Quantum Computation via Quantum Speed Limits and Possible Applications to Many-Body Systems
• Energy gap at first-order quantum phase transitions: An anomalous case
• Greedy parameter optimization for diabatic quantum annealing
• Quantum annealing with twisted fields
• Performance enhancement of quantum annealing under the Lechner-Hauke-Zoller scheme by non-linear driving of the constraint term
• Rigorous convergence condition for quantum annealing
• How to experimentally evaluate the adiabatic condition for quantum annealing
• Nonstoquastic catalyst for bifurcation-based quantum annealing of ferromagnetic $p$-spin model