1Institut for Fysik, ETH Zürich, Schweiz
2Institut for Teoretiske Studier, ETH Zürich, Schweiz
Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.
Abstrakt
Et kvantebevis er en type udfordring-svar-protokol, hvor en klassisk verifikator effektivt kan certificere $textit{quantum advantage}$ af en upålidelig beviser. Det vil sige, at en kvantebeviser korrekt kan besvare verifikatorens udfordringer og blive accepteret, mens enhver polynomisk-tids klassisk beviser vil blive afvist med høj sandsynlighed, baseret på plausible beregningsantagelser. For at besvare verifikatorens udfordringer kræver eksisterende beviser for kvantehed typisk, at kvantebeviseren udfører en kombination af polynomisk størrelse kvantekredsløb og målinger.
I dette papir giver vi to bevis for kvantekonstruktioner, hvor beviseren kun behøver at udføre $textit{konstant-dybde kvantekredsløb}$ (og målinger) sammen med log-dybde klassisk beregning. Vores første konstruktion er en generisk compiler, der giver os mulighed for at oversætte alle eksisterende beviser for kvante til konstant kvantedybde versioner. Vores anden konstruktion er baseret på $textit{learning with rounding}$-problemet og giver kredsløb med kortere dybde og kræver færre qubits end den generiske konstruktion. Derudover har den anden konstruktion også en vis robusthed over for støj.
► BibTeX-data
► Referencer
[1] Scott Aaronson og Alex Arkhipov. Den beregningsmæssige kompleksitet af lineær optik. I Proceedings of the 333. årlige ACM symposium on Theory of computing, side 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, et al. Kvanteoverlegenhed ved hjælp af en programmerbar superledende 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: En open source-ramme til kvanteberegning, 2021.
[4] Sanjeev Arora og Boaz Barak. Beregningsmæssig kompleksitet: en moderne tilgang. Cambridge University Press, 2009.
[5] Scott Aaronson og Lijie Chen. Kompleksitetsteoretiske grundlag for kvanteoverherredømmeeksperimenter. In Proceedings of the 32nd Computational Complexity Conference, CCC '17, side 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[6] Scott Aaronson og Sam Gunn. Om den klassiske hårdhed ved spoofing Lineær krydsentropi benchmarking. Theory of Computing, 16(11):1–8, 2020.
https:///doi.org/10.4086/toc.2020.v016a011
[7] B. Applebaum, Y. Ishai og E. Kushilevitz. Kryptografi i ${NC}^0$. I det 45. årlige IEEE Symposium on Foundations of Computer Science, side 166-175, 2004.
https:///doi.org/10.1109/FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak og Daniel Wichs. Læring med afrunding, Revisited. In Advances in Cryptology – CRYPTO 2013, side 57-74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A Barrington. Forgreningsprogrammer i polynomisk størrelse med afgrænset bredde genkender nøjagtigt de sprog 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 og Thomas Vidick. En kryptografisk test af kvante og certificerbar tilfældighed fra en enkelt kvanteenhed. I 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), side 320-331. IEEE, 2018.
https:///doi.org/10.1145/3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell og Jeremy M. Sage. Fanget-ion kvantecomputere: Fremskridt og udfordringer. Anvendt fysik anmeldelser, 2019.
https:///doi.org/10.1063/1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe og Umesh Vazirani. Om kompleksiteten og verifikationen af kvantetilfældig kredsløbsprøvetagning. 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 og Hartmut Neven. Karakterisering af kvanteoverherredømme i enheder på kort sigt. Nature Physics, 14(6):595–600, 2018.
https:///doi.org/10.1038/s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani og Thomas Vidick. Enklere beviser for kvantelighed. I 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), bind 158 af Leibniz International Proceedings in Informatics (LIPIcs), side 8:1–8:14, Dagstuhl, Tyskland, 2020. Schloss Dagstuhl–Leibniz- Zentrum for Informatik.
https:///doi.org/10.4230/LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert og Alon Rosen. Pseudorandom-funktioner og gitter. In Advances in Cryptology – EUROCRYPT 2012, side 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 og Richard A Holt. Foreslået eksperiment til at teste lokale skjulte variable teorier. Physical Review Letters, 23(15):880, 1969.
https:///doi.org/10.1103/PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark og Thomas Vidick. Handelssted for tid: certificerbar tilfældighed fra kredsløb med lav dybde. Communications in Mathematical Physics, 382(1):49–86, 2021.
https:///doi.org/10.1007/s00220-021-03963-w
[18] Richard Cleve og John Watrous. Hurtige parallelle kredsløb til kvante-Fourier-transformationen. I Proceedings 41st Annual Symposium on Foundations of Computer Science, side 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. Ph.d.-afhandling, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis og Andrew N Cleland. Overfladekoder: Mod praktisk storskala kvanteberegning. Physical Review A, 86(3):032324, 2012.
https:///doi.org/10.1103/PhysRevA.86.032324
[21] François Le Gall. Privat korrespondance, 2022.
[22] Craig Gidney og Martin Ekerå. Sådan faktoriseres 2048 bit RSA-heltal på 8 timer ved hjælp af 20 millioner støjende qubits. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu og Matty J Hoban. Det er svært at estimere entropien af lavvandede kredsløbsoutput. arXiv fortryk arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara og François Le Gall. Kvantetest med lille dybde kvantekredsløb. I 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), bind 202 af Leibniz International Proceedings in Informatics (LIPIcs), side 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 og Ashley Montanaro. Kvanteberegningsoverlegenhed. Nature, 549(7671):203-209, 2017.
https:///doi.org/10.1038/nature23458
[26] Peter Høyer og Robert Špalek. Quantum Fan-out er kraftfuld. 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 og Jianxin Chen. Klassisk simulering af Quantum Supremacy Circuits. arXiv preprint arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Smedning af kvantedata: klassisk besejre en IQP-baseret kvantetest. arXiv fortryk 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 og Norman Y. Yao. Klassisk verificerbar kvantefordel fra en beregningsmæssig Bell-test. Nature Physics, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert og Oded Regev. På ideelle gitter og læring med fejl over ringe. I årlig international konference om teorien og anvendelsen af kryptografiske teknikker, side 1-23. Springer, 2010.
https:///doi.org/10.1145/2535925
[31] Urmila Mahadev. Klassisk verifikation af kvanteberegninger. I 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), side 259-267. IEEE, 2018.
https:///doi.org/10.1109/FOCS.2018.00033
[32] Michael A Nielsen og Isaac Chuang. Kvanteberegning og kvanteinformation, 2002.
[33] AS Popova og AN Rubtsov. Knækning af Quantum Advantage Threshold for Gaussian Boson Sampling. I Quantum 2.0 Conference and Exhibition, side QW2A.15. Optica Publishing Group, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. Quantum Computing i NISQ-æraen og derefter. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Probabilistisk algoritme til test af primalitet. Journal of Number Theory, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. På gitter, læring med fejl, tilfældige lineære koder og kryptografi. Journal of the ACM (JACM), 56(6):1–40, 2009.
https:///doi.org/10.1145/1568318.1568324
[37] Dan Shepherd og Michael J Bremner. Tidsmæssigt ustruktureret kvanteberegning. 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 til kvanteberegning: diskrete logaritmer og factoring. I Proceedings 35. årlige symposium om grundlaget for datalogi, side 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 og Jian-Wei Pan. Stærk Quantum Computational Advantage ved at bruge en superledende kvanteprocessor. 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 af en 11-qubit kvantecomputer. Naturkommunikation, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Kvanteinformationsbehandling med superledende kredsløb: en gennemgang. 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 og Avisay Tal. Eksponentiel adskillelse mellem lavvandede kvantekredsløb og ubegrænsede fan-in lavvandede klassiske kredsløb. I Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, side 515-526, 2019.
https:///doi.org/10.1145/3313276.3316404
[43] Andrew Chi-Chih Yao. Hvordan man genererer og udveksler hemmeligheder. I 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), side 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 og Jian-Wei Pan. Kvanteberegningsfordel via 60-qubit 24-cyklus tilfældig kredsløbssampling. 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 og Christopher Monroe. Interaktive protokoller til klassisk verificerbar kvantefordel. arXiv fortryk 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 og Jian-Wei Pan. Kvanteberegningsfordel ved hjælp af fotoner. Science, 370(6523):1460-1463, 2020.
https://doi.org/10.1126/science.abe8770
Citeret af
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath og Ruben Verresen, "Et hierarki af topologisk orden fra enheder med begrænset dybde, måling og feedforward", arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch og Robert Koenig, "Adaptive kredsløb med konstant dybde til at manipulere ikke-abelske nogen", 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 og Christopher Monroe, "Interactive Protocols for Classically-Verifiable Quantum Advantage", arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo og Dmitriy Vassilyev, "Stjernespecifikke nøglehomomorfe PRF'er fra lineær regression og ekstremal sætteori", arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani og Norman Y. Yao, "Klassisk verificerbar kvantefordel fra en beregningsmæssig Bell-test", Nature Physics 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn og Avishay Tal, "On Certified Randomness from Quantum Advantage Experiments", arXiv: 2111.14846.
[7] Nai-Hui Chia og Shih-Han Hung, "Klassisk verifikation af kvantedybde", arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa og Seiichiro Tani, "Computational self-testing for entangled magic states", Fysisk gennemgang A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde og Eneet Kaur, "Multivariat sporestimering i konstant kvantedybde", arXiv: 2206.15405.
Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2022-09-21 12:16:02). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.
On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2022-09-21 12:16:00).
Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.
