Quantum search algorithms on the hypercube

Abstract

We investigate a set of discrete-time quantum search algorithms on the n-dimensional hypercube following a proposal by Shenvi, Kempe and Whaley [1]. We show that there exists a whole class of quantum search algorithms in the symmetry reduced space which perform a search of a marked vertex in time of order √ N where N = 2 n, the number of vertices. In analogy to Grover’s algorithm, the spatial search is effectively facilitated through a rotation in a two-level sub-space of the full Hilbert space. In the hypercube, these two-level systems are introduced through avoided crossings. We give estimates on the quantum states forming the 2-level sub-spaces at the avoided crossings and derive improved estimates on the search times. 1