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:1610.04708

Adiabatic Quantum Computation

Friederike Anna Dziemba

Published Oct 15, 2016• 2 citations
arXivHTMLPDF

Abstract

The quantum adiabatic theorem ensures that a slowly changing system, initially prepared in its ground state, will evolve to its final ground state with arbitrary precision. As a first result this thesis extends the original theorem to projection operators keeping the statement valid for Hamiltonians with degenerate ground spaces. Yet the main focus of this work lies in studying the efficiency of quantum circuit simulations by adabatic quantum computation. The standard Hamiltonian construction by Kitaev is based on a path graph reflecting the $L$ computation steps and influencing the scaling of the necessary evolution time by its spectral gap of $\mathcal{O}\left(\frac{1}{L^2}\right)$. Aspiring to an improved running time we generalize Kitaev's Hamiltonian to so-called standard graph Hamiltonians based on graph families with a different spectral gap. In this generalized construction the first two time derivatives of the Hamiltonian and the fraction of initial vertices appear as additional parameters of running time. In a first step the time derivatives can be proven to be constant. Expansion results from spectral graph theory however impose a trade-off between the spectral gap and the fraction of initial vertices as well as the fraction of final vertices which corresponds to the probability for obtaining the correct computational output. Graphs with spectral gap $\mathcal{O}\left(\frac{1}{L^k}\right)$, $k<2$, turn out to contradict very likely, graphs with $k<1$ even for sure at least one of the efficiency criterias for running time, output probability or Hamiltonian implementation. The above results may also be obstacles for a possible quantum PCP-theorem in complexity theory claiming the local Hamiltonian problem with constant gap to be QMA-complete since the very same Kitaev Hamiltonian is constructed in the QMA-hardness proof for the Local Hamiltonian problem.

DOI
10.48550/arxiv.1610.04708

Related papers

Simulating quantum circuits by adiabatic computation: Improved spectral gap bounds

Shane Dooley, Graham Kells, Hosho Katsura +1 more

Adiabatic quantum computing is a framework for quantum computing that is superficially very different to the standard circuit model. However, it can be shown that the two models are computationally equivalent. The key to the proof is a mapping of a quantum circuit to an adiabatic evolution, and then showing that the minimum spectral gap of the adiabatic Hamiltonian is at least inverse polynomial in the number of computational steps $L$. In this paper we provide two simplified proofs that the gap is inverse polynomial. Both proofs result in the same lower bound for the minimum gap, which for $L\ensuremath{\gg}1$ is ${min}_{s}{\mathrm{\ensuremath{\Delta}}}_{0}\ensuremath{\gtrsim}{\ensuremath{\pi}}^{2}/[8{(L+1)}^{2}]$, an improvement over previous bounds. Our first method is a direct approach based on an eigenstate ansatz, while the second uses Weyl's theorem to leverage known exact results into a bound for the gap. Our results suggest that it may be possible to use these methods to find bounds for spectral gaps of Hamiltonians in other scenarios.

arXiv:1906.05233•Physical Review A•Apr 1, 2020•5 citations

Local Hamiltonians in Quantum Computation

Daniel Nagaj

In this thesis, I investigate aspects of local Hamiltonians in quantum computing. First, I focus on the Adiabatic Quantum Computing model, based on evolution with a time dependent Hamiltonian. I show that to succeed using AQC, the Hamiltonian involved must have local structure, which leads to a result about eigenvalue gaps from information theory. I also improve results about simulating quantum circuits with AQC. Second, I look at classically simulating time evolution with local Hamiltonians and finding their ground state properties. I give a numerical method for finding the ground state of translationally invariant Hamiltonians on an infinite tree. This method is based on imaginary time evolution within the Matrix Product State ansatz, and uses a new method for bringing the state back to the ansatz after each imaginary time step. I then use it to investigate the phase transition in the transverse field Ising model on the Bethe lattice. Third, I focus on locally constrained quantum problems Local Hamiltonian and Quantum Satisfiability and prove several new results about their complexity. Finally, I define a Hamiltonian Quantum Cellular Automaton, a continuous-time model of computation which doesn't require control during the computation process, only preparation of product initial states. I construct two of these, showing that time evolution with a simple, local, translationally invariant and time-independent Hamiltonian can be used to simulate quantum circuits.

arXiv:0808.2117•Aug 15, 2008•34 citations

