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

Chinese Physics B

An adiabatic quantum optimization for exact cover 3 problem

Yingyu Zhang, Li-Li Xu, Junqing Li

Published Mar 1, 2014• 0 citations
Publisher

Abstract

A perturbation method is applied to study the structure of the ground state of the adiabatic quantum optimization for the exact cover 3 problem. It is found that the instantaneous ground state near the end of the evolution is mainly composed of the eigenstates of the problem Hamiltonian, which are Hamming close to the solution state. And the instantaneous ground state immediately after the starting is mainly formed of low energy eigenstates of the problem Hamiltonian. These results are then applied to estimate the minimum gap for a special case.

DOI
10.1088/1674-1056/23/3/030308

Related papers

Effect of Local Minima on Adiabatic Quantum Optimization

M. H. S. Amin

We present a perturbative method to estimate the spectral gap for adiabatic quantum optimization, based on the structure of the energy levels in the problem Hamiltonian. We show that, for problems that have an exponentially large number of local minima close to the global minimum, the gap becomes exponentially small making the computation time exponentially long. The quantum advantage of adiabatic quantum computation may then be accessed only via the local adiabatic evolution, which requires phase coherence throughout the evolution and knowledge of the spectrum. Such problems, therefore, are not suitable for adiabatic quantum computation.

arXiv:0709.0528•Physical Review Letters•Apr 4, 2008•38 citations

Chapter 9: Optimization with the adiabatic theorem

Giacomo Nannicini

The adiabatic theorem is a powerful result concerning the evolution of quantum mechanical systems. Intuitively, it states the following: suppose we want to study the evolution of a quantum mechanical system governed by a given Hamiltonian \(\mathcal H\) (Def. 6.1), and the initial state of the system is the eigenstate of \(\mathcal H\) corresponding to its lowest eigenvalue. The laws of quantum physics tell us that the evolution of the system over time follows the Schrüdinger equation, Eq. (6.1). Suppose now that the Hamiltonian is not fixed, but rather, it changes very slowly over time, so that the evolution of the system is described by the differential equation \(i\,\frac{\mathrm{d} | \psi(t) \rangle}{\mathrm{d}t} = \mathcal{H}(t) | \psi(t) \rangle\), and \(\mathcal{H}(t)\) is slowly changing. If, for any value of the time parameter \(t\), there is always a gap between the lowest eigenvalue of \(\mathcal{H}(t)\) and all other eigenvalues, then the adiabatic theorem asserts that the state of the system always remains in an eigenstate with the lowest eigenvalue throughout the evolution. One specific case of interest in this chapter occurs when the time-dependent Hamiltonian \(\mathcal{H}(t)\) varies from an initial (time-independent) Hamiltonian \(\mathcal{H}_{\mathrm{I}}\) to a final Hamiltonian \(\mathcal{H}_{\mathrm{F}}\). If the change happens slowly, and the initial state of the system is an eigenstate of \(\mathcal{H}_{\mathrm{I}}\) with minimum eigenvalue, the adiabatic theorem asserts that the evolution eventually leads to the eigenstate with minimum eigenvalue of the final Hamiltonian \(\mathcal{H}_{\mathrm{F}}\). This result can be used for optimization: imagine that the initial Hamiltonian encodes an easy problem for which we can construct the eigenstate with minimum eigenvalue, and the final Hamiltonian encodes a difficult optimization problem whose solution is given by the eigenstate with minimum eigenvalue. By the adiabatic theorem, evolving the eigenstate of the initial Hamiltonian while slowly changing the Hamiltonian into the final one leads to the solution of the difficult optimization problem. Of course we need to know how slowly \(\mathcal{H}_{\mathrm{I}}\) should be changed into \(\mathcal{H}_{\mathrm{F}}\). The adiabatic theorem is at the heart of the quantum approximate optimization algorithm (QAOA), a framework that has been widely used to implement optimization algorithms on existing quantum hardware, because it has low requirements of quantum resources–although it does not guarantee improvements over classical algorithms in general. In this chapter we first discuss the adiabatic theorem, and then give an overview of QAOA.

Society for Industrial and Applied Mathematics eBooks•Dec 17, 2025•0 citations

