paper

Global Symmetry is Unnecessary for Fast Quantum Search

arXiv:1403.2228 · doi:10.1103/PhysRevLett.112.210502

Abstract

Grover's quantum search algorithm can be formulated as a quantum particle randomly walking on the (highly symmetric) complete graph, with one vertex marked by a nonzero potential. From an initial equal superposition, the state evolves in a two-dimensional subspace. Strongly regular graphs have a local symmetry that ensures that the state evolves in a \emph{three}-dimensional subspace, but most have no \emph{global} symmetry. Using degenerate perturbation theory, we show that quantum random walk search on known families of strongly regular graphs nevertheless achieves the full quantum speedup of , disproving the intuition that fast quantum search requires global symmetry.

4 pages, 2 figures

References in corpus (1)

Cited by in corpus (56)