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:2301.10427 · Journal of the Physical Society of Japan

Eigenvalue-Invariant Transformation of Ising Problem for Anti-Crossing Mitigation in Quantum Annealing

Tôru Fujii, Koshi Komuro, Yosuke Okudaira, Masayasu Sawada

Published Mar 2, 2023• 6 citations
arXivHTMLPDF

Abstract

We have proposed the energy landscape transformation of Ising problems (ELTIP), which changes the combination of the state and eigenvalue without changing all the original eigenvalues [arXiv:2202.05927]. We study how the ELTIP affects the anti-crossing between two levels of the ground and first excited states during quantum annealing. We use a 5-spin maximum-weighted independent set for the problem to numerically investigate the anticrossing. For comparison, we introduce a non-stoquastic Hamiltonian that adds antiferromagnetic interaction to the normal transverse magnetic field. Annealing with the non-stoquastic Hamiltonian is effective for difficult problems. The non-stoquastic Hamiltonian mitigates the anti-crossing when only the energy gap between the ground state and the first excited state of the final state is small. When the ELTIP is used, the anti-crossing disappears. For the problems investigated in this paper, the ELTIP shortens the annealing time to guarantee adiabatic change more than the non-stoquastic Hamiltonian.

DOI
10.7566/jpsj.92.044001

Related papers

Energy landscape transformation of Ising problem with invariant eigenvalues for quantum annealing

Toru Fujii, Koshi Komuro, Yosuke Okudaira +2 more

Quantum annealing tends to be more difficult as the energy landscape of the problem becomes complicated with many local minima. We have found a transformation for changing the energy landscape that swaps the eigenvalues and paired states without changing the eigenvalues of the instance at all. The transformation is basically a partial recombination of the two-spin interaction coefficient Jij and the longitudinal magnetic field interaction coefficient hi. The Hamming distance corresponding to a barrier between the states changes by the transformation, which in turn affects the ground state convergence. In the quantum annealing simulation results of a small number of spin instances, the annealing time was shortened by several orders of magnitude by applying the transformation. In addition, we also obtained a result using a D-Wave quantum annealer, which also showed a big improvement in the ground state convergence.

arXiv:2202.05927•Feb 11, 2022•0 citations

Static and Dynamic Analysis of Energy Landscape Transformation of the Ising Problems

Hiroki Kanai, Shu Tanaka

Ising machines are promising next-generation computers that aim to efficiently obtain good solutions to combinatorial optimization problems, which are converted to the Ising model. To obtain the ground state of the Ising model with high accuracy, tuning the hyperparameters in the Ising model is of great importance. Recently, a new method called Energy Landscape Transformation of Ising Problems (ELTIP) has been proposed which does not change any of the original eigenenergies at all. The previous study demonstrated that the Time-to-Solution (TTS) of Quantum Annealing (QA) decreases for the specific problems after ELTIP. We reveal the scope of the problems where ELTIP can be sufficiently beneficial. To this end, we analyze the correlation between the mean Hamming distance and the ground state probability in both the static and dynamic analysis.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•0 citations

Limitation of Stoquastic Quantum Annealing: A Structural Perspective

Vicky Choi

We analyze the behavior of stoquastic transverse-field quantum annealing (TFQA) on a structured class of Maximum Independent Set (MIS) instances, using the same decomposition framework developed in our companion work on the DIC-DAC-DOA algorithm (Beyond Stoquasticity). For these instances, we provide a structural explanation for the anti-crossing arising from the competition between the energies associated with a set of degenerate local minima (LM) and the global minimum (GM), and analytically derive the associated exponentially small gap. Our analysis proceeds in two steps. First, we reduce the dynamics to an effective two-block Hamiltonian $H_{core}$, constructed from the bare (decoupled) subsystems associated with the LM and GM. This reduction is justified analytically using the structural decomposition. Second, we reformulate the eigenvalue problem as a generalized eigenvalue problem in a non-orthogonal basis constructed from the bare eigenstates of the subsystems. This transformation enables a clean perturbative treatment of the anti-crossing structure, independent of the transverse field, unlike standard perturbation theory approach, which requires treating the transverse field as a small parameter. This paper serves as a supplementary companion to our main work on the DIC-DAC-DOA algorithm, where we demonstrate how appropriately designed non-stoquastic drivers can bypass this tunneling-induced bottleneck.