Case studies in quantum adiabatic optimization

David Gosset

Quantum adiabatic optimization is a quantum algorithm for solving classical optimization problems (E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106). The solution to an optimization prob-lem is encoded in the ground state of a "problem Hamiltonian " Hp which acts on the Hilbert space of n spin 1/2 particles and is diagonal in the Pauli z basis. To produce this ground state, one first initializes the quantum system in the ground state of a different Hamiltonian and then adiabatically changes the Hamiltonian into Hp. Farhi et al suggest the interpolating Hamiltonian i where the parameter s is slowly changed as a function of time between 0 and 1. The running time of this algorithm is related to the minimum spectral gap of H(s) for s E (0, 11. We study such transverse field spin Hamiltonians using both analytic and numerical techniques. Our approach is example-based, that is, we study some specific choices for the problem Hamiltonian Hp which illustrate the breadth of phenomena which can occur. We

•Jan 1, 2011•1 citation

Does Adiabatic Quantum Optimization Fail for NP-hard problems?

Neil G. Dickson, M. H. S. Amin

It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem of maximum independent set there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.

•Oct 4, 2010•0 citations

Does Adiabatic Quantum Optimization Fail for NP-Complete Problems?

Neil G. Dickson, M. H. S. Amin

It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem known as maximum independent set, there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.

arXiv:1010.0669•Physical Review Letters•Feb 2, 2011•65 citations

Quantum adiabatic theorem with energy gap regularization

Nikolay Borisovich Ilin

The dynamics of a nonstationary quantum system whose Hamiltonian explicitly depends on time is called adiabatic if a system state that is an eigenstate of the Hamiltonian at the initial instant of time remains close to this eigenstate throughout the evolution. The degree of such closeness depends on the smallness of the parameter that determines the rate of change of the Hamiltonian. It is usually believed that one of the factors playing a decisive role for the stability of the adiabatic dynamics is the structure of the spectrum of the Hamiltonian. As the quantum adiabatic theorem states in its usual formulation, deviations from the adiabatic evolution can be estimated from above by the ratio of the rate of change of the Hamiltonian to the minimum distance between the energy of the state that approximates the adiabatic dynamics and the rest of the spectrum of the Hamiltonian. We analyze this dependence and prove theorems showing that the efficiency of the adiabatic approximation is more influenced by the rate of change of the Hamiltonian eigenvectors than by the dynamics of the spectrum. In a vast majority of physically meaningful cases, it turns out that controlling the dynamics of eigenvectors is sufficient for ensuring the adiabaticity, regardless of the dynamics of the spectrum as such.

Theoretical and Mathematical Physics•Apr 1, 2022•1 citation
A perturbation method is applied to study the structure of the ground state of the adiabatic quantum optimization for the exact cover 3 problem. It is found that the instantaneous ground state near the end of the evolution is mainly composed of the eigenstates of the problem Hamiltonian, which are Hamming close to the solution state. And the instantaneous ground state immediately after the starting is mainly formed of low energy eigenstates of the problem Hamiltonian. These results are then applied to estimate the minimum gap for a special case.
We present a perturbative method to estimate the spectral gap for adiabatic quantum optimization, based on the structure of the energy levels in the problem Hamiltonian. We show that, for problems that have an exponentially large number of local minima close to the global minimum, the gap becomes exponentially small making the computation time exponentially long. The quantum advantage of adiabatic quantum computation may then be accessed only via the local adiabatic evolution, which requires phase coherence throughout the evolution and knowledge of the spectrum. Such problems, therefore, are not suitable for adiabatic quantum computation.
The adiabatic theorem is a powerful result concerning the evolution of quantum mechanical systems. Intuitively, it states the following: suppose we want to study the evolution of a quantum mechanical system governed by a given Hamiltonian H\mathcal HH (Def. 6.1), and the initial state of the system is the eigenstate of H\mathcal HH corresponding to its lowest eigenvalue. The laws of quantum physics tell us that the evolution of the system over time follows the Schrüdinger equation, Eq. (6.1). Suppose now that the Hamiltonian is not fixed, but rather, it changes very slowly over time, so that the evolution of the system is described by the differential equation i d∣ψ(t)⟩dt=H(t)∣ψ(t)⟩i\,\frac{\mathrm{d} | \psi(t) \rangle}{\mathrm{d}t} = \mathcal{H}(t) | \psi(t) \rangleidtd∣ψ(t)⟩​=H(t)∣ψ(t)⟩, and H(t)\mathcal{H}(t)H(t) is slowly changing. If, for any value of the time parameter ttt, there is always a gap between the lowest eigenvalue of H(t)\mathcal{H}(t)H(t) and all other eigenvalues, then the adiabatic theorem asserts that the state of the system always remains in an eigenstate with the lowest eigenvalue throughout the evolution. One specific case of interest in this chapter occurs when the time-dependent Hamiltonian H(t)\mathcal{H}(t)H(t) varies from an initial (time-independent) Hamiltonian HI\mathcal{H}_{\mathrm{I}}HI​ to a final Hamiltonian HF\mathcal{H}_{\mathrm{F}}HF​. If the change happens slowly, and the initial state of the system is an eigenstate of HI\mathcal{H}_{\mathrm{I}}HI​ with minimum eigenvalue, the adiabatic theorem asserts that the evolution eventually leads to the eigenstate with minimum eigenvalue of the final Hamiltonian HF\mathcal{H}_{\mathrm{F}}HF​. This result can be used for optimization: imagine that the initial Hamiltonian encodes an easy problem for which we can construct the eigenstate with minimum eigenvalue, and the final Hamiltonian encodes a difficult optimization problem whose solution is given by the eigenstate with minimum eigenvalue. By the adiabatic theorem, evolving the eigenstate of the initial Hamiltonian while slowly changing the Hamiltonian into the final one leads to the solution of the difficult optimization problem. Of course we need to know how slowly HI\mathcal{H}_{\mathrm{I}}HI​ should be changed into HF\mathcal{H}_{\mathrm{F}}HF​. The adiabatic theorem is at the heart of the quantum approximate optimization algorithm (QAOA), a framework that has been widely used to implement optimization algorithms on existing quantum hardware, because it has low requirements of quantum resources–although it does not guarantee improvements over classical algorithms in general. In this chapter we first discuss the adiabatic theorem, and then give an overview of QAOA.
Quantum adiabatic optimization is a quantum algorithm for solving classical optimization problems (E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106). The solution to an optimization prob-lem is encoded in the ground state of a "problem Hamiltonian " Hp which acts on the Hilbert space of n spin 1/2 particles and is diagonal in the Pauli z basis. To produce this ground state, one first initializes the quantum system in the ground state of a different Hamiltonian and then adiabatically changes the Hamiltonian into Hp. Farhi et al suggest the interpolating Hamiltonian i where the parameter s is slowly changed as a function of time between 0 and 1. The running time of this algorithm is related to the minimum spectral gap of H(s) for s E (0, 11. We study such transverse field spin Hamiltonians using both analytic and numerical techniques. Our approach is example-based, that is, we study some specific choices for the problem Hamiltonian Hp which illustrate the breadth of phenomena which can occur. We
It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem of maximum independent set there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.
It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem known as maximum independent set, there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.
The dynamics of a nonstationary quantum system whose Hamiltonian explicitly depends on time is called adiabatic if a system state that is an eigenstate of the Hamiltonian at the initial instant of time remains close to this eigenstate throughout the evolution. The degree of such closeness depends on the smallness of the parameter that determines the rate of change of the Hamiltonian. It is usually believed that one of the factors playing a decisive role for the stability of the adiabatic dynamics is the structure of the spectrum of the Hamiltonian. As the quantum adiabatic theorem states in its usual formulation, deviations from the adiabatic evolution can be estimated from above by the ratio of the rate of change of the Hamiltonian to the minimum distance between the energy of the state that approximates the adiabatic dynamics and the rest of the spectrum of the Hamiltonian. We analyze this dependence and prove theorems showing that the efficiency of the adiabatic approximation is more influenced by the rate of change of the Hamiltonian eigenvectors than by the dynamics of the spectrum. In a vast majority of physically meaningful cases, it turns out that controlling the dynamics of eigenvectors is sufficient for ensuring the adiabaticity, regardless of the dynamics of the spectrum as such.