1Τμήμα Φυσικής, ETH Ζυρίχης, Ελβετία
2Ινστιτούτο Θεωρητικών Σπουδών, ETH Ζυρίχης, Ελβετία
Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.
Περίληψη
Η απόδειξη του κβαντικού χαρακτήρα είναι ένας τύπος πρωτοκόλλου πρόκλησης-απόκρισης στο οποίο ένας κλασικός επαληθευτής μπορεί να πιστοποιήσει αποτελεσματικά το $textit{quantum plus}$ ενός μη αξιόπιστου prover. Δηλαδή, ένας κβαντικός prover μπορεί να απαντήσει σωστά στις προκλήσεις του επαληθευτή και να γίνει αποδεκτός, ενώ οποιοσδήποτε κλασικός prover πολυωνυμικού χρόνου θα απορριφθεί με μεγάλη πιθανότητα, με βάση εύλογες υπολογιστικές υποθέσεις. Για να απαντηθούν οι προκλήσεις του επαληθευτή, οι υπάρχουσες αποδείξεις κβαντικότητας απαιτούν συνήθως από τον κβαντικό αποδεδειγμένο να εκτελέσει έναν συνδυασμό κβαντικών κυκλωμάτων και μετρήσεων πολυωνυμικού μεγέθους.
Σε αυτό το άρθρο, δίνουμε δύο αποδείξεις κβαντικών κατασκευών στις οποίες ο prover χρειάζεται μόνο να εκτελέσει $textit{κβαντικά κυκλώματα σταθερού βάθους}$ (και μετρήσεις) μαζί με κλασικό υπολογισμό βάθους log. Η πρώτη μας κατασκευή είναι ένας γενικός μεταγλωττιστής που μας επιτρέπει να μεταφράσουμε όλες τις υπάρχουσες αποδείξεις κβαντικού χαρακτήρα σε εκδόσεις σταθερού κβαντικού βάθους. Η δεύτερη κατασκευή μας βασίζεται στο πρόβλημα $textit{learning with rounding}$ και αποδίδει κυκλώματα με μικρότερο βάθος και απαιτούν λιγότερα qubits από τη γενική κατασκευή. Επιπλέον, η δεύτερη κατασκευή έχει επίσης κάποια στιβαρότητα έναντι του θορύβου.
► Δεδομένα BibTeX
► Αναφορές
[1] Scott Aaronson και Alex Arkhipov. Η υπολογιστική πολυπλοκότητα της γραμμικής οπτικής. In Proceedings of the σαράντα τρίτου ετήσιου συμποσίου ACM on Theory of Computing, σελίδες 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, κ.ά. Κβαντική υπεροχή χρησιμοποιώντας προγραμματιζόμενο υπεραγώγιμο επεξεργαστή. 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: Ένα πλαίσιο ανοιχτού κώδικα για κβαντικό υπολογισμό, 2021.
[4] Sanjeev Arora και Boaz Barak. Υπολογιστική πολυπλοκότητα: μια σύγχρονη προσέγγιση. Cambridge University Press, 2009.
[5] Scott Aaronson και Lijie Chen. Πολυπλοκότητα-Θεωρητικά Θεμέλια Πειραμάτων Κβαντικής Υπεροχής. In Proceedings of the 32nd Computational Complexity Conference, CCC '17, σελίδες 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https://doi.org/10.48550/arXiv.1612.05903
[6] Scott Aaronson και Sam Gunn. Σχετικά με την κλασική σκληρότητα της πλαστογράφησης Γραμμικής συγκριτικής αξιολόγησης διασταυρούμενης εντροπίας. Theory of Computing, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai, and E. Kushilevitz. Κρυπτογραφία σε ${NC}^0$. Στο 45th Annual IEEE Symposium on Foundations of Computer Science, σελίδες 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak και Daniel Wichs. Learning with Rounding, Revisited. In Advances in Cryptology – CRYPTO 2013, σελίδες 57–74, Βερολίνο, Χαϊδελβέργη, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] Ντέιβιντ Α Μπάρινγκτον. Τα προγράμματα διακλάδωσης πολυωνυμικού μεγέθους περιορισμένου πλάτους αναγνωρίζουν ακριβώς αυτές τις γλώσσες σε ${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 και Thomas Vidick. Μια κρυπτογραφική δοκιμή κβαντικής και πιστοποιήσιμης τυχαιότητας από μια ενιαία κβαντική συσκευή. Το 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), σελίδες 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell και Jeremy M. Sage. Κβαντικοί υπολογιστές παγιδευμένων ιόντων: Πρόοδος και προκλήσεις. Κριτικές Applied Physics, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe και Umesh Vazirani. Σχετικά με την πολυπλοκότητα και την επαλήθευση της δειγματοληψίας κβαντικών τυχαίων κυκλωμάτων. Nature Physics, 15(2):159–163, Φεβ 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 και Hartmut Neven. Χαρακτηρισμός της κβαντικής υπεροχής σε βραχυπρόθεσμες συσκευές. Nature Physics, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani και Thomas Vidick. Πιο απλές αποδείξεις Κβαντισμού. Στο 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), τόμος 158 του Leibniz International Proceedings in Informatics (LIPIcs), σελίδες 8:1–8:14, Dagstuhl, Γερμανία, 2020. SchlossLeib Dagstuhl– Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert και Alon Rosen. Ψευδοτυχαίες συναρτήσεις και πλέγματα. Στο Advances in Cryptology – EUROCRYPT 2012, σελίδες 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 και Richard A Holt. Προτεινόμενο πείραμα για τη δοκιμή τοπικών θεωριών κρυφών μεταβλητών. Physical Review Letters, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark και Thomas Vidick. Τοποθεσία συναλλαγών για το χρόνο: πιστοποιήσιμη τυχαιότητα από κυκλώματα χαμηλού βάθους. Communications in Mathematical Physics, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richard Cleve και John Watrous. Γρήγορα παράλληλα κυκλώματα για τον κβαντικό μετασχηματισμό Fourier. In Proceedings 41st Annual Symposium on Foundations of Computer Science, σελίδες 526–536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
[19] Πιερ Ντυσάρ. Autour de la fonction qui compte le nombre de nombres premiers. Διδακτορική διατριβή, Université de Limoges, 1998.
https://www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis και Andrew N Cleland. Κωδικοί επιφάνειας: Προς πρακτικούς κβαντικούς υπολογισμούς μεγάλης κλίμακας. Physical Review A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] Φρανσουά Λε Γκαλ. Ιδιωτική αλληλογραφία, 2022.
[22] Craig Gidney και Martin Ekerå. Πώς να συνυπολογίσετε ακέραιους αριθμούς RSA 2048 bit σε 8 ώρες χρησιμοποιώντας 20 εκατομμύρια θορυβώδη qubits. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu και Matty J Hoban. Η εκτίμηση της εντροπίας των εξόδων ρηχού κυκλώματος είναι δύσκολη. arXiv προεκτύπωση arXiv:2002.12814, 2020.
https://doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara και François Le Gall. Δοκιμή κβαντομορφίας με κβαντικά κυκλώματα μικρού βάθους. Στο 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), τόμος 202 του Leibniz International Proceedings in Informatics (LIPIcs), σελίδες 59:1–59:15, Dagstuhl, Γερμανία, 2021. Schloss Dagstuhl – Leibniz-Leibniz .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Aram W Harrow και Ashley Montanaro. Κβαντική υπολογιστική υπεροχή. Nature, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Peter Høyer και Robert Špalek. Το Quantum Fan-out είναι ισχυρό. 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 και Jianxin Chen. Κλασική προσομοίωση κυκλωμάτων κβαντικής υπεροχής. arXiv προεκτύπωση arXiv:2005.06787, 2020.
https://doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Σφυρηλάτηση κβαντικών δεδομένων: κλασικά νικώντας ένα κβαντικό τεστ που βασίζεται στο IQP. arXiv προεκτύπωση 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 και Norman Y. Yao. Κλασικά επαληθεύσιμο κβαντικό πλεονέκτημα από μια υπολογιστική δοκιμή Bell. Nature Physics, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert και Oded Regev. Σε ιδανικά πλέγματα και εκμάθηση με σφάλματα πάνω από δαχτυλίδια. Στο Ετήσιο Διεθνές Συνέδριο για τη Θεωρία και τις Εφαρμογές των Κρυπτογραφικών Τεχνικών, σελίδες 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Ουρμίλα Μαχάντεφ. Κλασική επαλήθευση κβαντικών υπολογισμών. Το 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), σελίδες 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A Nielsen και Isaac Chuang. Κβαντικός υπολογισμός και κβαντικές πληροφορίες, 2002.
[33] AS Popova και AN Rubtsov. Σπάσιμο του ορίου κβαντικού πλεονεκτήματος για τη δειγματοληψία Gaussian Boson. Στο συνέδριο και έκθεση Quantum 2.0, σελίδα QW2A.15. Optica Publishing Group, 2022.
https://doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] Τζον Πρέσκιλ. Quantum Computing στην εποχή NISQ και όχι μόνο. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Πιθανοτικός αλγόριθμος για τον έλεγχο της πρωταρχικότητας. Journal of Number Theory, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. Στα πλέγματα, μάθηση με σφάλματα, τυχαίους γραμμικούς κώδικες και κρυπτογραφία. Journal of the ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Dan Shepherd και Michael J Bremner. Χρονικά μη δομημένος κβαντικός υπολογισμός. 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. Αλγόριθμοι για κβαντικούς υπολογισμούς: διακριτοί λογάριθμοι και παραγοντοποίηση. Στο Πρακτικά 35ο ετήσιο συμπόσιο για τα θεμέλια της επιστήμης των υπολογιστών, σελίδες 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 και Jian-Wei Pan. Ισχυρό κβαντικό υπολογιστικό πλεονέκτημα με χρήση υπεραγώγιμου κβαντικού επεξεργαστή. 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. Συγκριτική αξιολόγηση ενός κβαντικού υπολογιστή 11 qubit. Nature communications, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] Γ Βέντιν. Κβαντική επεξεργασία πληροφοριών με υπεραγώγιμα κυκλώματα: ανασκόπηση. 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 και Avishay Tal. Εκθετικός διαχωρισμός μεταξύ ρηχών κβαντικών κυκλωμάτων και απεριόριστων ρηχών κλασσικών κυκλωμάτων ανεμιστήρα. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, σελίδες 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Andrew Chi-Chih Yao. Πώς να δημιουργήσετε και να ανταλλάξετε μυστικά. Στο 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), σελίδες 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 και Jian-Wei Pan. Κβαντικό υπολογιστικό πλεονέκτημα μέσω δειγματοληψίας τυχαίου κυκλώματος 60-qubit 24 κύκλων. 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 Vazirani, Y. Yao, Marko Cetina και Christopher Monroe. Διαδραστικά πρωτόκολλα για κλασικά επαληθεύσιμο κβαντικό πλεονέκτημα. arXiv προεκτύπωση 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 και Jian-Wei Pan. Κβαντικό υπολογιστικό πλεονέκτημα με χρήση φωτονίων. Science, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Αναφέρεται από
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath και Ruben Verresen, «Μια ιεραρχία τοπολογικής τάξης από μονάδες πεπερασμένου βάθους, μέτρηση και τροφοδοσία». arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch και Robert Koenig, «Προσαρμοζόμενα κυκλώματα σταθερού βάθους για χειρισμό μη αβελιανών οποιωνδήποτε», 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 Visinger Vazirani, Norman Y. Yao, Marko Cetina και Christopher Monroe, «Διαδραστικά Πρωτόκολλα για Κλασικά Επαληθεύσιμο Κβαντικό Πλεονέκτημα», arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo και Dmitriy Vassilyev, «Star-specific Key-homomorphic PRFs from Linear Regression and Extremal Set Theory». arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani και Norman Y. Yao, «Κλασικά επαληθεύσιμο κβαντικό πλεονέκτημα από μια υπολογιστική δοκιμή Bell», Φυσική της φύσης 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn και Avishay Tal, «On Certified Randomness from Quantum Advantage Experiments», arXiv: 2111.14846.
[7] Nai-Hui Chia και Shih-Han Hung, «Κλασική επαλήθευση του κβαντικού βάθους», arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa και Seiichiro Tani, «Υπολογιστικός αυτοέλεγχος για εμπλεκόμενες μαγικές καταστάσεις», Φυσική ανασκόπηση A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde και Eneet Kaur, «Πολυμεταβλητή εκτίμηση ιχνών σε σταθερό κβαντικό βάθος», arXiv: 2206.15405.
Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2022-09-21 12:16:02). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.
On Η υπηρεσία παραπομπής του Crossref δεν βρέθηκαν δεδομένα σχετικά με την αναφορά έργων (τελευταία προσπάθεια 2022-09-21 12:16:00).
Αυτό το Βιβλίο δημοσιεύεται στο Quantum στο πλαίσιο του Creative Commons Attribution 4.0 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους
