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

Non-Hermitian Quantum Annealing in the Transverse Ising Model

Alexander I. Nesterov, Juan Carlos Beas Zepeda, G. P. Berman

Published Nov 14, 2012• 0 citations
OpenAlex

Abstract

We create a non-Hermitian quantum optimization algorithm to find the ground state of an Ising model with up to 1024 spins (qubits). Our approach leads to significant reduction of the annealing time. Analytic and numerical results demonstrate that the total annealing time is proportional to ln N, where N is the number of spins. This encouraging result is important for the rapid solution of NP-complete problems. Additional research is proposed for extending our dissipative algorithm to more complicated problems.

Related papers

Non-Hermitian quantum annealing in the ferromagnetic Ising model

Alexander I. Nesterov, Juan Carlos Beas Zepeda, G. P. Berman

We developed a non-Hermitian quantum optimization algorithm to find the ground state of the ferromagnetic Ising model with up to 1024 spins (qubits). Our approach leads to significant reduction of the annealing time. Analytical and numerical results demonstrate that the total annealing time is proportional to $\mathrm{ln}N$, where $N$ is the number of spins. This encouraging result is important in using classical computers in combination with quantum algorithms for the fast solutions of NP-complete problems. Additional research is proposed for extending our dissipative algorithm to more complicated problems.

arXiv:1211.3178•Physical Review A•Apr 25, 2013•10 citations

Quantum search using non-Hermitian adiabatic evolution

Alexander I. Nesterov, G. P. Berman

We propose a non-Hermitian quantum annealing algorithm which can be useful for solving complex optimization problems. We demonstrate our approach on Grover's problem [L. K. Grover, Phys. Rev. Lett. 79, 325 (1997)] of finding a marked item inside of an unsorted database. We show that the energy gap between the ground and excited states depends on the relaxation parameters and is not exponentially small. This allows a significant reduction of the searching time, which is proportional to the number of qubits. We discuss the relations between the probabilities of finding the ground state and the survival of a quantum computer in a dissipative environment, and we discuss alternate ways to solve $NP$-complete problems.

arXiv:1208.4642•Physical Review A•Nov 12, 2012•10 citations

Analytical solution for ground state estimation by a nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian

Bin Yan, Nikolai A. Sinitsyn

We point to the existence of an analytical solution to a general quantum annealing (QA) problem of finding low energy states of an arbitrary Ising spin Hamiltonian $H_I$ by implementing time evolution with a Hamiltonian $H(t)=H_I+g(t) H_t$. We will assume that the nonadiabatic annealing protocol is defined by a specific decaying coupling $g(t)$ and a specific mixing Hamiltonian $H_t$ that make the model analytically solvable arbitrarily far from the adiabatic regime. In specific cases of $H_I$, the solution shows the possibility of a considerable quantum speedup of finding the Ising ground state. We then compare predictions of our solution to results of numerical simulations and argue that the solvable QA protocol produces the optimal performance in the limit of maximal complexity of the computational problem. Our solution demonstrates for the most complex spin glasses a power-law energy relaxation with the annealing time $T$ and uncorrelated from the $H_I$ annealing schedule. This proves the possibility for spin glasses of a faster than $\sim 1/\log^{\beta} T$ energy relaxation.

•Oct 24, 2021•0 citations

On complexity of the quantum Ising model

Sergey B. Bravyi, Matthew B. Hastings

