Grundlegende Quantenunterprogramme: Finden mehrerer markierter Elemente und Summieren von Zahlen

Grundlegende Quantenunterprogramme: Finden mehrerer markierter Elemente und Summieren von Zahlen

Zeitstempel: 14. März 2024, 9:40 Uhr
Grundlegende Quantenunterprogramme: Finden mehrerer markierter Elemente und Summieren von Zahlen PlatoBlockchain Data Intelligence. Vertikale Suche. Ai.

Joran van Apeldoorn1, Sander Gribling2 und Harold Nieuwboer3

1IViR und QuSoft, Universität Amsterdam, Niederlande
2Abteilung für Ökonometrie und Operations Research, Universität Tilburg, Tilburg, Niederlande
3Korteweg-de-Vries-Institut für Mathematik und QuSoft, Universität Amsterdam, Niederlande und Fakultät für Informatik, Ruhr-Universität Bochum, Deutschland und Fakultät für Mathematische Wissenschaften, Universität Kopenhagen, Dänemark

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

Abstrakt

Wir zeigen, wie man alle mit $k$ markierten Elemente in einer Liste der Größe $N$ findet, indem man die optimale Anzahl $O(sqrt{N k})$ von Quantenabfragen und nur einen polylogarithmischen Overhead in der Gatterkomplexität verwendet, in der Einstellung wo man hat ein kleines Quantengedächtnis. Frühere Algorithmen verursachten entweder einen Overhead von Faktor $k$ bei der Gate-Komplexität oder hatten einen zusätzlichen Faktor $log(k)$ bei der Abfragekomplexität.
Wir betrachten dann das Problem, eine multiplikative $delta$-Approximation von $s = sum_{i=1}^N v_i$ zu finden, wobei $v=(v_i) in [0,1]^N$, gegebener Quantenabfragezugriff auf eine binäre Beschreibung von $v$. Wir geben einen Algorithmus an, der dies mit einer Wahrscheinlichkeit von mindestens $1-rho$ unter Verwendung von $O(sqrt{N log(1/rho) / delta})$ Quantenabfragen tut (unter milden Annahmen zu $rho$). Dadurch wird die Abhängigkeit von $1/delta$ und $log(1/rho)$ im Vergleich zu einer einfachen Anwendung der Amplitudenschätzung quadratisch verbessert. Um die verbesserte $log(1/rho)$-Abhängigkeit zu erhalten, verwenden wir das erste Ergebnis.

► BibTeX-Daten

► Referenzen

[1] Srinivasan Arunachalam und Ronald de Wolf. Optimierung der Anzahl von Gattern bei der Quantensuche. Quanteninfo. Comput., 17(3-4):251–261, 2017. doi:10.26421/​qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[2] José A. Adell und P. Jodrá. Exakte Kolmogorov- und Gesamtvariationsabstände zwischen einigen bekannten diskreten Verteilungen. Journal of Inequalities and Applications, 2006(1):1–8, 2006. doi:10.1155/​JIA/​2006/​64307.
https://​/​doi.org/​10.1155/​JIA/​2006/​64307

