Quantum search algorithms on the hypercube
Birgit Hein, Gregor Tanner · Journal of Physics A Mathematical and Theoretical · 2009
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 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 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.