1Departamentul de Fizică, ETH Zürich, Elveția
2Institutul de Studii Teoretice, ETH Zürich, Elveția
Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.
Abstract
O dovadă a cuanticității este un tip de protocol provocare-răspuns în care un verificator clasic poate certifica eficient $textit{avantajul cuantic}$ al unui demonstrator neîncrezat. Adică, un demonstrator cuantic poate răspunde corect provocărilor verificatorului și poate fi acceptat, în timp ce orice demonstrator clasic în timp polinomial va fi respins cu mare probabilitate, pe baza unor ipoteze de calcul plauzibile. Pentru a răspunde provocărilor verificatorului, dovezile existente ale cuanticei necesită de obicei ca demonstratorul cuantic să efectueze o combinație de circuite și măsurători cuantice de dimensiune polinomială.
În această lucrare, oferim două dovezi ale construcțiilor cuantice în care probatorul trebuie doar să efectueze $textit{circuite cuantice cu adâncime constantă}$ (și măsurători) împreună cu calculul clasic log-depth. Prima noastră construcție este un compilator generic care ne permite să traducem toate dovezile existente ale cuanticei în versiuni cu adâncime cuantică constantă. A doua noastră construcție se bazează pe problema $textit{învățare cu rotunjire}$ și generează circuite cu adâncime mai mică și necesită mai puțini qubiți decât construcția generică. În plus, a doua construcție are și o anumită robustețe împotriva zgomotului.
► Date BibTeX
► Referințe
[1] Scott Aaronson și Alex Arkhipov. Complexitatea de calcul a opticii liniare. În Actele celui de-al patruzeci și treilea simpozion anual ACM despre teoria calculului, paginile 333–342, 2011.
https: / / doi.org/ 10.1145 / 1993636.1993682
[2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell și colab. Supremație cuantică folosind un procesor supraconductor programabil. Nature, 574(7779):505–510, 2019.
https://doi.org/10.1038/s41586-019-1666-5
[3] MD SAJID ANIS, Abby-Mitchell, Héctor Abraham, AduOffei, et al. Qiskit: Un cadru open-source pentru calculul cuantic, 2021.
[4] Sanjeev Arora și Boaz Barak. Complexitatea computațională: o abordare modernă. Cambridge University Press, 2009.
[5] Scott Aaronson și Lijie Chen. Fundamentele teoretice ale complexității experimentelor de supremație cuantică. În Proceedings of the 32nd Computational Complexity Conference, CCC '17, pages 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[6] Scott Aaronson și Sam Gunn. Despre duritatea clasică a spoofingului Benchmarking-ul liniar încrucișat. Theory of Computing, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai și E. Kushilevitz. Criptografia în ${NC}^0$. În cel de-al 45-lea Simpozion anual IEEE privind fundamentele informaticii, paginile 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak și Daniel Wichs. Învățarea cu rotunjire, revizuită. În Advances in Cryptology – CRYPTO 2013, paginile 57–74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A Barrington. Programele de ramificare cu lățime delimitată de dimensiunea polinomilor recunosc exact acele limbi în ${NC}^1$. Journal of Computer and System Sciences, 38(1):150–164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
[10] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani și Thomas Vidick. Un test criptografic al caracterului cuantic și al aleatoriei certificabile dintr-un singur dispozitiv cuantic. În 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), paginile 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell și Jeremy M. Sage. Calcul cuantic cu ioni prinși: progrese și provocări. Recenzii de fizică aplicată, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe și Umesh Vazirani. Despre complexitatea și verificarea eșantionării cu circuite aleatorii cuantice. Nature Physics, 15(2):159–163, februarie 2019.
https://doi.org/10.1038/s41567-018-0318-2
[13] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis și Hartmut Neven. Caracterizarea supremației cuantice în dispozitivele pe termen scurt. Nature Physics, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani și Thomas Vidick. Dovezi mai simple de cuantum. În a 15-a conferință privind teoria calculului cuantic, comunicării și criptografiei (TQC 2020), volumul 158 din Leibniz International Proceedings in Informatics (LIPIcs), paginile 8:1–8:14, Dagstuhl, Germania, 2020. Schloss Dagstuhl–Leibniz- Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert și Alon Rosen. Funcții și rețele pseudo-random. In Advances in Cryptology – EUROCRYPT 2012, paginile 719–737. Springer Berlin Heidelberg, 2012.
https://doi.org/10.1007/978-3-642-29011-4_42
[16] John F Clauser, Michael A Horne, Abner Shimony și Richard A Holt. Experiment propus pentru a testa teoriile locale cu variabile ascunse. Physical Review Letters, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark și Thomas Vidick. Localitate comercială pentru timp: aleatorie certificabilă din circuite cu adâncime mică. Communications in Mathematical Physics, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richard Cleve și John Watrous. Circuite paralele rapide pentru transformarea cuantică Fourier. În Proceedings 41st Annual Symposium on Foundations of Computer Science, paginile 526–536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
[19] Pierre Dusart. Autour de la fonction qui compte le nombre de nombres premiers. Teză de doctorat, Université de Limoges, 1998.
https://www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis și Andrew N Cleland. Codurile de suprafață: Către calcule cuantice practice la scară largă. Physical Review A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] François Le Gall. Corespondență privată, 2022.
[22] Craig Gidney și Martin Ekerå. Cum să factorizezi numere întregi RSA de 2048 de biți în 8 ore folosind 20 de milioane de qubiți zgomotoși. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu și Matty J Hoban. Estimarea entropiei ieșirilor de circuit superficial este dificilă. arXiv preprint arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara și François Le Gall. Test de cuantitate cu circuite cuantice de adâncime mică. În 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volumul 202 din Leibniz International Proceedings in Informatics (LIPIcs), paginile 59:1–59:15, Dagstuhl, Germania, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Aram W Harrow și Ashley Montanaro. Supremația computațională cuantică. Nature, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Peter Høyer și Robert Špalek. Fan-out-ul cuantic este puternic. Theory of Computing, 1(5):81–103, 2005.
https: / / doi.org/ 10.4086 / toc.2005.v001a005
[27] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi și Jianxin Chen. Simularea clasică a circuitelor de supremație cuantică. arXiv preprint arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Falsificarea datelor cuantice: înfrângerea clasică a unui test cuantic bazat pe IQP. arXiv preprint arXiv:1912.05547, 2019.
https:///doi.org/10.48550/arXiv.1912.05547
arXiv: 1912.05547
[29] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani și Norman Y. Yao. Avantaj cuantic verificabil clasic de la un test Bell computațional. Nature Physics, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert și Oded Regev. Pe zăbrele ideale și învățarea cu erori peste inele. În Conferința internațională anuală privind teoria și aplicațiile tehnicilor criptografice, paginile 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Urmila Mahadev. Verificarea clasică a calculelor cuantice. În 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), paginile 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A Nielsen și Isaac Chuang. Calcul cuantic și informații cuantice, 2002.
[33] AS Popova și AN Rubțov. Scăparea pragului de avantaj cuantic pentru eșantionarea bosonilor gaussiani. În Conferința și Expoziția Quantum 2.0, pagina QW2A.15. Optica Publishing Group, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. Calcularea cuantică în era NISQ și nu numai. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Algoritm probabilistic pentru testarea primalității. Journal of Number Theory, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. Pe zăbrele, învățarea cu erori, coduri liniare aleatorii și criptografie. Jurnalul ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Dan Shepherd și Michael J Bremner. Calcul cuantic nestructurat temporal. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465(2105):1413–1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
[38] Peter W Shor. Algoritmi pentru calcul cuantic: logaritmi discreti si factoring. În Proceedings, al 35-lea simpozion anual despre fundamentele informaticii, paginile 124–134. IEEE, 1994.
https: / / doi.org/ 10.1109 / SFCS.1994.365700
[39] 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 și Jian-Wei Pan. Avantaj puternic de calcul cuantic folosind un procesor cuantic supraconductor. Fiz. Rev. Lett., 127:180501, 2021.
https: / / doi.org/ 10.1103 / PhysRevLett.127.180501
[40] K Wright, KM Beck, Sea Debnath, JM Amini, Y Nam, N Grzesiak, JS Chen, NC Pisenti, M Chmielewski, C Collins și colab. Evaluarea comparativă a unui computer cuantic de 11 qubiți. Nature communications, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Procesarea informațiilor cuantice cu circuite supraconductoare: o revizuire. Rapoarte privind progresul în fizică, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer și Avishay Tal. Separarea exponențială între circuitele cuantice superficiale și circuitele clasice superficiale nelimitate de ventilator. În Proceedings of the 51th Annual ACM SIGACT Symposium on Theory of Computing, paginile 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Andrew Chi-Chih Yao. Cum să generați și să schimbați secrete. În cel de-al 27-lea Simpozion anual privind fundamentele informaticii (sfcs 1986), paginile 162–167. IEEE, 1986.
https: / / doi.org/ 10.1109 / SFCS.1986.25
[44] 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 și Jian-Wei Pan. Avantaj computațional cuantic prin eșantionare aleatoare a circuitelor de 60 de qubiți pe 24 de cicluri. Science Bulletin, 67(3):240–245, 2022.
https: / / doi.org/ 10.1016 / j.scib.2021.10.017
[45] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or 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 și Christopher Monroe. Protocoale interactive pentru avantajul cuantic verificabil clasic. arXiv preprint arXiv:2112.05156, 2021.
https:///doi.org/10.48550/arXiv.2112.05156
arXiv: 2112.05156
[46] 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 și Jian-Wei Pan. Avantaj computațional cuantic folosind fotoni. Science, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Citat de
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath și Ruben Verresen, „O ierarhie a ordinii topologice din unități de adâncime finită, măsurare și feedforward”, arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch și Robert Koenig, „Circuite adaptive constant-depth for manipulating non-abelian anyons”, arXiv: 2205.01933.
[3] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or 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 și Christopher Monroe, „Protocoale interactive pentru avantajul cuantic verificabil clasic”, arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo și Dmitriy Vassiliev, „PRF-uri homomorfe cheie specifice stelelor din regresia liniară și teoria seturilor extreme”, arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani și Norman Y. Yao, „Classically verificable quantum advantage from a computational Bell test”, Fizica naturii 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn și Avishay Tal, „On Certified Randomness from Quantum Advantage Experiments”, arXiv: 2111.14846.
[7] Nai-Hui Chia și Shih-Han Hung, „Verificarea clasică a adâncimii cuantice”, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa și Seiichiro Tani, „Autotestarea computațională pentru stări magice încurcate”, Revizuire fizică A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde și Eneet Kaur, „Multivariate trace estimation in constant quantum depth”, arXiv: 2206.15405.
Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2022-09-21 12:16:02). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.
On Serviciul citat de Crossref nu s-au găsit date despre citarea lucrărilor (ultima încercare 2022-09-21 12:16:00).
Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.
