Institut für Informatik, The University of Texas at Austin, Austin, TX 78712, USA
Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.
Abstrakt
Ein führender Vorschlag zur Verifizierung kurzfristiger Quantenüberlegenheitsexperimente an verrauschten Zufallsquantenschaltungen ist das lineare Kreuzentropie-Benchmarking. Für einen Quantenschaltkreis $C$ auf $n$ Qubits und ein Sample $z in {0,1}^n$ beinhaltet der Benchmark die Berechnung von $|langle z|C|0^n rangle|^2$, dh der Wahrscheinlichkeit der Messung von $z$ aus der Ausgabeverteilung von $C$ bei der Eingabe ausschließlich aus Nullen. Unter einer starken Vermutung über die klassische Härte der Schätzung von Ausgabewahrscheinlichkeiten von Quantenschaltungen kann kein klassischer Algorithmus in Polynomialzeit bei gegebenem $C$ einen String $z$ ausgeben, so dass $|langle z|C|0^nrangle|^2$ ist wesentlich größer als $frac{1}{2^n}$ (Aaronson und Gunn, 2019). Für eine zufällige Quantenschaltung $C$ hingegen ergibt das Abtasten von $z$ aus der Ausgabeverteilung von $C$ $|langle z|C|0^nrangle|^2 approximativ frac{2}{2^n} $ im Durchschnitt (Arute et al., 2019).
In Analogie zur Tsirelson-Ungleichung aus nichtlokalen Quantenkorrelationen fragen wir: Kann ein Quantenalgorithmus in Polynomialzeit wesentlich besser abschneiden als $frac{2}{2^n}$? Wir untersuchen diese Frage im Abfrage- (oder Black-Box-)Modell, bei dem dem Quantenalgorithmus Orakelzugriff auf $C$ gewährt wird. Wir zeigen, dass für jedes $varepsilon ge frac{1}{mathrm{poly}(n)}$ ein Beispiel $z$ ausgegeben wird, so dass $|langle z|C|0^nrangle|^2 ge frac{2 + varepsilon}{2^n}$ erfordert im Durchschnitt mindestens $Omegaleft(frac{2^{n/4}}{mathrm{poly}(n)}right)$-Abfragen an $C$, aber nicht mehr als $Oleft (2^{n/3}rechts)$ fragt an $C$, wenn $C$ entweder ein Haar-zufälliges $n$-Qubit-Unitary oder ein kanonisches Zustandsvorbereitungs-Orakel für ein Haar-zufälliges $n$-Qubit ist Zustand. Wir zeigen auch, dass, wenn $C$ von der Fourier-Verteilung einer zufälligen Booleschen Funktion abtastet, der naive Algorithmus, der von $C$ abtastet, der optimale 1-Abfrage-Algorithmus zum Maximieren von $|langle z|C|0^nrangle|^2 . ist $ im Durchschnitt.
Populäre Zusammenfassung
Wir argumentieren, dass diese Obergrenze der Leistungsfähigkeit klassischer Algorithmen für die lineare XEB analog zur Bell-Ungleichung in nichtlokalen Korrelationen ist: Beide erfassen inhärente Grenzen der Leistungsfähigkeit klassischer Informationen und Berechnungen, die in der Quantenumgebung verletzt werden können. Motiviert durch diesen Zusammenhang fragen wir: Was ist das Quantensupremacy-Analogon der Tsirelson-Ungleichung? Das heißt, was ist der höchste lineare XEB-Score, der mit einem effizienten Quantenalgorithmus erreichbar ist? Wir belegen, dass der naive Quantenalgorithmus zum Bestehen des Benchmarks in dieser Hinsicht im Wesentlichen optimal ist.
► BibTeX-Daten
► Referenzen
[1] Scott Aaronson. Random Circuit Sampling: Gedanken und offene Probleme. The Quantum Wave in Computing, 2020. URL https://simons.berkeley.edu/talks/tbd-124.
https:///simons.berkeley.edu/talks/tbd-124
[2] Scott Aaronson und Lijie Chen. Komplexitätstheoretische Grundlagen von Quantensupremacy-Experimenten. In Ryan O'Donnell, Herausgeber, 32nd Computational Complexity Conference (CCC 2017), Band 79 der Leibniz International Proceedings in Informatics (LIPIcs), Seiten 22:1–22:67, Dagstuhl, Deutschland, 2017. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-040-8. 10.4230/LIPIcs.CCC.2017.22. URL http://drops.dagstuhl.de/opus/volltexte/2017/7527.
https: // doi.org/ 10.4230 / LIPIcs.CCC.2017.22
http: // drops.dagstuhl.de/ opus / volltexte / 2017/7527
[3] Scott Aaronson und Sam Gunn. Zur klassischen Härte des Spoofings lineares Cross-Entropie-Benchmarking. Theory of Computing, 16 (11): 1–8, 2020. 10.4086/toc.2020.v016a011. URL http://www.theoryofcomputing.org/articles/v016a011.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
http: // www.theoryofcomputing.org/ articles / v016a011
[4] Scott Aaronson, Robin Kothari, William Kretschmer und Justin Thaler. Quantenuntergrenzen für das ungefähre Zählen über Laurent-Polynome. In Shubhangi Saraf, Herausgeber, 35th Computational Complexity Conference (CCC 2020), Band 169 der Leibniz International Proceedings in Informatics (LIPIcs), Seiten 7:1–7:47, Dagstuhl, Deutschland, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik . ISBN 978-3-95977-156-6. 10.4230/LIPIcs.CCC.2020.7. URL https://drops.dagstuhl.de/opus/volltexte/2020/12559.
https: // doi.org/ 10.4230 / LIPIcs.CCC.2020.7
https:///drops.dagstuhl.de/opus/volltexte/2020/12559
[5] Dorit Aharonov, Alexei Kitaev und Noam Nisan. Quantenschaltungen mit gemischten Zuständen. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC '98, Seite 20–30, New York, NY, USA, 1998. Association for Computing Machinery. ISBN 0897919629. 10.1145/276698.276708. URL https://doi.org/10.1145/276698.276708.
https: / / doi.org/ 10.1145 / 276698.276708
[6] Andris Ambainis. Verständnis von Quantenalgorithmen über Abfragekomplexität. In Proceedings of the 2018 International Congress of Mathematicians, Band 3, Seiten 3249–3270, 2018. 10.1142/9789813272880_0181.
https: / / doi.org/ 10.1142 / 9789813272880_0181
[7] Andris Ambainis, Loïck Magnin, Martin Roetteler und Jeremie Roland. Symmetrieunterstützte Gegner für die Erzeugung von Quantenzuständen. In Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity, CCC '11, Seite 167–177, USA, 2011. IEEE Computer Society. ISBN 9780769544113. 10.1109/CCC.2011.24. URL https://doi.org/10.1109/CCC.2011.24.
https: / / doi.org/ 10.1109 / CCC.2011.24
[8] Andris Ambainis, Ansis Rosmanis und Dominique Unruh. Quantenangriffe auf klassische Beweissysteme: Die Härte des Quantenrückspulens. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS '14, Seite 474–483, USA, 2014. IEEE Computer Society. ISBN 9781479965175. 10.1109/FOCS.2014.57. URL https://doi.org/10.1109/FOCS.2014.57.
https: / / doi.org/ 10.1109 / FOCS.2014.57
[9] Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis und Ronald de Wolf. Quanten-Coupon-Sammler. In Steven T. Flammia, Herausgeber, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Band 158 der Leibniz International Proceedings in Informatics (LIPIcs), Seiten 10:1–10:17, Dagstuhl, Deutschland, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-146-7. 10.4230/LIPIcs.TQC.2020.10. URL https://drops.dagstuhl.de/opus/volltexte/2020/12069.
https: // doi.org/ 10.4230 / LIPIcs.TQC.2020.10
https:///drops.dagstuhl.de/opus/volltexte/2020/12069
[10] Frank Arute, Kunal Arya, Ryan Babbush et al. Quantenüberlegenheit mit einem programmierbaren supraleitenden Prozessor. Nature, 574 (7779): 505–510, 2019. 10.1038/s41586-019-1666-5. URL https://doi.org/10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5
[11] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca und Ronald de Wolf. Quantenuntergrenzen durch Polynome. J. ACM, 48 (4): 778–797, Juli 2001. ISSN 0004-5411. 10.1145/502090.502097. URL https://doi.org/10.1145/502090.502097.
https: / / doi.org/ 10.1145 / 502090.502097
[12] John Bell. Zum Einstein-Podolsky-Rosen-Paradoxon. Physik, 1: 195–200, Nov. 1964. 10.1103/PhysicsPhysiqueFizika.1.195. URL https://link.aps.org/doi/10.1103/PhysicsPhysiqueFizika.1.195.
https: / / doi.org/ 10.1103 / PhysicsPhysiqueFizika.1.195
[13] Alexander Belovs. Variationen über Quantengegner, 2015.
arXiv: 1504.06943
[14] Alexander Belovs und Ansis Rosmanis. Enge Quantenuntergrenze für ungefähres Zählen mit Quantenzuständen, 2020.
arXiv: 2002.06879
[15] Fernando GSL Brandão, Aram W. Harrow und Michał Horodecki. Lokale zufällige Quantenschaltungen sind angenäherte Polynom-Designs. Communications in Mathematical Physics, 346 (2): 397–434, 2016. 10.1007/s00220-016-2706-8. URL https://doi.org/10.1007/s00220-016-2706-8.
https://doi.org/10.1007/s00220-016-2706-8
[16] Gilles Brassard, Peter Høyer und Alain Tapp. Quantenkryptanalyse von Hash- und Claw-free-Funktionen. SIGACT News, 28 (2): 14–19, Juni 1997. ISSN 0163-5700. 10.1145/261342.261346. URL https://doi.org/10.1145/261342.261346.
https: / / doi.org/ 10.1145 / 261342.261346
[17] Gilles Brassard, Peter Høyer, Michele Mosca und Alain Tapp. Quantenamplitudenverstärkung und -schätzung. In Quantum Computation and Quantum Information, Band 305 von Contemporary Mathematics, Seiten 53–74. American Mathematical Society, 2002. ISBN 9780821821404. 10.1090/conm/305.
https: / / doi.org/ 10.1090 / conm / 305
[18] Mark Bun und Justin Thaler. Duale untere Schranken für ungefähre Grad- und Markov-Bernstein-Ungleichungen. Inf. Comput., 243 (C): 2.–25. August 2015. ISSN 0890-5401. 10.1016/j.ic.2014.12.003. URL https://doi.org/10.1016/j.ic.2014.12.003.
https: / / doi.org/ 10.1016 / j.ic.2014.12.003
[19] Boris Cirel'son (Tsirelson). Quantenverallgemeinerungen der Bellschen Ungleichung. Letters in Mathematical Physics, 4 (2): 93–100, 1980. 10.1007/BF00417500. URL https://doi.org/10.1007/BF00417500.
https: / / doi.org/ 10.1007 / BF00417500
[20] John F. Clauser, Michael A. Horne, Abner Shimony und Richard A. Holt. Vorgeschlagenes Experiment zum Testen lokaler versteckter Variablentheorien. Phys. Rev. Lett., 23: 880–884, Okt. 1969. 10.1103/PhysRevLett.23.880. URL https://link.aps.org/doi/10.1103/PhysRevLett.23.880.
https://doi.org/ 10.1103/PhysRevLett.23.880
[21] Richard Cleve, Peter Høyer, Benjamin Toner und John Watrous. Konsequenzen und Grenzen nichtlokaler Strategien. In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, CCC '04, Seite 236–249, USA, 2004. IEEE Computer Society. ISBN 0769521207. 10.1109/CCC.2004.1313847.
https: / / doi.org/ 10.1109 / CCC.2004.1313847
[22] Aram Harrow und Saeed Mehraban. Ungefähre unitäre t-Designs durch kurze zufällige Quantenschaltungen unter Verwendung von Next-Neighbor- und Long-Range-Gates, 2018.
arXiv: 1809.06957
[23] Norman L. Johnson und Samuel Kotz. Urnenmodelle und ihre Anwendung: ein Ansatz zur modernen diskreten Wahrscheinlichkeitstheorie. Wiley, 1977. ISBN 9780471446309.
[24] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols und Theodore J. Yoder. Hamiltonsche Simulation mit optimaler Probenkomplexität. npj Quantum Information, 3 (1): 13, 2017. 10.1038/s41534-017-0013-7. URL https://doi.org/10.1038/s41534-017-0013-7.
https://doi.org/10.1038/s41534-017-0013-7
[25] Wilhelm Kretschmer. Die Tsirelson-Ungleichung der Quantenvorherrschaft. In James R. Lee, Herausgeber, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), Band 185 der Leibniz International Proceedings in Informatics (LIPIcs), Seiten 13:1–13:13, Dagstuhl, Deutschland, 2021. Schloss Dagstuhl– Leibniz-Zentrum für Informatik. ISBN 978-3-95977-177-1. 10.4230/LIPIcs.ITCS.2021.13. URL https://drops.dagstuhl.de/opus/volltexte/2021/13552.
https: // doi.org/ 10.4230 / LIPIcs.ITCS.2021.13
https:///drops.dagstuhl.de/opus/volltexte/2021/13552
[26] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek und Mario Szegedy. Quantenabfragekomplexität der Zustandsumwandlung. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS '11, Seite 344–353, USA, 2011. IEEE Computer Society. ISBN 9780769545714. 10.1109/FOCS.2011.75. URL https://doi.org/10.1109/FOCS.2011.75.
https: / / doi.org/ 10.1109 / FOCS.2011.75
[27] Nathan Lindzey und Ansis Rosmanis. Eine enge untere Grenze für nicht kohärente Indexlöschung. In Thomas Vidick, Herausgeber, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), Band 151 der Leibniz International Proceedings in Informatics (LIPIcs), Seiten 59:1–59:37, Dagstuhl, Deutschland, 2020. Schloss Dagstuhl–Leibniz- Zentrum für Informatik. ISBN 978-3-95977-134-4. 10.4230/LIPIcs.ITCS.2020.59. URL https://drops.dagstuhl.de/opus/volltexte/2020/11744.
https: // doi.org/ 10.4230 / LIPIcs.ITCS.2020.59
https:///drops.dagstuhl.de/opus/volltexte/2020/11744
[28] Frederic Magniez, Ashwin Nayak, Jeremie Roland und Miklos Santha. Suche per Quantenspaziergang. In Proceedings of the 07th Annual ACM Symposium on Theory of Computing, STOC '575, Seite 584–2007, New York, NY, USA, 9781595936318. Association for Computing Machinery. ISBN 10.1145. 1250790.1250874/10.1145. URL https://doi.org/1250790.1250874/XNUMX.
https: / / doi.org/ 10.1145 / 1250790.1250874
[29] Ryan O'Donnell. Analyse boolescher Funktionen. Cambridge University Press, USA, 2014. ISBN 1107038324. 10.1017/CBO9781139814782.
https: / / doi.org/ 10.1017 / CBO9781139814782
[30] Martin Raab und Angelika Steger. „Balls into bins“ – eine einfache und genaue Analyse. In Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM '98, Seiten 159–170, Berlin, Heidelberg, 1998. Springer-Verlag. ISBN 354065142X. 10.1007/3-540-49543-6_13.
https://doi.org/10.1007/3-540-49543-6_13
[31] Ben W. Reichardt. Überlegungen zu Quantenabfragealgorithmen. In Proceedings of the Twenty Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11, Seite 560–569, USA, 2011. Society for Industrial and Applied Mathematics. 10.1137/1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44
[32] Alfred Rényi. Zur Theorie der Ordnungsstatistik. Acta Mathematica Academiae Scientiarum Hungarica, 4 (3): 191–231, 1953. 10.1007/BF02127580. URL https://doi.org/10.1007/BF02127580.
https: / / doi.org/ 10.1007 / BF02127580
Zitiert von
[1] Daniel Stilck França und Raul Garcia-Patron, „Ein Spiel mit Quantenvorteilen: Verknüpfung von Verifikation und Simulation“, arXiv: 2011.12173.
[2] Nicholas LaRacuente, „Quanten-Oracle-Trennungen von komplexen, aber leicht zu spezifizierenden Zuständen“, arXiv: 2104.07247.
[3] Scott Aaronson, „Offene Probleme im Zusammenhang mit der Komplexität von Quantenabfragen“, arXiv: 2109.06917.
Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2021, 10:07:11 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.
Konnte nicht abrufen Crossref zitiert von Daten während des letzten Versuchs 2021-10-07 11:15:13: Von Crossref konnten keine zitierten Daten für 10.22331 / q-2021-10-07-560 abgerufen werden. Dies ist normal, wenn der DOI kürzlich registriert wurde.
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.
PlatonAi. Web3 neu erfunden. Datenintelligenz verstärkt.
Klicken Sie hier, um darauf zuzugreifen.
Quelle: https://quantum-journal.org/papers/q-2021-10-07-560/
