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

Non-Hermitian quantum annealing in the ferromagnetic Ising model

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

Published Apr 25, 2013• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.87.042332

Related papers

Non-Hermitian Quantum Annealing in the Transverse Ising Model

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

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.

•Nov 14, 2012•0 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•11 citations

Ising formulation of integer optimization problems for utilizing quantum annealing in iterative improvement strategy

Shuntaro Okada, Masayuki Ohzeki

Quantum annealing is a heuristic algorithm for searching the ground state of an Ising model. Heuristic algorithms aim to obtain near-optimal solutions with a reasonable computation time. Accordingly, many algorithms have so far been proposed. In general, the performance of heuristic algorithms strongly depends on the instance of the combinatorial optimization problem to be solved because they escape the local minima in different ways. Therefore, combining several algorithms to exploit their complementary strength is effective for obtaining highly accurate solutions for a wide range of combinatorial optimization problems. However, quantum annealing cannot be used to improve a candidate solution obtained by other algorithms because it starts from an initial state where all spin configurations are found with a uniform probability. In this study, we propose an Ising formulation of integer optimization problems to utilize quantum annealing in the iterative improvement strategy. Our formulation exploits the biased sampling of degenerated ground states in transverse magnetic field quantum annealing. We also analytically show that a first-order phase transition is successfully avoided for a fully connected ferromagnetic Potts model if the overlap between a ground state and a candidate solution exceeds a threshold. The proposed formulation is applicable to a wide range of integer optimization problems and enables us to hybridize quantum annealing with other optimization algorithms.

arXiv:2211.03957•Nov 8, 2022•0 citations

Effectiveness of Hybrid Optimization Method for Quantum Annealing Machines

Shuta Kikuchi, Nozomu Togawa, Shu Tanaka

To enhance the performance of quantum annealing machines, several methods have been proposed to reduce the number of spins by fixing spin values through preprocessing. We proposed a hybrid optimization method that combines a simulated annealing (SA)-based non-quantum-type Ising machine with a quantum annealing machine. However, its applicability remains unclear. Therefore, we evaluated the performance of the hybrid method on large-size Ising models and analyzed its characteristics. The results indicate that the hybrid method improves upon solutions obtained by the preprocessing SA, even if the Ising models cannot be embedded in the quantum annealing machine. We analyzed the method from three perspectives: preprocessing, spin-fixed sub-Ising model generation method, and the accuracy of the quantum annealing machine. From the viewpoint of the minimum energy gap, we found that solving the sub-Ising model with a quantum annealing machine results in a higher solution accuracy than solving the original Ising model. Additionally, we demonstrated that the number of fixed spins and the accuracy of the quantum annealing machine affect the dependency of the solution accuracy on the sub-Ising model size.

arXiv:2507.15544•Jul 21, 2025•5 citations

Non-Hermitian ground-state-searching algorithm enhanced by a variational toolbox

Yuqin Chen, Shi‐Xin Zhang, Chang‐Yu Hsieh +1 more

Ground-state preparation for a given Hamiltonian is a common quantum-computing task of great importance and has relevant applications in quantum chemistry, computational material modeling, and combinatorial optimization. We consider an approach to simulate dissipative non-Hermitian Hamiltonian quantum dynamics using Hamiltonian simulation techniques to efficiently recover the ground state of a target Hamiltonian. The proposed method facilitates the energy transfer by repeatedly projecting ancilla qubits to the desired state, rendering the effective non-Hermitian Hamiltonian evolution on the system qubits. To make the method more resource friendly in the noisy intermediate-scale quantum (NISQ) and early fault-tolerant era, we combine the non-Hermitian projection algorithm with multiple variational gadgets, including variational module enhancement and variational state recording, to reduce the required circuit depth and avoid the exponentially vanishing success probability for postselections. We compare our method, the non-Hermitian-variational algorithm, with a pure variational method, the quantum approximate optimization algorithm (QAOA), for solving the 3-SAT problem and preparing the ground state for the transverse field Ising model. As demonstrated by numerical evidence, the non-Hermitian-variational algorithm outperforms QAOA in convergence speed with improved quantum resource efficiency.

arXiv:2210.09007•Physical Review A•Apr 14, 2023•8 citations

Variational optimization of the quantum annealing schedule for the Lechner-Hauke-Zoller scheme

Yuki Susa, Hidetoshi Nishimori