Evolution-Time Dependence in Near-Adiabatic Quantum Evolutions

Lucas T. Brady, Wim van Dam

We expand upon the standard quantum adiabatic theorem, examining the time-dependence of quantum evolution in the near-adiabatic limit. We examine a Hamiltonian that evolves along some fixed trajectory from $\hat{H}_0$ to $\hat{H}_1$ in a total evolution-time $τ$, and our goal is to determine how the final state of the system depends on $τ$. If the system is initialized in a non-degenerate ground state, the adiabatic theorem says that in the limit of large $τ$, the system will stay in the ground state. We examine the near-adiabatic limit where the system evolves slowly enough that most but not all of the final state is in the ground state, and we find that the probability of leaving the ground state oscillates in $τ$ with a frequency determined by the integral of the spectral gap along the trajectory of the Hamiltonian, so long as the gap is big. If the gap becomes exceedingly small, the final probability is the sum of oscillatory behavior determined by the integrals of the gap before and after the small gap. We confirm these analytic predictions with numerical evidence from barrier tunneling problems in the context of quantum adiabatic optimization.

arXiv:1801.04349•Jan 12, 2018•3 citations

Quantum Computation by Adiabatic Evolution

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +1 more

We give a quantum algorithm for solving instances of the satisfiability problem, based on adiabatic evolution. The evolution of the quantum state is governed by a time-dependent Hamiltonian that interpolates between an initial Hamiltonian, whose ground state is easy to construct, and a final Hamiltonian, whose ground state encodes the satisfying assignment. To ensure that the system evolves to the desired final ground state, the evolution time must be big enough. The time required depends on the minimum energy difference between the two lowest states of the interpolating Hamiltonian. We are unable to estimate this gap in general. We give some special symmetric cases of the satisfiability problem where the symmetry allows us to estimate the gap and we show that, in these cases, our algorithm runs in polynomial time.

arXiv:quant-ph/0001106•Jan 28, 2000•2,419 citations

From quantum circuits to adiabatic algorithms

M. Stewart Siu

This paper explores several aspects of the adiabatic quantum-computation model. We first show a way that directly maps any arbitrary circuit in the standard quantum-computing model to an adiabatic algorithm of the same depth. Specifically, we look for a smooth time-dependent Hamiltonian whose unique ground state slowly changes from the initial state of the circuit to its final state. Since this construction requires in general an $n$-local Hamiltonian, we will study whether approximation is possible using previous results on ground-state entanglement and perturbation theory. Finally we will point out how the adiabatic model can be relaxed in various ways to allow for 2-local partially adiabatic algorithms as well as 2-local holonomic quantum algorithms.

