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. 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 $\sqrt{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.

References in corpus (1)

• Spatial search by quantum walk

Cited by in corpus (15)

• Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Quantum search algorithms on a regular lattice
• Directional correlations in quantum walks with two particles
• Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2
• Microwave Experiments Simulating Quantum Search and Directed Transport in Artificial Graphene
• Quantum walks and quantum search on graphene lattices
• High-dimensional quantum state transfer in a noisy network environment
• The quantum walk search algorithm: Factors affecting efficiency
• Quantum walk based state transfer algorithms on the complete M-partite graph
• Doubling the Success of Quantum Walk Search Using Internal-State Measurements
• Robust Diabatic Quantum Search by Landau-Zener-Stückelberg Oscillations
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
• Quantum walk state transfer on a hypercube
• Search and state transfer between hubs by quantum walks