Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Quantum Information Processing
Erschienen in: Quantum Information Processing 11/2016

01.11.2016

Szegedy’s quantum walk with queries

verfasst von: Raqueline A. M. Santos

Erschienen in: Quantum Information Processing | Ausgabe 11/2016

Einloggen

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

search-config
loading …

Abstract

When searching for a marked vertex in a graph, Szegedy’s usual search operator is defined by using the transition probability matrix of the random walk with absorbing barriers at the marked vertices. Instead of using this operator, we analyze searching with Szegedy’s quantum walk by using reflections around the marked vertices, that is, the standard form of quantum query. We show we can boost the probability to 1 of finding a marked vertex in the complete graph. Numerical simulations suggest that the success probability can be improved for other graphs, like the two-dimensional grid. We also prove that, for a certain class of graphs, we can express Szegedy’s search operator, obtained from the absorbing walk, using the standard query model.
Vorheriger Artikel Least significant qubit algorithm for quantum images
Nächster Artikel Simulating Weyl points and nodal loops in an optical superlattice

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
Fußnoten
1
A strongly regular graph is a regular graph where every two adjacent vertices have \(\lambda \) common neighbors and every two non-adjacent vertices have \(\mu \) common neighbors.
 
Literatur
1.
Shenvi, N., Kempe, J., Whaley, K.B.: A quantum random walk search algorithm. Phys. Rev. A 67, 1–11 (2003)
2.
Childs, A., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A 70, 1–11 (2004)
3.
Ambainis, A.: Quantum walk algorithm for element distinctness. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (2004)
4.
Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1099–1108 (2005)
5.
Krovi, H., Magniez, F., Ozols, M., Roland, J.: Finding is as easy as detecting for quantum walks. In: Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming, pp. 540–551 (2010)
6.
7.
Aharonov, Y., Davidovich, L., Zagury, N.: Quantum random walks. Phys. Rev. A 48(2), 1687–1690 (1993)ADSCrossRef
8.
9.
Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th Symposium on Foundations of Computer Science, pp. 32–41 (2004)
10.
11.
Santos, R.A.M., Portugal, R.: Quantum hitting time on the complete graph. Int. J. Quant. Inf. 8(5), 881–894 (2010)CrossRefMATH
12.
Portugal, R., Santos, R.A.M., Fernandes, T.D., Gonçalves, D.N.: The staggered quantum walk model. Quant. Inf. Process. 15(1), 85–101 (2015)ADSMathSciNetCrossRefMATH
13.
Portugal, R.: Establishing the equivalence between Szegedy’s and coined quantum walks using the staggered model. Quant. Inf. Process. 5(4), 1387–1409 (2016)
14.
15.
16.
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th ACM Symposium on the Theory of Computing, pp. 212–219 (1996)
17.
Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510–1523 (1997)MathSciNetCrossRefMATH
18.
Prūsis, K., Vihrovs, J., Wong, T.G.: Doubling the success of quantum walk search using internal-state measurements. arXiv:​1511.​03865 [quant-ph] (2015)
Metadaten
Titel
Szegedy’s quantum walk with queries
verfasst von
Raqueline A. M. Santos
Publikationsdatum
01.11.2016
Verlag
Springer US
Erschienen in
Quantum Information Processing / Ausgabe 11/2016
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-016-1427-4

Weitere Artikel der Ausgabe 11/2016

Quantum Information Processing 11/2016 Zur Ausgabe

OriginalPaper

Detecting relay attacks on RFID communication systems using quantum bits

OriginalPaper

New quantum codes from dual-containing cyclic codes over finite rings

OriginalPaper

A comparative study of protocols for secure quantum communication under noisy environment: single-qubit-based protocols versus entangled-state-based protocols

OriginalPaper

Classical–quantum arbitrarily varying wiretap channel: Ahlswede dichotomy, positivity, resources, super-activation

OriginalPaper

Simulating Weyl points and nodal loops in an optical superlattice

OriginalPaper

High-capacity quantum key distribution using Chebyshev-map values corresponding to Lucas numbers coding

Neuer Inhalt

    Bildnachweise