1Afdeling Natuurkunde, ETH Zürich, Zwitserland
2Instituut voor Theoretische Studies, ETH Zürich, Zwitserland
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
Een bewijs van kwantumheid is een soort uitdaging-antwoordprotocol waarin een klassieke verificateur op efficiënte wijze het $textit{kwantumvoordeel}$ van een niet-vertrouwde bewijzer kan certificeren. Dat wil zeggen dat een kwantumbewijzer de uitdagingen van de verificateur correct kan beantwoorden en geaccepteerd kan worden, terwijl elke klassieke bewijzer met polynomiale tijd met grote waarschijnlijkheid zal worden afgewezen, op basis van plausibele computationele aannames. Om de uitdagingen van de verificateur te beantwoorden, vereisen bestaande bewijzen van kwantumheid doorgaans dat de kwantumbewijzer een combinatie van kwantumcircuits en metingen van polynomiale grootte uitvoert.
In dit artikel geven we twee bewijzen van kwantumconstructies waarbij de bewijzer alleen $textit{kwantumcircuits met constante diepte}$ (en metingen) hoeft uit te voeren, samen met klassieke berekeningen met logdiepte. Onze eerste constructie is een generieke compiler waarmee we alle bestaande bewijzen van kwantumheid kunnen vertalen naar versies met constante kwantumdiepte. Onze tweede constructie is gebaseerd op het probleem $textit{learning with rounding}$ en levert circuits op met een kortere diepte en die minder qubits vereisen dan de generieke constructie. Daarnaast heeft de tweede constructie ook enige robuustheid tegen geluid.
► BibTeX-gegevens
► Referenties
[1] Scott Aaronson en Alex Arkhipov. De computationele complexiteit van lineaire optica. In Proceedings of the drieënveertigste jaarlijkse ACM-symposium over Theory of computing, pagina's 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, et al. Kwantumsuprematie met behulp van een programmeerbare supergeleidende processor. Natuur, 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: een open-sourceframework voor kwantumcomputing, 2021.
[4] Sanjeev Arora en Boaz Barak. Computationele complexiteit: een moderne benadering. Cambridge University Press, 2009.
[5] Scott Aaronson en Lijie Chen. Complexiteitstheoretische grondslagen van kwantumsuprematie-experimenten. In Proceedings of the 32nd Computational Complexity Conference, CCC '17, pagina's 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik.
https://doi.org/10.48550/arXiv.1612.05903
[6] Scott Aaronson en Sam Gunn. Over de klassieke hardheid van spoofing Lineaire cross-entropie-benchmarking. Theorie van computergebruik, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai en E. Kushilevitz. Cryptografie in ${NC}^0$. In het 45e jaarlijkse IEEE-symposium over de grondslagen van computerwetenschappen, pagina's 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak en Daniel Wichs. Leren met afronding, herzien. In Advances in Cryptology - CRYPTO 2013, pagina's 57-74, Berlijn, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A Barrington. Vertakkingsprogramma's met polynoomgrootte met beperkte breedte herkennen precies die talen in ${NC}^1$. Journal of Computer- en Systeemwetenschappen, 38(1):150–164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
[10] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani en Thomas Vidick. Een cryptografische test van kwantumheid en certificeerbare willekeur vanuit één enkel kwantumapparaat. In 2018 IEEE 59e jaarlijkse symposium over de grondslagen van computerwetenschappen (FOCS), pagina's 320-331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell en Jeremy M. Sage. Trapped-ion quantum computing: vooruitgang en uitdagingen. Technische Natuurkunde beoordelingen, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe en Umesh Vazirani. Over de complexiteit en verificatie van kwantum-willekeurige circuitbemonstering. Natuurfysica, 15(2):159–163, februari 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 en Hartmut Neven. Karakterisering van kwantumsuprematie in apparaten voor de korte termijn. Natuurfysica, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani en Thomas Vidick. Eenvoudiger bewijzen van kwantumheid. In de 15e conferentie over de theorie van kwantumcomputatie, communicatie en cryptografie (TQC 2020), deel 158 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 8:1–8:14, Dagstuhl, Duitsland, 2020. Schloss Dagstuhl–Leibniz- Centrum voor Informatica.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert en Alon Rosen. Pseudo-willekeurige functies en roosters. In Advances in Cryptology – EUROCRYPT 2012, pagina's 719–737. Springer Berlijn Heidelberg, 2012.
https://doi.org/10.1007/978-3-642-29011-4_42
[16] John F Clauser, Michael A Horne, Abner Shimony en Richard A Holt. Voorgesteld experiment om lokale theorieën over verborgen variabelen te testen. Physical Review Letters, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark en Thomas Vidick. Handelsplaats voor tijd: certificeerbare willekeur van circuits met een lage diepte. Communicatie in de wiskundige natuurkunde, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richard Cleve en John Watrous. Snelle parallelle circuits voor de kwantum Fourier-transformatie. In Proceedings 41e jaarlijkse symposium over de fundamenten van de computerwetenschappen, pagina's 526–536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
[19] Pierre Dusart. Autor de functie die het aantal premiers compte. PhD proefschrift, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis en Andrew N Cleland. Oppervlaktecodes: naar praktische grootschalige kwantumberekeningen. Fysieke beoordeling A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] François Le Gall. Privécorrespondentie, 2022.
[22] Craig Gidney en Martin Ekerå. Hoe je 2048-bits RSA-gehele getallen kunt ontbinden in 8 uur met behulp van 20 miljoen luidruchtige qubits. Kwantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu en Matty J Hoban. Het schatten van de entropie van ondiepe circuituitgangen is moeilijk. arXiv voordruk arXiv:2002.12814, 2020.
https://doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara en François Le Gall. Test van kwantumheid met kwantumcircuits met kleine diepte. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), deel 202 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 59:1–59:15, Dagstuhl, Duitsland, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Aram W Harrow en Ashley Montanaro. Kwantum computationele suprematie. Natuur, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Peter Høyer en Robert Spalek. Quantum Fan-out is krachtig. Theorie van computergebruik, 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 en Jianxin Chen. Klassieke simulatie van Quantum Supremacy-circuits. arXiv voordruk arXiv:2005.06787, 2020.
https://doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Kwantumgegevens vervalsen: klassiek een op IQP gebaseerde kwantumtest verslaan. arXiv voordruk 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 en Norman Y. Yao. Klassiek verifieerbaar kwantumvoordeel van een computationele Bell-test. Natuurfysica, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Ljoebashevski, Chris Peikert en Oded Regev. Over ideale roosters en leren met fouten over ringen. In de jaarlijkse internationale conferentie over de theorie en toepassingen van cryptografische technieken, pagina's 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Urmila Mahadev. Klassieke verificatie van kwantumberekeningen. In 2018 IEEE 59e jaarlijkse symposium over de grondslagen van computerwetenschappen (FOCS), pagina's 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A Nielsen en Isaac Chuang. Kwantumberekening en kwantuminformatie, 2002.
[33] A. S. Popova en A.N. Rubtsov. Het kraken van de Quantum Advantage-drempel voor Gauss-bosonbemonstering. In Quantum 2.0 Conferentie en tentoonstelling, pagina QW2A.15. Optica Uitgeversgroep, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. Quantum Computing in het NISQ-tijdperk en daarna. Kwantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Probabilistisch algoritme voor het testen van primaliteit. Journal of Getaltheorie, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. Over roosters, leren met fouten, willekeurige lineaire codes en cryptografie. Publicatieblad van de ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Dan Shepherd en Michael J Bremner. Tijdelijk ongestructureerde kwantumberekening. Proceedings of the Royal Society A: Wiskundige, Fysische en Technische Wetenschappen, 465 (2105): 1413–1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
[38] Peter W. Shor. Algoritmen voor kwantumberekeningen: discrete logaritmen en factoring. In Proceedings 35e jaarlijkse symposium over de grondslagen van de informatica, pagina's 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 Zon, 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 en Jian-Wei Pan. Sterk kwantumcomputervoordeel met behulp van een supergeleidende kwantumprocessor. Fys. 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, et al. Benchmarking van een 11-qubit-kwantumcomputer. Natuurcommunicatie, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Kwantuminformatieverwerking met supergeleidende circuits: een overzicht. Rapporten over de vooruitgang in de natuurkunde, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer en Avishay Tal. Exponentiële scheiding tussen ondiepe kwantumcircuits en onbegrensde, ondiepe klassieke circuits. In Proceedings of the 51e jaarlijkse ACM SIGACT Symposium on Theory of Computing, pagina's 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Andrew Chi-Chih Yao. Hoe geheimen te genereren en uit te wisselen. In het 27e jaarlijkse symposium over de grondslagen van computerwetenschappen (sfcs 1986), pagina's 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, Hij -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 en Jian-Wei Pan. Kwantumcomputervoordeel via willekeurige circuitsampling met 60 qubit en 24 cycli. Wetenschapsbulletin, 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 en Christopher Monroe. Interactieve protocollen voor klassiek verifieerbaar kwantumvoordeel. arXiv voordruk 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 en Jian-Wei Pan. Kwantumcomputervoordeel met behulp van fotonen. Wetenschap, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Geciteerd door
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath en Ruben Verresen, "Een hiërarchie van topologische orde van eenheden met eindige diepte, meting en feedforward", arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch en Robert Koenig, "Adaptieve circuits met constante diepte voor het manipuleren van niet-abelse 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 en Christopher Monroe, “Interactieve protocollen voor klassiek verifieerbaar kwantumvoordeel”, arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo en Dmitriy Vassilyev, "Sterspecifieke sleutel-homomorfe PRF's uit lineaire regressie en extreme verzamelingenleer", arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani en Norman Y. Yao, "Klassiek verifieerbaar kwantumvoordeel van een computationele Bell-test", Natuurfysica 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn en Avishay Tal, “Over gecertificeerde willekeur uit Quantum Advantage Experiments”, arXiv: 2111.14846.
[7] Nai-Hui Chia en Shih-Han Hung, “Klassieke verificatie van kwantumdiepte”, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa en Seiichiro Tani, “Computationele zelftesten voor verstrengelde magische toestanden”, Fysieke beoordeling A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde en Eneet Kaur, "Multivariate sporenschatting in constante kwantumdiepte", arXiv: 2206.15405.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2022-09-21 12:16:02). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2022-09-21 12:16:00).
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.
