Zum Inhalt
Erweiterte Suche
Anmelden
Nach oben
Quantum Information Processing

Faster search by lackadaisical quantum walk

  • 01.03.2018
Erschienen in:
Verfasst von
Thomas G. Wong
Erschienen in
Quantum Information Processing | Ausgabe 3/2018

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In the typical model, a discrete-time coined quantum walk searching the 2D grid for a marked vertex achieves a success probability of \(O(1/\log N)\) in \(O(\sqrt{N \log N})\) steps, which with amplitude amplification yields an overall runtime of \(O(\sqrt{N} \log N)\). We show that making the quantum walk lackadaisical or lazy by adding a self-loop of weight 4 / N to each vertex speeds up the search, causing the success probability to reach a constant near 1 in \(O(\sqrt{N \log N})\) steps, thus yielding an \(O(\sqrt{\log N})\) improvement over the typical, loopless algorithm. This improved runtime matches the best known quantum algorithms for this search problem. Our results are based on numerical simulations since the algorithm is not an instance of the abstract search algorithm.

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Jetzt einloggen Kostenlos registrieren

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriger Artikel Quantum pattern recognition with multi-neuron interactions
Nächster Artikel Open quantum random walk in terms of quantum Bernoulli noise
Titel
Faster search by lackadaisical quantum walk
Verfasst von
Thomas G. Wong
Publikationsdatum
01.03.2018
Verlag
Springer US
Erschienen in
Quantum Information Processing / Ausgabe 3/2018
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-018-1840-y
Dieser Inhalt ist nur sichtbar, wenn du eingeloggt bist und die entsprechende Berechtigung hast.

Weitere Artikel der Ausgabe 3/2018

An economical state-dependent telecloning for a multiparticle GHZ state

Deterministic remote preparation of arbitrary multi-qubit equatorial states via two-qubit entangled states

Measurement-device-independent quantum key distribution with multiple crystal heralded source with post-selection

The statistical fluctuation study of quantum key distribution in means of uncertainty principle

Quantum metrology of phase for accelerated two-level atom coupled with electromagnetic field with and without boundary

Steady-state entanglement and thermalization of coupled qubits in two common heat baths