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

Quantum speedup at zero temperature via coherent catalysis

Gabriel A. Durkin

Published Mar 12, 2019• 18 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.99.032315

Related papers

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

Yang Wei Koh, Hidetoshi Nishimori

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.

arXiv:1912.11952•Physical Review A•May 4, 2020•1 citation

Speedup of the quantum adiabatic algorithm using delocalization catalysis

Chenfeng Cao, Jian Xue, Nic Shannon +1 more

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.

arXiv:2007.11212•Physical Review Research•Jan 29, 2021•17 citations

Quantum Catalysis of Magnetic Phase Transitions in a Quantum Simulator

Philip Richerme, Crystal Senko, S. É. Korenblit +5 more

We control quantum fluctuations to create the ground state magnetic phases of a classical Ising model with a tunable longitudinal magnetic field using a system of 6 to 10 atomic ion spins. Because of the long-range Ising interactions, the various ground state spin configurations are separated by multiple first-order phase transitions, which in our zero temperature system cannot be driven by thermal fluctuations. We instead use a transverse magnetic field as a quantum catalyst to observe the first steps of the complete fractal devil's staircase, which emerges in the thermodynamic limit and can be mapped to a large number of many-body and energy-optimization problems.

arXiv:1303.6983•Physical Review Letters•Sep 5, 2013•40 citations

Two-parameter counter-diabatic driving in quantum annealing

Luise Prielinger, Andreas Hartmann, Yu Yamashiro +3 more

We introduce a two-parameter approximate counter-diabatic term into the Hamiltonian of the transversefield Ising model for quantum annealing to accelerate convergence to the solution, generalizing an existing single-parameter approach.The protocol is equivalent to unconventional diabatic control of the longitudinal and transverse fields in the transverse-field Ising model and thus makes it more feasible for experimental realization than an introduction of new terms such as nonstoquastic catalysts toward the same goal of performance enhancement.We test the idea for the p-spin model with p = 3, which has a first-order quantum phase transition, and show that our two-parameter approach leads to significantly larger ground-state fidelity and lower residual energy than those by traditional quantum annealing and by the single-parameter method.We also find a scaling advantage in terms of the time-to-solution as a function of the system size in a certain range of parameters as compared to the traditional methods in the sense that an exponential time complexity is reduced to another exponential complexity with a smaller coefficient.Although the present method may not always lead to a drastic exponential speedup in difficult optimization problems, it is useful because of its versatility and applicability for any problem after a simple algebraic manipulation, in contrast to some other powerful prescriptions for acceleration such as nonstoquastic catalysts in which one should carefully study in advance if it works in a given problem and should identify a proper way to meticulously control the system parameters to achieve the goal, which is generally highly nontrivial.

arXiv:2011.02691•Physical Review Research•Mar 9, 2021•45 citations

Exponential Quantum Speedup on Structured Hard Instances of Maximum Independent Set

Vicky Choi

Establishing quantum speedup for computationally hard problems of practical relevance, particularly combinatorial optimization problems, remains a central challenge in quantum computation. In this work, we identify a structurally defined family of classically hard maximum independent set (MIS) instances, and design and analyze a non-stoquastic adiabatic quantum optimization algorithm that exploits this structure. The algorithm runs in polynomial time and achieves an exponential speedup over both transverse-field quantum annealing and state-of-the-art classical solvers on these instances, under assumptions supported by analytical and numerical evidence. We identify the essential quantum mechanism enabling the speedup as the use of a non-stoquastic XX-driver to access a larger sign-structured admissible subspace beyond the stoquastic regime, which allows sign-generating quantum interference to create smooth evolution paths that bypass tunneling. This identifies a distinctive quantum mechanism underlying the speedup and explains why no efficient classical analogue is likely to exist. In addition, our analysis produces scalable small-scale models, derived from our structural reduction, that capture the essential dynamics of the algorithm. These models provide a concrete opportunity for verification of the quantum advantage mechanism on currently available universal quantum computers.

quant-pharXiv:2601.17686•Jan 27, 2026•1 citation

Universal scaling of finite-temperature quantum adiabaticity in driven many-body systems

Li-Ying Chou, Jyong-Hao Chen

