Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2007.11212 · Physical Review Research

Speedup of the quantum adiabatic algorithm using delocalization catalysis

Chenfeng Cao, Jian Xue, Nic Shannon, Robert Joynt

Published Jan 29, 2021• 17 citations
arXivHTMLPDF

Abstract

We propose a method to speed up the quantum adiabatic algorithm using catalysis by many-body delocalization.This is applied to random-field antiferromagnetic Ising spin models.The algorithm is catalyzed in such a way that the evolution approximates a Heisenberg model in the middle of its course, and the model is in a delocalized phase.We show numerically that we can speed up the standard algorithm for finding the ground state of the random-field Ising model using this idea.We also demonstrate that the speedup is due to gap amplification, even though the underlying model is not frustration-free.The crossover to speedup occurs at roughly the value of the interaction which is known to be the critical one for the delocalization transition.We also calculate the participation ratio and entanglement entropy as a function of time: Their time dependencies indicate that the system is exploring more states and that they are more entangled than when there is no catalyst.Together, all these pieces of evidence demonstrate that the speedup is related to delocalization.Even though only relatively small systems can be investigated, the evidence suggests that the scaling of the method with system size is favorable.Our method is illustrated by experimental results from a small online IBM quantum computer, showing how to verify the method in future as such machines improve.The cost of the catalytic method compared with the standard algorithm is only a constant factor.

DOI
10.1103/physrevresearch.3.013092

Related papers

Steering random spin systems to speed up the quantum adiabatic algorithm

A. Barış Özgüler, Robert Joynt, Maxim Vavilov

A general time-dependent quantum system can be driven fast from its initial ground state to its final ground state without generating transitions by adding a steering term to the Hamiltonian. We show how this technique can be modified to improve on the standard quantum adiabatic algorithm by making a single-particle and cluster approximation to the steering term. The method is applied to a one-dimensional Ising model in a random field. For the limit of strong disorder, the correction terms significantly enhance the probability for the whole system to remain in the ground state for the proposed nonstoquastic annealing protocol. We demonstrate that even when transitions occur for stronger interaction between qubits, the most probable quantum state is one of the lower-energy states of the final Hamiltonian. Since the method can be applied to any model, and more sophisticated approximations to the steering term are possible, the alternative technique opens up an avenue for the improvement of the quantum adiabatic algorithm.

arXiv:1804.01180•Physical Review A•Dec 7, 2018•28 citations

Improving the efficiency of quantum annealing with controlled diagonal catalysts

T Hattori, Shu Tanaka

Quantum annealing is a promising algorithm for solving combinatorial optimization problems. It searches for the ground state of the Ising model, which corresponds to the optimal solution of a given combinatorial optimization problem. The guiding principle of quantum annealing is the adiabatic theorem in quantum mechanics, which guarantees that a system remains in the ground state of its Hamiltonian if the time evolution is sufficiently slow. According to the adiabatic theorem, the annealing time required for quantum annealing to satisfy the adiabaticity scales inversely proportional to the square of the minimum energy gap between the ground state and the first excited state during time evolution. As a result, finding the ground state becomes significantly more difficult when the energy gap is small, creating a major bottleneck in quantum annealing. Expanding the energy gap is one strategy for improving the performance of quantum annealing; however, its implementation in actual hardware remains difficult. This study proposes a method for efficiently solving instances with small energy gaps by introducing additional local terms to the Hamiltonian and exploiting the diabatic transition remaining in the small energy gap. The proposed method achieves an approximate quadratic speedup of the exponential scaling exponent in time to solution compared to the conventional quantum annealing. In addition, we investigate the transferability of the parameters obtained with the proposed method.

arXiv:2503.15244•Physical Review A•Feb 3, 2026•4 citations

Quantum speedup at zero temperature via coherent catalysis

Gabriel A. Durkin

It is known that secondary nonstoquastic drivers may offer speedups or catalysis in some models of adiabatic quantum computation accompanying the more typical transverse field driver. Their combined intent is to raze potential barriers to zero during adiabatic evolution from a false vacuum to a true minimum; first-order phase transitions are softened into second-order transitions. We move beyond mean-field analysis to a fully quantum model of a spin ensemble undergoing adiabatic evolution in which the spins are mapped to a variable mass particle in a continuous one-dimensional potential. We demonstrate that the necessary criterion for enhanced mobility or ``speedup'' across potential barriers is actually a quantum form of the Rayleigh criterion. Quantum catalysis is exhibited in models where previously thought not possible, when barriers cannot be eliminated. For the 3-spin model with a secondary antiferromagnetic driver, catalyzed time complexity scales between linear and quadratic with the number of qubits. As a corollary, we identify a useful resonance criterion for quantum phase transition that differs from the classical one, but converges on it, in the thermodynamic limit.

