Bounding Run-Times of Local Adiabatic Algorithms

DOI10.1007/978-3-540-72504-6_41zbMATH Open1198.68150arXivquant-ph/0701147OpenAlexW2124911447MaRDI QIDQ5425456

M. V. Panduranga Rao

Publication date: 13 November 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: A common trick for designing faster quantum adiabatic algorithms is to apply the adiabaticity condition locally at every instant. However it is often difficult to determine the instantaneous gap between the lowest two eigenvalues, which is an essential ingredient in the adiabaticity condition. In this paper we present a simple linear algebraic technique for obtaining a lower bound on the instantaneous gap even in such a situation. As an illustration, we investigate the adiabatic unordered search of van Dam et al. (How powerful is adiabatic quantum computation? Proc. IEEE FOCS, pp. 279-287, 2001) and Roland and Cerf (Physical Review A 65, 042308, 2002) when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in $logN$, where $N$ is the length of the unordered list) amount. We use our technique to derive a bound on the running time of a local adiabatic schedule in terms of the minimum gap between the lowest two eigenvalues.

Full work available at URL: https://arxiv.org/abs/quant-ph/0701147

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (2)

Error-run-time trade-off in the adiabatic approximation beyond scaling relations ⋮ On barren plateaus and cost function locality in variational quantum algorithms

This page was built for publication: Bounding Run-Times of Local Adiabatic Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5425456)