Establishing quantitative adiabaticity criteria at finite temperature remains substantially less developed than in the pure-state setting, even though realistic quantum systems are never at absolute zero. Here, by combining a mixed-state quantum speed limit with mixed-state fidelity susceptibility within the Liouville-space formulation of quantum mechanics, we derive rigorous bounds on the Hilbert-Schmidt fidelity between mixed states. Focusing on protocols that drive an initial Gibbs state toward a quasi-Gibbs target, these bounds yield an explicit threshold driving rate for the onset of nonadiabaticity. For a broad class of local Hamiltonians in gapped phases, we show that, in the thermodynamic limit, the threshold driving rate factorizes into a system-size contribution that recovers the zero-temperature scaling and a universal temperature-dependent factor. The latter is exponentially close to unity at low temperature, whereas at high temperature it is linear in temperature. We verify the predicted scaling in several spin-1/2 chains by obtaining closed-form expressions for the threshold driving rate. Our results provide a practical and largely model-independent criterion for finite-temperature adiabaticity in driven many-body systems under closed-system unitary evolution.

quant-pharXiv:2602.01943•Feb 3, 2026•1 citation
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.
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.
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.
We control quantum fluctuations to create the ground state magnetic phases of a classical Ising model with a tunable longitudinal magnetic field using a system of 6 to 10 atomic ion spins. Because of the long-range Ising interactions, the various ground state spin configurations are separated by multiple first-order phase transitions, which in our zero temperature system cannot be driven by thermal fluctuations. We instead use a transverse magnetic field as a quantum catalyst to observe the first steps of the complete fractal devil's staircase, which emerges in the thermodynamic limit and can be mapped to a large number of many-body and energy-optimization problems.
We introduce a two-parameter approximate counter-diabatic term into the Hamiltonian of the transversefield Ising model for quantum annealing to accelerate convergence to the solution, generalizing an existing single-parameter approach.The protocol is equivalent to unconventional diabatic control of the longitudinal and transverse fields in the transverse-field Ising model and thus makes it more feasible for experimental realization than an introduction of new terms such as nonstoquastic catalysts toward the same goal of performance enhancement.We test the idea for the p-spin model with p = 3, which has a first-order quantum phase transition, and show that our two-parameter approach leads to significantly larger ground-state fidelity and lower residual energy than those by traditional quantum annealing and by the single-parameter method.We also find a scaling advantage in terms of the time-to-solution as a function of the system size in a certain range of parameters as compared to the traditional methods in the sense that an exponential time complexity is reduced to another exponential complexity with a smaller coefficient.Although the present method may not always lead to a drastic exponential speedup in difficult optimization problems, it is useful because of its versatility and applicability for any problem after a simple algebraic manipulation, in contrast to some other powerful prescriptions for acceleration such as nonstoquastic catalysts in which one should carefully study in advance if it works in a given problem and should identify a proper way to meticulously control the system parameters to achieve the goal, which is generally highly nontrivial.
Establishing quantum speedup for computationally hard problems of practical relevance, particularly combinatorial optimization problems, remains a central challenge in quantum computation. In this work, we identify a structurally defined family of classically hard maximum independent set (MIS) instances, and design and analyze a non-stoquastic adiabatic quantum optimization algorithm that exploits this structure. The algorithm runs in polynomial time and achieves an exponential speedup over both transverse-field quantum annealing and state-of-the-art classical solvers on these instances, under assumptions supported by analytical and numerical evidence. We identify the essential quantum mechanism enabling the speedup as the use of a non-stoquastic XX-driver to access a larger sign-structured admissible subspace beyond the stoquastic regime, which allows sign-generating quantum interference to create smooth evolution paths that bypass tunneling. This identifies a distinctive quantum mechanism underlying the speedup and explains why no efficient classical analogue is likely to exist. In addition, our analysis produces scalable small-scale models, derived from our structural reduction, that capture the essential dynamics of the algorithm. These models provide a concrete opportunity for verification of the quantum advantage mechanism on currently available universal quantum computers.
Establishing quantitative adiabaticity criteria at finite temperature remains substantially less developed than in the pure-state setting, even though realistic quantum systems are never at absolute zero. Here, by combining a mixed-state quantum speed limit with mixed-state fidelity susceptibility within the Liouville-space formulation of quantum mechanics, we derive rigorous bounds on the Hilbert-Schmidt fidelity between mixed states. Focusing on protocols that drive an initial Gibbs state toward a quasi-Gibbs target, these bounds yield an explicit threshold driving rate for the onset of nonadiabaticity. For a broad class of local Hamiltonians in gapped phases, we show that, in the thermodynamic limit, the threshold driving rate factorizes into a system-size contribution that recovers the zero-temperature scaling and a universal temperature-dependent factor. The latter is exponentially close to unity at low temperature, whereas at high temperature it is linear in temperature. We verify the predicted scaling in several spin-1/2 chains by obtaining closed-form expressions for the threshold driving rate. Our results provide a practical and largely model-independent criterion for finite-temperature adiabaticity in driven many-body systems under closed-system unitary evolution.