Quantum search algorithms on the hypercube

We investigate a set of discrete-time quantum search algorithms on the n-dimensional hypercube following a proposal by Shenvi et al (2003 Phys. Rev. A 67 052307). 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 = 2n, the number of vertices. In analogy to Grover's algorithm, the spatial search is effectively facilitated through a rotation in a two-level subspace 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 two-level subspaces at the avoided crossings and derive improved estimates on the search times