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:1912.11952 · Physical Review A

Reduction of energy-gap scaling by coherent catalysis in models of quantum annealing

Yang Wei Koh, Hidetoshi Nishimori

Published May 4, 2020• 1 citation
arXivHTMLPDF

Abstract

Nonstoquastic drivers are known to improve the performance of quantum annealing by reducing first-order phase transitions into second-order ones in several mean-field-type model systems. Nevertheless, statistical-mechanical analysis shows that some target Hamiltonians still exhibit unavoidable first-order transitions even with nonstoquastic drivers, making them difficult for quantum annealing to solve. Recently, a mechanism called coherent catalysis was proposed by Durkin [Phys. Rev. A 99, 032315 (2019)], in which he showed the existence of a particular point on the line of first-order phase transitions where the energy gap scales polynomially as expected for a second-order transition. We show by extensive numerical computations that this phenomenon is observed in a few additional mean-field-type optimization problems where nonstoquastic drivers fail to change the order of phase transition in the thermodynamic limit. This opens up the possibility of using coherent catalysis to search for exponential speedups in systems previously thought to be exponentially slow for quantum annealing to solve.

DOI
10.1103/physreva.101.052304

Related papers

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

Nonstoquastic catalyst for bifurcation-based quantum annealing of the ferromagnetic p -spin model

Yuki Susa, Takashi Imoto, Yuichiro Matsuzaki

Introducing a nonstoquastic catalyst is a promising avenue to improve quantum annealing with the transverse field. In the present paper, we propose a nonstoquastic catalyst for bifurcation-based quantum annealing described by the spin-1 operators to improve the efficiency of a ground-state search. To investigate the effect of the nonstoquastic catalyst, we study the ferromagnetic $p$-spin model, which has difficulty with finding the ground state due to the first-order phase transition for quantum annealing. A semiclassical analysis shows that the problematic first-order phase transition can be eliminated by introducing the proposed nonstoquastic catalyst with the appropriate amplitude. We also numerically calculate the minimum energy gap for a finite-size system by diagonalizing the Hamiltonian. We find that while the energy gap decreases exponentially with increasing system size for the original Hamiltonian, it decreases polynomially against the system size for the Hamiltonian with the nonstoquastic catalyst. This result implies that the proposed nonstoquastic catalyst has the potential to improve the performance of bifurcation-based quantum annealing.

arXiv:2209.01737•Physical Review A•May 1, 2023•8 citations

Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field

Yuki Susa, Yu Yamashiro, Masayuki Yamamoto +1 more

We show, for quantum annealing, that a certain type of inhomogeneous driving of the transverse field erases first-order quantum phase transitions in the p-body interacting mean-field-type model with and without longitudinal random field. Since a first-order phase transition poses a serious difficulty for quantum annealing (adiabatic quantum computing) due to the exponentially small energy gap, the removal of first-order transitions means an exponential speedup of the annealing process. The present method may serve as a simple protocol for the performance enhancement of quantum annealing, complementary to non-stoquastic Hamiltonians.

arXiv:1801.02005•Journal of the Physical Society of Japan•Jan 17, 2018•76 citations

Energy gaps in quantum first-order mean-field–like transitions: The problems that quantum annealing cannot solve

Thomas Jörg, Florent Krząkała, Jorge Kurchan +2 more

We study first-order quantum phase transitions in models where the mean-field treatment is exact, and in particular the exponentially fast closure of the energy gap with the system size at the transition. We consider exactly solvable ferromagnetic models, and show that they reduce to the Grover problem in a particular limit. We compute the coefficient in the exponential closure of the gap using an instantonic approach, and discuss the (dire) consequences for quantum annealing.

arXiv:0912.4865•Europhysics Letters (EPL)•Feb 1, 2010•129 citations

Enhancement of quantum annealing via n -local catalysts

Roopayan Ghosh, Luca A. Nutricati, Natasha Feinstein +2 more

