Limitations of some simple adiabatic quantum algorithms
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
Let $H(t)=(1-t/T)H_0 + (t/T)H_1$, $t\in [0,T]$, be the Hamiltonian governing an adiabatic quantum algorithm, where $H_0$ is diagonal in the Hadamard basis and $H_1$ is diagonal in the computational basis. We prove that $H_0$ and $H_1$ must each have at least two large mutually-orthogonal eigenspaces if the algorithm's running time is to be subexponential in the number of qubits. We also reproduce the optimality proof of Farhi and Gutmann's search algorithm in the context of this adiabatic scheme; because we only consider initial Hamiltonians that are diagonal in the Hadamard basis, our result is slightly stronger than the original.
This work originally appeared in L. Ioannou's Master's thesis, submitted to the University of Waterloo, in 2002 (available at http://etheses.uwaterloo.ca/)
This work originally appeared in L. Ioannou's Master's thesis, submitted to the University of Waterloo, in 2002 (available at http://etheses.uwaterloo.ca/)