Verbesserte Quantenabfragekomplexität bei einfacheren Eingaben

Verbesserte Quantenabfragekomplexität bei einfacheren Eingaben

Zeitstempel: 8. April 2024, 11:29 Uhr

Noel T. Anderson1, Jay-U Chung1, Shelby Kimmel1, Da-Yeon Koh2, und Xiaohan Ye1,3

1Middlebury College, Middlebury, VT, USA
2Williams College, Williamstown, MA, USA
3Brown University, Providence, Rhode Island, USA

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Quantum-Span-Programmalgorithmen zur Funktionsauswertung haben manchmal eine geringere Abfragekomplexität, wenn versprochen wird, dass die Eingabe eine bestimmte Struktur hat. Wir entwerfen einen modifizierten Span-Programmalgorithmus, um zu zeigen, dass diese Verbesserungen auch ohne vorherige Zusage bestehen bleiben, und wir erweitern diesen Ansatz auf das allgemeinere Problem der Zustandsumwandlung. Als Anwendung beweisen wir exponentielle und superpolynomielle Quantenvorteile in der durchschnittlichen Abfragekomplexität für mehrere Suchprobleme und verallgemeinern Montanaros Search with Advice [Montanaro, TQC 2010].

Verbesserte Quantenabfragekomplexität bei einfacheren Eingaben PlatoBlockchain Data Intelligence. Vertikale Suche. Ai.

Ausgewähltes Bild: Entscheidungsbaum, der zur Erstellung eines unserer Algorithmen verwendet wird.

Populäre Zusammenfassung

Wir gehen davon aus, dass Quantenalgorithmen wie klassische Algorithmen bei einfacheren Eingaben schneller laufen sollten. Wenn Sie beispielsweise nach einem Element in einer ungeordneten Liste suchen und es viele Kopien dieses Elements gibt, würden wir erwarten, dass der Quantenalgorithmus in dieser Situation schneller läuft, als wenn es nur ein markiertes Element gibt, auch ohne es zu wissen die Anzahl der Zielelemente im Voraus. Tatsächlich ist für das Problem der Suche bekannt, wie man bei einfacheren Eingaben einen solchen Vorteil erzielen kann. Die Verallgemeinerung dieser Idee auf Probleme, die über die Suche hinausgehen, ist jedoch schwierig, wenn es keine offensichtliche Möglichkeit gibt, zu kennzeichnen, wann die Berechnung lange genug ausgeführt wurde. Wir modifizieren mehrere gängige algorithmische Frameworks im Abfragemodell, um Flags zu erstellen, die uns darauf aufmerksam machen, ob die Berechnung lange genug ausgeführt wurde, sodass wir den Algorithmus bei einfacheren Eingaben frühzeitig beenden können, ohne vorher zu wissen, ob die Instanz einfach oder schwierig ist. Als Anwendung können wir bei gegebener Verteilung sowohl einfacher als auch schwieriger Eingaben zu einem Problem die durchschnittliche Abfragekomplexität analysieren. Wir zeigen, dass bestimmte Eingabeverteilungen für Suchprobleme große durchschnittliche Quantenabfragevorteile gegenüber klassischen Algorithmen bieten.

► BibTeX-Daten

► Referenzen

[1] Andris Ambainis und Ronald de Wolf. Quantenabfragekomplexität im durchschnittlichen Fall. Journal of Physics A: Mathematical and General, 34(35):6741, 2001. doi:10.1088/​0305-4470/​34/​35/​302.
https:/​/​doi.org/​10.1088/​0305-4470/​34/​35/​302

[2] Dorit Aharonov. Quantenberechnung. Annual Reviews of Computational Physics VI, Seiten 259–346, 1999. doi:10.1142/9789812815569_0007.
https: / / doi.org/ 10.1142 / 9789812815569_0007

[3] Michel Boyer, Gilles Brassard, Peter Høyer und Alain Tapp. Enge Grenzen für die Quantensuche. Fortschritte der Physik, 46(4-5):493–505, 1998. doi:10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2 -P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[4] Aleksandrs Belovs. Span-Programme für Funktionen mit 1-Zertifikaten konstanter Größe: Erweiterte Zusammenfassung. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12, Seiten 77–84, 2012. doi:10.1145/​2213977.2213985.
https: / / doi.org/ 10.1145 / 2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca und Alain Tapp. Quantenamplitudenverstärkung und -schätzung. In Quantenberechnung und -information, Band 305 von Contemp. Math., Seiten 53–74. Amer. Mathematik. Soc., Providence, RI, 2002. doi:10.1090/​conm/​305/​05215.
https: / / doi.org/ 10.1090 / conm / 305/05215

[6] Gilles Brassard, Peter Høyer und Alain Tapp. Quantenzählung. In Automata, Languages ​​and Programming, Seiten 820–831, 1998. doi:10.1007/​BFb0055105.
https: / / doi.org/ 10.1007 / BFb0055105

[7] Aleksandrs Belovs und Ben W. Reichardt. Span-Programme und Quantenalgorithmen für ST-Konnektivität und Klauenerkennung. Vorlesungsunterlagen in Informatik, 7501 LNCS:193–204, 2012. doi:10.1007/978-3-642-33090-2_18.
https:/​/​doi.org/​10.1007/​978-3-642-33090-2_18

[8] Aleksandrs Belovs und Ansis Rosmanis. Enge untere Quantengrenze für das Näherungszählen mit Quantenzuständen. 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] Salman Beigi und Leila Taghavi. Quantenbeschleunigung basierend auf klassischen Entscheidungsbäumen. Quantum, 4:241, 2020. doi:10.22331/​q-2020-03-02-241.
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

