Quantum search algorithms on the hypercube

DOI10.1088/1751-8113/42/8/085303zbMATH Open1157.81006arXiv0906.3094OpenAlexW2000620635MaRDI QIDQ3608959FDOQ3608959

Authors: Birgit Hein, Gregor Tanner 

Publication date: 6 March 2009

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

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 $sqrtN$ 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.

Full work available at URL: https://arxiv.org/abs/0906.3094

Recommendations

• Quantum search of spatial regions
• Search on a hypercubic lattice using a quantum random walk. I. \(d>2\)
• Search on a hypercubic lattice using a quantum random walk. II. \(d=2\)
• Spatial search using the discrete time quantum walk
• Spatial search and the Dirac equation

Mathematics Subject Classification ID

Search theory (90B40) Quantum computation (81P68)

Cited In (13)

• Parametric quantum search algorithm by CP maps: algebraic, geometric and complexity aspects
• Quantum search in a possible three-dimensional complex subspace
• HIERARCHICAL QUANTUM SEARCH
• Strong dispersion property for the quantum walk on the hypercube
• Quantum search of spatial regions
• Search on a hypercubic lattice using a quantum random walk. II. \(d=2\)
• Title not available (Why is that?)
• The quantum walk search algorithm: factors affecting efficiency
• Scheme for Implementing Quantum Search Algorithm in a Cluster State Quantum Computer
• Directional correlations in quantum walks with two particles
• Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
• Title not available (Why is that?)
• Search on a hypercubic lattice using a quantum random walk. I. \(d>2\)

This page was built for publication: Quantum search algorithms on the hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608959)