1Fysiikan laitos, ETH Zürich, Sveitsi
2Institute for Theoretical Studies, ETH Zürich, Sveitsi
Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.
Abstrakti
Todistus kvanttiudesta on eräänlainen haaste-vastausprotokolla, jossa klassinen todentaja voi tehokkaasti varmentaa epäluotettavan todistajan $teksti{kvanttietu}$. Toisin sanoen kvanttitodistaja voi vastata oikein todentajan haasteisiin ja tulla hyväksytyksi, kun taas kaikki polynomiaikaiset klassiset todistajat hylätään suurella todennäköisyydellä uskottavien laskennallisten oletusten perusteella. Vastatakseen todentajan haasteisiin olemassa olevat kvanttitodisteet edellyttävät tyypillisesti kvanttitodistajaa yhdistelmän polynomikokoisia kvanttipiirejä ja mittauksia.
Tässä artikkelissa annamme kaksi todistetta kvanttikonstruktioista, joissa todistajan tarvitsee suorittaa vain $textit{vakiosyvyys kvanttipiirit}$ (ja mittaukset) yhdessä log-syvyysklassisen laskennan kanssa. Ensimmäinen konstruktiomme on yleinen kääntäjä, jonka avulla voimme kääntää kaikki olemassa olevat kvanttitodisteet vakiokvanttisyvyyden versioiksi. Toinen konstruktiomme perustuu $textit{learning with rounding}$ -ongelmaan, ja se tuottaa piirejä, joiden syvyys on lyhyempi ja jotka vaativat vähemmän kubitteja kuin yleinen rakenne. Lisäksi toisessa rakenteessa on myös jonkin verran kestävyyttä melua vastaan.
► BibTeX-tiedot
► Viitteet
[1] Scott Aaronson ja Alex Arkhipov. Lineaarioptiikan laskennallinen monimutkaisuus. Teoksessa Proceedings of the 333-th century ACM symposium on Theory of Computing, sivut 342–2011, XNUMX.
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 jne. Kvanttiylivalta ohjelmoitavalla suprajohtavalla prosessorilla. 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 ai. Qiskit: Avoimen lähdekoodin kehys kvanttilaskentaan, 2021.
[4] Sanjeev Arora ja Boaz Barak. Laskennallinen monimutkaisuus: moderni lähestymistapa. Cambridge University Press, 2009.
[5] Scott Aaronson ja Lijie Chen. Kvanttiylivoimakokeiden monimutkaisuusteoreettiset perusteet. Julkaisussa Proceedings of the 32nd Computational Complexity Conference, CCC ’17, sivut 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[6] Scott Aaronson ja Sam Gunn. Huijauksen klassisesta kovuudesta Lineaarisen ristien entropia-benchmarking. Theory of Computing, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai ja E. Kushilevitz. Kryptografia ${NC}^0$. 45. vuotuisessa IEEE-symposiumissa tietojenkäsittelytieteen perusteista, sivut 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak ja Daniel Wichs. Learning with Rounding, Revisited. In Advances in Cryptology – CRYPTO 2013, sivut 57–74, Berliini, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A Barrington. Rajatun leveyden polynomikokoiset haarautumisohjelmat tunnistavat täsmälleen kyseiset kielet kohdassa ${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 ja Thomas Vidick. Kvanttiuden ja sertifioitavan satunnaisuuden kryptografinen testi yhdestä kvanttilaitteesta. Vuonna 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), sivut 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / +3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell ja Jeremy M. Sage. Loukkuun jäänyt kvanttilaskenta: edistyminen ja haasteet. Applied Physics Reviews, 2019.
https: / / doi.org/ 10.1063 / +1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe ja Umesh Vazirani. Kvanttisatunnaispiirinäytteistyksen monimutkaisuudesta ja todentamisesta. Nature Physics, 15(2):159–163, helmikuu 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 ja Hartmut Neven. Kvanttiylivallan karakterisointi lähiajan laitteissa. Nature Physics, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani ja Thomas Vidick. Yksinkertaiset todisteet kvanttiudesta. 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics (LIPIcs) osa 158, sivut 8:1–8:14, Dagstuhl, Saksa, 2020. Schloss Dagstuhl-Leibnizniz Tietokeskus.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert ja Alon Rosen. Pseudosatunnaiset funktiot ja hilat. Julkaisussa Advances in Cryptology – EUROCRYPT 2012, sivut 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 ja Richard A Holt. Ehdotettu kokeilu paikallisten piilomuuttujien teorioiden testaamiseksi. Physical Review Letters, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark ja Thomas Vidick. Ajan kaupankäyntipaikka: varmennettu satunnaisuus matalan syvyyspiireistä. Communications in Mathematical Physics, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richard Cleve ja John Watrous. Nopeat rinnakkaispiirit kvantti-Fourier-muunnokselle. Julkaisussa Proceedings 41st Annual Symposium on Foundations of Computer Science, sivut 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. Väitöskirja, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis ja Andrew N Cleland. Pintakoodit: Kohti käytännöllistä suuren mittakaavan kvanttilaskentaa. Physical Review A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] François Le Gall. Yksityinen kirjeenvaihto, 2022.
[22] Craig Gidney ja Martin Ekerå. Kuinka kertoa 2048-bittiset RSA-kokonaisluvut 8 tunnissa käyttämällä 20 miljoonaa meluisaa kubittia. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu ja Matty J Hoban. Matalien piirien lähtöjen entropian arviointi on vaikeaa. arXiv preprint arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara ja François Le Gall. Kvanttimittaus pienisyvyyden kvanttipiireillä. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Leibniz International Proceedings in Informatics (LIPIcs) nide 202, sivut 59:1–59:15, Dagstuhl, Saksa, 2021. Schloss Dagstuhl – Leibniz-Z-Z. .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Aram W Harrow ja Ashley Montanaro. Kvanttilaskennallinen ylivalta. Nature, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Peter Høyer ja Robert Špalek. Quantum Fan-out on tehokas. 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 ja Jianxin Chen. Kvanttiylivoimapiirien klassinen simulointi. arXiv preprint arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Kvanttidatan väärentäminen: klassinen IQP-pohjaisen kvanttitestin kukistaminen. 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 ja Norman Y. Yao. Klassisesti todennettavissa oleva kvanttietu laskennallisesta Bell-testistä. Nature Physics, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert ja Oded Regev. Ihanteellisella hilalla ja oppiminen virheillä renkaiden yli. Vuosittaisessa kansainvälisessä kryptografisten tekniikoiden teoriaa ja sovelluksia käsittelevässä konferenssissa, sivut 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / +2535925
[31] Urmila Mahadev. Kvanttilaskunnan klassinen verifiointi. Vuonna 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), sivut 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A Nielsen ja Isaac Chuang. Kvanttilaskenta ja kvanttitiedot, 2002.
[33] A.S. Popova ja A.N. Rubtsov. Kvanttiedun kynnyksen murtaminen Gaussin bosonin näytteenottoon. Quantum 2.0 -konferenssissa ja -näyttelyssä sivulla QW2A.15. Optica Publishing Group, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. Kvanttilaskenta NISQ-aikakaudella ja sen jälkeen. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Todennäköisyyspohjainen algoritmi primaalisuuden testaamiseen. Journal of Number Theory, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. Hilat, oppiminen virheiden, satunnaisten lineaaristen koodien ja kryptografian kanssa. Journal of the ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / +1568318.1568324
[37] Dan Shepherd ja Michael J Bremner. Ajallisesti strukturoimaton kvanttilaskenta. 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. Kvanttilaskennan algoritmit: diskreetit logaritmit ja factoring. Proceedingsissa 35. vuotuinen symposium tietojenkäsittelytieteen perusteista, sivut 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 ja Jian-Wei Pan. Vahva kvanttilaskennan etu suprajohtavan kvanttiprosessorin käyttämisessä. Phys. 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, J-S Chen, NC Pisenti, M Chmielewski, C Collins, et ai. 11 qubitin kvanttitietokoneen benchmarking. Luontoviestintä, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Kvanttitietojen käsittely suprajohtavilla piireillä: katsaus. Reports on Progress in Physics, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer ja Avishay Tal. Eksponentiaalinen erotus matalien kvanttipiirien ja rajoittamattomien matalien klassisten piirien välillä. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, sivut 515–526, 2019.
https: / / doi.org/ 10.1145 / +3313276.3316404
[43] Andrew Chi-Chih Yao. Kuinka luoda ja vaihtaa salaisuuksia. 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), sivut 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 ja Jian-Wei Pan. Kvanttilaskennan etu 60 qubitin 24-syklin satunnaispiirinäytteistyksen avulla. 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 Vazira Y. Yao, Marko Cetina ja Christopher Monroe. Interaktiiviset protokollat klassisesti todennettavissa olevaan kvanttiedukseen. 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 ja Jian-Wei Pan. Kvanttilaskennan etu fotoneilla. Science, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Viitattu
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath ja Ruben Verresen, "Topologisen järjestyksen hierarkia äärellisistä syvyyksistä unitaareista, mittauksesta ja eteenpäin". arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch ja Robert Koenig, "Adaptiiviset vakiosyvyydet piirit ei-abelilaisten anyonien manipulointiin", 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, Thomassh Vidick, U. Vazirani, Norman Y. Yao, Marko Cetina ja Christopher Monroe, "Interactive Protocols for Classically-Verifable Quantum Advantage", arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo ja Dmitriy Vassiljev, "Tähtispesifiset avainhomomorfiset PRF:t lineaarisesta regressiosta ja äärimmäisestä joukkoteoriasta", arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani ja Norman Y. Yao, "Klassisesti todennettavissa oleva kvanttietu laskennallisesta Bell-testistä", Luontofysiikka 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn ja Avishay Tal, "On Certified Randomness from Quantum Advantage Experiments", arXiv: 2111.14846.
[7] Nai-Hui Chia ja Shih-Han Hung, "Kvanttisyvyyden klassinen verifiointi", arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa ja Seiichiro Tani, "Computational self-testing for takeled magic states", Fyysinen tarkastelu A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde ja Eneet Kaur, "Multivariate trace estimation in vakio kvanttisyvyydellä", arXiv: 2206.15405.
Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2022-09-21 12:16:02). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.
On Crossrefin siteerattu palvelu tietoja teosten viittaamisesta ei löytynyt (viimeinen yritys 2022-09-21 12:16:00).
Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.