arXiv:1806.07602•Physical Review A•Mar 12, 2019•18 citations

Numerical Studies of the Quantum Adiabatic Algorithm

A. P. Young, Itay Hen

Quantum annealers promise to solve practical optimization problems potentially faster than conventional classical computers. One of the major ongoing debates in this context pertains to their robustness against the decohering effects of finite temperature and interactions with the environment. We argue that even in an ideal setting of very low temperatures and in the absence of a decohering environment, quantum annealers do not necessarily perform better than classical heuristic solvers. Here, we numerically study the performance of the quantum adiabatic algorithm (QAA) on a variety of constraint satisfaction problems and a spin glass problem by studying the size dependence of the minimum energy gap during the evolution of the QAA. We do so by employing Quantum Monte Carlo schemes as these allow us to study these problems at much larger scales than exact methods would allow. We find that in all cases a quantum phase transition occurs and the minimum gap decreases exponentially with system size, leading to an exponentially large running time for the QAA. Based on these and other results, we briefly discuss potential modifications to the QAA that may improve the scaling of the minimum gap, leading to faster quantum adiabatic algorithms.

Journal of Physics Conference Series•Sep 28, 2015•0 citations

Counterdiabatic driving of the quantum Ising model

Bogdan Damski

A system undergoes adiabatic evolution when its population in the instantaneous eigenbasis of its time-dependent Hamiltonian changes only negligibly. The realization of such dynamics requires slow-enough changes of the parameters of the Hamiltonian, a task that can be hard to achieve near quantum critical points. A powerful alternative is provided by the counterdiabatic modification of the Hamiltonian allowing for an arbitrarily quick implementation of the adiabatic dynamics. Such a counterdiabatic driving protocol has been recently proposed for the quantum Ising model (del Campo et al 2012 Phys. Rev. Lett. 109 115703 ). We derive an exact closed-form expression for all the coefficients of the counterdiabatic Ising Hamiltonian. We discuss two approximations to the exact counterdiabatic Ising Hamiltonian quantifying their efficiency of the dynamical preparation of the desired ground state. In particular, these studies show how quantum criticality enhances finite-size effects in counterdiabatic dynamics.

arXiv:1410.0059•Journal of Statistical Mechanics Theory and Experiment•Dec 22, 2014•50 citations

Quantum Adiabatic Algorithm and Scaling of Gaps at First-Order Quantum Phase Transitions

Chris R. Laumann, Roderich Moessner, Antonello Scardicchio +1 more

Motivated by the quantum adiabatic algorithm (QAA), we consider the scaling of the Hamiltonian gap at quantum first-order transitions, generally expected to be exponentially small in the size of the system. However, we show that a quantum antiferromagnetic Ising chain in a staggered field can exhibit a first-order transition with only an algebraically small gap. In addition, we construct a simple classical translationally invariant one-dimensional Hamiltonian containing nearest-neighbor interactions only, which exhibits an exponential gap at a thermodynamic quantum first-order transition of essentially topological origin. This establishes that (i) the QAA can be successful even across first-order transitions but also that (ii) it can fail on exceedingly simple problems readily solved by inspection, or by classical annealing.

