Quenching and annealing are extreme opposites in the time evolution of a quantum system: Annealing explores equilibrium phases of a Hamiltonian with slowly changing parameters and can be exploited as a tool for solving complex optimization problems. In contrast, quenches are sudden changes of the Hamiltonian, producing a non-equilibrium situation in which dynamical phase transitions can occur. Here, we investigate the relation between the two cases. Specifically, we show that the minimum of the annealing gap, which is an important bottleneck of quantum annealing algorithms, can be revealed from the order parameter which describes the dynamical quantum phase transition after the quench. Combined with statistical tools including the training of a neural network, the relation between quench and annealing dynamics can be exploited to reproduce the full functional behavior of the annealing gap from the quench data. We show that the partial or full knowledge about the annealing gap which can be gained in this way can be used to design optimized quantum annealing protocols with a practical time-to-solution benefit. Our results are obtained from simulating random Ising Hamiltonians, representing hard-to-solve instances of the exact cover problem.Quenching and annealing are extreme opposites in the time evolution of a quantum system: Annealing explores equilibrium phases of a Hamiltonian with slowly changing parameters and can be exploited as a tool for solving complex optimization problems. In contrast, quenches are sudden changes of the Hamiltonian, producing a non-equilibrium situation in which dynamical phase transitions can occur. Here, we investigate the relation between the two cases. Specifically, we show that the minimum of the annealing gap, which is an important bottleneck of quantum annealing algorithms, can be revealed from the order parameter which describes the dynamical quantum phase transition after the quench. Combined with statistical tools including the training of a neural network, the relation between quench and annealing dynamics can be exploited to reproduce the full functional behavior of the annealing gap from the quench data. We show that the partial or full knowledge about the annealing gap which can be gained in this way can be used to design optimized quantum annealing protocols with a practical time-to-solution benefit. Our results are obtained from simulating random Ising Hamiltonians, representing hard-to-solve instances of the exact cover problem.

Jun 15, 20210 citations

Energetic Perspective on Rapid Quenches in Quantum Annealing

Adam Callison, Max Z. Festenstein, Jie Chen +3 more

There are well-developed theoretical tools to analyze how quantum dynamics can solve computational problems by varying Hamiltonian parameters slowly, near the adiabatic limit.On the other hand, there are relatively few tools to understand the opposite limit of rapid quenches, as used in quantum annealing and (in the limit of infinitely rapid quenches) in quantum walks.In this paper, we develop several tools that are applicable in the rapid-quench regime.Firstly, we analyze the energy expectation value of different elements of the Hamiltonian.From this, we show that monotonic quenches, where the strength of the problem Hamiltonian is consistently increased relative to fluctuation (driver) terms, will yield a better result on average than random guessing.Secondly, we develop methods to determine whether dynamics will occur locally under rapid-quench Hamiltonians and identify cases where a rapid quench will lead to a substantially improved solution.In particular, we find that a technique we refer to as "preannealing" can significantly improve the performance of quantum walks.We also show how these tools can provide efficient heuristic estimates for Hamiltonian parameters, a key requirement for practical application of quantum annealing.There are well-developed theoretical tools to analyze how quantum dynamics can solve computational problems by varying Hamiltonian parameters slowly, near the adiabatic limit.On the other hand, there are relatively few tools to understand the opposite limit of rapid quenches, as used in quantum annealing and (in the limit of infinitely rapid quenches) in quantum walks.In this paper, we develop several tools that are applicable in the rapid-quench regime.Firstly, we analyze the energy expectation value of different elements of the Hamiltonian.From this, we show that monotonic quenches, where the strength of the problem Hamiltonian is consistently increased relative to fluctuation (driver) terms, will yield a better result on average than random guessing.Secondly, we develop methods to determine whether dynamics will occur locally under rapid-quench Hamiltonians and identify cases where a rapid quench will lead to a substantially improved solution.In particular, we find that a technique we refer to as "preannealing" can significantly improve the performance of quantum walks.We also show how these tools can provide efficient heuristic estimates for Hamiltonian parameters, a key requirement for practical application of quantum annealing.

arXiv:2007.11599PRX QuantumMar 4, 202137 citations

Optimization by quantum annealing: Lessons from hard satisfiability problems

Demian A. Battaglia, Giuseppe E. Santoro, Erio Tosatti

The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.

arXiv:cond-mat/0502468Physical Review EJun 29, 2005107 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.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.15244Physical Review AFeb 3, 20263 citations

Distinguishing thermal versus quantum annealing using probability-flux signatures across interaction networks

Yoshiaki Horiike, Yuki Kawaguchi

