Département d'informatique, Université du Texas à Austin, Austin, TX 78712, États-Unis
Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.
Abstract
Une proposition majeure pour vérifier les expériences de suprématie quantique à court terme sur des circuits quantiques aléatoires bruyants est l'analyse comparative d'entropie croisée linéaire. Pour un circuit quantique $C$ sur $n$ qubits et un échantillon $z dans {0,1}^n$, le benchmark consiste à calculer $|langle z|C|0^n rangle|^2$, c'est-à-dire la probabilité de mesurer $z$ à partir de la distribution de sortie de $C$ sur l'entrée tout à zéro. Sous une forte conjecture sur la dureté classique de l'estimation des probabilités de sortie des circuits quantiques, aucun algorithme classique en temps polynomial étant donné $C$ ne peut sortir une chaîne $z$ telle que $|langle z|C|0^nrangle|^2$ est beaucoup plus grand que $frac{1}{2^n}$ (Aaronson et Gunn, 2019). D'autre part, pour un circuit quantique aléatoire $C$, l'échantillonnage de $z$ à partir de la distribution de sortie de $C$ atteint $|langle z|C|0^nrangle|^2 approx frac{2}{2^n} $ en moyenne (Arute et al., 2019).
Par analogie avec l'inégalité de Tsirelson à partir de corrélations quantiques non locales, nous demandons : un algorithme quantique en temps polynomial peut-il faire sensiblement mieux que $frac{2}{2^n}$ ? Nous étudions cette question dans le modèle de requête (ou boîte noire), où l'algorithme quantique reçoit un accès oracle à $C$. Nous montrons que, pour tout $varepsilon ge frac{1}{mathrm{poly}(n)}$, produisant un échantillon $z$ tel que $|langle z|C|0^nrangle|^2 ge frac{2 + varepsilon}{2^n}$ nécessite en moyenne au moins $Omegaleft(frac{2^{n/4}}{mathrm{poly}(n)}right)$ requêtes à $C$, mais pas plus de $Oleft (2^{n/3}right)$ requêtes à $C$, si $C$ est soit un $n$-qubit unitaire Haar-random, soit un oracle de préparation d'état canonique pour un $n$-qubit Haar-random Etat. Nous montrons également que lorsque $C$ échantillonne à partir de la distribution de Fourier d'une fonction booléenne aléatoire, l'algorithme naïf qui échantillonne à partir de $C$ est l'algorithme optimal à 1 requête pour maximiser $|langle z|C|0^nrangle|^2 $ en moyenne.
Résumé populaire
Nous soutenons que cette limite supérieure de la puissance des algorithmes classiques pour le XEB linéaire est analogue à l'inégalité de Bell dans les corrélations non locales : les deux capturent les limites inhérentes à la puissance de l'information et du calcul classiques qui peuvent être violées dans le cadre quantique. Motivés par cette connexion, nous demandons : quel est l'analogue de suprématie quantique de l'inégalité de Tsirelson ? Autrement dit, quel est le score XEB linéaire le plus élevé pouvant être atteint par un algorithme quantique efficace ? Nous montrons que l'algorithme quantique naïf pour passer le repère est essentiellement optimal à cet égard.
► Données BibTeX
► Références
Scott Aaronson. Échantillonnage de circuits aléatoires : pensées et problèmes ouverts. La vague quantique en informatique, 2020. URL https://simons.berkeley.edu/talks/tbd-124.
https:///simons.berkeley.edu/talks/tbd-124
Scott Aaronson et Lijie Chen. Fondements théoriques de la complexité des expériences de suprématie quantique. Dans Ryan O'Donnell, éditeur, 32e Computational Complexity Conference (CCC 2017), volume 79 de Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:67, Dagstuhl, Allemagne, 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
Scott Aaronson et Sam Gunn. Sur la dureté classique de l'usurpation d'indices d'entropie croisée linéaire. Théorie de l'informatique, 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
Scott Aaronson, Robin Kothari, William Kretschmer et Justin Thaler. Limites inférieures quantiques pour le comptage approximatif via les polynômes de Laurent. Dans Shubhangi Saraf, éditeur, 35th Computational Complexity Conference (CCC 2020), volume 169 de Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:47, Dagstuhl, Allemagne, 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
Dorit Aharonov, Alexei Kitaev et Noam Nisan. Circuits quantiques à états mixtes. Dans Actes du trentième symposium annuel de l'ACM sur la théorie de l'informatique, STOC '98, pages 20-30, New York, NY, États-Unis, 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
Andris Ambainis. Comprendre les algorithmes quantiques via la complexité des requêtes. Dans Actes du Congrès international des mathématiciens 2018, volume 3, pages 3249–3270, 2018. 10.1142/9789813272880_0181.
https: / / doi.org/ 10.1142 / 9789813272880_0181
Andris Ambainis, Loïck Magnin, Martin Roetteler et Jérémie Roland. Adversaires assistés par symétrie pour la génération d'états quantiques. Dans Actes de la 2011e conférence annuelle de l'IEEE sur la complexité informatique, CCC '26, pages 11-167, États-Unis, 177. IEEE Computer Society. ISBN 2011. 9780769544113/CCC.10.1109. URL https://doi.org/2011.24/CCC.10.1109.
https: / / doi.org/ 10.1109 / CCC.2011.24
Andris Ambainis, Ansis Rosmanis et Dominique Unruh. Attaques quantiques sur les systèmes de preuve classiques : La dureté du rembobinage quantique. Dans Actes du 2014e Symposium annuel IEEE 55 sur les fondements de l'informatique, FOCS '14, pages 474-483, États-Unis, 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
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis et Ronald de Wolf. Collectionneur de coupons quantiques. Dans Steven T. Flammia, éditeur, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 de Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:17, Dagstuhl, Allemagne, 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
Frank Arute, Kunal Arya, Ryan Babbush et al. Suprématie quantique à l'aide d'un processeur supraconducteur programmable. 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
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca et Ronald de Wolf. Bornes inférieures quantiques par polynômes. J. ACM, 48 (4) : 778-797, juillet 2001. ISSN 0004-5411. 10.1145/502090.502097. URL https://doi.org/10.1145/502090.502097.
https: / / doi.org/ 10.1145 / 502090.502097
John Bell. Sur le paradoxe Einstein-Podolsky-Rosen. Physique, 1 : 195-200, novembre 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
Alexandre Belovs. Variations sur l'adversaire quantique, 2015.
arXiv: 1504.06943
Aleksandrs Belovs et Ansis Rosmanis. Limite inférieure quantique stricte pour le comptage approximatif avec des états quantiques, 2020.
arXiv: 2002.06879
Fernando GSL Brandão, Aram W. Harrow et Michał Horodecki. Les circuits quantiques aléatoires locaux sont des conceptions polynomiales approximatives. 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
Gilles Brassard, Peter Høyer et Alain Tapp. Cryptanalyse quantique des fonctions de hachage et sans griffe. SIGACT News, 28 (2) : 14-19, juin 1997. ISSN 0163-5700. 10.1145/261342.261346. URL https://doi.org/10.1145/261342.261346.
https: / / doi.org/ 10.1145 / 261342.261346
Gilles Brassard, Peter Høyer, Michèle Mosca et Alain Tapp. Amplification et estimation d'amplitude quantique. Dans Quantum Computation and Quantum Information, volume 305 de Contemporary Mathematics, pages 53-74. Société mathématique américaine, 2002. ISBN 9780821821404. 10.1090/conm/305.
https: / / doi.org/ 10.1090 / conm / 305
Mark Bun et Justin Thaler. Doubles bornes inférieures pour le degré approximatif et les inégalités de Markov-Bernstein. Inf. Comput., 243 (C) : 2-25, août 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
Boris Cirel'son (Tsirelson). Généralisations quantiques de l'inégalité de 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
John F. Clauser, Michael A. Horne, Abner Shimony et Richard A. Holt. Expérience proposée pour tester les théories locales des variables cachées. Phys. Rev. Lett., 23 : 880–884, octobre 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
Richard Cleve, Peter Høyer, Benjamin Toner et John Watrous. Conséquences et limites des stratégies non locales. Dans Actes de la 19e conférence annuelle de l'IEEE sur la complexité informatique, CCC '04, pages 236-249, États-Unis, 2004. IEEE Computer Society. ISBN 0769521207. 10.1109/CCC.2004.1313847.
https: / / doi.org/ 10.1109 / CCC.2004.1313847
Aram Harrow et Saeed Mehraban. Conceptions en t unitaires approximatives par de courts circuits quantiques aléatoires utilisant des portes plus proches et à longue portée, 2018.
arXiv: 1809.06957
Norman L. Johnson et Samuel Kotz. Modèles d'urnes et leur application : une approche de la théorie moderne des probabilités discrètes. Wiley, 1977. ISBN 9780471446309.
Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols et Theodore J. Yoder. Simulation hamiltonienne avec une complexité d'échantillon optimale. 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
Guillaume Kretschmer. L'inégalité de Tsirelson de la suprématie quantique. Dans James R. Lee, éditeur, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 de Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:13, Dagstuhl, Allemagne, 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
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek et Mario Szegedy. Complexité des requêtes quantiques de la conversion d'état. Dans Actes du 2011e Symposium annuel IEEE 52 sur les fondements de l'informatique, FOCS '11, pages 344-353, États-Unis, 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
Nathan Lindzey et Ansis Rosmanis. Une limite inférieure serrée pour l'effacement d'index non cohérent. Dans Thomas Vidick, éditeur, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 de Leibniz International Proceedings in Informatics (LIPIcs), pages 59:1–59:37, Dagstuhl, Allemagne, 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
Frédéric Magniez, Ashwin Nayak, Jérémie Roland et Miklos Santha. Recherche via la marche quantique. Dans Actes du trente-neuvième symposium annuel de l'ACM sur la théorie de l'informatique, STOC '07, pages 575–584, New York, NY, États-Unis, 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
Ryan O'Donnell. Analyse des fonctions booléennes. Cambridge University Press, États-Unis, 2014. ISBN 1107038324. 10.1017/CBO9781139814782.
https: / / doi.org/ 10.1017 / CBO9781139814782
Martin Raab et Angelika Steger. « Balls into bins » – une analyse simple et précise. Dans Actes du deuxième atelier international sur les techniques de randomisation et d'approximation en informatique, RANDOM '98, pages 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
Ben W. Reichardt. Réflexions pour les algorithmes de requêtes quantiques. Dans Actes du vingt-deuxième symposium annuel ACM-SIAM sur les algorithmes discrets, SODA '11, pages 560–569, États-Unis, 2011. Society for Industrial and Applied Mathematics. 10.1137/1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44
Alfred Rényi. Sur la théorie des statistiques d'ordre. 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
Cité par
[1] Daniel Stilck França et Raul Garcia-Patron, « Un jeu d'avantage quantique : lier vérification et simulation », arXiv: 2011.12173.
[2] Nicholas LaRacuente, « Séparations de l'oracle quantique à partir d'états complexes mais facilement spécifiés », arXiv: 2104.07247.
[3] Scott Aaronson, « Problèmes ouverts liés à la complexité des requêtes quantiques », arXiv: 2109.06917.
Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2021-10-07 11:15:15). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.
Impossible de récupérer Données de référence croisée lors de la dernière tentative 2021-10-07 11:15:13: Impossible de récupérer les données citées par 10.22331 / q-2021-10-07-560 de Crossref. C'est normal si le DOI a été enregistré récemment.
Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.
PlatonAi. Web3 réinventé. L'intelligence des données amplifiée.
Cliquez ici pour y accéder.
Source : https://quantum-journal.org/papers/q-2021-10-07-560/