arXiv:2509.16265•Sep 18, 2025•0 citations

Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stoquastic Hamiltonians

Hidetoshi Nishimori, Kabuki Takada

Non-stoquastic Hamiltonians have both positive and negative signs in off-diagonal elements in their matrix representation in the standard computational basis and thus cannot be simulated efficiently by the standard quantum Monte Carlo method due to the sign problem. We describe our analytical studies of this type of Hamiltonians with infinite-range non-random as well as random interactions from the perspective of possible enhancement of the efficiency of quantum annealing or adiabatic quantum computing. It is shown that multi-body transverse interactions like XX and XXXXX with positive coefficients appended to a stoquastic transverse-field Ising model render the Hamiltonian non-stoquastic and reduce a first-order quantum phase transition in the simple transverse-field case to a second-order transition. This implies that the efficiency of quantum annealing is exponentially enhanced, because a first-order transition has an exponentially small energy gap (and therefore exponentially long computation time) whereas a second-order transition has a polynomially decaying gap (polynomial computation time). The examples presented here represent rare instances where strong quantum effects, in the sense that they cannot be efficiently simulated in the standard quantum Monte Carlo, have analytically been shown to exponentially enhance the efficiency of quantum annealing for combinatorial optimization problems.

arXiv:1609.03785•Frontiers in ICT•Feb 17, 2017•97 citations

Best Annealing Path of Quantum Annealing via Efficient Adiabatic Phase Transition

Kiyotaka Murashima

Quantum Annealing (QA) has already put into practical use and considered useful for solving many social issues, such as reduction of traffic congestion and delivery optimization. But in QA, when the energy difference between the ground state and the first excited state is small, the transition probability between them increases. Therefore, in order to decrease the transition, QA has to be performed at extremely low temperatures. To simulate the situation, it has the problem in that it takes much time. Many studies are underway to accelerate QA theoretically, one of which is to incorporate non-stoquastic Hamiltonian. On the other hand, I proposed Nested Simulated Annealing (NSA) inspired by Quantum Monte Carlo (QMC). I showed the computational speedup could be achieved dramatically, by considering the idea that the effect of flipping a spin preferentially influenced the spins directly interacting with it. Although NSA was based on such classical concept of causality, the hybrid computation both quantum and classical approach worked well. In this paper, in order to discuss the relationship between NSA and non-stoquastic Hamiltonian like XX-interaction, the spins are treated as continuous variables. I derive the formula to calculate the total energy in both with a problem Hamiltonian and the perturbation Hamiltonian induced by a transverse electromagnetic field. And I will show a clear relationship between local-maxima and the convergence speed when calculating it with the binary spin. More precisely, the annealing path with the smallest local-maxima converges fast, even though it consumes fewer computational resources. Therefore, it is possible to induce an optimal adiabatic phase transition by selecting NSA parameters appropriately. This paper shows an effective method to choose the parameters when simulating QMC on a classical computer.

quant-pharXiv:2608.30282•Sep 1, 2026•0 citations

Essentiality of the Non-stoquastic Hamiltonians and Driver Graph Design in Quantum Optimization Annealing

Vicky Choi