Simulated annealing provides a heuristic solution to combinatorial optimization problems. The cost function of a problem is mapped onto the energy function of a physical many-body system, and, by using thermal or quantum fluctuations, the system explores the state space to find the ground state, which corresponds to the optimal solution of the problem. Studies have highlighted both the similarities and differences between thermal and quantum fluctuations. Nevertheless, fundamental understanding of thermal and quantum annealing remains incomplete, making it unclear how quantum annealing outperforms thermal annealing in which problem instances. Here, we investigate the many-body dynamics of thermal and quantum annealing by examining all possible interaction networks of $\pm J$ Ising spin systems up to seven spins. Our comprehensive investigation reveals that differences between thermal and quantum annealing emerge for particular interaction networks, indicating that the structure of the energy landscape distinguishes the two dynamics. We identify the microscopic origin of these differences through probability fluxes in state space, finding that the two dynamics are broadly similar, but that quantum tunnelling produces qualitative differences. Our results provide insight into how thermal and quantum fluctuations navigate a system toward the ground state in simulated annealing, and are experimentally verifiable in atomic, molecular, and optical systems. Furthermore, these insights may improve mappings of optimization problems to Ising spin systems, yielding more accurate solutions in faster simulated annealing and thus benefiting real-world applications in industry. Our comprehensive survey of interaction networks and visualization of probability flux can help to understand, predict, and control quantum advantage in quantum annealing.Simulated annealing provides a heuristic solution to combinatorial optimization problems. The cost function of a problem is mapped onto the energy function of a physical many-body system, and, by using thermal or quantum fluctuations, the system explores the state space to find the ground state, which corresponds to the optimal solution of the problem. Studies have highlighted both the similarities and differences between thermal and quantum fluctuations. Nevertheless, fundamental understanding of thermal and quantum annealing remains incomplete, making it unclear how quantum annealing outperforms thermal annealing in which problem instances. Here, we investigate the many-body dynamics of thermal and quantum annealing by examining all possible interaction networks of $\pm J$ Ising spin systems up to seven spins. Our comprehensive investigation reveals that differences between thermal and quantum annealing emerge for particular interaction networks, indicating that the structure of the energy landscape distinguishes the two dynamics. We identify the microscopic origin of these differences through probability fluxes in state space, finding that the two dynamics are broadly similar, but that quantum tunnelling produces qualitative differences. Our results provide insight into how thermal and quantum fluctuations navigate a system toward the ground state in simulated annealing, and are experimentally verifiable in atomic, molecular, and optical systems. Furthermore, these insights may improve mappings of optimization problems to Ising spin systems, yielding more accurate solutions in faster simulated annealing and thus benefiting real-world applications in industry. Our comprehensive survey of interaction networks and visualization of probability flux can help to understand, predict, and control quantum advantage in quantum annealing.

cond-mat.stat-mechCross-listedarXiv:2511.16457Nov 21, 20250 citations

Steered quantum annealing: improving time efficiency with partial information

Ana Palacios de Luis, Artur García-Sáez, Marta P. Estarellas

In the computational model of quantum annealing, the size of the minimum gap between the ground state and the first excited state of the system is of particular importance, since it is inversely proportional to the running time of the algorithm. Thus, it is desirable to keep the gap as large as possible during the annealing process, since it allows the computation to remain under the protection of the adiabatic theorem while staying efficient. We propose steered quantum annealing as a new method to enlarge the gap throughout the process, in the case of diagonal final Hamiltonians, based on the exploitation of some assumptions we can make about the particular problem instance. In order to introduce this information, we propose beginning the anneal from a biased Hamiltonian that incorporates reliable assumptions about the final ground state. Our simulations show that this method yields a larger average gap throughout the whole computation, which results in an increased robustness of the overall annealing process.In the computational model of quantum annealing, the size of the minimum gap between the ground state and the first excited state of the system is of particular importance, since it is inversely proportional to the running time of the algorithm. Thus, it is desirable to keep the gap as large as possible during the annealing process, since it allows the computation to remain under the protection of the adiabatic theorem while staying efficient. We propose steered quantum annealing as a new method to enlarge the gap throughout the process, in the case of diagonal final Hamiltonians, based on the exploitation of some assumptions we can make about the particular problem instance. In order to introduce this information, we propose beginning the anneal from a biased Hamiltonian that incorporates reliable assumptions about the final ground state. Our simulations show that this method yields a larger average gap throughout the whole computation, which results in an increased robustness of the overall annealing process.

arXiv:2206.07646Jun 15, 20220 citations

\pm J

Ising spin systems up to seven spins. Our comprehensive investigation reveals that differences between thermal and quantum annealing emerge for particular interaction networks, indicating that the structure of the energy landscape distinguishes the two dynamics. We identify the microscopic origin of these differences through probability fluxes in state space, finding that the two dynamics are broadly similar, but that quantum tunnelling produces qualitative differences. Our results provide insight into how thermal and quantum fluctuations navigate a system toward the ground state in simulated annealing, and are experimentally verifiable in atomic, molecular, and optical systems. Furthermore, these insights may improve mappings of optimization problems to Ising spin systems, yielding more accurate solutions in faster simulated annealing and thus benefiting real-world applications in industry. Our comprehensive survey of interaction networks and visualization of probability flux can help to understand, predict, and control quantum advantage in quantum annealing.