Global Symmetry is Unnecessary for Fast Quantum Search
2014 (English)In: Physical Review Letters, ISSN 0031-9007, Vol. 112, no 21, 210502- p.Article in journal (Refereed) Published
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 three-dimensional subspace but most have no 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 speed-up of Theta(root N), disproving the intuition that fast quantum search requires global symmetry.
Place, publisher, year, edition, pages
2014. Vol. 112, no 21, 210502- p.
IdentifiersURN: urn:nbn:se:kth:diva-147422DOI: 10.1103/PhysRevLett.112.210502ISI: 000336765200003ScopusID: 2-s2.0-84901675814OAI: oai:DiVA.org:kth-147422DiVA: diva2:731178
QC 201407012014-07-012014-06-272014-07-01Bibliographically approved