arXiv:1202.3646•Physical Review Letters•Jul 19, 2012•73 citations
We propose a method to speed up the quantum adiabatic algorithm using catalysis by many-body delocalization.This is applied to random-field antiferromagnetic Ising spin models.The algorithm is catalyzed in such a way that the evolution approximates a Heisenberg model in the middle of its course, and the model is in a delocalized phase.We show numerically that we can speed up the standard algorithm for finding the ground state of the random-field Ising model using this idea.We also demonstrate that the speedup is due to gap amplification, even though the underlying model is not frustration-free.The crossover to speedup occurs at roughly the value of the interaction which is known to be the critical one for the delocalization transition.We also calculate the participation ratio and entanglement entropy as a function of time: Their time dependencies indicate that the system is exploring more states and that they are more entangled than when there is no catalyst.Together, all these pieces of evidence demonstrate that the speedup is related to delocalization.Even though only relatively small systems can be investigated, the evidence suggests that the scaling of the method with system size is favorable.Our method is illustrated by experimental results from a small online IBM quantum computer, showing how to verify the method in future as such machines improve.The cost of the catalytic method compared with the standard algorithm is only a constant factor.
A general time-dependent quantum system can be driven fast from its initial ground state to its final ground state without generating transitions by adding a steering term to the Hamiltonian. We show how this technique can be modified to improve on the standard quantum adiabatic algorithm by making a single-particle and cluster approximation to the steering term. The method is applied to a one-dimensional Ising model in a random field. For the limit of strong disorder, the correction terms significantly enhance the probability for the whole system to remain in the ground state for the proposed nonstoquastic annealing protocol. We demonstrate that even when transitions occur for stronger interaction between qubits, the most probable quantum state is one of the lower-energy states of the final Hamiltonian. Since the method can be applied to any model, and more sophisticated approximations to the steering term are possible, the alternative technique opens up an avenue for the improvement of the quantum adiabatic algorithm.
Quantum annealing is a promising algorithm for solving combinatorial optimization problems. It searches for the ground state of the Ising model, which corresponds to the optimal solution of a given combinatorial optimization problem. The guiding principle of quantum annealing is the adiabatic theorem in quantum mechanics, which guarantees that a system remains in the ground state of its Hamiltonian if the time evolution is sufficiently slow. According to the adiabatic theorem, the annealing time required for quantum annealing to satisfy the adiabaticity scales inversely proportional to the square of the minimum energy gap between the ground state and the first excited state during time evolution. As a result, finding the ground state becomes significantly more difficult when the energy gap is small, creating a major bottleneck in quantum annealing. Expanding the energy gap is one strategy for improving the performance of quantum annealing; however, its implementation in actual hardware remains difficult. This study proposes a method for efficiently solving instances with small energy gaps by introducing additional local terms to the Hamiltonian and exploiting the diabatic transition remaining in the small energy gap. The proposed method achieves an approximate quadratic speedup of the exponential scaling exponent in time to solution compared to the conventional quantum annealing. In addition, we investigate the transferability of the parameters obtained with the proposed method.
It is known that secondary nonstoquastic drivers may offer speedups or catalysis in some models of adiabatic quantum computation accompanying the more typical transverse field driver. Their combined intent is to raze potential barriers to zero during adiabatic evolution from a false vacuum to a true minimum; first-order phase transitions are softened into second-order transitions. We move beyond mean-field analysis to a fully quantum model of a spin ensemble undergoing adiabatic evolution in which the spins are mapped to a variable mass particle in a continuous one-dimensional potential. We demonstrate that the necessary criterion for enhanced mobility or ``speedup'' across potential barriers is actually a quantum form of the Rayleigh criterion. Quantum catalysis is exhibited in models where previously thought not possible, when barriers cannot be eliminated. For the 3-spin model with a secondary antiferromagnetic driver, catalyzed time complexity scales between linear and quadratic with the number of qubits. As a corollary, we identify a useful resonance criterion for quantum phase transition that differs from the classical one, but converges on it, in the thermodynamic limit.
Quantum annealers promise to solve practical optimization problems potentially faster than conventional classical computers. One of the major ongoing debates in this context pertains to their robustness against the decohering effects of finite temperature and interactions with the environment. We argue that even in an ideal setting of very low temperatures and in the absence of a decohering environment, quantum annealers do not necessarily perform better than classical heuristic solvers. Here, we numerically study the performance of the quantum adiabatic algorithm (QAA) on a variety of constraint satisfaction problems and a spin glass problem by studying the size dependence of the minimum energy gap during the evolution of the QAA. We do so by employing Quantum Monte Carlo schemes as these allow us to study these problems at much larger scales than exact methods would allow. We find that in all cases a quantum phase transition occurs and the minimum gap decreases exponentially with system size, leading to an exponentially large running time for the QAA. Based on these and other results, we briefly discuss potential modifications to the QAA that may improve the scaling of the minimum gap, leading to faster quantum adiabatic algorithms.
A system undergoes adiabatic evolution when its population in the instantaneous eigenbasis of its time-dependent Hamiltonian changes only negligibly. The realization of such dynamics requires slow-enough changes of the parameters of the Hamiltonian, a task that can be hard to achieve near quantum critical points. A powerful alternative is provided by the counterdiabatic modification of the Hamiltonian allowing for an arbitrarily quick implementation of the adiabatic dynamics. Such a counterdiabatic driving protocol has been recently proposed for the quantum Ising model (del Campo et al 2012 Phys. Rev. Lett. 109 115703 ). We derive an exact closed-form expression for all the coefficients of the counterdiabatic Ising Hamiltonian. We discuss two approximations to the exact counterdiabatic Ising Hamiltonian quantifying their efficiency of the dynamical preparation of the desired ground state. In particular, these studies show how quantum criticality enhances finite-size effects in counterdiabatic dynamics.
Motivated by the quantum adiabatic algorithm (QAA), we consider the scaling of the Hamiltonian gap at quantum first-order transitions, generally expected to be exponentially small in the size of the system. However, we show that a quantum antiferromagnetic Ising chain in a staggered field can exhibit a first-order transition with only an algebraically small gap. In addition, we construct a simple classical translationally invariant one-dimensional Hamiltonian containing nearest-neighbor interactions only, which exhibits an exponential gap at a thermodynamic quantum first-order transition of essentially topological origin. This establishes that (i) the QAA can be successful even across first-order transitions but also that (ii) it can fail on exceedingly simple problems readily solved by inspection, or by classical annealing.