  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.