We study complexity of several problems related to the Transverse field Ising Model (TIM). First, we consider the problem of estimating the ground state energy known as the Local Hamiltonian Problem (LHP). It is shown that the LHP for TIM on degree-3 graphs is equivalent modulo polynomial reductions to the LHP for general k-local `stoquastic' Hamiltonians with any constant $k\ge 2$. This result implies that estimating the ground state energy of TIM on degree-3 graphs is a complete problem for the complexity class StoqMA - an extension of the classical class MA. As a corollary, we complete the complexity classification of 2-local Hamiltonians with a fixed set of interactions proposed recently by Cubitt and Montanaro. Secondly, we study quantum annealing algorithms for finding ground states of classical spin Hamiltonians associated with hard optimization problems. We prove that the quantum annealing with TIM Hamiltonians is equivalent modulo polynomial reductions to the quantum annealing with a certain subclass of k-local stoquastic Hamiltonians. This subclass includes all Hamiltonians representable as a sum of a k-local diagonal Hamiltonian and a 2-local stoquastic Hamiltonian.

arXiv:1410.0703•Oct 2, 2014•8 citations

Energy Extrapolation in Quantum Optimization Algorithms

Chenfeng Cao, Yunlong Yu, Zipeng Wu +3 more

Quantum annealing and the variational quantum eigensolver are two promising quantum algorithms to find the ground state of complicated Hamiltonians on near-term quantum devices. However, it is necessary to limit the evolution time or the circuit depth as much as possible since otherwise decoherence will degrade the computation. Even when this is done, there always exists a non-negligible estimation error in the ground state energy. Here we propose a scalable extrapolation approach to mitigate this error. With an appropriate regression, we can significantly improve the estimation accuracy for quantum annealing and variational quantum eigensolver for fixed quantum resources. The inference is achieved by extrapolating the annealing time to infinity or extrapolating the variance to zero. The only additional overhead is an increase in the number of measurements by a constant factor. We verified the validity of our method with the transverse-field Ising model. The method is robust to noise, and the techniques are applicable to other physics problems. Analytic derivations for the quadratic convergence feature of the residual energy in quantum annealing and the linear convergence feature of energy variance are given.

•Sep 16, 2021•1 citation

Study of Optimization Problems by Quantum Annealing

Tadashi Kadowaki

We introduce quantum fluctuations into the simulated annealing process of optimization problems, aiming at faster convergence to the optimal state. The idea is tested by the two models, the transverse Ising model and the traveling salesman problem (TSP). Adding the transverse field to the Ising model is a simple way to introduce quantum fluctuations. The strength of the transverse field is controlled as a function of time similarly to the temperature in the conventional method. TSP can be described by the Ising spin, so that we also apply the same technique to TSP. We directory solve the time-dependent Schrödinger equation for small-size systems and perform the quantum Monte Carlo simulation for large-size systems. Comparison with the results of the corresponding classical (thermal) method reveals that the quantum method leads to the ground state with much larger probability in almost all cases if we use the same annealing schedule of the control parameters. We also find that the relaxation time is quite short for quantum systems by numerical simulations. We consider this is one of the reasons why the annealing in quantum systems have a better performance of finding the optimal state in comparison with classical systems.

arXiv:quant-ph/0205020•May 5, 2002•39 citations
We create a non-Hermitian quantum optimization algorithm to find the ground state of an Ising model with up to 1024 spins (qubits). Our approach leads to significant reduction of the annealing time. Analytic and numerical results demonstrate that the total annealing time is proportional to ln N, where N is the number of spins. This encouraging result is important for the rapid solution of NP-complete problems. Additional research is proposed for extending our dissipative algorithm to more complicated problems.
We developed a non-Hermitian quantum optimization algorithm to find the ground state of the ferromagnetic Ising model with up to 1024 spins (qubits). Our approach leads to significant reduction of the annealing time. Analytical and numerical results demonstrate that the total annealing time is proportional to lnN\mathrm{ln}NlnN, where NNN is the number of spins. This encouraging result is important in using classical computers in combination with quantum algorithms for the fast solutions of NP-complete problems. Additional research is proposed for extending our dissipative algorithm to more complicated problems.
We propose a non-Hermitian quantum annealing algorithm which can be useful for solving complex optimization problems. We demonstrate our approach on Grover's problem [L. K. Grover, Phys. Rev. Lett. 79, 325 (1997)] of finding a marked item inside of an unsorted database. We show that the energy gap between the ground and excited states depends on the relaxation parameters and is not exponentially small. This allows a significant reduction of the searching time, which is proportional to the number of qubits. We discuss the relations between the probabilities of finding the ground state and the survival of a quantum computer in a dissipative environment, and we discuss alternate ways to solve NPNPNP-complete problems.
We point to the existence of an analytical solution to a general quantum annealing (QA) problem of finding low energy states of an arbitrary Ising spin Hamiltonian HIH_IHI​ by implementing time evolution with a Hamiltonian H(t)=HI+g(t)HtH(t)=H_I+g(t) H_tH(t)=HI​+g(t)Ht​. We will assume that the nonadiabatic annealing protocol is defined by a specific decaying coupling g(t)g(t)g(t) and a specific mixing Hamiltonian HtH_tHt​ that make the model analytically solvable arbitrarily far from the adiabatic regime. In specific cases of HIH_IHI​, the solution shows the possibility of a considerable quantum speedup of finding the Ising ground state. We then compare predictions of our solution to results of numerical simulations and argue that the solvable QA protocol produces the optimal performance in the limit of maximal complexity of the computational problem. Our solution demonstrates for the most complex spin glasses a power-law energy relaxation with the annealing time TTT and uncorrelated from the HIH_IHI​ annealing schedule. This proves the possibility for spin glasses of a faster than ∼1/log⁡βT\sim 1/\log^{\beta} T∼1/logβT energy relaxation.
We study complexity of several problems related to the Transverse field Ising Model (TIM). First, we consider the problem of estimating the ground state energy known as the Local Hamiltonian Problem (LHP). It is shown that the LHP for TIM on degree-3 graphs is equivalent modulo polynomial reductions to the LHP for general k-local `stoquastic' Hamiltonians with any constant k≥2k\ge 2k≥2. This result implies that estimating the ground state energy of TIM on degree-3 graphs is a complete problem for the complexity class StoqMA - an extension of the classical class MA. As a corollary, we complete the complexity classification of 2-local Hamiltonians with a fixed set of interactions proposed recently by Cubitt and Montanaro. Secondly, we study quantum annealing algorithms for finding ground states of classical spin Hamiltonians associated with hard optimization problems. We prove that the quantum annealing with TIM Hamiltonians is equivalent modulo polynomial reductions to the quantum annealing with a certain subclass of k-local stoquastic Hamiltonians. This subclass includes all Hamiltonians representable as a sum of a k-local diagonal Hamiltonian and a 2-local stoquastic Hamiltonian.
Quantum annealing and the variational quantum eigensolver are two promising quantum algorithms to find the ground state of complicated Hamiltonians on near-term quantum devices. However, it is necessary to limit the evolution time or the circuit depth as much as possible since otherwise decoherence will degrade the computation. Even when this is done, there always exists a non-negligible estimation error in the ground state energy. Here we propose a scalable extrapolation approach to mitigate this error. With an appropriate regression, we can significantly improve the estimation accuracy for quantum annealing and variational quantum eigensolver for fixed quantum resources. The inference is achieved by extrapolating the annealing time to infinity or extrapolating the variance to zero. The only additional overhead is an increase in the number of measurements by a constant factor. We verified the validity of our method with the transverse-field Ising model. The method is robust to noise, and the techniques are applicable to other physics problems. Analytic derivations for the quadratic convergence feature of the residual energy in quantum annealing and the linear convergence feature of energy variance are given.
We introduce quantum fluctuations into the simulated annealing process of optimization problems, aiming at faster convergence to the optimal state. The idea is tested by the two models, the transverse Ising model and the traveling salesman problem (TSP). Adding the transverse field to the Ising model is a simple way to introduce quantum fluctuations. The strength of the transverse field is controlled as a function of time similarly to the temperature in the conventional method. TSP can be described by the Ising spin, so that we also apply the same technique to TSP. We directory solve the time-dependent Schrödinger equation for small-size systems and perform the quantum Monte Carlo simulation for large-size systems. Comparison with the results of the corresponding classical (thermal) method reveals that the quantum method leads to the ground state with much larger probability in almost all cases if we use the same annealing schedule of the control parameters. We also find that the relaxation time is quite short for quantum systems by numerical simulations. We consider this is one of the reasons why the annealing in quantum systems have a better performance of finding the optimal state in comparison with classical systems.