One of the distinct features of quantum mechanics is that the probability amplitude can have both positive and negative signs, which has no classical counterpart as the classical probability must be positive. Consequently, one possible way to achieve quantum speedup is to explicitly harness this feature. Unlike a stoquastic Hamiltonian whose ground state has only positive amplitudes (with respect to the computational basis), a non-stoquastic Hamiltonian can be eventually stoquastic or properly non-stoquastic when its ground state has both positive and negative amplitudes. In this paper, we describe that, for some hard instances which are characterized by the presence of an anti-crossing (AC) in a transverse-field quantum annealing (QA) algorithm, how to design an appropriate XX-driver graph (without knowing the prior problem structure) with an appropriate XX-coupler strength such that the resulting non-stoquastic QA algorithm is proper-non-stoquastic with two bridged anti-crossings (a double-AC) where the spectral gap between the first and second level is large enough such that the system can be operated diabatically in polynomial time. The speedup is exponential in the original AC-distance, which can be sub-exponential or exponential in the system size, over the stoquastic QA algorithm, and possibly the same order of speedup over the state-of-the-art classical algorithms in optimization. This work is developed based on the novel characterizations of a modified and generalized parametrization definition of an anti-crossing in the context of quantum optimization annealing introduced in [4].

arXiv:2105.02110•May 5, 2021•4 citations
We have proposed the energy landscape transformation of Ising problems (ELTIP), which changes the combination of the state and eigenvalue without changing all the original eigenvalues [arXiv:2202.05927]. We study how the ELTIP affects the anti-crossing between two levels of the ground and first excited states during quantum annealing. We use a 5-spin maximum-weighted independent set for the problem to numerically investigate the anticrossing. For comparison, we introduce a non-stoquastic Hamiltonian that adds antiferromagnetic interaction to the normal transverse magnetic field. Annealing with the non-stoquastic Hamiltonian is effective for difficult problems. The non-stoquastic Hamiltonian mitigates the anti-crossing when only the energy gap between the ground state and the first excited state of the final state is small. When the ELTIP is used, the anti-crossing disappears. For the problems investigated in this paper, the ELTIP shortens the annealing time to guarantee adiabatic change more than the non-stoquastic Hamiltonian.
Quantum annealing tends to be more difficult as the energy landscape of the problem becomes complicated with many local minima. We have found a transformation for changing the energy landscape that swaps the eigenvalues and paired states without changing the eigenvalues of the instance at all. The transformation is basically a partial recombination of the two-spin interaction coefficient Jij and the longitudinal magnetic field interaction coefficient hi. The Hamming distance corresponding to a barrier between the states changes by the transformation, which in turn affects the ground state convergence. In the quantum annealing simulation results of a small number of spin instances, the annealing time was shortened by several orders of magnitude by applying the transformation. In addition, we also obtained a result using a D-Wave quantum annealer, which also showed a big improvement in the ground state convergence.
Ising machines are promising next-generation computers that aim to efficiently obtain good solutions to combinatorial optimization problems, which are converted to the Ising model. To obtain the ground state of the Ising model with high accuracy, tuning the hyperparameters in the Ising model is of great importance. Recently, a new method called Energy Landscape Transformation of Ising Problems (ELTIP) has been proposed which does not change any of the original eigenenergies at all. The previous study demonstrated that the Time-to-Solution (TTS) of Quantum Annealing (QA) decreases for the specific problems after ELTIP. We reveal the scope of the problems where ELTIP can be sufficiently beneficial. To this end, we analyze the correlation between the mean Hamming distance and the ground state probability in both the static and dynamic analysis.
We analyze the behavior of stoquastic transverse-field quantum annealing (TFQA) on a structured class of Maximum Independent Set (MIS) instances, using the same decomposition framework developed in our companion work on the DIC-DAC-DOA algorithm (Beyond Stoquasticity). For these instances, we provide a structural explanation for the anti-crossing arising from the competition between the energies associated with a set of degenerate local minima (LM) and the global minimum (GM), and analytically derive the associated exponentially small gap. Our analysis proceeds in two steps. First, we reduce the dynamics to an effective two-block Hamiltonian HcoreH_{core}Hcore​, constructed from the bare (decoupled) subsystems associated with the LM and GM. This reduction is justified analytically using the structural decomposition. Second, we reformulate the eigenvalue problem as a generalized eigenvalue problem in a non-orthogonal basis constructed from the bare eigenstates of the subsystems. This transformation enables a clean perturbative treatment of the anti-crossing structure, independent of the transverse field, unlike standard perturbation theory approach, which requires treating the transverse field as a small parameter. This paper serves as a supplementary companion to our main work on the DIC-DAC-DOA algorithm, where we demonstrate how appropriately designed non-stoquastic drivers can bypass this tunneling-induced bottleneck.
Non-stoquastic Hamiltonians have both positive and negative signs in off-diagonal elements in their matrix representation in the standard computational basis and thus cannot be simulated efficiently by the standard quantum Monte Carlo method due to the sign problem. We describe our analytical studies of this type of Hamiltonians with infinite-range non-random as well as random interactions from the perspective of possible enhancement of the efficiency of quantum annealing or adiabatic quantum computing. It is shown that multi-body transverse interactions like XX and XXXXX with positive coefficients appended to a stoquastic transverse-field Ising model render the Hamiltonian non-stoquastic and reduce a first-order quantum phase transition in the simple transverse-field case to a second-order transition. This implies that the efficiency of quantum annealing is exponentially enhanced, because a first-order transition has an exponentially small energy gap (and therefore exponentially long computation time) whereas a second-order transition has a polynomially decaying gap (polynomial computation time). The examples presented here represent rare instances where strong quantum effects, in the sense that they cannot be efficiently simulated in the standard quantum Monte Carlo, have analytically been shown to exponentially enhance the efficiency of quantum annealing for combinatorial optimization problems.
Quantum Annealing (QA) has already put into practical use and considered useful for solving many social issues, such as reduction of traffic congestion and delivery optimization. But in QA, when the energy difference between the ground state and the first excited state is small, the transition probability between them increases. Therefore, in order to decrease the transition, QA has to be performed at extremely low temperatures. To simulate the situation, it has the problem in that it takes much time. Many studies are underway to accelerate QA theoretically, one of which is to incorporate non-stoquastic Hamiltonian. On the other hand, I proposed Nested Simulated Annealing (NSA) inspired by Quantum Monte Carlo (QMC). I showed the computational speedup could be achieved dramatically, by considering the idea that the effect of flipping a spin preferentially influenced the spins directly interacting with it. Although NSA was based on such classical concept of causality, the hybrid computation both quantum and classical approach worked well. In this paper, in order to discuss the relationship between NSA and non-stoquastic Hamiltonian like XX-interaction, the spins are treated as continuous variables. I derive the formula to calculate the total energy in both with a problem Hamiltonian and the perturbation Hamiltonian induced by a transverse electromagnetic field. And I will show a clear relationship between local-maxima and the convergence speed when calculating it with the binary spin. More precisely, the annealing path with the smallest local-maxima converges fast, even though it consumes fewer computational resources. Therefore, it is possible to induce an optimal adiabatic phase transition by selecting NSA parameters appropriately. This paper shows an effective method to choose the parameters when simulating QMC on a classical computer.
One of the distinct features of quantum mechanics is that the probability amplitude can have both positive and negative signs, which has no classical counterpart as the classical probability must be positive. Consequently, one possible way to achieve quantum speedup is to explicitly harness this feature. Unlike a stoquastic Hamiltonian whose ground state has only positive amplitudes (with respect to the computational basis), a non-stoquastic Hamiltonian can be eventually stoquastic or properly non-stoquastic when its ground state has both positive and negative amplitudes. In this paper, we describe that, for some hard instances which are characterized by the presence of an anti-crossing (AC) in a transverse-field quantum annealing (QA) algorithm, how to design an appropriate XX-driver graph (without knowing the prior problem structure) with an appropriate XX-coupler strength such that the resulting non-stoquastic QA algorithm is proper-non-stoquastic with two bridged anti-crossings (a double-AC) where the spectral gap between the first and second level is large enough such that the system can be operated diabatically in polynomial time. The speedup is exponential in the original AC-distance, which can be sub-exponential or exponential in the system size, over the stoquastic QA algorithm, and possibly the same order of speedup over the state-of-the-art classical algorithms in optimization. This work is developed based on the novel characterizations of a modified and generalized parametrization definition of an anti-crossing in the context of quantum optimization annealing introduced in [4].