1Oddelek za fiziko, ETH Zürich, Švica
2Inštitut za teoretične študije, ETH Zürich, Švica
Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.
Minimalizem
Dokaz kvantnosti je vrsta protokola izziv-odziv, v katerem lahko klasičen verifikator učinkovito potrdi $textit{kvantno prednost}$ nezaupljivega dokazovalca. To pomeni, da lahko kvantni dokazovalnik pravilno odgovori na izzive preveritelja in je sprejet, medtem ko bo vsak klasični dokaznik s polinomskim časom zavrnjen z veliko verjetnostjo na podlagi verjetnih računskih predpostavk. Da bi odgovorili na izzive preverjatelja, obstoječi dokazi o kvantnosti običajno zahtevajo, da kvantni dokaznik izvede kombinacijo kvantnih vezij in meritev polinomske velikosti.
V tem prispevku podajamo dve konstrukciji dokaza kvantnosti, v katerih mora dokazovalnik izvesti samo $textit{kvantna vezja s konstantno globino}$ (in meritve) skupaj s klasičnim izračunom globine log. Naša prva konstrukcija je generični prevajalnik, ki nam omogoča, da vse obstoječe dokaze o kvantnosti prevedemo v različice s konstantno kvantno globino. Naša druga konstrukcija temelji na problemu $textit{učenje z zaokroževanjem}$ in daje vezja s krajšo globino, ki zahtevajo manj kubitov kot generična konstrukcija. Poleg tega ima druga konstrukcija tudi nekaj robustnosti proti hrupu.
► BibTeX podatki
► Reference
[1] Scott Aaronson in Alex Arkhipov. Računska kompleksnost linearne optike. V zborniku triinštiridesetega letnega simpozija ACM o teoriji računalništva, strani 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. Kvantna premoč z uporabo programabilnega superprevodnega procesorja. Narava, 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: Odprtokodni okvir za kvantno računalništvo, 2021.
[4] Sanjeev Arora in Boaz Barak. Računalniška kompleksnost: sodoben pristop. Cambridge University Press, 2009.
[5] Scott Aaronson in Lijie Chen. Teoretične osnove zapletenosti eksperimentov kvantne premoči. V zborniku 32. konference Computational Complexity, CCC '17, strani 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[6] Scott Aaronson in Sam Gunn. O klasični trdoti lažnega linearnega navzkrižnega entropijskega primerjanja. Teorija računalništva, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai in E. Kushilevitz. Kriptografija v ${NC}^0$. Na 45. letnem simpoziju IEEE o temeljih računalništva, strani 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak in Daniel Wichs. Učenje z zaokroževanjem, ponovno. V Napredek v kriptologiji – CRYPTO 2013, strani 57–74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A Barrington. Programi za razvejanje polinomske velikosti z omejeno širino prepoznajo točno te jezike v ${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 in Thomas Vidick. Kriptografski test kvantnosti in naključnosti, ki jo je mogoče potrditi, iz ene same kvantne naprave. Leta 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), strani 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell in Jeremy M. Sage. Kvantno računalništvo z ujetimi ioni: napredek in izzivi. Applied Physics Reviews, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe in Umesh Vazirani. O kompleksnosti in preverjanju vzorčenja kvantnega naključnega vezja. Nature Physics, 15 (2): 159–163, februar 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 in Hartmut Neven. Označevanje kvantne premoči v napravah za bližnji čas. Nature Physics, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani in Thomas Vidick. Preprostejši dokazi kvantnosti. Na 15. konferenci o teoriji kvantnega računalništva, komunikacije in kriptografije (TQC 2020), zvezek 158 Leibniz International Proceedings in Informatics (LIPIcs), strani 8:1–8:14, Dagstuhl, Nemčija, 2020. Schloss Dagstuhl–Leibniz- Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert in Alon Rosen. Psevdonaključne funkcije in mreže. V Napredek v kriptologiji – EUROCRYPT 2012, strani 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 in Richard A Holt. Predlagani eksperiment za testiranje teorij lokalnih skritih spremenljivk. Physical Review Letters, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark in Thomas Vidick. Trgovanje z lokalnostjo za čas: naključnost, ki jo je mogoče potrditi iz krogov z nizko globino. Komunikacije v matematični fiziki, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richard Cleve in John Watrous. Hitra vzporedna vezja za kvantno Fourierjevo transformacijo. V zborniku 41. letnega simpozija o temeljih računalništva, strani 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. Doktorska disertacija, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis in Andrew N Cleland. Površinske kode: K praktičnemu obsežnemu kvantnemu računanju. Physical Review A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] François Le Gall. Zasebno dopisovanje, 2022.
[22] Craig Gidney in Martin Ekerå. Kako faktorizirati 2048-bitna cela števila RSA v 8 urah z uporabo 20 milijonov hrupnih kubitov. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu in Matty J Hoban. Ocenjevanje entropije izhodov plitvega vezja je težko. arXiv prednatis arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara and François Le Gall. Test of Quantumness with Small-Depth Quantum Circuits. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 59:1–59:15, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Aram W Harrow in Ashley Montanaro. Kvantna računalniška premoč. Narava, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Peter Høyer in Robert Špalek. Quantum Fan-out je močan. Teorija računalništva, 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 in Jianxin Chen. Klasična simulacija vezij kvantne premoči. arXiv prednatis arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Kovanje kvantnih podatkov: klasična poraz kvantnega testa, ki temelji na IQP. arXiv prednatis 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 in Norman Y. Yao. Klasično preverljiva kvantna prednost iz računalniškega Bellovega testa. Fizika narave, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert in Oded Regev. Na idealnih mrežah in učenje z napakami nad obroči. Na letni mednarodni konferenci o teoriji in aplikacijah kriptografskih tehnik, strani 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Urmila Mahadev. Klasična verifikacija kvantnih izračunov. Leta 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), strani 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A Nielsen in Isaac Chuang. Kvantno računanje in kvantne informacije, 2002.
[33] AS Popova in AN Rubtsov. Razbijanje praga kvantne prednosti za vzorčenje Gaussovih bozonov. Na konferenci in razstavi Quantum 2.0, stran QW2A.15. Založniška skupina Optika, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. Kvantno računalništvo v dobi NISQ in pozneje. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Probabilistični algoritem za testiranje primalnosti. Journal of Number Theory, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. Na mrežah, učenje z napakami, naključne linearne kode in kriptografija. Journal of the ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Dan Shepherd in Michael J Bremner. Časovno nestrukturirano kvantno računanje. 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 Šor. Algoritmi za kvantno računanje: diskretni logaritmi in faktoring. V zborniku 35. letnega simpozija o temeljih računalništva, strani 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 in Jian-Wei Pan. Močna kvantna računalniška prednost z uporabo superprevodnega kvantnega procesorja. 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, et al. Primerjalno testiranje 11-qubitnega kvantnega računalnika. Nature Communications, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Kvantna obdelava informacij s superprevodnimi vezji: pregled. Poročila o napredku v fiziki, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer in Avishay Tal. Eksponentna ločitev med plitvimi kvantnimi vezji in neomejenimi plitvimi klasičnimi vezji. V zborniku 51. letnega simpozija ACM SIGACT o teoriji računalništva, strani 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Andrew Chi-Chih Yao. Kako ustvariti in izmenjati skrivnosti. V 27. letnem simpoziju o temeljih računalništva (sfcs 1986), strani 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, and Jian-Wei Pan. Quantum computational advantage via 60-qubit 24-cycle random circuit sampling. 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 in Christopher Monroe. Interaktivni protokoli za klasično preverljivo kvantno prednost. arXiv prednatis 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 in Jian-Wei Pan. Kvantna računska prednost z uporabo fotonov. Znanost, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Navedel
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath in Ruben Verresen, "Hierarhija topološkega reda iz enot s končno globino, merjenje in posredovanje naprej", arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch in Robert Koenig, »Prilagodljiva vezja s konstantno globino za manipulacijo neabelovih anionov«, 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 in Christopher Monroe, "Interaktivni protokoli za klasično preverljivo kvantno prednost", arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo in Dmitriy Vassilyev, »Zvezdno specifični ključni homomorfni PRF-ji iz linearne regresije in teorije ekstremnih množic«, arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani in Norman Y. Yao, "Klasično preverljiva kvantna prednost iz računalniškega Bellovega testa", Naravna fizika 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn in Avishay Tal, "O certificirani naključnosti iz eksperimentov kvantne prednosti", arXiv: 2111.14846.
[7] Nai-Hui Chia in Shih-Han Hung, “Klasično preverjanje kvantne globine”, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa in Seiichiro Tani, "Računalniško samotestiranje za zapletena magična stanja", Fizični pregled A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde in Eneet Kaur, »Multivariatna ocena sledi v konstantni kvantni globini«, arXiv: 2206.15405.
Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2022-09-21 12:16:02). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.
On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2022-09-21 12:16:00).
Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.