The potential quantum speedup in solving optimization problems via adiabatic quantum annealing is often hindered by the closing of the energy gap during the anneal, especially when this gap scales exponentially with system size. In this work, we alleviate this bottleneck by demonstrating that for the NP-complete Maximum Weighted Independent Set (MWIS) problem, an informed choice of n -local catalysts (operators involving n qubits) can reopen the gap during the annealing process. By analyzing first-order phase transitions in toy instances of the MWIS problem, we first identify direct-tunneling catalysts that effectively eliminate the transition and provide an analytical discussion on when the sign of the catalyst influences its impact. We then reveal that n -local catalysts exponentially improve gap scaling and in certain scenarios are as effective as direct-tunnel coupling between two minima. Utilizing this understanding, we show that they also increase the efficiency of ground-state preparation via adiabatic quantum annealing in random graphs and analytically demonstrate the necessity of their placement across unfrustrated loops in the graph for effective performance in MWIS problems. Additionally, using a circuit implementation of the n -local catalyst (requiring 2 n nearest-neighbor gates), we demonstrate that both the circuit depth and the total number of gates required to solve the problem are reduced by several orders of magnitude when compared to the discrete-time version of traditional quantum annealing using local drivers. Our analysis suggests that nonlocal quantum fluctuations entangling multiple qubits as a catalyst are key to achieving the desired quantum advantage.

arXiv:2409.13029•Physical Review Research•Feb 9, 2026•19 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
Nonstoquastic drivers are known to improve the performance of quantum annealing by reducing first-order phase transitions into second-order ones in several mean-field-type model systems. Nevertheless, statistical-mechanical analysis shows that some target Hamiltonians still exhibit unavoidable first-order transitions even with nonstoquastic drivers, making them difficult for quantum annealing to solve. Recently, a mechanism called coherent catalysis was proposed by Durkin [Phys. Rev. A 99, 032315 (2019)], in which he showed the existence of a particular point on the line of first-order phase transitions where the energy gap scales polynomially as expected for a second-order transition. We show by extensive numerical computations that this phenomenon is observed in a few additional mean-field-type optimization problems where nonstoquastic drivers fail to change the order of phase transition in the thermodynamic limit. This opens up the possibility of using coherent catalysis to search for exponential speedups in systems previously thought to be exponentially slow for quantum annealing to solve.
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.
Introducing a nonstoquastic catalyst is a promising avenue to improve quantum annealing with the transverse field. In the present paper, we propose a nonstoquastic catalyst for bifurcation-based quantum annealing described by the spin-1 operators to improve the efficiency of a ground-state search. To investigate the effect of the nonstoquastic catalyst, we study the ferromagnetic ppp-spin model, which has difficulty with finding the ground state due to the first-order phase transition for quantum annealing. A semiclassical analysis shows that the problematic first-order phase transition can be eliminated by introducing the proposed nonstoquastic catalyst with the appropriate amplitude. We also numerically calculate the minimum energy gap for a finite-size system by diagonalizing the Hamiltonian. We find that while the energy gap decreases exponentially with increasing system size for the original Hamiltonian, it decreases polynomially against the system size for the Hamiltonian with the nonstoquastic catalyst. This result implies that the proposed nonstoquastic catalyst has the potential to improve the performance of bifurcation-based quantum annealing.
We show, for quantum annealing, that a certain type of inhomogeneous driving of the transverse field erases first-order quantum phase transitions in the p-body interacting mean-field-type model with and without longitudinal random field. Since a first-order phase transition poses a serious difficulty for quantum annealing (adiabatic quantum computing) due to the exponentially small energy gap, the removal of first-order transitions means an exponential speedup of the annealing process. The present method may serve as a simple protocol for the performance enhancement of quantum annealing, complementary to non-stoquastic Hamiltonians.
The potential quantum speedup in solving optimization problems via adiabatic quantum annealing is often hindered by the closing of the energy gap during the anneal, especially when this gap scales exponentially with system size. In this work, we alleviate this bottleneck by demonstrating that for the NP-complete Maximum Weighted Independent Set (MWIS) problem, an informed choice of n -local catalysts (operators involving n qubits) can reopen the gap during the annealing process. By analyzing first-order phase transitions in toy instances of the MWIS problem, we first identify direct-tunneling catalysts that effectively eliminate the transition and provide an analytical discussion on when the sign of the catalyst influences its impact. We then reveal that n -local catalysts exponentially improve gap scaling and in certain scenarios are as effective as direct-tunnel coupling between two minima. Utilizing this understanding, we show that they also increase the efficiency of ground-state preparation via adiabatic quantum annealing in random graphs and analytically demonstrate the necessity of their placement across unfrustrated loops in the graph for effective performance in MWIS problems. Additionally, using a circuit implementation of the n -local catalyst (requiring 2 n nearest-neighbor gates), we demonstrate that both the circuit depth and the total number of gates required to solve the problem are reduced by several orders of magnitude when compared to the discrete-time version of traditional quantum annealing using local drivers. Our analysis suggests that nonlocal quantum fluctuations entangling multiple qubits as a catalyst are key to achieving the desired quantum advantage.
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.