Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy
- 26 August 2024
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 110 (2) , 022620
Abstract
Quantum annealing (QA) is a method for solving combinatorial optimization problems. We can estimate the computational time for QA using what is referred to as the adiabatic condition derived from the adiabatic theorem. 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 , where 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. For concrete examples, we consider the adiabatic Grover search and the ferromagnetic -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 are able to achieve a success probability considerably higher than that of conventional QA. Moreover, in concrete examples, we numerically show the scaling of the computational cost is quadratically improved compared to the conventional QA. Our findings pave the way for a better understanding of QA performance.
Keywords
Funding Information
- New Energy and Industrial Technology Development Organization (JPNP16007)
- Ministry of Education, Culture, Sports, Science and Technology
- Japan Science and Technology Corporation (JPMJPR1919)
This publication has 52 references indexed in Scilit:
- How to experimentally evaluate the adiabatic condition for quantum annealingScientific Reports, 2024
- Undecidability of the spectral gapNature, 2015
- Statistical mechanics and dynamics of solvable models with long-range interactionsPhysics Reports, 2009
- Mathematical foundation of quantum annealingJournal of Mathematical Physics, 2008
- Bounds for the adiabatic approximation with applications to quantum computationJournal of Mathematical Physics, 2007
- Adiabatic Population Transfer with Control FieldsThe Journal of Physical Chemistry A, 2003
- The maximum speed of dynamical evolutionPhysica D: Nonlinear Phenomena, 1998
- Quantum annealing: A new method for minimizing multidimensional functionsChemical Physics Letters, 1994
- Quantum stochastic optimizationStochastic Processes and their Applications, 1989
- On the van der Waals Theory of the Vapor-Liquid Equilibrium. I. Discussion of a One-Dimensional ModelJournal of Mathematical Physics, 1963