Abstract Adiabatic quantum computing and optimization have garnered much attention recently as possible models for achieving a quantum advantage over classical approaches to optimization and other special purpose computations. Both techniques are probabilistic in nature and the minimum gap between the ground state and first excited state of the system during evolution is a major factor in determining the success probability. In this work we investigate a strategy for increasing the minimum gap and success probability by introducing intermediate Hamiltonians that modify the evolution path between initial and final Hamiltonians. We focus on an optimization problem relevant to recent hardware implementations and present numerical evidence for the existence of a purely local intermediate Hamiltonian that achieve the optimum performance in terms of pushing the minimum gap to one of the end points of the evolution. As a part of this study we develop a convex optimization formulation of the search for optimal adiabatic schedules that makes this computation more tractable, and which may be of independent interest. We further study the effectiveness of random intermediate Hamiltonians on the minimum gap and success probability, and empirically find that random Hamiltonians have a significant probability of increasing the success probability, but only by a modest amount.
Abstract Adiabatic quantum computing and optimization have garnered much attention recently as possible models for achieving a quantum advantage over classical approaches to optimization and other special purpose computations. Both techniques are probabilistic in nature and the minimum gap between the ground state and first excited state of the system during evolution is a major factor in determining the success probability. In this work we investigate a strategy for increasing the minimum gap and success probability by introducing intermediate Hamiltonians that modify the evolution path between initial and final Hamiltonians. We focus on an optimization problem relevant to recent hardware implementations and present numerical evidence for the existence of a purely local intermediate Hamiltonian that achieve the optimum performance in terms of pushing the minimum gap to one of the end points of the evolution. As a part of this study we develop a convex optimization formulation of the search for optimal adiabatic schedules that makes this computation more tractable, and which may be of independent interest. We further study the effectiveness of random intermediate Hamiltonians on the minimum gap and success probability, and empirically find that random Hamiltonians have a significant probability of increasing the success probability, but only by a modest amount.
We explore the relationship between two figures of merit for an adiabatic quantum computation process: the success probability P and the minimum gap Δ min between the ground and first excited states, investigating to what extent the success probability for an ensemble of problem Hamiltonians can be fitted by a function of Δ min and the computation time T . We study a generic adiabatic algorithm and show that a rich structure exists in the distribution of P and Δ min . In the case of two qubits, P is to a good approximation a function of Δ min , of the stage in the evolution at which the minimum occurs and of T . This structure persists in examples of larger systems.
Adiabatic quantum computation is based on the adiabatic evolution of quantum systems. We analyze a particular class of quantum adiabatic evolutions where either the initial or final Hamiltonian is a one-dimensional projector Hamiltonian on the corresponding ground state. The minimum-energy gap, which governs the time required for a successful evolution, is shown to be proportional to the overlap of the ground states of the initial and final Hamiltonians. We show that such evolutions exhibit a rapid crossover as the ground state changes abruptly near the transition point where the energy gap is minimum. Furthermore, a faster evolution can be obtained by performing a partial adiabatic evolution within a narrow interval around the transition point. These results generalize and quantify earlier works.
Adiabatic quantum computation employs a slow change of a time-dependent control function (or functions) to interpolate between an initial and final Hamiltonian, which helps to keep the system in the instantaneous ground state. When the evolution time is finite, the degree of adiabaticity (quantified in this work as the average ground-state population during evolution) depends on the particulars of a dynamic trajectory associated with a given set of control functions. We use quantum optimal control theory with a composite objective functional to numerically search for controls that achieve the target final state with a high fidelity while simultaneously maximizing the degree of adiabaticity. Exploring the properties of optimal adiabatic trajectories in model systems elucidates the dynamic mechanisms that suppress unwanted excitations from the ground state. Specifically, we discover that the use of multiple control functions makes it possible to access a rich set of dynamic trajectories, some of which attain a significantly improved performance (in terms of both fidelity and adiabaticity) through the increase of the energy gap during most of the evolution time.
Adiabatic quantum computation is a form of computation that acts by slowly interpolating a quantum system between an easy to prepare initial state and a final state that represents a solution to a given computational problem. The choice of the interpolation schedule is critical to the performance: if at a certain time point, the evolution is too rapid, the system has a high probability to transfer to a higher energy state, which does not represent a solution to the problem. On the other hand, an evolution that is too slow leads to a loss of computation time and increases the probability of failure due to decoherence. In this work, we train deep neural models to produce optimal schedules that are conditioned on the problem at hand. We consider two types of problem representation: the Hamiltonian form, and the Quadratic Unconstrained Binary Optimization (QUBO) form. A novel loss function that scores schedules according to their approximated success probability is introduced. We benchmark our approach on random QUBO problems, Grover search, 3-SAT, and MAX-CUT problems and show that our approach outperforms, by a sizable margin, the linear schedules as well as alternative approaches that were very recently proposed.
Adiabatic quantum optimization is a procedure to solve a vast class of optimization problems by slowly changing the Hamiltonian of a quantum system. The evolution time necessary for the algorithm to be successful scales inversely with the minimum energy gap encountered during the dynamics. Unfortunately, the direct calculation of the gap is strongly limited by the exponential growth in the dimensionality of the Hilbert space associated to the quantum system. Although many special-purpose methods have been devised to reduce the effective dimensionality, they are strongly limited to particular classes of problems with evident symmetries. Moreover, little is known about the computational power of adiabatic quantum optimizers in real-world conditions. Here we propose and implement a general purposes reduction method that does not rely on any explicit symmetry and which requires, under certain general conditions, only a polynomial amount of classical resources. Thanks to this method, we are able to analyze the performance of ``nonideal'' quantum adiabatic optimizers to solve the well-known Grover problem, namely the search of target entries in an unsorted database, in the presence of discrete local defects. In this case, we show that adiabatic quantum optimization, even if affected by random noise, is still potentially faster than any classical algorithm.
Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian H(s) with spectral gap γ(s). Assuming the existence of an oracle Γ such that $γ_\min = Θ\left(\min_sΓ(s)\right)$, we provide an algorithm that reliably performs QAO in time $O\left(γ_\min^{-1}\right)$ with $O\left(\log(γ_\min^{-1})\right)$ oracle queries, where $γ_\min = \min_s γ(s)$. Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that ∥dH/ds∥≈γ(s) and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle Γ for the problem of finding the minimum point m=argminuW(u) of the cost function W:V⟶[0,1], restricting ourselves to computational basis measurements and driving Hamiltonian H(0)=I−∣V∣−1∑u,v∈V∣u⟩⟨v∣. Requiring only that W have a constant lower bound on its spectral gap and upper bound κ on its spectral ratio, our QAO algorithm returns m with probability (1−ε)(1−e−1/ε) in time O(ε−1[∣V∣+(κ−1)2/3∣V∣2/3]). This achieves a quantum advantage for all κ, and recovers Grover scaling up to logarithmic factors when κ≈1. We implement the algorithm as a subroutine in an optimization procedure that produces m with exponentially small failure probability and expected runtime O(ε−1[∣V∣+(κ−1)2/3∣V∣2/3]) even when κ is not known beforehand.