We present a bound on the length of the path defined by the ground states of a continuous family of Hamiltonians in terms of the spectral gap $\ensuremath{\Delta}$. We use this bound to obtain a significant improvement over the cost of recently proposed methods for quantum adiabatic state transformations and eigenpath traversal. In particular, we prove that a method based on evolution randomization, which is a simple extension of adiabatic quantum computation, has an average cost of order $1/{\ensuremath{\Delta}}^{2}$, and a method based on fixed-point search has a maximum cost of order $1/{\ensuremath{\Delta}}^{3/2}$. Additionally, if the Hamiltonians satisfy a frustration-free property, such costs can be further improved to order $1/{\ensuremath{\Delta}}^{3/2}$ and $1/\ensuremath{\Delta}$, respectively. Our methods offer an important advantage over adiabatic quantum computation when the gap is small, where the cost is of order $1/{\ensuremath{\Delta}}^{3}$.
We present a bound on the length of the path defined by the ground states of a continuous family of Hamiltonians in terms of the spectral gap \ensuremathΔ. We use this bound to obtain a significant improvement over the cost of recently proposed methods for quantum adiabatic state transformations and eigenpath traversal. In particular, we prove that a method based on evolution randomization, which is a simple extension of adiabatic quantum computation, has an average cost of order 1/\ensuremathΔ2, and a method based on fixed-point search has a maximum cost of order 1/\ensuremathΔ3/2. Additionally, if the Hamiltonians satisfy a frustration-free property, such costs can be further improved to order 1/\ensuremathΔ3/2 and 1/\ensuremathΔ, respectively. Our methods offer an important advantage over adiabatic quantum computation when the gap is small, where the cost is of order 1/\ensuremathΔ3.
Consider a path of non-degenerate eigenstates of unitary operators or Hamiltonians with minimum eigenvalue gap G. The eigenpath traversal problem is to transform one or more copies of the initial to the final eigenstate. Solutions to this problem have applications ranging from quantum physics simulation to optimization. For Hamiltonians, the conventional way of doing this is by applying the adiabatic theorem. We give ``digital'' methods for performing the transformation that require no assumption on path continuity or differentiability other than the absence of large jumps. Given sufficient information about eigenvalues and overlaps between states on the path, the transformation can be accomplished with complexity O(L/G log(L/e)), where L is the angular length of the path and e is a specified bound on the error of the output state. We show that the required information can be obtained in a first set of transformations, whose complexity per state transformed has an additional factor that depends logarithmically on a maximum angular velocity along the path. This velocity is averaged over constant angular distances and does not require continuity. Our methods have substantially better behavior than conventional adiabatic algorithms, with fewer conditions on the path. They also improve on the previously best digital methods and demonstrate that path length and the gap are the primary parameters that determine the complexity of state transformation along a path.
A computation in adiabatic quantum computing is implemented by traversing a path of nondegenerate eigenstates of a continuous family of Hamiltonians. We introduce a method that traverses a discretized form of the path: At each step we apply the instantaneous Hamiltonian for a random time. The resulting decoherence approximates a projective measurement onto the desired eigenstate, achieving a version of the quantum Zeno effect. If negative evolution times can be implemented with constant overhead, then the average absolute evolution time required by our method is $\cO(L^{2} /\Delta)$ for constant error probability, where L is the length of the path of eigenstates and Δ is the minimum spectral gap of the Hamiltonian. The dependence of the cost on Δ is optimal. Making explicit the dependence on the path length is useful for cases where L is much less than the general bound. The complexity of our method has a logarithmic improvement over previous algorithms of this type. The same cost applies to the discrete-time case, where a family of unitary operators is given and each unitary and its inverse can be used. Restriction to positive evolution times incurs an error that decreases exponentially with the cost. Applications of this method to unstructured search and quantum sampling are considered. In particular, we discuss the quantum simulated annealing algorithm for solving combinatorial optimization problems. This algorithm provides a quadratic speed-up in the gap of the stochastic matrix over its classical counterpart implemented via Markov chain Monte Carlo.
The time or cost of simulating a quantum circuit by adiabatic evolution is determined by the spectral gap of the Hamiltonians involved in the simulation. In "standard" constructions based on Feynman's Hamiltonian, such a gap decreases polynomially with the number of gates in the circuit, L. Because a larger gap implies a smaller cost, we study the limits of spectral gap amplification in this context. We show that, under some assumptions on the ground states and the cost of evolving with the Hamiltonians (which apply to the standard constructions), an upper bound on the gap of the order 1/L follows. In addition, if the Hamiltonians satisfy a frustration-free property, the upper bound is of the order 1/L2. Our proofs use recent results on adiabatic state transformations, spectral gap amplification, and the simulation of continuous-time quantum query algorithms. They also consider a reduction from the unstructured search problem, whose lower bound in the oracle cost translates into the upper bounds in the gaps. The impact of our results is that improving the gap beyond that of standard constructions (i.e. 1/L2), if possible, is challenging.
In an adiabatic evolution, the wave function follows the path of ground states ∣Φ0(s)⟩ of a Hamiltonian H(s) as s is tuned from 0 to 1. The geometry of this adiabatic path is described by quantities such as its length L=∫01∥∂s∣Φ0(s)⟩∥ds and its total curvature K. This geometry affects the evolution time T. For instance, T is at least of order L/Δ∗, where Δ∗ is the minimum energy gap over s∈[0,1]. The traditional approach gives L=O(Δ∗−1/2) and K=O(Δ∗−1), which are loose in many cases. We improve these bounds by using μ<(γ), the width of the region in s on which the gap is below γ. The gap profile is in width class p when μ<(γ) falls at least as fast as γ1/p. A typical avoided crossing is in width class p=1, which gives L=O(logΔ∗−1) and K=O(logΔ∗−1). A profile in width class p>1 gives power laws with exponents (p−1)/(2p) for L and (p−1)/p for K. The width class also bounds the evolution time. At p=1 we have T=O(Δ∗−2) with a schedule that advances s at a constant rate, and T=O(Δ∗−1) up to a polylogarithmic correction with a schedule that traverses the path at a constant geometric speed. The bounds on L hold for any twice continuously differentiable H(s), and the bounds on K for affine H(s). We also prove the tightness of scaling of L in Δ∗ for every integer p≥1, and the scaling of K at p=1. We demonstrate the bounds on the adiabatic Grover search, the XXZ spin chain, and molecular electronic Hamiltonians.
Many problems in science could be solved by preparing the low-energy quantum state (or any eigenstate) of a Hamiltonian. A common example is the Boolean satisfiability problem, where each clause can be mapped to the energy of an interacting many-body system, and the problem reduces to minimizing the energy. In quantum computing, adiabatic quantum state transformations (ASTs) provide a tool for preparing the quantum state. ASTs are conventionally implemented via slow or adiabatic perturbations to the Hamiltonian, relying on the quantum adiabatic theorem. Nevertheless, more efficient implementations of ASTs exist. In this talk I will review recently developed methods for ASTs that are more efficient and require less assumptions on the Hamiltonians than the conventional implementation [1,2]. Such methods involve measurements of the states along the evolution path and have a best-case implementation cost of L/G, where L is the length of the (evolved) state path and G is a lower bound to the spectral gap of the Hamiltonians. I will show that this cost is optimal [3] and comment on results of the gap amplification problem, where the goal is to reduce the cost by increasing G [4].