1Fizikai Tanszék, ETH Zürich, Svájc
2Institute for Theoretical Studies, ETH Zürich, Svájc
Érdekesnek találja ezt a cikket, vagy szeretne megvitatni? Scite vagy hagyjon megjegyzést a SciRate-en.
Absztrakt
A kvantumosság igazolása egyfajta kihívás-válasz protokoll, amelyben egy klasszikus hitelesítő hatékonyan tudja igazolni egy nem megbízható bizonyító $textit{kvantumelőnye}$. Ez azt jelenti, hogy a kvantumbizonyító helyesen tud válaszolni a hitelesítő kihívásaira, és elfogadásra kerül, míg bármely polinomiális idejű klasszikus bizonyító nagy valószínűséggel elutasításra kerül, elfogadható számítási feltevések alapján. Az ellenőrző kihívásainak megválaszolása érdekében a meglévő kvantumbizonyítások általában megkövetelik, hogy a kvantumbizonyító polinomiális méretű kvantumáramkörök és mérések kombinációját hajtsa végre.
Ebben a cikkben két bizonyítást adunk a kvantumkonstrukciókra, amelyekben a bizonyítónak csak $textit{konstans mélységű kvantumáramkörök}$ (és méréseket) kell végrehajtania a log-mélység klasszikus számítással együtt. Első konstrukciónk egy általános fordítóprogram, amely lehetővé teszi számunkra, hogy a kvantum minden létező bizonyítását állandó kvantummélységű verziókra fordítsuk. Második konstrukciónk a $textit{learning with rounding}$ probléma köré épül, és rövidebb mélységű és kevesebb qubitet igénylő áramköröket eredményez, mint az általános konstrukció. Ezenkívül a második konstrukció némi robusztussággal is rendelkezik a zaj ellen.
► BibTeX adatok
► Referenciák
[1] Scott Aaronson és Alex Arkhipov. A lineáris optika számítási bonyolultsága. In Proceedings of the negyvenharmadik éves ACM szimpózium a számítástechnika elméletéről, 333–342. oldal, 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 és mások. Kvantumfölény programozható szupravezető processzor segítségével. 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 és munkatársai. Qiskit: Nyílt forráskódú keretrendszer a kvantumszámításhoz, 2021.
[4] Sanjeev Arora és Boaz Barak. Számítási komplexitás: modern megközelítés. Cambridge University Press, 2009.
[5] Scott Aaronson és Lijie Chen. A kvantumfölény kísérletek komplexitáselméleti alapjai. In 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 és Sam Gunn. A hamisítás klasszikus keménységéről Lineáris kereszt-entrópia benchmarking. A számítástechnika elmélete, 16(11):1–8, 2020.
https:///doi.org/10.4086/toc.2020.v016a011
[7] B. Applebaum, Y. Ishai és E. Kushilevitz. Kriptográfia ${NC}^0$ nyelven. A 45. éves IEEE szimpózium a számítástechnika alapjairól, 166–175. oldal, 2004.
https:///doi.org/10.1109/FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak és Daniel Wichs. Tanulás kerekítéssel, Revisited. In Advances in Cryptology – CRYPTO 2013, 57–74. oldal, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A Barrington. A korlátos szélességű polinom méretű elágazó programok pontosan felismerik a ${NC}^1$ nyelveket. 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 és Thomas Vidick. A kvantumosság és a hitelesíthető véletlenszerűség kriptográfiai tesztje egyetlen kvantumeszközről. 2018-ban az IEEE 59. éves szimpóziuma a számítástechnika alapjairól (FOCS), 320–331. oldal. IEEE, 2018.
https:///doi.org/10.1145/3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell és Jeremy M. Sage. Csapdába esett kvantumszámítástechnika: Haladás és kihívások. Alkalmazott Fizikai Szemle, 2019.
https:///doi.org/10.1063/1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe és Umesh Vazirani. A kvantum véletlenszerű áramköri mintavétel bonyolultságáról és ellenőrzéséről. Nature Physics, 15(2):159–163, 2019. febr.
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 és Hartmut Neven. A kvantumfölény jellemzése rövid távú eszközökben. Természetfizika, 14(6):595–600, 2018.
https:///doi.org/10.1038/s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani és Thomas Vidick. A kvantumosság egyszerűbb bizonyítékai. A 15. konferencián a kvantumszámítás, kommunikáció és kriptográfia elméletéről (TQC 2020), Leibniz International Proceedings in Informatics (LIPIcs) 158. kötete, 8:1–8:14, Dagstuhl, Németország, 2020. Schloss Dagstuhl-Leibnizniz Zentrum für Informatik.
https:///doi.org/10.4230/LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert és Alon Rosen. Álvéletlen függvények és rácsok. In Advances in Cryptology – EUROCRYPT 2012, 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 és Richard A Holt. Javasolt kísérlet a lokális rejtett változós elméletek tesztelésére. Physical Review Letters, 23(15):880, 1969.
https:///doi.org/10.1103/PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark és Thomas Vidick. Kereskedési hely idővel: igazolható véletlenszerűség alacsony mélységű áramkörökből. Communications in Mathematical Physics, 382(1):49–86, 2021.
https:///doi.org/10.1007/s00220-021-03963-w
[18] Richard Cleve és John Watrous. Gyors párhuzamos áramkörök a kvantum Fourier transzformációhoz. In Proceedings 41st Annual Symposium on Foundations of Computer Science, 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. PhD értekezés, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis és Andrew N Cleland. Felületi kódok: A gyakorlati nagy léptékű kvantumszámítás felé. Fizikai Szemle A, 86(3):032324, 2012.
https:///doi.org/10.1103/PhysRevA.86.032324
[21] François Le Gall. Magánlevelezés, 2022.
[22] Craig Gidney és Martin Ekerå. Hogyan lehet 2048 bites RSA egész számokat faktorálni 8 óra alatt 20 millió zajos qubit használatával. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu és Matty J Hoban. A sekély áramköri kimenetek entrópiáját nehéz megbecsülni. arXiv preprint arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara és François Le Gall. Kvantumvizsgálat kismélységű kvantumáramkörökkel. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Leibniz International Proceedings in Informatics (LIPIcs) 202. kötete, 59:1–59:15 oldal, Dagstuhl, Németország, 2021. Schloss Dagstuhl – Leibniz-Zeten .
https:///doi.org/10.4230/LIPIcs.MFCS.2021.59
[25] Aram W Harrow és Ashley Montanaro. Kvantumszámítási fölény. Nature, 549(7671):203–209, 2017.
https:///doi.org/10.1038/nature23458
[26] Peter Høyer és Robert Špalek. A Quantum Fan-out erős. Számítástechnika elmélete, 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 és Jianxin Chen. A kvantumfölényes áramkörök klasszikus szimulációja. arXiv preprint arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Kvantumadatok kovácsolása: klasszikusan az IQP-alapú kvantumteszt legyőzése. 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 és Norman Y. Yao. Klasszikusan ellenőrizhető kvantumelőny a számítási Bell-tesztből. Nature Physics, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Ljubasevszkij, Chris Peikert és Oded Regev. Az ideális rácsokon és a gyűrűk feletti hibákkal való tanulás. A kriptográfiai technikák elméletével és alkalmazásaival foglalkozó éves nemzetközi konferencia 1–23. Springer, 2010.
https:///doi.org/10.1145/2535925
[31] Urmila Mahadev. Kvantumszámítások klasszikus verifikációja. 2018-ban az IEEE 59. éves szimpóziuma a számítástechnika alapjairól (FOCS), 259–267. oldal. IEEE, 2018.
https:///doi.org/10.1109/FOCS.2018.00033
[32] Michael A Nielsen és Isaac Chuang. Kvantumszámítás és kvantuminformáció, 2002.
[33] AS Popova és AN Rubtsov. A kvantumelőny küszöbének megtörése a Gauss-bozon mintavételénél. A Quantum 2.0 konferencián és kiállításon, a QW2A.15 oldalon. Optica Publishing Group, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. Kvantumszámítástechnika a NISQ-korszakban és azon túl. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Valószínűségi algoritmus a primalitás tesztelésére. Journal of Number Theory, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. Rácsokon, tanulás hibákkal, véletlenszerű lineáris kódokkal és titkosítással. Journal of the ACM (JACM), 56(6):1–40, 2009.
https:///doi.org/10.1145/1568318.1568324
[37] Dan Shepherd és Michael J Bremner. Időben strukturálatlan kvantumszámítás. 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. Algoritmusok kvantumszámításhoz: diszkrét logaritmusok és faktoring. In Proceedings 35. éves szimpózium a számítástechnika alapjairól, 124–134. oldal. 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 és Jian-Wei Pan. Erős kvantumszámítási előny a szupravezető kvantumprocesszor használatával. 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, JS Chen, NC Pisenti, M Chmielewski, C Collins és mások. Egy 11 qubites kvantumszámítógép teljesítményértékelése. Nature Communications, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Kvantum információfeldolgozás szupravezető áramkörökkel: áttekintés. 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 és Avishay Tal. Exponenciális elválasztás a sekély kvantumáramkörök és a korlátlan fan-in sekély klasszikus áramkörök között. In Proceedings of the 51. Annual ACM SIGACT Symposium on Theory of Computing, 515–526. oldal, 2019.
https:///doi.org/10.1145/3313276.3316404
[43] Andrew Chi-Chih Yao. Titkok generálása és cseréje. In 27th Annual Symposium on Foundations of Computer Science (sfcs, 1986), 162–167. oldal. 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 és Jian-Wei Pan. Kvantumszámítási előny a 60 qubites, 24 ciklusú véletlenszerű áramköri mintavételezéssel. 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 és Christopher Monroe. Interaktív protokollok a klasszikusan ellenőrizhető kvantumelőnyhöz. 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 és Jian-Wei Pan. Kvantumszámítási előny fotonok használatával. Science, 370(6523):1460–1463, 2020.
https:///doi.org/10.1126/science.abe8770
Idézi
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath és Ruben Verresen, „A topológiai sorrend hierarchiája véges mélységű egységekből, mérésből és előremenőből”, arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch és Robert Koenig, „Adaptive állandó mélységű áramkörök a nem-abeli anyonok manipulálásához”, 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 Vazirani, Norman Y. Yao, Marko Cetina és Christopher Monroe, „Interactive Protocols for Classically-Verifiable Quantum Advantage”, arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo és Dmitriy Vasziljev, „Csillagspecifikus kulcshomomorf PRF-ek a lineáris regresszióból és az extrém halmazelméletből”, arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani és Norman Y. Yao, „Klasszikusan ellenőrizhető kvantumelőny egy számítási Bell-tesztből”, Nature Physics 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn és Avishay Tal, „On Certified Randomness from Quantum Advantage Experiments”, arXiv: 2111.14846.
[7] Nai-Hui Chia és Shih-Han Hung, „A kvantummélység klasszikus ellenőrzése”, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa és Seiichiro Tani, „Számítógépes önteszt összefonódott mágikus állapotokhoz”, Fizikai áttekintés A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde és Eneet Kaur, „Többváltozós nyombecslés állandó kvantummélységben”, arXiv: 2206.15405.
A fenti idézetek innen származnak SAO/NASA HIRDETÉSEK (utolsó sikeres frissítés: 2022-09-21 12:16:02). Előfordulhat, hogy a lista hiányos, mivel nem minden kiadó ad megfelelő és teljes hivatkozási adatokat.
On Crossref által idézett szolgáltatás művekre hivatkozó adat nem található (utolsó próbálkozás 2022-09-21 12:16:00).
Ez a tanulmány a Quantumban jelent meg Creative Commons Nevezd meg 4.0 International (CC BY 4.0) engedély. A szerzői jog az eredeti szerzői jog tulajdonosainál marad, például a szerzőknél vagy intézményeiknél.
