FROM THE QUBIT TO THE QUANTUM SEARCH ALGORITHMS

Mr. K. Suresh Babu Dr. T. P. Anish Dr. Cornelius K

BAO JINGE

Mrs. Sri Lavanya Sajja Dr. L. Sherly Puspha Annabel Dr. Chatrapathy K

Zijian Diao, Goong Chen

Victor M. Kureichik

Lawrence M. Ioannou, Michele Mosca

Let H(t) = (1 - t/T)H0 + (t/T)H1, t ∈ [0,T], be the Hamiltonian governing an adiabatic quantum algorithm, where H0 is diagonal in the Hadamard basis and H1 is diagonal in the computational basis. We prove that H0 and H1 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.