1Füüsika osakond, ETH Zürich, Šveits
2Teoreetiliste uuringute instituut, ETH Zürich, Šveits
Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.
Abstraktne
Kvantsuse tõend on väljakutse-vastuse protokoll, mille puhul klassikaline kontrollija saab tõhusalt sertifitseerida ebausaldusväärse tõestaja $teksti{kvantieelise}$. See tähendab, et kvanttõestaja suudab õigesti vastata tõendaja väljakutsetele ja olla aktsepteeritud, samas kui iga polünoomaja klassikaline tõestaja lükatakse suure tõenäosusega tagasi, tuginedes usutavatele arvutuslikele eeldustele. Tõendaja väljakutsetele vastamiseks nõuavad olemasolevad kvantitõestused tavaliselt, et kvanttõestaja teostaks polünoomisuuruses kvantahelate ja mõõtmiste kombinatsiooni.
Selles artiklis anname kaks tõestust kvantkonstruktsioonide kohta, mille puhul tõestaja peab tegema ainult $tekstiit{konstantse sügavusega kvantahelad}$ (ja mõõtmised) koos logaritmilise sügavuse klassikalise arvutusega. Meie esimene konstruktsioon on üldine kompilaator, mis võimaldab meil tõlkida kõik olemasolevad kvantsuse tõendid konstantse kvantsügavuse versioonideks. Meie teine konstruktsioon põhineb $textit{learning with rounding}$ probleemil ja annab lühema sügavusega ahelad, mis nõuavad vähem kubiteid kui tavaline konstruktsioon. Lisaks on teisel konstruktsioonil ka mõningane mürakindlus.
► BibTeX-i andmed
► Viited
[1] Scott Aaronson ja Alex Arkhipov. Lineaaroptika arvutuslik keerukus. Väljaandes Proceedings of the 333-th century ACM symposium on Theory of Computing, lk 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 jt. Kvantülimus programmeeritava ülijuhtiva protsessori abil. 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 jt. Qiskit: avatud lähtekoodiga raamistik kvantarvutite jaoks, 2021.
[4] Sanjeev Arora ja Boaz Barak. Arvutuslik keerukus: kaasaegne lähenemine. Cambridge University Press, 2009.
[5] Scott Aaronson ja Lijie Chen. Kvantülimsuse katsete keerukus-teoreetilised alused. In Proceedings of the 32nd Computational Complexity Conference, CCC ’17, lk 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. Lineaarse rist-entroopia võrdlusuuringu võltsimise klassikalisest kõvadusest. Arvutusteooria, 16(11):1–8, 2020.
https:///doi.org/10.4086/toc.2020.v016a011
[7] B. Applebaum, Y. Ishai ja E. Kushilevitz. Krüptograafia keeles ${NC}^0$. 45. aastasel IEEE sümpoosionil arvutiteaduse aluste kohta, lk 166–175, 2004.
https:///doi.org/10.1109/FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak ja Daniel Wichs. Ümardamisega õppimine, uuesti läbi vaadatud. In Advances in Cryptology – CRYPTO 2013, lk 57–74, Berliin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A Barrington. Piiratud laiusega polünoomi suuruses hargnemisprogrammid tunnevad ära täpselt need keeled keeles ${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. Kvantsuse ja sertifitseeritava juhuslikkuse krüptograafiline test ühest kvantseadmest. 2018. aastal IEEE 59. iga-aastane arvutiteaduse aluste sümpoosion (FOCS), lk 320–331. IEEE, 2018.
https:///doi.org/10.1145/3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell ja Jeremy M. Sage. Püütud ioonide kvantarvuti: edusammud ja väljakutsed. Rakendusfüüsika ülevaated, 2019.
https:///doi.org/10.1063/1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe ja Umesh Vazirani. Kvantjuhusliku vooluringi valimi võtmise keerukusest ja kontrollimisest. Nature Physics, 15(2):159–163, veebruar 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. Kvantiülemuse iseloomustamine lähiaja seadmetes. 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. Kvantsuse lihtsamad tõendid. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics (LIPIcs), köide 158, lk 8:1–8:14, Dagstuhl, Saksamaa, 2020. Schloss Dagstuhl-Leibnizniz Informaatika keskus.
https:///doi.org/10.4230/LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert ja Alon Rosen. Pseudojuhuslikud funktsioonid ja võred. Väljaandes Advances in Cryptology – EUROCRYPT 2012, lk 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. Kavandatud katse kohalike peidetud muutujate teooriate testimiseks. Physical Review Letters, 23(15):880, 1969.
https:///doi.org/10.1103/PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark ja Thomas Vidick. Ajaga kauplemispaik: madala sügavusega ahelatest sertifitseeritav juhuslikkus. Communications in Mathematical Physics, 382(1):49–86, 2021.
https:///doi.org/10.1007/s00220-021-03963-w
[18] Richard Cleve ja John Watrous. Kiired paralleelsed ahelad kvant-Fourieri teisenduseks. In Proceedings 41st Annual Symposium on Foundations of Computer Science, lk 526–536. IEEE, 2000.
https:///doi.org/10.1109/SFCS.2000.892140
[19] Pierre Dusart. Autor de la fonction qui compte le nombre de nombres premiers. Doktoritöö, 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. Pinnakoodid: praktilise suuremahulise kvantarvutuse suunas. Physical Review A, 86(3):032324, 2012.
https:///doi.org/10.1103/PhysRevA.86.032324
[21] François Le Gall. Erakirjavahetus, 2022.
[22] Craig Gidney ja Martin Ekerå. Kuidas faktoreerida 2048-bitised RSA-täisarvud 8 tunni jooksul, kasutades 20 miljonit mürarikast kubitti. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu ja Matty J Hoban. Madalate vooluahelate väljundite entroopia hindamine on raske. arXiv eeltrükk arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara ja François Le Gall. Kvantsuse test väikese sügavusega kvantahelatega. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Leibniz International Proceedings in Informatics (LIPIcs) köide 202, lk 59:1–59:15, Dagstuhl, Saksamaa, 2021. Schloss Dagstuhl – Leibniz-Zatiken .
https:///doi.org/10.4230/LIPIcs.MFCS.2021.59
[25] Aram W Harrow ja Ashley Montanaro. Kvantarvutuslik ülimuslikkus. Nature, 549 (7671): 203–209, 2017.
https:///doi.org/10.1038/nature23458
[26] Peter Høyer ja Robert Špalek. Quantum Fan-out on võimas. Arvutusteooria, 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. Kvantülimuse vooluringide klassikaline simulatsioon. arXiv eeltrükk arXiv: 2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Kvantandmete sepistamine: klassikaline IQP-põhise kvanttesti alistamine. arXiv eeltrükk 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. Klassikaliselt kontrollitav kvanteelis arvutuslikust Belli testist. Nature Physics, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Ljubaševski, Chris Peikert ja Oded Regev. Ideaalvõredest ja rõngaste üle vigadega õppimisest. Krüptotehnikate teooria ja rakenduste aastakonverentsil, lk 1–23. Springer, 2010.
https:///doi.org/10.1145/2535925
[31] Urmila Mahadev. Kvantarvutuste klassikaline kontrollimine. 2018. aastal IEEE 59. iga-aastane arvutiteaduse aluste sümpoosion (FOCS), lk 259–267. IEEE, 2018.
https:///doi.org/10.1109/FOCS.2018.00033
[32] Michael A Nielsen ja Isaac Chuang. Kvantarvutus ja kvantteave, 2002.
[33] A. S. Popova ja A.N. Rubtsov. Gaussi bosoni proovivõtu kvanteelise läve murdmine. Quantum 2.0 konverentsil ja näitusel lk QW2A.15. Optica Publishing Group, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. Kvantarvuti NISQ ajastul ja pärast seda. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Tõenäosuslik algoritm primaalsuse testimiseks. Journal of Number Theory, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. Võretel, vigadega õppimine, juhuslikud lineaarsed koodid ja krüptograafia. Journal of the ACM (JACM), 56(6):1–40, 2009.
https:///doi.org/10.1145/1568318.1568324
[37] Dan Shepherd ja Michael J Bremner. Ajaliselt struktureerimata kvantarvutus. 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. Kvantarvutuse algoritmid: diskreetsed logaritmid ja faktoring. Väljaandes Proceedings 35th year symposium on Foundations of Computer science, lk 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. Ülijuhtiva kvantprotsessori kasutamise tugev kvantarvutuslik eelis. 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 jt. 11-kubitise kvantarvuti võrdlusuuringud. Looduskommunikatsioonid, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Kvantinformatsiooni töötlemine ülijuhtivate ahelatega: ülevaade. Aruanded füüsika edusammude kohta, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer ja Avishay Tal. Eksponentsiaalne eraldus madalate kvantahelate ja piiramata ventilaatoriga madalate klassikaliste vooluahelate vahel. In Proceedings of the 51. Annual ACM SIGACT Symposium on Theory of Computing, lk 515–526, 2019.
https:///doi.org/10.1145/3313276.3316404
[43] Andrew Chi-Chih Yao. Kuidas luua ja vahetada saladusi. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), lk 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. Kvantarvutuse eelis 60-kubitise 24-tsüklilise juhusliku vooluringi diskreetimise kaudu. 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. Interaktiivsed protokollid klassikaliselt kontrollitava kvanteelise jaoks. arXiv eeltrükk 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. Kvantarvutuse eelis footonite kasutamisel. Science, 370 (6523): 1460–1463, 2020.
https:///doi.org/10.1126/science.abe8770
Viidatud
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath ja Ruben Verresen, "Topoloogilise järjekorra hierarhia piiratud sügavustest unitaaridest, mõõtmisest ja edasisuunamisest", arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch ja Robert Koenig, „Adaptive constant-depth circuits 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, Thomassh Vidick, U Vazirani, Norman Y. Yao, Marko Cetina ja Christopher Monroe, "Interactive Protocols for Classically-Verifible Quantum Advantage" arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo ja Dmitriy Vassiljev, "Tähespetsiifilised võtmehomomorfsed PRF-id lineaarsest regressioonist ja äärmusliku hulga teooriast", arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani ja Norman Y. Yao, "Klassikaliselt kontrollitav kvanteelis arvutuslikust Belli testist", Nature Physics 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, "Kvantsügavuse klassikaline kontrollimine", arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa ja Seiichiro Tani, "Arvutuslik enesetestimine takerdunud võluseisundite jaoks", Physical Review A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde ja Eneet Kaur, "Multivariate trace estimation in constant quantumsügavus", arXiv: 2206.15405.
Ülaltoodud tsitaadid on pärit SAO/NASA KUULUTUSED (viimati edukalt värskendatud 2022-09-21 12:16:02). Loend võib olla puudulik, kuna mitte kõik väljaandjad ei esita sobivaid ja täielikke viiteandmeid.
On Crossrefi viidatud teenus teoste viitamise andmeid ei leitud (viimane katse 2022-09-21 12:16:00).
See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.
