Afdeling Computerwetenschappen, de Universiteit van Texas in Austin, Austin, TX 78712, VS
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
Een toonaangevend voorstel voor het verifiëren van quantum suprematie-experimenten op korte termijn op luidruchtige willekeurige quantumcircuits is lineaire cross-entropie-benchmarking. Voor een kwantumcircuit $C$ op $n$ qubits en een steekproef $z in {0,1}^n$, omvat de benchmark het berekenen van $|langle z|C|0^n rangle|^2$, dwz de waarschijnlijkheid van het meten van $z$ uit de uitvoerverdeling van $C$ op de invoer met allemaal nullen. Onder een sterk vermoeden over de klassieke hardheid van het schatten van uitgangswaarschijnlijkheden van kwantumcircuits, kan geen enkel polynomiaal-tijd klassiek algoritme gegeven $C$ een string $z$ uitvoeren zodat $|langle z|C|0^nrangle|^2$ is aanzienlijk groter dan $frac{1}{2^n}$ (Aaronson en Gunn, 2019). Aan de andere kant, voor een willekeurig kwantumcircuit $C$, behaalt het bemonsteren van $z$ uit de uitvoerverdeling van $C$ $|langle z|C|0^nrangle|^2 ongeveer frac{2}{2^n} $ gemiddeld (Arute et al., 2019).
In analogie met de Tsirelson-ongelijkheid van niet-lokale kwantumcorrelaties, vragen we ons af: kan een kwantumalgoritme in polynomiale tijd substantieel beter presteren dan $frac{2}{2^n}$? We bestuderen deze vraag in het querymodel (of black box), waarbij het kwantumalgoritme orakeltoegang krijgt tot $C$. We laten zien dat voor elke $varepsilon ge frac{1}{mathrm{poly}(n)}$ een steekproef $z$ wordt uitgevoerd zodat $|langle z|C|0^nrangle|^2 ge frac{2 + varepsilon}{2^n}$ vereist gemiddeld ten minste $Omegaleft(frac{2^{n/4}}{mathrm{poly}(n)}right)$-zoekopdrachten naar $C$, maar niet meer dan $Oleft (2^{n/3}right)$ vraagt naar $C$, als $C$ ofwel een Haar-willekeurige $n$-qubit unitair is, of een canoniek staatsvoorbereidend orakel voor een Haar-willekeurige $n$-qubit staat. We laten ook zien dat wanneer $C$ steekproeven neemt van de Fourier-verdeling van een willekeurige Booleaanse functie, het naïeve algoritme dat steekproeven uit $C$ het optimale 1-query-algoritme is voor het maximaliseren van $|langle z|C|0^nrangle|^2 gemiddeld $.
Populaire samenvatting
We stellen dat deze bovengrens van de kracht van klassieke algoritmen voor de lineaire XEB analoog is aan de Bell-ongelijkheid in niet-lokale correlaties: beide vangen inherente limieten op aan de kracht van klassieke informatie en berekeningen die mogelijk worden geschonden in de kwantumomgeving. Gemotiveerd door deze connectie vragen we: wat is de kwantum suprematie analoog van de Tsirelson ongelijkheid? Dat wil zeggen, wat is de hoogste Lineaire XEB-score die kan worden bereikt door een efficiënt kwantumalgoritme? We bewijzen dat het naïeve kwantumalgoritme om de benchmark te halen in dit opzicht in wezen optimaal is.
► BibTeX-gegevens
► Referenties
[1] Scott Aaronson. Random circuit sampling: gedachten en open problemen. The Quantum Wave in Computing, 2020. URL https://simons.berkeley.edu/talks/tbd-124.
https:///simons.berkeley.edu/talks/tbd-124
[2] Scott Aaronson en Lijie Chen. Complexiteitstheoretische grondslagen van Quantum Supremacy-experimenten. In Ryan O'Donnell, redacteur, 32nd Computational Complexity Conference (CCC 2017), volume 79 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 22:1–22:67, Dagstuhl, Duitsland, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer 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 en Sam Gunn. Over de klassieke hardheid van spoofing lineaire 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/ artikelen / v016a011
[4] Scott Aaronson, Robin Kothari, William Kretschmer en Justin Thaler. Quantum Lower Bounds voor benaderend tellen via Laurent Polynomen. In Shubhangi Saraf, redacteur, 35th Computational Complexity Conference (CCC 2020), volume 169 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 7:1–7:47, Dagstuhl, Duitsland, 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 en Noam Nisan. Kwantumcircuits met gemengde toestanden. In Proceedings of the Thirtyth Annual ACM Symposium on Theory of Computing, STOC '98, pagina 20-30, New York, NY, VS, 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. Inzicht in kwantumalgoritmen via querycomplexiteit. In Proceedings of the 2018 International Congress of Mathematicians, volume 3, pagina's 3249-3270, 2018. 10.1142/9789813272880_0181.
https: / / doi.org/ 10.1142 / 9789813272880_0181
[7] Andris Ambainis, Loïck Magnin, Martin Roetteler en Jeremie Roland. Door symmetrie ondersteunde tegenstanders voor het genereren van kwantumtoestanden. In Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity, CCC '11, pagina 167-177, VS, 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 en Dominique Unruh. Kwantumaanvallen op klassieke bewijssystemen: de hardheid van kwantumterugspoelen. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS '14, pagina 474-483, VS, 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 en Ronald de Wolf. Quantum coupon verzamelaar. In Steven T. Flammia, redacteur, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 10:1–10:17, Dagstuhl, Duitsland, 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. Quantum suprematie met behulp van een programmeerbare supergeleidende processor. Natuur, 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 en Ronald de Wolf. Quantum ondergrenzen door polynomen. 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] Jan Bel. Over de Einstein-Podolsky-Rosen-paradox. Natuurkunde, 1: 195-200, november 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. Variaties op kwantumtegenstander, 2015.
arXiv: 1504.06943
[14] Aleksandrs Belovs en Ansis Rosmanis. Strakke kwantumondergrens voor benaderend tellen met kwantumtoestanden, 2020.
arXiv: 2002.06879
[15] Fernando GSL Brandão, Aram W. Harrow en Michał Horodecki. Lokale willekeurige kwantumcircuits zijn benaderende polynoomontwerpen. Communicatie in wiskundige natuurkunde, 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 en Alain Tapp. Kwantumcryptanalyse van hash- en klauwvrije functies. 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 en Alain Tapp. Quantumamplitudeversterking en schatting. In Quantum Computation en Quantum Information, volume 305 van Contemporary Mathematics, pagina's 53-74. American Mathematical Society, 2002. ISBN 9780821821404. 10.1090/conm/305.
https: / / doi.org/ 10.1090 / conm / 305
[18] Mark Bun en Justin Thaler. Dubbele ondergrenzen voor ongelijkheden bij benadering en Markov-Bernstein. Inf. Computer, 243 (C): 2-25, augustus 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 Cirelson (Tsirelson). Kwantumgeneralisaties van de ongelijkheid van Bell. 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 en Richard A. Holt. Voorgesteld experiment om lokale theorieën over verborgen variabelen te testen. Fys. Rev. Lett., 23: 880-884, oktober 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 en John Watrous. Gevolgen en beperkingen van niet-lokale strategieën. In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, CCC '04, pagina 236-249, VS, 2004. IEEE Computer Society. ISBN 0769521207. 10.1109/CCC.2004.1313847.
https: / / doi.org/ 10.1109 / CCC.2004.1313847
[22] Aram Harrow en Saeed Mehraban. Geschatte unitaire t-ontwerpen door korte willekeurige kwantumcircuits met behulp van naaste buren en langeafstandspoorten, 2018.
arXiv: 1809.06957
[23] Norman L. Johnson en Samuel Kotz. Urnmodellen en hun toepassing: een benadering van de moderne discrete kansrekening. Wiley, 1977. ISBN 9780471446309.
[24] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols en Theodore J. Yoder. Hamiltoniaanse simulatie met optimale steekproefcomplexiteit. 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] Willem Kretschmer. De Quantum Supremacy Tsirelson Ongelijkheid. In James R. Lee, redacteur, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 13:1–13:13, Dagstuhl, Duitsland, 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 en Mario Szegedy. Quantum query complexiteit van toestandsconversie. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS '11, pagina 344-353, VS, 2011. IEEE Computer Society. ISBN 9780769545714/FOCS.10.1109. URL https://doi.org/2011.75/FOCS.10.1109.
https: / / doi.org/ 10.1109 / FOCS.2011.75
[27] Nathan Lindzey en Ansis Rosmanis. Een strakke ondergrens voor niet-coherente indexwissing. In Thomas Vidick, redacteur, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 59:1–59:37, Dagstuhl, Duitsland, 2020. Schloss Dagstuhl–Leibniz- Zentrum fuer 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 en Miklos Santha. Zoeken via kwantumwandeling. In Proceedings van het negenendertigste jaarlijkse ACM Symposium on Theory of Computing, STOC '07, pagina 575-584, New York, NY, VS, 2007. Association for Computing Machinery. ISBN 9781595936318. 10.1145/1250790.1250874. URL https://doi.org/10.1145/1250790.1250874.
https: / / doi.org/ 10.1145 / 1250790.1250874
[29] Ryan O'Donnell. Analyse van Booleaanse functies. Cambridge University Press, VS, 2014. ISBN 1107038324 10.1017/CBO9781139814782.
https: / / doi.org/ 10.1017 / CBO9781139814782
[30] Martin Raab en Angelika Steger. “Balls into bins” – een eenvoudige en strakke analyse. In Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM '98, pagina's 159-170, Berlijn, 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. Reflecties voor algoritmen voor kwantumquery's. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11, pagina 560-569, VS, 2011. Society for Industrial and Applied Mathematics. 10.1137/1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44
[32] Alfred Renyi. Over de theorie van orderstatistieken. 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
Geciteerd door
[1] Daniel Stilck França en Raul Garcia-Patron, "Een spel van kwantumvoordeel: verificatie en simulatie koppelen", arXiv: 2011.12173.
[2] Nicholas LaRacuente, "Quantum Oracle-scheidingen van complexe maar gemakkelijk te specificeren toestanden", arXiv: 2104.07247.
[3] Scott Aaronson, "Open problemen met betrekking tot Quantum Query Complexity", arXiv: 2109.06917.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2021-10-07 11:15:15). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
Kon niet ophalen Door Crossref geciteerde gegevens tijdens laatste poging 2021-10-07 11:15:13: kon niet geciteerde gegevens voor 10.22331 / q-2021-10-07-560 niet ophalen van Crossref. Dit is normaal als de DOI recent is geregistreerd.
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
PlatoAi. Web3 opnieuw uitgevonden. Gegevensintelligentie versterkt.
Klik hier om toegang te krijgen.
