Quantum search algorithms on the hypercube

DOI10.1088/1751-8113/42/8/085303zbMATH Open1157.81006OpenAlexW2000620635MaRDI 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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(14)

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

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)