1Institutt for fysikk, ETH Zürich, Sveits
2Institutt for teoretiske studier, ETH Zürich, Sveits
Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.
Abstrakt
Et bevis på kvante er en type utfordring-respons-protokoll der en klassisk verifikatoren effektivt kan sertifisere $textit{quantum advantage}$ til en upålitelig beviser. Det vil si at en kvantebeviser kan svare korrekt på verifikatorens utfordringer og bli akseptert, mens enhver polynom-tids klassisk bevis vil bli avvist med høy sannsynlighet, basert på plausible beregningsforutsetninger. For å svare på verifikatorens utfordringer krever eksisterende bevis på kvantehet typisk at kvantebeviseren utfører en kombinasjon av kvantekretser og målinger i polynomstørrelse.
I denne artikkelen gir vi to bevis på kvantekonstruksjoner der beviseren bare trenger å utføre $textit{konstant-dybde kvantekretser}$ (og målinger) sammen med log-dybde klassisk beregning. Vår første konstruksjon er en generisk kompilator som lar oss oversette alle eksisterende bevis på kvantehet til versjoner med konstant kvantedybde. Vår andre konstruksjon er basert på $textit{learning with rounding}$-problemet, og gir kretser med kortere dybde og som krever færre qubits enn den generiske konstruksjonen. I tillegg har den andre konstruksjonen også en viss robusthet mot støy.
► BibTeX-data
► Referanser
[1] Scott Aaronson og Alex Arkhipov. Beregningskompleksiteten til lineær optikk. I Proceedings of the førtitredje årlige ACM-symposium om Theory of computing, side 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. Kvanteoverlegenhet ved hjelp av en programmerbar superledende prosessor. 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: Et rammeverk med åpen kildekode for kvanteberegning, 2021.
[4] Sanjeev Arora og Boaz Barak. Beregningskompleksitet: en moderne tilnærming. Cambridge University Press, 2009.
[5] Scott Aaronson og Lijie Chen. Kompleksitetsteoretiske grunnlag for kvanteoverlegenhetseksperimenter. 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 hardheten til forfalskning Lineær kryssentropi 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 45th Annual 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 avrunding, 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 med avgrenset bredde i polynomstørrelse gjenkjenner nøyaktig de språkene 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 av kvante og sertifiserbar tilfeldighet fra en enkelt kvanteenhet. 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 kvantedatabehandling: Fremgang og utfordringer. Applied Physics Review, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe og Umesh Vazirani. Om kompleksiteten og verifiseringen av kvantetilfeldig kretsprøvetaking. 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 og Hartmut Neven. Karakteriserer kvanteoverlegenhet 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 og Thomas Vidick. Enklere bevis på kvantelighet. I 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), bind 158 av Leibniz International Proceedings in Informatics (LIPIcs), side 8:1–8:14, Dagstuhl, Tyskland, 2020. Schloss Dagstuhl–Leibniz- Zentrum for Informatikk.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert og Alon Rosen. Pseudorandomfunksjoner 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ått eksperiment for å teste lokale teorier om skjulte variabler. 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: sertifiserbar tilfeldighet fra kretsløp 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. Raske parallellkretser for kvante-Fourier-transformasjonen. 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. PhD-avhandling, 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. Overflatekoder: Mot praktisk storskala kvanteberegning. Physical Review A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] François Le Gall. Privat korrespondanse, 2022.
[22] Craig Gidney og Martin Ekerå. Hvordan faktorisere 2048-biters RSA-heltall på 8 timer ved å bruke 20 millioner støyende qubits. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu og Matty J Hoban. Det er vanskelig å estimere entropien til grunne kretsutganger. arXiv preprint arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arxiv: 2002.12814
[24] Shuichi Hirahara og François Le Gall. Test av kvantestyrke med kvantekretser med liten dybde. I 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), bind 202 av 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. Kvanteberegningsoverlegenhet. Nature, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Peter Høyer og Robert Špalek. Quantum Fan-out er kraftig. 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 av Quantum Supremacy Circuits. arXiv forhåndstrykk arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arxiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Smi kvantedata: klassisk beseire en IQP-basert kvantetest. arXiv forhåndstrykk 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 verifiserbar kvantefordel fra en beregningsbasert 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 feil over ringer. I årlig internasjonal konferanse om teori og anvendelser av kryptografiske teknikker, side 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Urmila Mahadev. Klassisk verifisering av 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 kvanteinformasjon, 2002.
[33] AS Popova og AN Rubtsov. Å knekke Quantum Advantage Terskelen 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 utover. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Probabilistisk algoritme for testing av 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 feil, tilfeldige 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. Tidsmessig ustrukturert 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 for kvanteberegning: diskrete logaritmer og faktorisering. I Proceedings 35. årlige symposium om grunnlaget for informatikk, 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. Sterk Quantum Computational Advantage ved å bruke en superledende kvanteprosessor. 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 kvantedatamaskin. Naturkommunikasjon, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Kvanteinformasjonsbehandling med superledende kretser: en gjennomgang. 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. Eksponentiell separasjon mellom grunne kvantekretser og ubegrensede fan-in grunne klassiske kretser. 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 generere og utveksle hemmeligheter. 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-syklus tilfeldig 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 og Christopher Monroe. Interaktive protokoller for klassisk verifiserbar kvantefordel. arXiv forhåndstrykk 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 bruk av fotoner. Science, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Sitert av
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath og Ruben Verresen, "Et hierarki av topologisk orden fra enheter med begrenset dybde, måling og feedforward", arxiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch og Robert Koenig, "Adaptive kretsløp med konstant dybde for å manipulere ikke-abelske noen", 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, "Stjernespesifikke nøkkelhomomorfe PRFs fra lineær regresjon og ekstrem settteori", arxiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani og Norman Y. Yao, "Klassisk verifiserbar kvantefordel fra en beregningsbasert Bell-test", Naturfysikk 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn og Avisay Tal, "On Certified Randomness from Quantum Advantage Experiments", arxiv: 2111.14846.
[7] Nai-Hui Chia og Shih-Han Hung, "Klassisk verifisering av kvantedybde", arxiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa og Seiichiro Tani, "Computational self-testing for entangled magic states", Fysisk gjennomgang A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde og Eneet Kaur, "Multivariate trace estimering i konstant kvantedybde", arxiv: 2206.15405.
Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2022-09-21 12:16:02). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.
On Crossrefs siterte tjeneste ingen data om sitering av verk ble funnet (siste forsøk 2022-09-21 12:16:00).
Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.
