1Institutionen för fysik, ETH Zürich, Schweiz
2Institutet för teoretiska studier, ETH Zürich, Schweiz
Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.
Abstrakt
Ett bevis på kvantitet är en typ av utmaning-svar-protokoll där en klassisk verifierare effektivt kan certifiera $textit{quantum advantage}$ för en opålitlig bevisare. Det vill säga, en kvantbevisare kan korrekt svara på verifierarens utmaningar och accepteras, medan alla klassiska polynom-tidsbevisare kommer att förkastas med hög sannolikhet, baserat på rimliga beräkningsantaganden. För att svara på verifierarens utmaningar kräver befintliga bevis på kvantitet typiskt att kvantbevisaren utför en kombination av kvantkretsar och mätningar i polynomstorlek.
I den här artikeln ger vi två bevis på kvantitetskonstruktioner där provaren bara behöver utföra $textit{kvantkretsar med konstant djup}$ (och mätningar) tillsammans med klassisk beräkning av log-djup. Vår första konstruktion är en generisk kompilator som låter oss översätta alla befintliga bevis på kvantitet till versioner med konstant kvantdjup. Vår andra konstruktion är baserad på problemet $textit{learning with rounding}$, och ger kretsar med kortare djup och som kräver färre qubits än den generiska konstruktionen. Dessutom har den andra konstruktionen också en viss robusthet mot buller.
► BibTeX-data
► Referenser
[1] Scott Aaronson och Alex Arkhipov. Beräkningskomplexiteten hos linjär optik. I Proceedings of the fyrtiotredje årliga ACM-symposium om Theory of computing, sidorna 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. Kvantöverlägsenhet med hjälp av en programmerbar supraledande processor. 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 al. Qiskit: Ett ramverk med öppen källkod för kvantberäkning, 2021.
[4] Sanjeev Arora och Boaz Barak. Beräkningskomplexitet: ett modernt tillvägagångssätt. Cambridge University Press, 2009.
[5] Scott Aaronson och Lijie Chen. Komplexitetsteoretiska grunder för kvantöverlägsenhetsexperiment. In Proceedings of the 32nd Computational Complexity Conference, CCC '17, sid 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[6] Scott Aaronson och Sam Gunn. Om den klassiska hårdheten av spoofing Linjär cross-entropy benchmarking. Theory of Computing, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai och E. Kushilevitz. Kryptografi i ${NC}^0$. I 45:e årliga IEEE Symposium on Foundations of Computer Science, sidorna 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak och Daniel Wichs. Lärande med avrundning, Revisited. In Advances in Cryptology – CRYPTO 2013, sidorna 57–74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A Barrington. Förgreningsprogram med begränsad bredd i polynomstorlek känner igen exakt de språken i ${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 och Thomas Vidick. Ett kryptografiskt test av kvantitet och certifierbar slumpmässighet från en enda kvantenhet. Under 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), sidorna 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell och Jeremy M. Sage. Fångad-jon kvantberäkning: Framsteg och utmaningar. Applied Physics Reviews, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe och Umesh Vazirani. Om komplexiteten och verifieringen av slumpmässig kvantkretssampling. Nature Physics, 15(2):159–163, feb 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 och Hartmut Neven. Karakteriserande kvantöverlägsenhet i enheter på kort sikt. Nature Physics, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani och Thomas Vidick. Enklare bevis på kvantitet. I 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volym 158 av Leibniz International Proceedings in Informatics (LIPIcs), sidorna 8:1–8:14, Dagstuhl, Tyskland, 2020. Schloss Dagstuhl–Leibniz- Zentrum für Informatik.
https: / ⠀ </ ⠀ <doi.org/†<10.4230 / ⠀ <LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert och Alon Rosen. Pseudoslumpmässiga funktioner och gitter. In Advances in Cryptology – EUROCRYPT 2012, sidorna 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 och Richard A Holt. Föreslaget experiment för att testa lokala teorier om dolda variabler. Physical Review Letters, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark och Thomas Vidick. Handelsplats för tid: certifierbar slumpmässighet från lågdjupa kretsar. Communications in Mathematical Physics, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richard Cleve och John Watrous. Snabba parallella kretsar för kvant-Fourier-transformen. I Proceedings 41st Annual Symposium on Foundations of Computer Science, sidorna 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. Doktorsavhandling, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis och Andrew N Cleland. Ytkoder: Mot praktisk storskalig kvantberäkning. Physical Review A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] François Le Gall. Privat korrespondens, 2022.
[22] Craig Gidney och Martin Ekerå. Hur man faktorisera 2048 bitars RSA-heltal på 8 timmar med 20 miljoner brusiga qubits. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu och Matty J Hoban. Att uppskatta entropin för grunda kretsutgångar är svårt. arXiv förtryck arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara och François Le Gall. Test av kvantitet med små djupa kvantkretsar. I 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volym 202 av Leibniz International Proceedings in Informatics (LIPIcs), sid 59:1–59:15, Dagstuhl, Tyskland, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Aram W Harrow och Ashley Montanaro. Kvantberäkningsöverlägsenhet. Nature, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Peter Høyer och Robert Špalek. Quantum Fan-out är kraftfull. 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 och Jianxin Chen. Klassisk simulering av Quantum Supremacy Circuits. arXiv förtryck arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Smida kvantdata: klassiskt besegra ett IQP-baserat kvanttest. arXiv förtryck 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 och Norman Y. Yao. Klassiskt verifierbar kvantfördel från ett beräkningsmässigt Bell-test. Nature Physics, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert och Oded Regev. På idealiska galler och lärande med fel över ringar. I årlig internationell konferens om teori och tillämpningar av kryptografiska tekniker, sidorna 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Urmila Mahadev. Klassisk verifiering av kvantberäkningar. Under 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), sidorna 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A Nielsen och Isaac Chuang. Kvantberäkning och kvantinformation, 2002.
[33] AS Popova och AN Rubtsov. Knäcka Quantum Advantage-tröskeln för Gaussisk bosonsampling. I Quantum 2.0 Conference and Exhibition, sidan QW2A.15. Optica Publishing Group, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. Quantum Computing i NISQ-eran och därefter. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Probabilistisk algoritm för att testa primatitet. Journal of Number Theory, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. På gitter, inlärning med fel, slumpmässiga linjära koder och kryptografi. Journal of the ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Dan Shepherd och Michael J Bremner. Temporärt ostrukturerad kvantberäkning. 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. Algoritmer för kvantberäkning: diskreta logaritmer och factoring. I Proceedings 35:e årliga symposium om grunderna för datavetenskap, sidorna 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 och Jian-Wei Pan. Stark Quantum Computational Advantage Att använda en supraledande kvantprocessor. 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. Benchmarking av en 11-qubit kvantdator. Naturkommunikationer, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Kvantinformationsbehandling med supraledande kretsar: en recension. 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 och Avisay Tal. Exponentiell separation mellan grunda kvantkretsar och obegränsade fan-in grunda klassiska kretsar. I Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, sidorna 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Andrew Chi-Chih Yao. Hur man genererar och utbyter hemligheter. I 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), sidorna 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 och Jian-Wei Pan. Kvantberäkningsfördel via 60-qubit 24-cyklers slumpmässig kretssampling. 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 och Christopher Monroe. Interaktiva protokoll för klassiskt verifierbara kvantfördelar. arXiv förtryck 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 och Jian-Wei Pan. Kvantberäkningsfördelar med fotoner. Science, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Citerad av
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath och Ruben Verresen, "En hierarki av topologisk ordning från enheter med ändligt djup, mätning och feedforward", arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch och Robert Koenig, "Adaptiva kretsar med konstant djup för att manipulera icke-abelska vem som helst", 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 och Christopher Monroe, "Interactive Protocols for Classically-Verifiable Quantum Advantage", arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo och Dmitriy Vassilyev, "Stjärnspecifika Key-homomorphic PRFs from Linear Regression and Extremal Set Theory", arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani och Norman Y. Yao, "Klassiskt verifierbar kvantfördel från ett beräkningsmässigt Bell-test", Naturfysik 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn och Avisay Tal, "On Certified Randomness from Quantum Advantage Experiments", arXiv: 2111.14846.
[7] Nai-Hui Chia och Shih-Han Hung, "Klassisk verifiering av kvantdjup", arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa och Seiichiro Tani, "Computational self-testing for entangled magic states", Fysisk granskning A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde och Eneet Kaur, "Multivariat spåruppskattning i konstant kvantdjup", arXiv: 2206.15405.
Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2022-09-21 12:16:02). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.
On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2022-09-21 12:16:00).
Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.
