1Khoa Vật lý, ETH Zürich, Thụy Sĩ
2Viện nghiên cứu lý thuyết, ETH Zürich, Thụy Sĩ
Tìm bài báo này thú vị hay muốn thảo luận? Scite hoặc để lại nhận xét về SciRate.
Tóm tắt
Bằng chứng về lượng tử là một loại giao thức phản hồi thử thách trong đó trình xác minh cổ điển có thể chứng nhận một cách hiệu quả $textit{lợi thế lượng tử}$ của một trình xác minh không đáng tin cậy. Nghĩa là, một bộ chứng minh lượng tử có thể trả lời chính xác những thách thức của người xác minh và được chấp nhận, trong khi bất kỳ bộ chứng minh cổ điển thời gian đa thức nào cũng sẽ bị từ chối với xác suất cao, dựa trên các giả định tính toán hợp lý. Để trả lời những thách thức của người xác minh, các bằng chứng hiện có về lượng tử thường yêu cầu người chứng minh lượng tử thực hiện kết hợp các phép đo và mạch lượng tử có kích thước đa thức.
Trong bài báo này, chúng tôi đưa ra hai bằng chứng về cấu trúc lượng tử, trong đó người chứng minh chỉ cần thực hiện $textit{mạch lượng tử có độ sâu không đổi}$ (và các phép đo) cùng với tính toán cổ điển theo độ sâu log. Cấu trúc đầu tiên của chúng tôi là một trình biên dịch chung cho phép chúng tôi dịch tất cả các bằng chứng hiện có về lượng tử thành các phiên bản có độ sâu lượng tử không đổi. Cấu trúc thứ hai của chúng tôi dựa trên vấn đề $textit{learning với làm tròn}$ và tạo ra các mạch có độ sâu ngắn hơn và yêu cầu ít qubit hơn so với cấu trúc chung. Ngoài ra, cấu trúc thứ hai còn có khả năng chống ồn nhất định.
► Dữ liệu BibTeX
► Tài liệu tham khảo
[1] Scott Aaronson và Alex Arkhipov. Độ phức tạp tính toán của quang học tuyến tính. Trong Kỷ yếu của hội nghị chuyên đề ACM thường niên lần thứ 333 về Lý thuyết điện toán, trang 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, và những người khác. Ưu thế lượng tử sử dụng bộ xử lý siêu dẫn có thể lập trình. Thiên nhiên, 574(7779):505–510, 2019.
https://doi.org/10.1038/s41586-019-1666-5
[3] MD SAJID ANIS, Abby-Mitchell, Héctor Abraham, AduOffei và những người khác. Qiskit: Khung nguồn mở cho điện toán lượng tử, 2021.
[4] Sanjeev Arora và Boaz Barak. Tính phức tạp: một cách tiếp cận hiện đại. Nhà xuất bản Đại học Cambridge, 2009.
[5] Scott Aaronson và Lijie Chen. Cơ sở lý thuyết-phức tạp của các thí nghiệm về ưu thế lượng tử. Trong Kỷ yếu của Hội nghị về độ phức tạp tính toán lần thứ 32, CCC '17, trang 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.48550 / arXiv.1612.05903
[6] Scott Aaronson và Sam Gunn. Về độ cứng cổ điển của việc giả mạo Điểm chuẩn Entropy chéo tuyến tính giả mạo. Lý thuyết máy tính, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai và E. Kushilevitz. Mật mã bằng ${NC}^0$. Trong Hội nghị chuyên đề thường niên lần thứ 45 của IEEE về nền tảng khoa học máy tính, trang 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak và Daniel Wichs. Học với Làm tròn, Xem lại. Trong Những tiến bộ về mật mã học – CRYPTO 2013, trang 57–74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A Barrington. Các chương trình phân nhánh có kích thước đa thức có độ rộng giới hạn nhận dạng chính xác các ngôn ngữ đó trong ${NC}^1$. Tạp chí Khoa học Hệ thống và Máy tính, 38(1):150–164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
[10] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani và Thomas Vidick. Một bài kiểm tra mật mã về lượng tử và tính ngẫu nhiên có thể chứng nhận từ một thiết bị lượng tử duy nhất. Năm 2018, Hội nghị chuyên đề thường niên lần thứ 59 của IEEE về Nền tảng Khoa học Máy tính (FOCS), trang 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell và Jeremy M. Sage. Điện toán lượng tử bẫy ion: Tiến bộ và thách thức. Tạp chí Vật lý Ứng dụng, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe và Umesh Vazirani. Về độ phức tạp và xác minh của việc lấy mẫu mạch ngẫu nhiên lượng tử. Vật lý Tự nhiên, 15(2):159–163, tháng 2019 năm XNUMX.
https://doi.org/10.1038/s41567-018-0318-2
[13] Sergio Boixo, Sergei V Iskov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis và Hartmut Neven. Đặc trưng của ưu thế lượng tử trong các thiết bị ngắn hạn. Vật lý Tự nhiên, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani và Thomas Vidick. Bằng chứng đơn giản hơn về lượng tử. Trong Hội nghị lần thứ 15 về Lý thuyết tính toán lượng tử, truyền thông và mật mã (TQC 2020), tập 158 của Kỷ yếu tin học quốc tế Leibniz (LIPIcs), trang 8:1–8:14, Dagstuhl, Đức, 2020. Schloss Dagstuhl–Leibniz- Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert và Alon Rosen. Hàm và lưới giả ngẫu nhiên. Trong Những tiến bộ về mật mã học - EUROCRYPT 2012, trang 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 và Richard A Holt. Đề xuất thí nghiệm kiểm định lý thuyết biến ẩn cục bộ. Thư đánh giá vật lý, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark và Thomas Vidick. Giao dịch địa phương theo thời gian: tính ngẫu nhiên có thể chứng nhận từ các mạch có độ sâu thấp. Truyền thông trong Vật lý toán học, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richard Cleve và John Watrous. Mạch song song nhanh cho phép biến đổi Fourier lượng tử. Trong Kỷ yếu Hội nghị chuyên đề thường niên lần thứ 41 về Cơ sở Khoa học Máy tính, trang 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 ra mắt. Luận án tiến sĩ, Đại học Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis và Andrew N Cleland. Mã bề mặt: Hướng tới tính toán lượng tử quy mô lớn thực tế. Đánh giá vật lý A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] Francois Le Gall. Thư từ riêng tư, 2022.
[22] Craig Gidney và Martin Ekerå. Cách phân tích số nguyên RSA 2048 bit trong 8 giờ bằng cách sử dụng 20 triệu qubit nhiễu. Lượng tử, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu và Matty J Hoban. Việc ước tính entropy của đầu ra mạch nông là khó. bản in trước arXiv arXiv:2002.12814, 2020.
https: / / doi.org/ 10.48550 / arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara và François Le Gall. Kiểm tra lượng tử bằng mạch lượng tử có độ sâu nhỏ. Trong Hội nghị chuyên đề quốc tế lần thứ 46 về Cơ sở toán học của khoa học máy tính (MFCS 2021), tập 202 của Kỷ yếu quốc tế về tin học của Leibniz (LIPIcs), trang 59:1–59:15, Dagstuhl, Đức, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Aram W Harrow và Ashley Montanaro. Ưu thế tính toán lượng tử. Thiên nhiên, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / thiên nhiên23458
[26] Peter Høyer và Robert Špalek. Quạt lượng tử rất mạnh mẽ. Lý thuyết máy tính, 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 và Jianxin Chen. Mô phỏng cổ điển của mạch lượng tử tối cao. bản in trước arXiv arXiv:2005.06787, 2020.
https: / / doi.org/ 10.48550 / arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Giả mạo dữ liệu lượng tử: đánh bại bài kiểm tra lượng tử dựa trên IQP một cách cổ điển. bản in trước 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 và Norman Y. Yao. Lợi thế lượng tử có thể kiểm chứng được về mặt cổ điển từ bài kiểm tra Bell tính toán. Vật lý Tự nhiên, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert và Oded Regev. Về các mạng lý tưởng và học có lỗi trên các vòng. Trong Hội nghị quốc tế thường niên về lý thuyết và ứng dụng kỹ thuật mã hóa, trang 1–23. Mùa xuân, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Urmila Mahadev. Xác minh cổ điển của tính toán lượng tử. Năm 2018, Hội nghị chuyên đề thường niên lần thứ 59 của IEEE về Nền tảng Khoa học Máy tính (FOCS), trang 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A Nielsen và Isaac Chuang. Tính toán lượng tử và thông tin lượng tử, 2002.
[33] NHƯ Popova và AN Rubtsov. Phá vỡ ngưỡng lợi thế lượng tử để lấy mẫu Boson Gaussian. Trong Hội nghị và Triển lãm Lượng tử 2.0, trang QW2A.15. Nhóm xuất bản Optica, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. Điện toán lượng tử trong kỷ nguyên NISQ và hơn thế nữa. Lượng tử, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Thuật toán xác suất để kiểm tra tính nguyên tố. Tạp chí Lý thuyết Số, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. Về mạng, học với lỗi, mã tuyến tính ngẫu nhiên và mật mã. Tạp chí của ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Dan Shepherd và Michael J Bremner. Tính toán lượng tử không có cấu trúc tạm thời. Kỷ yếu của Hiệp hội Hoàng gia A: Khoa học Toán học, Vật lý và Kỹ thuật, 465(2105):1413–1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
[38] Peter W Shor. Các thuật toán tính toán lượng tử: logarit rời rạc và phân tích nhân tử. Trong Kỷ yếu hội nghị chuyên đề thường niên lần thứ 35 về nền tảng của khoa học máy tính, trang 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 và Jian-Wei Pan. Lợi thế tính toán lượng tử mạnh mẽ khi sử dụng bộ xử lý lượng tử siêu dẫn. Vật lý. Mục sư 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, và những người khác. Điểm chuẩn của một máy tính lượng tử 11 qubit. Truyền thông thiên nhiên, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Xử lý thông tin lượng tử với các mạch siêu dẫn: đánh giá. Báo cáo Tiến bộ trong Vật lý, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer và Avishay Tal. Sự phân tách theo cấp số nhân giữa các mạch lượng tử nông và các mạch cổ điển nông có quạt không giới hạn. Trong Kỷ yếu của Hội nghị chuyên đề ACM SIGACT thường niên lần thứ 51 về Lý thuyết máy tính, trang 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Andrew Chi-Chih Yao. Cách tạo và trao đổi bí mật. Trong Hội nghị chuyên đề thường niên lần thứ 27 về Cơ sở khoa học máy tính (sfcs 1986), trang 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 Chu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu và Jian-Wei Pan. Lợi thế tính toán lượng tử thông qua lấy mẫu mạch ngẫu nhiên 60 chu kỳ 24 qubit. Bản tin Khoa học, 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 và Christopher Monroe. Các giao thức tương tác cho lợi thế lượng tử có thể kiểm chứng được về mặt cổ điển. bản in trước arXiv arXiv:2112.05156, 2021.
https: / / doi.org/ 10.48550 / arXiv.2112.05156
arXiv: 2112.05156
[46] Han-Sen Zhong, Hui Wang, Yu-Hao Đặng, 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, Guanwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu và Jian-Wei Pan. Lợi thế tính toán lượng tử bằng cách sử dụng photon. Khoa học, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Trích dẫn
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath và Ruben Verresen, “Một hệ thống phân cấp của trật tự tôpô từ các đơn vị, phép đo và chuyển tiếp có độ sâu hữu hạn”, arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch và Robert Koenig, “Các mạch có độ sâu không đổi thích ứng để thao túng bất kỳ ai không abelian”, 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 và Christopher Monroe, “Các giao thức tương tác cho lợi thế lượng tử có thể xác minh được theo kiểu cổ điển”, arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo và Dmitriy Vassilyev, “PRF đồng hình khóa đặc trưng cho từng ngôi sao từ hồi quy tuyến tính và lý thuyết tập hợp cực trị”, arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani và Norman Y. Yao, “Lợi thế lượng tử có thể kiểm chứng được về mặt cổ điển từ bài kiểm tra Bell tính toán”, Vật lý tự nhiên 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn và Avishay Tal, “Về tính ngẫu nhiên được chứng nhận từ các thí nghiệm lợi thế lượng tử”, arXiv: 2111.14846.
[7] Nai-Hui Chia và Shih-Han Hung, “Xác minh cổ điển về độ sâu lượng tử”, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa và Seiichiro Tani, “Tự kiểm tra tính toán các trạng thái ma thuật vướng víu”, Đánh giá vật lý A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde và Eneet Kaur, “Ước tính dấu vết đa biến ở độ sâu lượng tử không đổi”, arXiv: 2206.15405.
Các trích dẫn trên là từ SAO / NASA ADS (cập nhật lần cuối thành công 2022 / 09-21 12:16:02). Danh sách có thể không đầy đủ vì không phải tất cả các nhà xuất bản đều cung cấp dữ liệu trích dẫn phù hợp và đầy đủ.
On Dịch vụ trích dẫn của Crossref không có dữ liệu về các công việc trích dẫn được tìm thấy (lần thử cuối cùng 2022 / 09-21 12:16:00).
Bài viết này được xuất bản trong Lượng tử dưới Creative Commons Ghi công 4.0 Quốc tế (CC BY 4.0) giấy phép. Bản quyền vẫn thuộc về chủ sở hữu bản quyền gốc như các tác giả hoặc tổ chức của họ.