arXiv:quant-ph/0409024•Physical Review A•Jun 14, 2005•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
The quantum adiabatic theorem ensures that a slowly changing system, initially prepared in its ground state, will evolve to its final ground state with arbitrary precision. As a first result this thesis extends the original theorem to projection operators keeping the statement valid for Hamiltonians with degenerate ground spaces. Yet the main focus of this work lies in studying the efficiency of quantum circuit simulations by adabatic quantum computation. The standard Hamiltonian construction by Kitaev is based on a path graph reflecting the LLL computation steps and influencing the scaling of the necessary evolution time by its spectral gap of O(1L2)\mathcal{O}\left(\frac{1}{L^2}\right)O(L21​). Aspiring to an improved running time we generalize Kitaev's Hamiltonian to so-called standard graph Hamiltonians based on graph families with a different spectral gap. In this generalized construction the first two time derivatives of the Hamiltonian and the fraction of initial vertices appear as additional parameters of running time. In a first step the time derivatives can be proven to be constant. Expansion results from spectral graph theory however impose a trade-off between the spectral gap and the fraction of initial vertices as well as the fraction of final vertices which corresponds to the probability for obtaining the correct computational output. Graphs with spectral gap O(1Lk)\mathcal{O}\left(\frac{1}{L^k}\right)O(Lk1​), k<2k<2k<2, turn out to contradict very likely, graphs with k<1k<1k<1 even for sure at least one of the efficiency criterias for running time, output probability or Hamiltonian implementation. The above results may also be obstacles for a possible quantum PCP-theorem in complexity theory claiming the local Hamiltonian problem with constant gap to be QMA-complete since the very same Kitaev Hamiltonian is constructed in the QMA-hardness proof for the Local Hamiltonian problem.
Adiabatic quantum computing is a framework for quantum computing that is superficially very different to the standard circuit model. However, it can be shown that the two models are computationally equivalent. The key to the proof is a mapping of a quantum circuit to an adiabatic evolution, and then showing that the minimum spectral gap of the adiabatic Hamiltonian is at least inverse polynomial in the number of computational steps LLL. In this paper we provide two simplified proofs that the gap is inverse polynomial. Both proofs result in the same lower bound for the minimum gap, which for $L\ensuremath{\gg}1$ is ${min}_{s}{\mathrm{\ensuremath{\Delta}}}_{0}\ensuremath{\gtrsim}{\ensuremath{\pi}}^{2}/[8{(L+1)}^{2}]$, an improvement over previous bounds. Our first method is a direct approach based on an eigenstate ansatz, while the second uses Weyl's theorem to leverage known exact results into a bound for the gap. Our results suggest that it may be possible to use these methods to find bounds for spectral gaps of Hamiltonians in other scenarios.
In this thesis, I investigate aspects of local Hamiltonians in quantum computing. First, I focus on the Adiabatic Quantum Computing model, based on evolution with a time dependent Hamiltonian. I show that to succeed using AQC, the Hamiltonian involved must have local structure, which leads to a result about eigenvalue gaps from information theory. I also improve results about simulating quantum circuits with AQC. Second, I look at classically simulating time evolution with local Hamiltonians and finding their ground state properties. I give a numerical method for finding the ground state of translationally invariant Hamiltonians on an infinite tree. This method is based on imaginary time evolution within the Matrix Product State ansatz, and uses a new method for bringing the state back to the ansatz after each imaginary time step. I then use it to investigate the phase transition in the transverse field Ising model on the Bethe lattice. Third, I focus on locally constrained quantum problems Local Hamiltonian and Quantum Satisfiability and prove several new results about their complexity. Finally, I define a Hamiltonian Quantum Cellular Automaton, a continuous-time model of computation which doesn't require control during the computation process, only preparation of product initial states. I construct two of these, showing that time evolution with a simple, local, translationally invariant and time-independent Hamiltonian can be used to simulate quantum circuits.
We expand upon the standard quantum adiabatic theorem, examining the time-dependence of quantum evolution in the near-adiabatic limit. We examine a Hamiltonian that evolves along some fixed trajectory from H^0\hat{H}_0H^0​ to H^1\hat{H}_1H^1​ in a total evolution-time τττ, and our goal is to determine how the final state of the system depends on τττ. If the system is initialized in a non-degenerate ground state, the adiabatic theorem says that in the limit of large τττ, the system will stay in the ground state. We examine the near-adiabatic limit where the system evolves slowly enough that most but not all of the final state is in the ground state, and we find that the probability of leaving the ground state oscillates in τττ with a frequency determined by the integral of the spectral gap along the trajectory of the Hamiltonian, so long as the gap is big. If the gap becomes exceedingly small, the final probability is the sum of oscillatory behavior determined by the integrals of the gap before and after the small gap. We confirm these analytic predictions with numerical evidence from barrier tunneling problems in the context of quantum adiabatic optimization.
We give a quantum algorithm for solving instances of the satisfiability problem, based on adiabatic evolution. The evolution of the quantum state is governed by a time-dependent Hamiltonian that interpolates between an initial Hamiltonian, whose ground state is easy to construct, and a final Hamiltonian, whose ground state encodes the satisfying assignment. To ensure that the system evolves to the desired final ground state, the evolution time must be big enough. The time required depends on the minimum energy difference between the two lowest states of the interpolating Hamiltonian. We are unable to estimate this gap in general. We give some special symmetric cases of the satisfiability problem where the symmetry allows us to estimate the gap and we show that, in these cases, our algorithm runs in polynomial time.
This paper explores several aspects of the adiabatic quantum-computation model. We first show a way that directly maps any arbitrary circuit in the standard quantum-computing model to an adiabatic algorithm of the same depth. Specifically, we look for a smooth time-dependent Hamiltonian whose unique ground state slowly changes from the initial state of the circuit to its final state. Since this construction requires in general an nnn-local Hamiltonian, we will study whether approximation is possible using previous results on ground-state entanglement and perturbation theory. Finally we will point out how the adiabatic model can be relaxed in various ways to allow for 2-local partially adiabatic algorithms as well as 2-local holonomic quantum algorithms.
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.