[10] Aleksandrs Belovs und Duyal Yolcu. One-Way-Ticket nach Las Vegas und zum Quantengegner. 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] Richard. Cleve, Artur. Ekert, Chiara Macchiavello und Michele Mosca. Quantenalgorithmen neu interpretiert. Tagungsband der Royal Society of London. Serie A: Mathematical, Physical and Engineering Sciences, 454(1969):339–354, 1998. doi:10.1098/​rspa.1998.0164.
https: / / doi.org/ 10.1098 / rspa.1998.0164

[12] Arjan Cornelissen, Stacey Jeffery, Maris Ozols und Alvaro Piedrafita. Span-Programme und Quantenzeitkomplexität. Im 45. Internationalen Symposium über mathematische Grundlagen der Informatik (MFCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. doi:10.4230/​LIPIcs.MFCS.2020.26.
https: // doi.org/ 10.4230 / LIPIcs.MFCS.2020.26

[13] Chris Cade, Ashley Montanaro und Aleksandrs Belovs. Zeit- und raumeffiziente Quantenalgorithmen zur Erkennung von Zyklen und zum Testen der Bipartitität. Quantum Information & Computation, 18(1-2):18–50, 2018.

[14] Kai DeLorenzo, Shelby Kimmel und R. Teal Witter. Anwendungen des Quantenalgorithmus für st-Konnektivität. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), Seiten 6:1–6:14, 2019. doi:10.4230/​LIPIcs.TQC.2019.6.
https: // doi.org/ 10.4230 / LIPIcs.TQC.2019.6

[15] Dmitry Grinko, Julien Gacon, Christa Zoufal und Stefan Woerner. Iterative Quantenamplitudenschätzung. npj Quantum Information, 7(1):52, März 2021. doi:10.1038/​s41534-021-00379-1.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] Liebe K. Grover. Quantenmechanik hilft bei der Suche nach der Nadel im Heuhaufen. Physical Review Letters, 79(2):325–328, 1997. doi:10.1103/​PhysRevLett.79.325.
https://doi.org/ 10.1103/PhysRevLett.79.325

[17] Wassily Höffding. Wahrscheinlichkeitsungleichungen für Summen beschränkter Zufallsvariablen. Journal of the American Statistical Association, 58(301):13–30, 1963. doi:10.1080/​01621459.1963.10500830.
https: / / doi.org/ 10.1080 / 01621459.1963.10500830

[18] Tsuyoshi Ito und Stacey Jeffery. Ungefähre Spannenprogramme. Algorithmica, 81(6):2158–2195, 2019. doi:10.1007/​s00453-018-0527-1.
https:/​/​doi.org/​10.1007/​s00453-018-0527-1

[19] Michael Jarret, Stacey Jeffery, Shelby Kimmel und Alvaro Piedrafita. Quantenalgorithmen für Konnektivität und verwandte Probleme. In 26th Annual European Symposium on Algorithms (ESA 2018), Seiten 49:1–49:13, 2018. doi:10.4230/​LIPIcs.ESA.2018.49.
https: // doi.org/ 10.4230 / LIPIcs.ESA.2018.49

[20] Alexei Y. Kitaev. Quantenmessungen und das Abelsche Stabilisatorproblem. 1995. arXiv:quant-ph/​9511026.
arXiv: quant-ph / 9511026

[21] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek und Mario Szegedy. Quantenabfragekomplexität der Zustandsumwandlung. Im Jahr 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Seiten 344–353, 2011. doi:10.1109/​FOCS.2011.75.
https: / / doi.org/ 10.1109 / FOCS.2011.75

[22] Frédéric Magniez, Ashwin Nayak, Jérémie Roland und Miklos Santha. Suche über Quantum Walk. SIAM Journal on Computing, 40(1):142–164, 2011. doi:10.1137/​090745854.
https: / / doi.org/ 10.1137 / 090745854

[23] Ashley Montanaro. Quantensuche mit Beratung. In der Konferenz über Quantenberechnung, Kommunikation und Kryptographie, Seiten 77–93. Springer, 2010. doi:10.1007/978-3-642-18073-6_7.
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_7

[24] Ben W. Reichardt. Span-Programme und Komplexität von Quantenabfragen: Die allgemeine Gegnergrenze ist für jede boolesche Funktion nahezu eng. 50. jährliches IEEE-Symposium zu Grundlagen der Informatik, Seiten 544–551, 2009. doi:10.1109/​FOCS.2009.55.
https: / / doi.org/ 10.1109 / FOCS.2009.55

[25] Ben W. Reichardt. Überlegungen zu Quantenabfragealgorithmen. In Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Seiten 560–569. 2011. doi:10.1137/​1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44

[26] Leila Taghavi. Vereinfachter Quantenalgorithmus für das Oracle-Identifizierungsproblem. Quantum Machine Intelligence, 4(2):19, 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

Zitiert von

[1] Stacey Jeffery, Shelby Kimmel und Alvaro Piedrafita, „Quantum Algorithm for Path-Edge Sampling“, arXiv: 2303.03319, (2023).

[2] Michael Czekanski, Shelby Kimmel und R. Teal Witter, „Robust and Space-Efficient Dual Adversary Quantum Query Algorithms“, arXiv: 2306.15040, (2023).

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2024, 04:11:15 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2024-04-11 15:45:17).

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.

Zeitstempel:

Mehr von Quantenjournal