1Departement Physik, ETH Zürich, Schweiz
2Institut für Theoretische Studien, ETH Zürich, Schweiz
Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.
Abstrakt
Ein Quantenbeweis ist eine Art Challenge-Response-Protokoll, bei dem ein klassischer Verifizierer den Quantenvorteil eines nicht vertrauenswürdigen Prüfers effizient zertifizieren kann. Das heißt, ein Quantenbeweis kann die Herausforderungen des Verifizierers korrekt beantworten und akzeptiert werden, während jeder klassische Beweis in Polynomzeit mit hoher Wahrscheinlichkeit abgelehnt wird, basierend auf plausiblen Berechnungsannahmen. Um die Herausforderungen des Prüfers zu meistern, erfordern bestehende Quantennachweise typischerweise, dass der Quantenprüfer eine Kombination aus Quantenschaltkreisen und Messungen in Polynomgröße durchführt.
In diesem Artikel geben wir zwei Beweiskonstruktionen für die Quantentheorie an, bei denen der Beweiser lediglich $textit{Quantenschaltungen mit konstanter Tiefe}$ (und Messungen) zusammen mit der klassischen Berechnung mit logarithmischer Tiefe durchführen muss. Unsere erste Konstruktion ist ein generischer Compiler, der es uns ermöglicht, alle vorhandenen Quantenbeweise in Versionen mit konstanter Quantentiefe zu übersetzen. Unsere zweite Konstruktion basiert auf dem $textit{Lernen mit Rundung}$-Problem und liefert Schaltkreise mit kürzerer Tiefe und weniger Qubits als die generische Konstruktion. Darüber hinaus weist die zweite Konstruktion auch eine gewisse Robustheit gegenüber Lärm auf.
► BibTeX-Daten
► Referenzen
[1] Scott Aaronson und Alex Arkhipov. Die rechnerische Komplexität der linearen Optik. In Proceedings of the Fourty-Three Annual ACM Symposium on Theory of Computing, Seiten 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. Quantenüberlegenheit mit einem programmierbaren supraleitenden Prozessor. 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: Ein Open-Source-Framework für Quantencomputing, 2021.
[4] Sanjeev Arora und Boaz Barak. Rechenkomplexität: ein moderner Ansatz. Cambridge University Press, 2009.
[5] Scott Aaronson und Lijie Chen. Komplexitätstheoretische Grundlagen von Quantenüberlegenheitsexperimenten. In Proceedings of the 32nd Computational Complexity Conference, CCC '17, Seiten 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[6] Scott Aaronson und Sam Gunn. Zur klassischen Spoofing-Härte des linearen Cross-Entropy-Benchmarkings. Theory of Computing, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai und E. Kushilevitz. Kryptographie in ${NC}^0$. Im 45. jährlichen IEEE-Symposium zu Grundlagen der Informatik, Seiten 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak und Daniel Wichs. Lernen mit Rundung, überarbeitet. In Advances in Cryptology – CRYPTO 2013, Seiten 57–74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A. Barrington. Verzweigungsprogramme mit begrenzter Polynomgröße erkennen genau diese Sprachen in ${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 und Thomas Vidick. Ein kryptografischer Test der Quantensicherheit und der zertifizierbaren Zufälligkeit eines einzelnen Quantengeräts. Im Jahr 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Seiten 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell und Jeremy M. Sage. Quantencomputing mit gefangenen Ionen: Fortschritte und Herausforderungen. Angewandte Physik-Rezensionen, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe und Umesh Vazirani. Zur Komplexität und Verifizierung des Quantenzufallsschaltkreis-Samplings. 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 und Hartmut Neven. Charakterisierung der Quantenüberlegenheit in kurzfristigen Geräten. Nature Physics, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani und Thomas Vidick. Einfachere Quantenbeweise. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Band 158 von Leibniz International Proceedings in Informatics (LIPIcs), Seiten 8:1–8:14, Dagstuhl, Deutschland, 2020. Schloss Dagstuhl–Leibniz- Zentrum für Informatik.
https: // doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert und Alon Rosen. Pseudozufallsfunktionen und Gitter. In Advances in Cryptology – EUROCRYPT 2012, Seiten 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 und Richard A. Holt. Vorgeschlagenes Experiment zum Testen lokaler Hidden-Variablen-Theorien. Physical Review Letters, 23(15):880, 1969.
https://doi.org/ 10.1103/PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark und Thomas Vidick. Ort gegen Zeit eintauschen: Zertifizierbare Zufälligkeit aus Schaltkreisen geringer Tiefe. Communications in Mathematical Physics, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richard Cleve und John Watrous. Schnelle Parallelschaltungen für die Quanten-Fourier-Transformation. In Proceedings 41st Annual Symposium on Foundations of Computer Science, Seiten 526–536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
[19] Pierre Dusart. Autor der Funktion, die die Anzahl der Premieren bestimmt. Doktorarbeit, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G. Fowler, Matteo Mariantoni, John M. Martinis und Andrew N. Cleland. Oberflächencodes: Auf dem Weg zur praktischen Quantenberechnung im großen Maßstab. Physical Review A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] François Le Gall. Private Korrespondenz, 2022.
[22] Craig Gidney und Martin Ekerå. So faktorisieren Sie 2048-Bit-RSA-Ganzzahlen in 8 Stunden unter Verwendung von 20 Millionen verrauschten Qubits. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu und Matty J. Hoban. Die Entropie flacher Schaltungsausgänge abzuschätzen ist schwierig. arXiv-Vorabdruck arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara und François Le Gall. Test der Quantität mit Quantenschaltungen geringer Tiefe. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Band 202 von Leibniz International Proceedings in Informatics (LIPIcs), Seiten 59:1–59:15, Dagstuhl, Deutschland, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: // doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Aram W. Harrow und Ashley Montanaro. Überlegenheit in der Quantenberechnung. Nature, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Peter Høyer und Robert Špalek. Quanten-Fanout ist leistungsstark. 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 und Jianxin Chen. Klassische Simulation von Quantenüberlegenheitsschaltungen. arXiv-Vorabdruck arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D. Kahanamoku-Meyer. Quantendaten fälschen: Klassisches Scheitern eines IQP-basierten Quantentests. arXiv-Vorabdruck 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 und Norman Y. Yao. Klassisch überprüfbarer Quantenvorteil durch einen rechnerischen Bell-Test. Nature Physics, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert und Oded Regev. Über ideale Gitter und Lernen mit Fehlern über Ringen. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, Seiten 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Urmila Mahadev. Klassische Verifizierung von Quantenberechnungen. Im Jahr 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Seiten 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A. Nielsen und Isaac Chuang. Quantenberechnung und Quanteninformation, 2002.
[33] AS Popova und AN Rubtsov. Knacken der Quantenvorteilsschwelle für die Gauß-Boson-Probenahme. In Quantum 2.0 Conference and Exhibition, Seite QW2A.15. Optica Publishing Group, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. Quantencomputing in der NISQ-Ära und darüber hinaus. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Wahrscheinlichkeitsalgorithmus zum Testen der Primalität. Journal of Number Theory, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. Über Gitter, Lernen mit Fehlern, zufällige lineare Codes und Kryptographie. Journal of the ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Dan Shepherd und Michael J. Bremner. Zeitlich unstrukturierte Quantenberechnung. 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. Algorithmen für die Quantenberechnung: Diskrete Logarithmen und Faktorisierung. In Proceedings 35. jährliches Symposium über Grundlagen der Informatik, Seiten 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 und Jian-Wei Pan. Starker Quantenrechenvorteil durch Verwendung eines supraleitenden Quantenprozessors. Physik. 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 eines 11-Qubit-Quantencomputers. Naturkommunikation, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Quanteninformationsverarbeitung mit supraleitenden Schaltkreisen: ein Rückblick. Berichte über Fortschritte in der Physik, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer und Avishay Tal. Exponentielle Trennung zwischen flachen Quantenschaltkreisen und unbegrenzten flachen klassischen Schaltkreisen. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Seiten 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Andrew Chi-Chih Yao. Wie man Geheimnisse generiert und austauscht. Im 27. Jahressymposium über Grundlagen der Informatik (sfcs 1986), Seiten 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 und Jian-Wei Pan. Quantenberechnungsvorteil durch 60-Qubit-24-Zyklen-Zufallskreisabtastung. 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 und Christopher Monroe. Interaktive Protokolle für klassisch nachweisbare Quantenvorteile. arXiv-Vorabdruck 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 und Jian-Wei Pan. Quantenberechnungsvorteil mit Photonen. Science, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Zitiert von
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath und Ruben Verresen, „Eine Hierarchie topologischer Ordnung aus Unitarien endlicher Tiefe, Messung und Feedforward“, arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch und Robert Koenig, „Adaptive Schaltkreise mit konstanter Tiefe zur Manipulation nicht-abelscher Anyons“, 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 und Christopher Monroe, „Interaktive Protokolle für klassisch überprüfbare Quantenvorteile“, arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo und Dmitriy Vassilyev, „Sternspezifische schlüsselhomomorphe PRFs aus linearer Regression und Extremalmengentheorie“, arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani und Norman Y. Yao, „Klassisch überprüfbarer Quantenvorteil aus einem rechnerischen Bell-Test“, Naturphysik 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn und Avishay Tal, „On Certified Randomness from Quantum Advantage Experiments“, arXiv: 2111.14846.
[7] Nai-Hui Chia und Shih-Han Hung, „Klassische Verifizierung der Quantentiefe“, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa und Seiichiro Tani, „Computergestützter Selbsttest für verschränkte magische Zustände“, Physische Überprüfung A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde und Eneet Kaur, „Multivariate Spurenschätzung in konstanter Quantentiefe“, arXiv: 2206.15405.
Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2022, 09:21:12 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.
On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2022-09-21 12:16:00).
Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.