The annealing schedule is optimized for a parameter in the Lechner-Hauke-Zoller (LHZ) scheme for quantum annealing designed for the all-to-all-interacting Ising model representing generic combinatorial optimization problems. We adapt the variational approach proposed by Matsuura et al. (arXiv:2003.09913) to the annealing schedule of a term representing a constraint for variables intrinsic to the LHZ scheme with the annealing schedule of other terms kept intact. Numerical results for a simple ferromagnetic model and the spin-glass problem show that nonmonotonic annealing schedules optimize the performance measured by the residual energy and the final ground-state fidelity. This improvement does not accompany a notable increase in the instantaneous energy gap, which suggests the importance of a dynamical viewpoint in addition to static analyses in the study of practically relevant diabatic processes in quantum annealing.

arXiv:2012.01694•Physical Review A•Feb 26, 2021•30 citations
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 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 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.
Quantum annealing is a heuristic algorithm for searching the ground state of an Ising model. Heuristic algorithms aim to obtain near-optimal solutions with a reasonable computation time. Accordingly, many algorithms have so far been proposed. In general, the performance of heuristic algorithms strongly depends on the instance of the combinatorial optimization problem to be solved because they escape the local minima in different ways. Therefore, combining several algorithms to exploit their complementary strength is effective for obtaining highly accurate solutions for a wide range of combinatorial optimization problems. However, quantum annealing cannot be used to improve a candidate solution obtained by other algorithms because it starts from an initial state where all spin configurations are found with a uniform probability. In this study, we propose an Ising formulation of integer optimization problems to utilize quantum annealing in the iterative improvement strategy. Our formulation exploits the biased sampling of degenerated ground states in transverse magnetic field quantum annealing. We also analytically show that a first-order phase transition is successfully avoided for a fully connected ferromagnetic Potts model if the overlap between a ground state and a candidate solution exceeds a threshold. The proposed formulation is applicable to a wide range of integer optimization problems and enables us to hybridize quantum annealing with other optimization algorithms.
To enhance the performance of quantum annealing machines, several methods have been proposed to reduce the number of spins by fixing spin values through preprocessing. We proposed a hybrid optimization method that combines a simulated annealing (SA)-based non-quantum-type Ising machine with a quantum annealing machine. However, its applicability remains unclear. Therefore, we evaluated the performance of the hybrid method on large-size Ising models and analyzed its characteristics. The results indicate that the hybrid method improves upon solutions obtained by the preprocessing SA, even if the Ising models cannot be embedded in the quantum annealing machine. We analyzed the method from three perspectives: preprocessing, spin-fixed sub-Ising model generation method, and the accuracy of the quantum annealing machine. From the viewpoint of the minimum energy gap, we found that solving the sub-Ising model with a quantum annealing machine results in a higher solution accuracy than solving the original Ising model. Additionally, we demonstrated that the number of fixed spins and the accuracy of the quantum annealing machine affect the dependency of the solution accuracy on the sub-Ising model size.
Ground-state preparation for a given Hamiltonian is a common quantum-computing task of great importance and has relevant applications in quantum chemistry, computational material modeling, and combinatorial optimization. We consider an approach to simulate dissipative non-Hermitian Hamiltonian quantum dynamics using Hamiltonian simulation techniques to efficiently recover the ground state of a target Hamiltonian. The proposed method facilitates the energy transfer by repeatedly projecting ancilla qubits to the desired state, rendering the effective non-Hermitian Hamiltonian evolution on the system qubits. To make the method more resource friendly in the noisy intermediate-scale quantum (NISQ) and early fault-tolerant era, we combine the non-Hermitian projection algorithm with multiple variational gadgets, including variational module enhancement and variational state recording, to reduce the required circuit depth and avoid the exponentially vanishing success probability for postselections. We compare our method, the non-Hermitian-variational algorithm, with a pure variational method, the quantum approximate optimization algorithm (QAOA), for solving the 3-SAT problem and preparing the ground state for the transverse field Ising model. As demonstrated by numerical evidence, the non-Hermitian-variational algorithm outperforms QAOA in convergence speed with improved quantum resource efficiency.
The annealing schedule is optimized for a parameter in the Lechner-Hauke-Zoller (LHZ) scheme for quantum annealing designed for the all-to-all-interacting Ising model representing generic combinatorial optimization problems. We adapt the variational approach proposed by Matsuura et al. (arXiv:2003.09913) to the annealing schedule of a term representing a constraint for variables intrinsic to the LHZ scheme with the annealing schedule of other terms kept intact. Numerical results for a simple ferromagnetic model and the spin-glass problem show that nonmonotonic annealing schedules optimize the performance measured by the residual energy and the final ground-state fidelity. This improvement does not accompany a notable increase in the instantaneous energy gap, which suggests the importance of a dynamical viewpoint in addition to static analyses in the study of practically relevant diabatic processes in quantum annealing.