1Département de physique, ETH Zürich, Suisse
2Institut d'études théoriques, ETH Zürich, Suisse
Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.
Abstract
Une preuve de caractère quantique est un type de protocole défi-réponse dans lequel un vérificateur classique peut certifier efficacement l'$textit{avantage quantique}$ d'un prouveur non fiable. Autrement dit, un prouveur quantique peut répondre correctement aux défis du vérificateur et être accepté, tandis que tout prouveur classique en temps polynomial sera rejeté avec une forte probabilité, sur la base d’hypothèses informatiques plausibles. Pour répondre aux défis du vérificateur, les preuves de caractère quantique existantes nécessitent généralement que le prouveur quantique effectue une combinaison de circuits et de mesures quantiques de taille polynomiale.
Dans cet article, nous donnons deux preuves de constructions quantiques dans lesquelles le prouveur n'a besoin que d'effectuer des $textit{circuits quantiques à profondeur constante}$ (et des mesures) avec un calcul classique de profondeur logarithmique. Notre première construction est un compilateur générique qui nous permet de traduire toutes les preuves quantiques existantes en versions à profondeur quantique constante. Notre deuxième construction est basée sur le problème $textit{apprentissage avec arrondi}$, et produit des circuits avec une profondeur plus courte et nécessitant moins de qubits que la construction générique. De plus, la deuxième construction présente également une certaine robustesse face au bruit.
► Données BibTeX
► Références
Scott Aaronson et Alex Arkhipov. La complexité informatique de l'optique linéaire. Dans Actes du quarante-troisième symposium annuel de l'ACM sur la théorie de l'informatique, pages 333-342, 2011.
https: / / doi.org/ 10.1145 / 1993636.1993682
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell et al. Suprématie quantique grâce à un processeur supraconducteur programmable. Nature, 574(7779):505-510, 2019.
https://doi.org/10.1038/s41586-019-1666-5
MD SAJID ANIS, Abby-Mitchell, Héctor Abraham, AduOffei, et al. Qiskit : Un framework open source pour l'informatique quantique, 2021.
Sanjeev Arora et Boaz Barak. Complexité informatique : une approche moderne. La Presse de l'Universite de Cambridge, 2009.
Scott Aaronson et Lijie Chen. Fondements théoriques de la complexité des expériences de suprématie quantique. Dans Actes de la 32e conférence sur la complexité informatique, CCC '17, pages 1 à 67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
Scott Aaronson et Sam Gunn. Sur la dureté classique de l’analyse comparative de l’entropie croisée linéaire de l’usurpation d’identité. Théorie de l'informatique, 16(11):1-8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
B. Applebaum, Y. Ishai et E. Kushilevitz. Cryptographie en ${NC}^0$. Dans le 45e Symposium annuel de l'IEEE sur les fondements de l'informatique, pages 166-175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
Joël Alwen, Stephan Krenn, Krzysztof Pietrzak et Daniel Wichs. Apprendre avec l'arrondi, revisité. Dans Advances in Cryptology – CRYPTO 2013, pages 57-74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
David A. Barrington. Les programmes de branchement de taille polynomiale à largeur limitée reconnaissent exactement ces langues dans ${NC}^1$. Journal des sciences informatiques et des systèmes, 38(1):150-164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani et Thomas Vidick. Un test cryptographique du caractère quantique et du caractère aléatoire certifiable à partir d'un seul appareil quantique. En 2018, 59e Symposium annuel de l'IEEE sur les fondements de l'informatique (FOCS), pages 320-331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
Colin D. Bruzewicz, John Chiaverini, Robert McConnell et Jeremy M. Sage. Informatique quantique à ions piégés : progrès et défis. Revues de physique appliquée, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
Adam Bouland, Bill Fefferman, Chinmay Nirkhe et Umesh Vazirani. Sur la complexité et la vérification de l'échantillonnage de circuits aléatoires quantiques. Nature Physics, 15(2):159-163, février 2019.
https://doi.org/10.1038/s41567-018-0318-2
Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis et Hartmut Neven. Caractériser la suprématie quantique dans les appareils à court terme. Physique de la nature, 14(6):595-600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
Zvika Brakerski, Venkata Koppula, Umesh Vazirani et Thomas Vidick. Preuves plus simples du caractère quantique. Dans 15e Conférence sur la théorie du calcul quantique, de la communication et de la cryptographie (TQC 2020), volume 158 de Leibniz International Proceedings in Informatics (LIPIcs), pages 8 :1–8 :14, Dagstuhl, Allemagne, 2020. Schloss Dagstuhl–Leibniz- Centre d'informatique.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
Abhishek Banerjee, Chris Peikert et Alon Rosen. Fonctions et réseaux pseudo-aléatoires. Dans Advances in Cryptology – EUROCRYPT 2012, pages 719-737. Springer Berlin-Heidelberg, 2012.
https://doi.org/10.1007/978-3-642-29011-4_42
John F Clauser, Michael A Horne, Abner Shimony et Richard A Holt. Expérience proposée pour tester les théories locales à variables cachées. Lettres d'examen physique, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
Matthieu Coudron, Jalex Stark et Thomas Vidick. Localité d'échange contre du temps : caractère aléatoire certifiable à partir de circuits de faible profondeur. Communications en physique mathématique, 382(1):49-86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
Richard Cleve et John Watrous. Circuits parallèles rapides pour la transformée de Fourier quantique. Dans Actes du 41e Symposium annuel sur les fondements de l'informatique, pages 526-536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
Pierre Dusart. Autour de la fonction qui compte le nombre de nombres premiers. Thèse de doctorat, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
Austin G Fowler, Matteo Mariantoni, John M Martinis et Andrew N Cleland. Codes de surface : vers un calcul quantique pratique à grande échelle. Examen physique A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
François Le Gall. Correspondance privée, 2022.
Craig Gidney et Martin Ekerå. Comment factoriser des entiers RSA de 2048 bits en 8 heures en utilisant 20 millions de qubits bruyants. Quantique, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
Alexandru Gheorghiu et Matty J Hoban. Il est difficile d’estimer l’entropie des sorties de circuits peu profonds. Préimpression arXiv arXiv :2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
Shuichi Hirahara et François Le Gall. Test de caractère quantique avec des circuits quantiques à petite profondeur. Dans le 46e Symposium international sur les fondements mathématiques de l'informatique (MFCS 2021), volume 202 de Leibniz International Proceedings in Informatics (LIPIcs), pages 59 :1–59 :15, Dagstuhl, Allemagne, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
Aram W Harrow et Ashley Montanaro. Suprématie informatique quantique. Nature, 549(7671):203-209, 2017.
https: / / doi.org/ 10.1038 / nature23458
Peter Høyer et Robert Spalek. La diffusion quantique est puissante. Théorie de l'informatique, 1(5):81-103, 2005.
https: / / doi.org/ 10.4086 / toc.2005.v001a005
Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi et Jianxin Chen. Simulation classique des circuits de suprématie quantique. Préimpression arXiv arXiv :2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
Gregory D. Kahanamoku-Meyer. Forger des données quantiques : vaincre de manière classique un test quantique basé sur l'IQP. Préimpression arXiv arXiv : 1912.05547, 2019.
https:///doi.org/10.48550/arXiv.1912.05547
arXiv: 1912.05547
Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani et Norman Y. Yao. Avantage quantique classiquement vérifiable d’un test informatique de Bell. Physique de la nature, 18(8):918-924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
Vadim Lyubashevsky, Chris Peikert et Oded Regev. Sur des réseaux idéaux et apprentissage avec erreurs sur anneaux. Dans Conférence internationale annuelle sur la théorie et les applications des techniques cryptographiques, pages 1 à 23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
Urmila Mahadev. Vérification classique des calculs quantiques. En 2018, 59e Symposium annuel de l'IEEE sur les fondements de l'informatique (FOCS), pages 259 à 267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
Michael A Nielsen et Isaac Chuang. Calcul quantique et information quantique, 2002.
A.S. Popova et A.N. Rubtsov. Dépasser le seuil d'avantage quantique pour l'échantillonnage du boson gaussien. Dans Conférence et exposition Quantum 2.0, page QW2A.15. Groupe d'édition Optica, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
John Preskill. L'informatique quantique à l'ère NISQ et au-delà. Quantique, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
Michael O Rabin. Algorithme probabiliste pour tester la primalité. Journal de théorie des nombres, 12(1):128-138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
Oded Regev. Sur les treillis, apprentissage avec erreurs, codes linéaires aléatoires et cryptographie. Journal de l'ACM (JACM), 56(6):1-40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
Dan Shepherd et Michael J Bremner. Calcul quantique temporellement non structuré. Actes de la Royal Society A : Sciences mathématiques, physiques et techniques, 465(2105) :1413-1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
Peter W. Shor. Algorithmes de calcul quantique : logarithmes discrets et factorisation. Dans Actes du 35e symposium annuel sur les fondements de l'informatique, pages 124-134. IEEE, 1994.
https: / / doi.org/ 10.1109 / SFCS.1994.365700
Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han , Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao , Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu et Jian-Wei Pan. Fort avantage informatique quantique utilisant un processeur quantique supraconducteur. Phys. Rév. Lett., 127 : 180501, 2021.
https: / / doi.org/ 10.1103 / PhysRevLett.127.180501
K Wright, KM Beck, Sea Debnath, JM Amini, Y Nam, N Grzesiak, JS Chen, NC Pisenti, M Chmielewski, C Collins et al. Analyse comparative d'un ordinateur quantique de 11 qubits. Communications sur la nature, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
G Wendin. Traitement de l'information quantique avec des circuits supraconducteurs : une revue. Rapports sur les progrès de la physique, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
Adam Bene Watts, Robin Kothari, Luke Schaeffer et Avishay Tal. Séparation exponentielle entre les circuits quantiques peu profonds et les circuits classiques peu profonds illimités en éventail. Dans Actes du 51e symposium annuel ACM SIGACT sur la théorie de l'informatique, pages 515-526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
Andrew Chi-Chih Yao. Comment générer et échanger des secrets. Dans le 27e Symposium annuel sur les fondements de l'informatique (sfcs 1986), pages 162-167. IEEE, 1986.
https: / / doi.org/ 10.1109 / SFCS.1986.25
Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He -Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang , Dachao Wu, Yulin Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu et Jian-Wei Pan. Avantage informatique quantique via un échantillonnage de circuit aléatoire de 60 qubits sur 24 cycles. Bulletin scientifique, 67(3):240-245, 2022.
https: / / doi.org/ 10.1016 / j.scib.2021.10.017
Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel ou Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. Yao, Marko Cetina et Christopher Monroe. Protocoles interactifs pour un avantage quantique classiquement vérifiable. Préimpression arXiv arXiv :2112.05156, 2021.
https:///doi.org/10.48550/arXiv.2112.05156
arXiv: 2112.05156
Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei- Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu et Jian-Wei Pan. Avantage informatique quantique utilisant les photons. Science, 370(6523) :1460-1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Cité par
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath et Ruben Verresen, « Une hiérarchie d'ordre topologique à partir d'unités de profondeur finie, de mesure et de rétroaction », arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch et Robert Koenig, « Circuits adaptatifs à profondeur constante pour manipuler les anyons non abéliens », arXiv: 2205.01933.
[3] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel ou Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. Yao, Marko Cetina et Christopher Monroe, « Protocoles interactifs pour un avantage quantique classiquement vérifiable », arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo et Dmitriy Vassilyev, « PRF homomorphes clés spécifiques aux étoiles issues de la régression linéaire et de la théorie des ensembles extrêmes », arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani et Norman Y. Yao, « Avantage quantique classiquement vérifiable d'un test informatique de Bell », Physique de la nature 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn et Avishay Tal, « Sur le caractère aléatoire certifié des expériences Quantum Advantage », arXiv: 2111.14846.
[7] Nai-Hui Chia et Shih-Han Hung, « Vérification classique de la profondeur quantique », arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa et Seiichiro Tani, « Autotest informatique pour les états magiques intriqués », Examen physique A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde et Eneet Kaur, « Estimation de traces multivariées en profondeur quantique constante », arXiv: 2206.15405.
Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2022-09-21 12:16:02). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.
On Le service cité par Crossref aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2022-09-21 12:16:00).
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.
