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.
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 to
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.
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
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.
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 (Def. 6.1), and the initial state of the system is the eigenstate of
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
idtd∣ψ(t)⟩=H(t)∣ψ(t)⟩, and
H(t) is slowly changing. If, for any value of the time parameter
t, there is always a gap between the lowest eigenvalue of
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) varies from an initial (time-independent) Hamiltonian
HI to a final Hamiltonian
HF. If the change happens slowly, and the initial state of the system is an eigenstate of
HI with minimum eigenvalue, the adiabatic theorem asserts that the evolution eventually leads to the eigenstate with minimum eigenvalue of the final Hamiltonian
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 should be changed into
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.