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

Quantum search using non-Hermitian adiabatic evolution

Alexander I. Nesterov, G. P. Berman

Published Nov 12, 2012• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.86.052316

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

Partial evolution based local adiabatic quantum search

Jie Sun, Songfeng Lu, Fang Liu +1 more

Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger than one. Later, they found that the above two adiabatic search algorithms had the same time complexity when there is only one marked item in the database. In the present paper, following the idea of Roland and Cerf [Roland J and Cerf N J 2002 Phys. Rev. A 65 042308 ], if within the small symmetric evolution interval defined by Zhang et al., a local adiabatic evolution is performed instead of the original "global" one, this "new" algorithm exhibits slightly better performance, although they are progressively equivalent with M increasing. In addition, the proof of the optimality for this partial evolution based local adiabatic search when M = 1 is also presented. Two other special cases of the adiabatic algorithm obtained by appropriately tuning the evolution interval of partial adiabatic evolution based quantum search, which are found to have the same phenomenon above, are also discussed.

Chinese Physics B•Jan 1, 2012•12 citations

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

An adiabatic oracle for Grover's algorithm

Bin Yan, Nikolai A. Sinitsyn

Grover's search algorithm was originally proposed for circuit-based quantum computers. A crucial part of it is to query an oracle -- a black-box unitary operation. Generation of this oracle is formally beyond the original algorithm design. Here, we propose a realization of Grover's oracle for a large class of searching problems using a quantum annealing step. The time of this step grows only logarithmically with the size of the database. This suggests an efficient path to application of Grover's algorithm to practically important problems, such as finding the ground state of a Hamiltonian with a spectral gap over its ground state.

arXiv:2207.05665•Jul 12, 2022•1 citation

Adiabatic quantum optimization in the presence of discrete noise: Reducing the problem dimensionality

Salvatore Mandrà, Gian Giacomo Guerreschi, Alán Aspuru‐Guzik

Adiabatic quantum optimization is a procedure to solve a vast class of optimization problems by slowly changing the Hamiltonian of a quantum system. The evolution time necessary for the algorithm to be successful scales inversely with the minimum energy gap encountered during the dynamics. Unfortunately, the direct calculation of the gap is strongly limited by the exponential growth in the dimensionality of the Hilbert space associated to the quantum system. Although many special-purpose methods have been devised to reduce the effective dimensionality, they are strongly limited to particular classes of problems with evident symmetries. Moreover, little is known about the computational power of adiabatic quantum optimizers in real-world conditions. Here we propose and implement a general purposes reduction method that does not rely on any explicit symmetry and which requires, under certain general conditions, only a polynomial amount of classical resources. Thanks to this method, we are able to analyze the performance of ``nonideal'' quantum adiabatic optimizers to solve the well-known Grover problem, namely the search of target entries in an unsorted database, in the presence of discrete local defects. In this case, we show that adiabatic quantum optimization, even if affected by random noise, is still potentially faster than any classical algorithm.

arXiv:1407.8183•Physical Review A•Dec 10, 2015•17 citations

Excited State Search Using Quantum Annealing

Yuya Seki, Yuichiro Matsuzaki, Shiro Kawabata

Quantum annealing (QA) is one of the ways to search the ground state of the problem Hamiltonian. Here, we propose the QA scheme to search arbitrary excited states of the problem Hamiltonian. In our scheme, an $n$-th excited state of the trivial Hamiltonian is initially prepared and is adiabatically changed into an $n$-th excited state of the target Hamiltonian. Although our scheme is general such that we can search any excited states, we especially discuss the first excited state search in this paper. As a comparison, we consider a non-adiabatic scheme to find the first excited state with non-adiabatic transitions from the ground state. By solving the Lindblad master equation, we evaluate the performance of each scheme under the influence of decoherence. Our conclusion is that the adiabatic scheme show better performance than the non-adiabatic scheme as long as the coherence time of qubits is sufficiently long. These results are important for applications in the area of quantum chemistry, quantum simulation, and post-quantum cryptography.

arXiv:2002.12621•Journal of the Physical Society of Japan•Apr 7, 2021•6 citations
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 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.
Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger than one. Later, they found that the above two adiabatic search algorithms had the same time complexity when there is only one marked item in the database. In the present paper, following the idea of Roland and Cerf [Roland J and Cerf N J 2002 Phys. Rev. A 65 042308 ], if within the small symmetric evolution interval defined by Zhang et al., a local adiabatic evolution is performed instead of the original "global" one, this "new" algorithm exhibits slightly better performance, although they are progressively equivalent with M increasing. In addition, the proof of the optimality for this partial evolution based local adiabatic search when M = 1 is also presented. Two other special cases of the adiabatic algorithm obtained by appropriately tuning the evolution interval of partial adiabatic evolution based quantum search, which are found to have the same phenomenon above, are also discussed.
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.
Grover's search algorithm was originally proposed for circuit-based quantum computers. A crucial part of it is to query an oracle -- a black-box unitary operation. Generation of this oracle is formally beyond the original algorithm design. Here, we propose a realization of Grover's oracle for a large class of searching problems using a quantum annealing step. The time of this step grows only logarithmically with the size of the database. This suggests an efficient path to application of Grover's algorithm to practically important problems, such as finding the ground state of a Hamiltonian with a spectral gap over its ground state.
Adiabatic quantum optimization is a procedure to solve a vast class of optimization problems by slowly changing the Hamiltonian of a quantum system. The evolution time necessary for the algorithm to be successful scales inversely with the minimum energy gap encountered during the dynamics. Unfortunately, the direct calculation of the gap is strongly limited by the exponential growth in the dimensionality of the Hilbert space associated to the quantum system. Although many special-purpose methods have been devised to reduce the effective dimensionality, they are strongly limited to particular classes of problems with evident symmetries. Moreover, little is known about the computational power of adiabatic quantum optimizers in real-world conditions. Here we propose and implement a general purposes reduction method that does not rely on any explicit symmetry and which requires, under certain general conditions, only a polynomial amount of classical resources. Thanks to this method, we are able to analyze the performance of ``nonideal'' quantum adiabatic optimizers to solve the well-known Grover problem, namely the search of target entries in an unsorted database, in the presence of discrete local defects. In this case, we show that adiabatic quantum optimization, even if affected by random noise, is still potentially faster than any classical algorithm.
Quantum annealing (QA) is one of the ways to search the ground state of the problem Hamiltonian. Here, we propose the QA scheme to search arbitrary excited states of the problem Hamiltonian. In our scheme, an nnn-th excited state of the trivial Hamiltonian is initially prepared and is adiabatically changed into an nnn-th excited state of the target Hamiltonian. Although our scheme is general such that we can search any excited states, we especially discuss the first excited state search in this paper. As a comparison, we consider a non-adiabatic scheme to find the first excited state with non-adiabatic transitions from the ground state. By solving the Lindblad master equation, we evaluate the performance of each scheme under the influence of decoherence. Our conclusion is that the adiabatic scheme show better performance than the non-adiabatic scheme as long as the coherence time of qubits is sufficiently long. These results are important for applications in the area of quantum chemistry, quantum simulation, and post-quantum cryptography.