[3] Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter und Ronald de Wolf. Quantenalgorithmen für Matrixskalierung und Matrixausgleich. In Proceedings of 48th International Colloquium on Automata, Languages, and Programming (ICALP'21), Band 198, Seiten 110:1–110:17, 2021. arXiv:2011.12823, doi:10.4230/​LIPIcs.ICALP.2021.110.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
arXiv: 2011.12823

[4] Scott Aaronson und Patrick Rall. Quantennäherungszählen, vereinfacht. In Symposium on Simplicity in Algorithms, Seiten 24–32, 2020. doi:10.1137/​1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

[5] Michel Boyer, Gilles Brassard, Peter Høyer und Alain Tapp. Enge Grenzen bei der Quantensuche. Fortschritte der Physik, 46(4–5):493–505, 1998. Frühere Version in Physcomp'96. arXiv:quant-ph/​9605034.
arXiv: quant-ph / 9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf und Christof Zalka. Grenzen für Quantenalgorithmen mit kleinem Fehler und Nullfehler. Im 40. jährlichen Symposium zu Grundlagen der Informatik (FOCS'99), Seiten 358–368. IEEE Computer Society, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca und Alain Tapp. Quantenamplitudenverstärkung und -schätzung. In Quantum Computation and Quantum Information: A Millennium Volume, Band 305 von Contemporary Mathematics, Seiten 53–74. American Mathematical Society, 2002. 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

[8] Richard Brent und Paul Zimmermann. Modern Computer Arithmetic, Band 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even und Oded Goldreich. Untergrenzen für Stichprobenalgorithmen zur Schätzung des Durchschnitts. Information Processing Letters, 53(1):17–25, Januar 1995. doi:10.1016/​0020-0190(94)00171-T.
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

[10] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini und Leonard Wossnig. Quantenmaschinelles Lernen: eine klassische Perspektive. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, Januar 2018. doi:10.1098/​rspa.2017.0551.
https: / / doi.org/ 10.1098 / rspa.2017.0551

[11] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen. MIT Press, 4. Auflage, 2022.

[12] P. Diaconis und D. Freedman. Endliche austauschbare Folgen. The Annals of Probability, 8(4):745–764, 1980. URL: https://www.jstor.org/​stable/​2242823.
https: // www.jstor.org/stable/2242823

[13] Christoph Dürr und Peter Høyer. Ein Quantenalgorithmus zum Finden des Minimums, 1996. doi:10.48550/​arXiv.quant-ph/​9607014.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv: quant-ph / 9607014

[14] Christoph Dürr, Mark Heiligman, Peter Høyer und Mehdi Mhalla. Quantenabfragekomplexität einiger Graphprobleme. SIAM Journal on Computing, 35(6):1310–1328, Januar 2006. doi:10.1137/​050644719.
https: / / doi.org/ 10.1137 / 050644719

[15] Paul Dagum, Richard Karp, Michael Luby und Sheldon Ross. Ein optimaler Algorithmus für die Monte-Carlo-Schätzung. SIAM Journal on Computing, 29(5):1484–1496, Januar 2000. doi:10.1137/​S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd und Lorenzo Maccone. Quanten-Direktzugriffsspeicher. Physical Review Letters, 100(16), April 2008. doi:10.1103/​physrevlett.100.160501.
https://doi.org/ 10.1103/physrevlett.100.160501

[17] Sander Gribling und Harold Nieuwboer. Verbesserte Quantenunter- und -obergrenzen für die Matrixskalierung. In Proceedings of 39th International Symposium on Theoretical Aspects of Computer Science (STACS'22), Band 219, Seiten 35:1–35:23, 2022. arXiv:2109.15282, doi:10.4230/​LIPIcs.STACS.2022.35.
https://doi.org/ 10.4230 / LIPIcs.STACS.2022.35
arXiv: 2109.15282

[18] Mart de Graaf und Ronald de Wolf. Über Quantenversionen des Yao-Prinzips. In 19th Symposium on Theoretical Aspects of Computer Science (STACS'02), Band 2285 von Lecture Notes in Computer Science, Seiten 347–358, Berlin, Heidelberg, 2002. Springer. doi:10.1007/​3-540-45841-7_28.
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

[19] Liebe K. Grover. Ein schneller quantenmechanischer Algorithmus für die Datenbanksuche. In Proceedings of 38th Annual ACM Symposium on Theory of Computing (STOC'96), Seiten 212–219, 1996. arXiv:quant-ph/​9605043, doi:10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043

[20] Liebe K. Grover. Quantentelecomputation, 1997. Bell Labs Technical Memorandum ITD97-31630F. doi:10.48550/​arXiv.quant-ph/​9704012.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv: quant-ph / 9704012

[21] Liebe K. Grover. Ein Framework für schnelle quantenmechanische Algorithmen. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC'98), Seiten 53–62, 1998. arXiv:quant-ph/​9711043, doi:10.1145/​276698.276712.
https: / / doi.org/ 10.1145 / 276698.276712
arXiv: quant-ph / 9711043

[22] Yassine Hamoudi. Quanten-Sub-Gaußscher Mittelwertschätzer. In 29th Annual European Symposium on Algorithms (ESA 2021), Band 204 von Leibniz International Proceedings in Informatics (LIPIcs), Seiten 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https: // doi.org/ 10.4230 / LIPIcs.ESA.2021.50

[23] Svante Janson. Endgrenzen für Summen geometrischer und exponentieller Variablen. Statistics & Probability Letters, 135:1–6, 2018. doi:10.1016/​j.spl.2017.11.017.
https://​/​doi.org/​10.1016/​j.spl.2017.11.017

[24] Donald Ervin Knuth. Die Kunst der Computerprogrammierung, Band III. Addison-Wesley, 2. Auflage, 1998. URL: https://www.worldcat.org/oclc/312994415.
https://​/​www.worldcat.org/​oclc/​312994415

[25] Robin Kothari und Ryan O'Donnell. Mittelwertschätzung, wenn Sie über den Quellcode verfügen; oder Quanten-Monte-Carlo-Methoden. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'23), Seiten 1186–1215, 2023. doi:10.1137/​1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] Michael A. Nielsen und Isaac L. Chuang. Quantenberechnung und Quanteninformation. Cambridge University Press, 2002.

[27] Ashwin Nayak und Felix Wu. Die Quantenabfragekomplexität der Approximation des Medians und zugehöriger Statistiken. In Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC'99), Seiten 384–393, 1999. arXiv:quant-ph/​9804066, doi:10.1145/​301250.301349.
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: quant-ph / 9804066

[28] B. Roos. Binomiale Annäherung an die Poisson-Binomialverteilung: Die Krawtchouk-Erweiterung. Theory of Probability & Its Applications, 45(2):258–272, 2001. doi:10.1137/​S0040585X9797821X.
https://​/​doi.org/​10.1137/​S0040585X9797821X

[29] Robert M. Young. 75.9 Eulersche Konstante. The Mathematical Gazette, 75(472):187–190, 1991. doi:10.2307/​3620251.
https: / / doi.org/ 10.2307 / 3620251

Zitiert von

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