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 1/2021

01.01.2021

Upperbounds on the probability of finding marked connected components using quantum walks

verfasst von: Adam Glos, Nikolajs Nahimovs, Konstantin Balakirev, Kamil Khadiev

Erschienen in: Quantum Information Processing | Ausgabe 1/2021

Einloggen

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

search-config
loading …

Abstract

Quantum walk search may exhibit phenomena beyond the intuition from a conventional random walk theory. One of such examples is exceptional configuration phenomenon—it appears that it may be much harder to find any of two or more marked vertices, that if only one of them is marked. In this paper, we analyze the probability of finding any of marked vertices in such scenarios and prove upperbounds for various sets of marked vertices. We apply the upperbounds to large collection of graphs and show that the quantum search may be slow even when taking real-world networks.
Vorheriger Artikel Single plasmon router with two quantum dots side coupled to two plasmonic waveguides with a junction
Nächster Artikel Analysis of efficient and secure dynamic quantum secret sharing protocol based on Bell states

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
The existence of stationary states is not a universal phenomenon, but a feature of a quantum walk model. For DTQW model, it depends on a coin transformation used by the walk [11].
 
2
More precisely, of the step of the quantum walk with a set of marked vertices \(V_M\).
 
Literatur
1.
Portugal, R.: Quantum Walks and Search Algorithms. Springer, New York (2013)CrossRef
2.
Aharonov, Y., Davidovich, L., Zagury, N.: Quantum random walks. Phys. Rev. A 48(2), 1687–1690 (1993)ADSCrossRef
3.
4.
5.
Shenvi, N., Kempe, J., Whaley, K.B.: A quantum random walk search algorithm. Phys. Rev. A 67, 052307 (2003)ADSCrossRef
6.
Ambainis, A., Rivosh, A.: Quantum walks with multiple or moving marked locations. In: Proceedings of SOFSEM, pp. 485–496 (2008)
7.
Wong, T.G., Ambainis, A.: Quantum search with multiple walk steps per oracle query. Phys. Rev. A 92, 022338 (2015)ADSCrossRef
8.
Nahimovs, N., Rivosh, A.: Quantum walks on two-dimensional grids with multiple marked locations. In: Proceedings of SOFSEM 2016, vol. 9587, pp. 381–391 (2016). arXiv:​1507.​03788
9.
Nahimovs, N., Rivosh, A.: Exceptional configurations of quantum walks with Grover’s coin. In: Proceedings of MEMICS, pp. 79–92 (2015)
10.
Nahimovs, N., Santos, R.: Adjacent vertices can be hard to find by quantum walks. In: Proceedings of SOFSEM 2017, vol. 10139, pp. 256–267 (2017)
11.
Prūsis, K., Vihrovs, J., Wong, T.G.: Stationary states in quantum walk search. Phys. Rev. A 94, 032334 (2016)ADSCrossRef
12.
Ambainis, A., Gilyén, A., Jeffery, S., Kokainis, M.: Quadratic speedup for finding marked vertices by quantum walks (2019) arXiv preprint arXiv:​1903.​07493
13.
Glos, A., Miszczak, J.A.: Impact of the malicious input data modification on the efficiency of quantum spatial search. Quantum Inf. Process. 18(11), 343 (2019)ADSMathSciNetCrossRef
14.
Nahimovs, N., Santos, R.A., Khadiev, K.: Adjacent vertices can be hard to find by quantum walks. Mosc. Univ. Comput. Math. Cybern. 43(1), 32–39 (2019)MathSciNetCrossRef
15.
Khadiev, K., Nahimovs, N., Santos, R.A.M.: On the probability of finding marked connected components using quantum walks. Lobachevskii J. Math. 39, 1016–1023 (2018)MathSciNetCrossRef
16.
Sadowski, P., Miszczak, J.A., Ostaszewski, M.: Lively quantum walks on cycles. J. Phys. A Math. Theor. 49(37), 375302 (2016)MathSciNetCrossRef
17.
Glos, A., Nahimovs, N.: Comment on Nahimovs et al. ‘On the probability of finding marked connected components using quantum walks (2019). arXiv preprint arXiv:​1907.​12277
18.
Erdős, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5(1), 17–60 (1960)MathSciNetMATH
19.
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440 (1998)ADSCrossRef
20.
21.
Flaxman, A., Frieze, A., Fenner, T.: High degree vertices and eigenvalues in the preferential attachment graph. Internet Math. 2(1), 1–19 (2005)MathSciNetCrossRef
22.
Bollobás, B.E., Riordan, O., Spencer, J., Tusnády, G.: The degree sequence of a scale-free random graph process. Random Struct. Algorithms 18(3), 279–290 (2001)MathSciNetCrossRef
Metadaten
Titel
Upperbounds on the probability of finding marked connected components using quantum walks
verfasst von
Adam Glos
Nikolajs Nahimovs
Konstantin Balakirev
Kamil Khadiev
Publikationsdatum
01.01.2021
Verlag
Springer US
Erschienen in
Quantum Information Processing / Ausgabe 1/2021
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-020-02939-4

Weitere Artikel der Ausgabe 1/2021

Quantum Information Processing 1/2021 Zur Ausgabe

OriginalPaper

Information gain and systems entanglement in tripartite measurement model

OriginalPaper

Performance improvement of unidimensional continuous-variable quantum key distribution using zero-photon quantum catalysis

OriginalPaper

Controlled asymmetric bidirectional quantum teleportation of two- and three-qubit states

OriginalPaper

The uncertainty of quantum channels in terms of variance

OriginalPaper

Non-locality and entanglement in multi-qubit systems from a unified framework

OriginalPaper

Quantum acceleration by an ancillary system in non-Markovian environments

Neuer Inhalt

    Bildnachweise