Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Global Symmetry is Unnecessary for Fast Quantum Search
KTH, School of Engineering Sciences (SCI), Physics.
2014 (English)In: Physical Review Letters, ISSN 0031-9007, E-ISSN 1079-7114, Vol. 112, no 21, 210502- p.Article in journal (Refereed) Published
Abstract [en]

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.
National Category
Physical Sciences
Identifiers
URN: urn:nbn:se:kth:diva-147422DOI: 10.1103/PhysRevLett.112.210502ISI: 000336765200003Scopus ID: 2-s2.0-84901675814OAI: oai:DiVA.org:kth-147422DiVA: diva2:731178
Note

QC 20140701

Available from: 2014-07-01 Created: 2014-06-27 Last updated: 2017-12-05Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Janmark, Jonatan
By organisation
Physics
In the same journal
Physical Review Letters
Physical Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 23 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf