Abstract Recent work [1] argued that the scaling of a dimensionless quantity $$Q_D$$ Q D with path length is a better proxy for quantifying the scaling of the computational cost of maintaining adiabaticity than the timescale. It also conjectured that generically the scaling will be superlinear (although special cases exist in which it is linear). The quantity $$Q_D$$ Q D depends only on the properties of ground states along the Hamiltonian path and the rate at which the path is followed. In this paper, we demonstrate that this conjecture holds for simple Hamiltonian systems that can be studied numerically. In particular, the systems studied exhibit the behavior that $$Q_D$$ Q D grows approximately as $$L \log L$$ L log L where L is the path length when the threshold error is fixed.
Abstract Recent work [1] argued that the scaling of a dimensionless quantity QD Q D with path length is a better proxy for quantifying the scaling of the computational cost of maintaining adiabaticity than the timescale. It also conjectured that generically the scaling will be superlinear (although special cases exist in which it is linear). The quantity QD Q D depends only on the properties of ground states along the Hamiltonian path and the rate at which the path is followed. In this paper, we demonstrate that this conjecture holds for simple Hamiltonian systems that can be studied numerically. In particular, the systems studied exhibit the behavior that QD Q D grows approximately as LlogL L log L where L is the path length when the threshold error is fixed.
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.
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}$.
The general class of models of adiabatic evolution was proposed to speed up the usual adiabatic computation in the case of quantum search problem. It was shown [8] that, by temporarily increasing the ground state energy of a time-dependent Hamiltonian to a suitable quantity, the quantum computation can perform the calculation in time complexity O(1). But it is also known that if the overlap between the initial and final states of the system is zero, then the computation based on the generalized models of adiabatic evolution can break down completely. In this paper, we find another severe limitation for this class of adiabatic evolution-based algorithms, which should be taken into account in applications. That is, it is still possible that this kind of evolution designed to deal with the quantum search problem fails completely if the interpolating paths in the system Hamiltonian are chosen inappropriately, while the usual adiabatic evolutions can do the same job relatively effectively. This implies that it is not always recommendable to use nonlinear paths in adiabatic computation. On the contrary, the usual simple adiabatic evolution may be sufficient for effective use.
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].
The Rényi area law conjecture is false below α=1 in high dimensions
Area laws express the expectation that entanglement in gapped quantum ground states scales with a boundary rather than a volume. In one dimension this holds for every Rényi entropy, and the Rényi area-law conjecture asserts the same in higher dimensions for each fixed 0<α<1. Here we disprove this conjecture in every spatial dimension two and higher. We construct finite-range Hamiltonians with fixed local dimension, bounded interaction strength, unique ground states and a uniform spectral gap, whose ground states exhibit volume-law Rényi entanglement while obeying a von Neumann area law and remaining connected to product states through uniformly gapped local paths. The mechanism is error-space complexity: locally identifiable components of arbitrarily small weight can encode states with high entanglement complexity. We also establish the worst-case rank-error trade-off for approximate ground-state projectors, a key tool in one-dimensional area-law proofs. At fixed gap, the optimal Schmidt rank at projection error ε across a planar cut of cross-section A scales as exp[Θ~((Alogε−1)2/3)] when logε−1≳A. Thus α=1 is the sharp threshold for a universal Rényi area law within this adiabatically connected class.
In quantum adiabatic evolution algorithms, the quantum computer follows the ground state of a slowly varying Hamiltonian. The ground state of the initial Hamiltonian is easy to construct; the ground state of the final Hamiltonian encodes the solution of the computational problem. These algorithms have generally been studied in the case where the "straight line" path from initial to final Hamiltonian is taken. But there is no reason not to try paths involving terms that are not linear combinations of the initial and final Hamiltonians. We give several proposals for randomly generating new paths. Using one of these proposals, we convert an algorithmic failure into a success.