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

The roadmap of quantum many-body physics : from exact diagonalization to machine learning

Yilun Gao

The study of interacting quantum many-body systems is constrained by the exponential growth of the Hilbert space with system size, which limits both numerical simulations and theoretical understanding. This thesis explores how the interplay between disorder and interactions shapes localization and ergodicity in quantum many-body systems, using the exact diagonalization method, and how machine learning can serve as an alternative approach for studying these systems. We first investigate the many-body localization problem in a one-dimensional SU(2)-invariant random antiferromagnetic Heisenberg chain using exact and sparse matrix diagonalization methods. By analyzing energy level gap-ratio statistics, participation ratio, entanglement entropy and the entanglement spectral parameter as a function of disorder strength under di!erent random coupling distributions, we identify clear qualitative di!erences from the widely studied random field Heisenberg chain. For system sizes up to L = 24, signatures of localized behaviour are much less pronounced than in the case of the random field model. Motivated by the limitations of conventional numerical methods, we examine machine learning as a scalable paradigm for many-body physics. Using the Bose- Hubbard model in one and two dimensions as a benchmark, we test HUBBARDNET, a deep neural network architecture, by replacing standard stochastic gradient descent with adaptive moment estimation (ADAM), adjusting the learning rate for improved optimization, and introducing physics-informed output activations that can resolve extremely small wave-function amplitudes. This approach yields ground-state energy errors reduced by orders of magnitude and wave function fidelities exceeding 99%, remaining robust across four decades of interaction strength and over superfluid, Mott-insulating, and quantum chaotic regimes. Beyond energy prediction, the trained models accurately reproduce generalized inverse participation ratios and multifractal dimensions for ground and excited states, capturing localization, delocalization, and multifractality across the spectrum, with excited-state training explicitly guided by fractal dimensions that encode the multifractal properties of the wave functions.

•Oct 16, 2026•0 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.
The study of interacting quantum many-body systems is constrained by the exponential growth of the Hilbert space with system size, which limits both numerical simulations and theoretical understanding. This thesis explores how the interplay between disorder and interactions shapes localization and ergodicity in quantum many-body systems, using the exact diagonalization method, and how machine learning can serve as an alternative approach for studying these systems. We first investigate the many-body localization problem in a one-dimensional SU(2)-invariant random antiferromagnetic Heisenberg chain using exact and sparse matrix diagonalization methods. By analyzing energy level gap-ratio statistics, participation ratio, entanglement entropy and the entanglement spectral parameter as a function of disorder strength under di!erent random coupling distributions, we identify clear qualitative di!erences from the widely studied random field Heisenberg chain. For system sizes up to L = 24, signatures of localized behaviour are much less pronounced than in the case of the random field model. Motivated by the limitations of conventional numerical methods, we examine machine learning as a scalable paradigm for many-body physics. Using the Bose- Hubbard model in one and two dimensions as a benchmark, we test HUBBARDNET, a deep neural network architecture, by replacing standard stochastic gradient descent with adaptive moment estimation (ADAM), adjusting the learning rate for improved optimization, and introducing physics-informed output activations that can resolve extremely small wave-function amplitudes. This approach yields ground-state energy errors reduced by orders of magnitude and wave function fidelities exceeding 99%, remaining robust across four decades of interaction strength and over superfluid, Mott-insulating, and quantum chaotic regimes. Beyond energy prediction, the trained models accurately reproduce generalized inverse participation ratios and multifractal dimensions for ground and excited states, capturing localization, delocalization, and multifractality across the spectrum, with excited-state training explicitly guided by fractal dimensions that encode the multifractal properties of the wave functions.