1Departemen Fisika, ETH Zรผrich, Swiss
2Institut Studi Teoritis, ETH Zรผrich, Swiss
Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.
Abstrak
Bukti kuantum adalah jenis protokol respons tantangan di mana pemverifikasi klasik dapat secara efisien mensertifikasi $textit{keuntungan kuantum}$ dari pembukti yang tidak tepercaya. Artinya, pembuktian kuantum dapat menjawab tantangan pemverifikasi dengan benar dan diterima, sedangkan pembuktian klasik waktu polinomial akan ditolak dengan probabilitas tinggi, berdasarkan asumsi komputasi yang masuk akal. Untuk menjawab tantangan pemverifikasi, bukti kuantum yang ada biasanya memerlukan pembuktian kuantum untuk melakukan kombinasi rangkaian dan pengukuran kuantum berukuran polinomial.
Dalam makalah ini, kami memberikan dua bukti konstruksi kuantum di mana pembuktinya hanya perlu melakukan $textit{rangkaian kuantum kedalaman konstan}$ (dan pengukuran) bersama dengan komputasi klasik kedalaman log. Konstruksi pertama kami adalah kompiler umum yang memungkinkan kami menerjemahkan semua bukti kuantum yang ada ke dalam versi kedalaman kuantum yang konstan. Konstruksi kedua kami didasarkan pada masalah $textit{learning with rounding}$, dan menghasilkan sirkuit dengan kedalaman lebih pendek dan membutuhkan qubit lebih sedikit daripada konstruksi umum. Selain itu, konstruksi kedua juga memiliki ketahanan terhadap kebisingan.
โบ data BibTeX
โบ Referensi
[1] Scott Aaronson dan Alex Arkhipov. Kompleksitas komputasi optik linier. Dalam Prosiding simposium ACM tahunan keempat puluh tiga tentang Teori komputasi, halaman 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, dkk. Supremasi kuantum menggunakan prosesor superkonduktor yang dapat diprogram. Alam, 574(7779):505โ510, 2019.
https:/โ/โdoi.org/โ10.1038/โs41586-019-1666-5
[3] MD SAJID ANIS, Abby-Mitchell, Hรฉctor Abraham, AduOffei, dkk. Qiskit: Kerangka kerja sumber terbuka untuk komputasi kuantum, 2021.
[4] Sanjeev Arora dan Boaz Barak. Kompleksitas komputasi: pendekatan modern. Cambridge University Press, 2009.
[5] Scott Aaronson dan Lijie Chen. Landasan Teori Kompleksitas dari Eksperimen Supremasi Kuantum. Dalam Prosiding Konferensi Kompleksitas Komputasi ke-32, CCC '17, halaman 1โ67, Dagstuhl, DEU, 2017. Schloss DagstuhlโLeibniz-Zentrum fuer Informatik.
https://โ/โdoi.org/โ10.48550/โarXiv.1612.05903
[6] Scott Aaronson dan Sam Gunn. Tentang Kekerasan Klasik dari Spoofing Linear Cross-Entropy Benchmarking. Teori Komputasi, 16(11):1โ8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai, dan E. Kushilevitz. Kriptografi dalam ${NC}^0$. Dalam Simposium IEEE Tahunan ke-45 tentang Landasan Ilmu Komputer, halaman 166โ175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joรซl Alwen, Stephan Krenn, Krzysztof Pietrzak, dan Daniel Wichs. Belajar dengan Pembulatan, Ditinjau Kembali. Dalam Kemajuan Kriptologi โ CRYPTO 2013, halaman 57โ74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https:/โ/โdoi.org/โ10.1007/โ978-3-642-40041-4_4
[9] David A Barrington. Program percabangan ukuran polinomial dengan lebar terbatas mengenali bahasa-bahasa tersebut dengan tepat di ${NC}^1$. Jurnal Ilmu Komputer dan Sistem, 38(1):150โ164, 1989.
https:/โ/โdoi.org/โ10.1016/โ0022-0000(89)90037-8
[10] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, dan Thomas Vidick. Uji kriptografi kuantum dan keacakan yang dapat disertifikasi dari satu perangkat kuantum. Pada Simposium Tahunan ke-2018 IEEE tentang Yayasan Ilmu Komputer (FOCS) tahun 59, halaman 320โ331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell, dan Jeremy M. Sage. Komputasi kuantum ion terperangkap: Kemajuan dan tantangan. Review Fisika Terapan, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, dan Umesh Vazirani. Tentang kompleksitas dan verifikasi pengambilan sampel rangkaian acak kuantum. Fisika Alam, 15(2):159โ163, Februari 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, dan Hartmut Neven. Mengkarakterisasi supremasi kuantum dalam perangkat jangka pendek. Fisika Alam, 14(6):595โ600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani, dan Thomas Vidick. Bukti Kuantitas yang Lebih Sederhana. Dalam Konferensi ke-15 tentang Teori Komputasi Kuantum, Komunikasi dan Kriptografi (TQC 2020), volume 158 dari Leibniz International Proceedings in Informatics (LIPIcs), halaman 8:1โ8:14, Dagstuhl, Jerman, 2020. Schloss DagstuhlโLeibniz- Zentrum untuk Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert, dan Alon Rosen. Fungsi dan Kisi Pseudorandom. Dalam Kemajuan Kriptologi โ EUROCRYPT 2012, halaman 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, dan Richard A Holt. Eksperimen yang diusulkan untuk menguji teori variabel tersembunyi lokal. Surat Tinjauan Fisik, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark, dan Thomas Vidick. Pertukaran lokalitas dengan waktu: keacakan yang dapat disertifikasi dari sirkuit dengan kedalaman rendah. Komunikasi dalam Fisika Matematika, 382(1):49โ86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richard Cleve dan John Watrous. Rangkaian paralel cepat untuk transformasi kuantum Fourier. Dalam Prosiding Simposium Tahunan ke-41 tentang Landasan Ilmu Komputer, halaman 526โ536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
[19] Pierre Dusart. Fungsi Autor yang menghitung nama-nama perdana menteri. Tesis PhD, Universitรฉ de Limoges, 1998.
https:/โ/โwww.unilim.fr/โlaco/โtheses/โ1998/โT1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis, dan Andrew N Cleland. Kode permukaan: Menuju komputasi kuantum skala besar yang praktis. Tinjauan Fisik A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] Francois Le Gall. Korespondensi pribadi, 2022.
[22] Craig Gidney dan Martin Ekerรฅ. Cara memfaktorkan bilangan bulat RSA 2048 bit dalam 8 jam menggunakan 20 juta qubit berisik. Kuantum, 5:433, 2021.
https:/โ/โdoi.org/โ10.22331/โq-2021-04-15-433
[23] Alexandru Gheorghiu dan Matty J Hoban. Sulit untuk memperkirakan entropi keluaran rangkaian dangkal. arXiv pracetak arXiv:2002.12814, 2020.
https://โ/โdoi.org/โ10.48550/โarXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara dan Francois Le Gall. Uji Kuantum dengan Sirkuit Kuantum Kedalaman Kecil. Dalam Simposium Internasional ke-46 tentang Landasan Matematika Ilmu Komputer (MFCS 2021), volume 202 dari Leibniz International Proceedings in Informatics (LIPIcs), halaman 59:1โ59:15, Dagstuhl, Jerman, 2021. Schloss Dagstuhl โ Leibniz-Zentrum fรผr Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Aram W Harrow dan Ashley Montanaro. Supremasi komputasi kuantum. Alam, 549(7671):203โ209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Peter Hรธyer dan Robert ล palek. Fantasi Quantum Sangat Kuat. Teori Komputasi, 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, dan Jianxin Chen. Simulasi Klasik Sirkuit Supremasi Kuantum. arXiv pracetak arXiv:2005.06787, 2020.
https://โ/โdoi.org/โ10.48550/โarXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Menempa data kuantum: mengalahkan tes kuantum berbasis IQP secara klasik. arXiv pracetak 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, dan Norman Y. Yao. Keuntungan kuantum yang dapat diverifikasi secara klasik dari uji Bell komputasi. Fisika Alam, 18(8):918โ924, 2022.
https:/โ/โdoi.org/โ10.1038/โs41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert, dan Oded Regev. Tentang kisi ideal dan pembelajaran dengan kesalahan pada cincin. Dalam Konferensi Internasional Tahunan tentang Teori dan Penerapan Teknik Kriptografi, halaman 1โ23. Pegas, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Urmila Mahadewa. Verifikasi klasik komputasi kuantum. Pada Simposium Tahunan ke-2018 IEEE tentang Yayasan Ilmu Komputer (FOCS) tahun 59, halaman 259โ267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A Nielsen dan Isaac Chuang. Komputasi kuantum dan informasi kuantum, 2002.
[33] A.S. Popova dan A.N. Rubtsov. Menembus Ambang Batas Keunggulan Kuantum untuk Pengambilan Sampel Gaussian Boson. Dalam Konferensi dan Pameran Quantum 2.0, halaman QW2A.15. Grup Penerbitan Optica, 2022.
https:/โ/โdoi.org/โ10.1364/โQUANTUM.2022.QW2A.15
[34] John Preskill. Komputasi Kuantum di era NISQ dan seterusnya. Kuantum, 2:79, 2018.
https:/โ/โdoi.org/โ10.22331/โq-2018-08-06-79
[35] Michael O Rabin. Algoritma probabilistik untuk menguji primalitas. Jurnal Teori Bilangan, 12(1):128โ138, 1980.
https:/โ/โdoi.org/โ10.1016/โ0022-314X(80)90084-0
[36] Regev Oded. Tentang kisi, pembelajaran dengan kesalahan, kode linier acak, dan kriptografi. Jurnal ACM (JACM), 56(6):1โ40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Dan Shepherd dan Michael J Bremner. Komputasi kuantum yang tidak terstruktur secara sementara. Prosiding Royal Society A: Ilmu Matematika, Fisika dan Teknik, 465(2105):1413โ1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
[38] Peter W Shor. Algoritma untuk komputasi kuantum: logaritma diskrit dan pemfaktoran. Dalam Prosiding Simposium Tahunan ke-35 tentang Dasar-dasar Ilmu Komputer, halaman 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, dan Jian-Wei Pan. Keunggulan Komputasi Kuantum yang Kuat Menggunakan Prosesor Kuantum Superkonduktor. Fis. Pdt 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, dkk. Membandingkan komputer kuantum 11-qubit. Komunikasi alam, 10(1):1โ6, 2019.
https:/โ/โdoi.org/โ10.1038/โs41467-019-13534-2
[41] G Wendin. Pemrosesan informasi kuantum dengan sirkuit superkonduktor: tinjauan. Laporan Kemajuan Fisika, 80(10):106001, 2017.
https:/โ/โdoi.org/โ10.1088/โ1361-6633/โaa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer, dan Avishay Tal. Pemisahan eksponensial antara sirkuit kuantum dangkal dan sirkuit klasik dangkal kipas tak terbatas. Dalam Prosiding Simposium ACM SIGACT Tahunan ke-51 tentang Teori Komputasi, halaman 515โ526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Andrew Chi-Chih Yao. Cara menghasilkan dan bertukar rahasia. Dalam Simposium Tahunan ke-27 tentang Landasan Ilmu Komputer (sfcs 1986), halaman 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, dan Jian-Wei Pan. Keuntungan komputasi kuantum melalui pengambilan sampel sirkuit acak 60 siklus 24-qubit. Buletin Sains, 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, dan Christopher Monroe. Protokol Interaktif untuk Keunggulan Kuantum yang Dapat Diverifikasi Secara Klasik. arXiv pracetak 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, dan Jian-Wei Pan. Keunggulan komputasi kuantum menggunakan foton. Sains, 370(6523):1460โ1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Dikutip oleh
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath, dan Ruben Verresen, โHierarki tatanan topologi dari kesatuan kedalaman hingga, pengukuran, dan umpan majuโ, arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch, dan Robert Koenig, โSirkuit kedalaman konstan adaptif untuk memanipulasi siapa pun non-abelianโ, arXiv: 2205.01933.
[3] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Atau 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, dan Christopher Monroe, โProtokol Interaktif untuk Keunggulan Kuantum yang Dapat Diverifikasi Secara Klasikโ, arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo, dan Dmitriy Vassilyev, โPRF Key-homomorfik khusus bintang dari Regresi Linier dan Teori Himpunan Ekstremalโ, arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, dan Norman Y. Yao, โKeuntungan kuantum yang dapat diverifikasi secara klasik dari uji Bell komputasiโ, Fisika Alam 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, dan Avishay Tal, โTentang Keacakan Tersertifikasi dari Eksperimen Keuntungan Kuantumโ, arXiv: 2111.14846.
[7] Nai-Hui Chia dan Shih-Han Hung, โVerifikasi klasik kedalaman kuantumโ, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa, dan Seiichiro Tani, โPengujian mandiri komputasi untuk keadaan sihir yang terjeratโ, Tinjauan Fisik A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde, dan Eneet Kaur, โEstimasi jejak multivariat dalam kedalaman kuantum konstanโ, arXiv: 2206.15405.
Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2022-09-21 12:16:02). Daftar ini mungkin tidak lengkap karena tidak semua penerbit menyediakan data kutipan yang cocok dan lengkap.
On Layanan dikutip-oleh Crossref tidak ada data tentang karya mengutip ditemukan (upaya terakhir 2022-09-21 12:16:00).
Makalah ini diterbitkan dalam Quantum di bawah Creative Commons Attribution 4.0 Internasional (CC BY 4.0) lisensi. Hak cipta tetap berada pada pemegang hak cipta asli seperti penulis atau lembaganya.
