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.
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.
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}$.
A basic building block of many quantum algorithms is the Phase Estimation algorithm (PEA). It estimates an eigenphase ϕ of a unitary operator U using a copy of the corresponding eigenstate ∣ϕ⟩. Suppose, in place of ∣ϕ⟩, we have a copy of an approximate eigenstate ∣ψ⟩ whose overlap magnitude with ∣ϕ⟩ is at least 2/3. Then PEA fails with a constant probability. However, using multiple copies of ∣ψ⟩, the failure probaility can be made to decrease exponentially with the number of copies. In this paper, we show that as long as we can perform a selective inversion of ∣ψ⟩, a single copy is sufficient to estimate ϕ. An important application is to improve the spatial complexity of eigenpath traversal algorithm, a digital analogue of quantum adiabatic evolution, having applications ranging from quantum physics simulation to optimization. Here the goal is to travel a path of eigenstates of n different unitary operators satisfying some conditions. The fastest algorithm is due to Boixo, Knill and Somma (BKS) which needs Θ(lnn) copies of the eigenstate. Using our algorithm, BKS algorithm can work using just a single copy of the eigenstate.
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].
We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error. Our algorithm digitally simulates the adiabatic evolution between two self-adjoint operators H0 and H1, exponentially suppressing the diabatic error by harnessing the theoretical concept of quasi-adiabatic continuation as an algorithmic tool. Given an upper bound α on ∥H0∥ and ∥H1∥ along with the promise that the kth eigenstate ∣ψk(s)⟩ of H(s)≡(1−s)H0+sH1 is separated from the rest of the spectrum by a gap of at least γ>0 for all s∈[0,1], this algorithm implements an operator U such that ∥∣ψk(1)⟩−U∣ψk(s)⟩∥≤ε using O(α2/γ2)polylog(α/γε) queries to block-encodings of H0 and H1. In addition, we develop an algorithm that is applicable only to ground states and requires multiple queries to an oracle that prepares ∣ψ0(0)⟩, but has slightly better scaling in all parameters. We also show that the costs of both algorithms can be further reduced under certain reasonable conditions, such as when ∥H1−H0∥ is small compared to α, or when more information about the gap of H(s) is available. For certain problems, the scaling can even be improved to linear in ∥H1−H0∥/γ up to polylogarithmic factors.
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. The average cost of our method is O(L2/Delta) for constant error probability, where L is the length of the path of eigenstates and Delta is the minimum spectral gap of the Hamiltonian. For many cases of interest, L does not depend on Delta so the scaling of the cost with the gap is better than the one obtained in rigorous proofs of the adiabatic theorem. We give an example where this situation occurs.