Mạch Clifford có thể được học PAC đúng cách khi và chỉ khi $textsf{RP}=textsf{NP}$

Mạch Clifford có thể được học PAC đúng cách khi và chỉ khi $textsf{RP}=textsf{NP}$

Dấu thời gian: ngày 7 tháng 2023 năm 6 07:XNUMX sáng
Nút nguồn: 2706854

Daniel Liang

Khoa Khoa học Máy tính, Đại học Texas ở Austin

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

Đưa ra một tập dữ liệu về trạng thái đầu vào, phép đo và xác suất, liệu có thể dự đoán hiệu quả xác suất phép đo liên quan đến mạch lượng tử không? Công việc gần đây của Caro và Datta [19] đã nghiên cứu vấn đề PAC học các mạch lượng tử theo nghĩa lý thuyết thông tin, để lại những câu hỏi mở về hiệu quả tính toán. Cụ thể, một loại ứng cử viên của các mạch mà một người học hiệu quả có thể có khả năng là mạch của Clifford, vì tập hợp các trạng thái tương ứng được tạo ra bởi các mạch như vậy, được gọi là trạng thái ổn định, được biết là có thể học được PAC một cách hiệu quả [44]. Ở đây chúng tôi cung cấp một kết quả tiêu cực, cho thấy rằng việc học đúng các mạch CNOT với lỗi 1/ poly($n$) là khó đối với những người học cổ điển trừ khi $textsf{RP = NP}$, loại trừ khả năng những người học mạnh theo lý thuyết phức tạp tiêu chuẩn giả thiết. Là chất tương tự cổ điển và tập hợp con của các mạch Clifford, điều này đương nhiên cũng dẫn đến kết quả về độ cứng cho các mạch Clifford. Ngoài ra, chúng tôi chỉ ra rằng nếu $textsf{RP = NP}$ thì sẽ tồn tại các thuật toán học phù hợp hiệu quả cho các mạch CNOT và Clifford. Bằng các lập luận tương tự, chúng tôi cũng thấy rằng một bộ học lượng tử phù hợp hiệu quả cho các mạch như vậy tồn tại khi và chỉ khi $textsf{NP ⊆ RQP}$. Chúng tôi để ngỏ vấn đề về độ cứng do học không đúng cách hoặc lỗi $mathcal{O(1)}$ cho công việc trong tương lai.

► Dữ liệu BibTeX

► Tài liệu tham khảo

[1] Scott Aaronson. Khả năng học hỏi của các trạng thái lượng tử. 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, 463 (2088): 3089–3114, 2007. 10.1098/​rspa.2007.0113.
https: / / doi.org/ 10.1098 / rspa.2007.0113

[2] Scott Aaronson. Chụp cắt lớp bóng của các trạng thái lượng tử. Trong Kỷ yếu của Hội nghị chuyên đề ACM SIGACT thường niên lần thứ 50 về Lý thuyết máy tính, STOC 2018, trang 325–338, New York, NY, Hoa Kỳ, 2018. Hiệp hội Máy tính. ISBN 9781450355599. 10.1145/​3188745.3188802.
https: / / doi.org/ 10.1145 / 3188745.3188802

[3] Scott Aaronson và Daniel Gottesman. Cải thiện mô phỏng mạch ổn định. Tạp chí Vật lý A, 70 (5): 052328, 2004. 10.1103/​physreva.70.052328.
https: / / doi.org/ 10.1103 / Physreva.70.052328

[4] JB Altepeter, D. Branning, E. Jeffrey, TC Wei, PG Kwiat, RT Thew, JL O'Brien, MA Nielsen và AG White. Chụp cắt lớp quá trình lượng tử được hỗ trợ bởi Ancilla. Vật lý. Mục sư Lett., 90: 193601, tháng 2003 năm 10.1103. 90.193601/​PhysRevLett.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevLett.90.193601

[5] Martin Anthony và Peter L. Bartlett. Chức năng học từ phép nội suy. Tổ hợp, Xác suất và Điện toán, 9 (3): 213–225, 2000. 10.1017/​S0963548300004247.
https: / / doi.org/ 10.1017 / S0963548300004247

[6] Srinivasan Arunachalam và Ronald de Wolf. Chuyên mục khách mời: Khảo sát về thuyết lượng tử học. ACM SIGACT News, 48 ​​(2): 41–67, 2017. 10.1145/​3106700.3106710.
https: / / doi.org/ 10.1145 / 3106700.3106710

[7] Srinivasan Arunachalam và Ronald de Wolf. Độ phức tạp mẫu lượng tử tối ưu của thuật toán học tập. Trong Ryan O'Donnell, biên tập viên, Hội nghị về độ phức tạp tính toán lần thứ 32 (CCC 2017), tập 79 của Kỷ yếu tin học quốc tế Leibniz (LIPIcs), trang 25:1–25:31, Dagstuhl, Đức, 2017. Schloss Dagstuhl–Leibniz-Zentrum thêm Informatik. ISBN 978-3-95977-040-8. 10.4230/​LIPics.CCC.2017.25.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.25

[8] Srinivasan Arunachalam, Alex B Grilo và Henry Yuen. Học tập truy vấn thống kê lượng tử. bản in trước arXiv arXiv:2002.08240, 2020. https://​/​doi.org/​10.48550/​arXiv.2002.08240.
https: / / doi.org/ 10.48550 / arXiv.2002.08240
arXiv: 2002.08240

[9] Srinivasan Arunachalam, Alex Bredariol Grilo và Aarthi Sundaram. Độ cứng lượng tử học nông mạch cổ điển. Tạp chí Điện toán SIAM, 50 (3): 972–1013, 2021. 10.1137/​20M1344202.
https: / / doi.org/ 10.1137 / 20M1344202

[10] Charles H. Bennett và Gilles Brassard. Mật mã lượng tử: Phân phối khóa công khai và tung đồng xu. Khoa học máy tính lý thuyết, 560: 7–11, tháng 2014 năm 0304. ISSN 3975-10.1016. 2014.05.025/​j.tcs.XNUMX.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

[11] Charles H. Bennett và Stephen J. Wiesner. Giao tiếp thông qua các toán tử một và hai hạt trên các trạng thái einstein-podolsky-rosen. vật lý. Rev. Lett., 69: 2881–2884, tháng 1992 năm 10.1103. 69.2881/​PhysRevLett.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevLett.69.2881

[12] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres và William K. Wootters. Dịch chuyển tức thời một trạng thái lượng tử chưa biết thông qua các kênh kép cổ điển và einstein-podolsky-rosen. vật lý. Rev. Lett., 70: 1895–1899, tháng 1993 năm 10.1103. 70.1895/​PhysRevLett.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevLett.70.1895

[13] Ethan Bernstein và Umesh Vazirani. Lý thuyết độ phức tạp lượng tử. Tạp chí SIAM về Máy tính, 26 (5): 1411–1473, 1997. 10.1137 / S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[14] Avirim Blum. Độ cứng tính toán của học tập. http://​/​www.cs.cmu.edu/​ avrim/​ML07/​lect1007.pdf, 2015. URL http://​/​www.cs.cmu.edu/​ avrim/​ML07/​lect1007 .pdf. Ghi chú bài giảng cho CS 10-806 Cơ sở của Máy học và Khoa học Dữ liệu.
http://​/​www.cs.cmu.edu/​~avrim/​ML07/​lect1007.pdf

[15] Avrim L. Blum và Ronald L. Rivest. Huấn luyện mạng thần kinh 3 nút là np-đầy đủ. Mạng thần kinh, 5 (1): 117–127, 1992. ISSN 0893-6080. https://​/​doi.org/​10.1016/​S0893-6080(05)80010-3.
https:/​/​doi.org/​10.1016/​S0893-6080(05)80010-3

[16] Anselm Blumer, A. Ehrenfeucht, David Haussler, và Manfred K. Warmuth. Khả năng học hỏi và chiều vapnik-chervonenkis. J. ACM, 36(4): 929–965, tháng 1989 năm 0004. ISSN 5411-10.1145. 76359.76371/​XNUMX.
https: / / doi.org/ 10.1145 / 76359.76371

[17] Jonathan F Buss, Gudmund S Frandsen, và Jeffrey O Shallit. Độ phức tạp tính toán của một số bài toán đại số tuyến tính. Tạp chí Khoa học Máy tính và Hệ thống, 58(3): 572–596, 1999. ISSN 0022-0000. https://​/​doi.org/​10.1006/​jcss.1998.1608.
https: / / doi.org/ 10.1006 / jcss.1998.1608

[18] Matthias C. Caro. Phân loại nhị phân với các trường hợp cổ điển và nhãn lượng tử. Quantum Machine Intelligence, 3 (1), tháng 2021 năm 10.1007. 42484/​s021-00043-XNUMX-z.
https: / / doi.org/ 10.1007 / s42484-021-00043-z

[19] Matthias C. Caro và Ishaun Datta. Giả chiều của mạch lượng tử. Quantum Machine Intelligence, 2 (2), tháng 2020 năm 2524. ISSN 4914-10.1007. 42484/​s020-00027-5-XNUMX.
https:/​/​doi.org/​10.1007/​s42484-020-00027-5

[20] Hao-Chung Cheng, Min-Hsiu Hsieh, và Ping-Cheng Yeh. Khả năng học hỏi của các phép đo lượng tử chưa biết. Thông tin lượng tử. Máy tính, 16 (7–8): 615–656, tháng 2016 năm 1533. ISSN 7146-10.26421. 16.7/​QIC8-4-XNUMX.
https: / / doi.org/ 10.26421 / QIC16.7-8-4

[21] Isaac L. Chuang và MA Nielsen. Đơn thuốc để xác định thực nghiệm động lực học của hộp đen lượng tử. Tạp chí Quang học Hiện đại, 44 (11-12): 2455–2467, 1997. 10.1080/​09500349708231894.
https: / / doi.org/ 10.1080 / 09500349708231894

[22] Kai-Min Chung và Han-Hsuan Lin. Các thuật toán hiệu quả mẫu để học các kênh lượng tử trong mô hình PAC và vấn đề phân biệt trạng thái gần đúng. Trong Min-Hsiu Hsieh, biên tập viên, Hội nghị lần thứ 16 về Lý thuyết tính toán lượng tử, truyền thông và mã hóa (TQC 2021), tập 197 của Leibniz International Proceedings in Informatics (LIPIcs), trang 3:1–3:22, Dagstuhl, Đức, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-198-6. 10.4230/​LIPIcs.TQC.2021.3.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2021.3

[23] Amit Daniely và Shai Shalev-Shwartz. Những hạn chế về lý thuyết phức tạp trong việc học dnf. Trong Vitaly Feldman, Alexander Rakhlin và Ohad Shamir, các biên tập viên, Hội nghị thường niên lần thứ 29 về Lý thuyết học tập, tập 49 của Kỷ yếu nghiên cứu học máy, trang 815–830, Đại học Columbia, New York, New York, Hoa Kỳ, ngày 23–26 tháng 2016 năm 49 .PMLR. URL https://​/​proceedings.mlr.press/​v16/​danielyXNUMX.html.
https://​/​proceedings.mlr.press/​v49/​daniely16.html

[24] Steven T Flammia, David Gross, Yi-Kai Liu và Jens Eisert. Chụp cắt lớp lượng tử thông qua cảm biến nén: giới hạn lỗi, độ phức tạp của mẫu và công cụ ước tính hiệu quả. Tạp chí Vật lý mới, 14(9): 095022, 2012/10.1088. 1367/​2630-14/​9/​095022/​XNUMX.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​9/​095022

[25] Paul W. Goldberg và Mark R. Jerrum. Giới hạn kích thước vapnik-chervonenkis của các lớp khái niệm được tham số hóa bằng số thực. Học máy, 18: 131–148, 1995. 10.1007/​BF00993408.
https: / / doi.org/ 10.1007 / BF00993408

[26] Daniel Gottman. Mã ổn định và sửa lỗi lượng tử, 1997.

[27] Daniel Gottman. Biểu diễn heisenberg của máy tính lượng tử, 1998.

[28] Venkatesan Guruswami và Prasad Raghavendra. Độ cứng của nửa không gian học tập với tiếng ồn. Tạp chí Điện toán SIAM, 39 (2): 742–765, 2009. 10.1137/​070685798.
https: / / doi.org/ 10.1137 / 070685798

[29] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu và Nengkun Yu. Chụp cắt lớp tối ưu mẫu của các trạng thái lượng tử. IEEE Giao dịch trên lý thuyết thông tin, trang 1–1, 2017. ISSN 1557-9654. 10.1109/​tit.2017.2719044.
https: / / doi.org/ 10.1109 / tit.2017.2719044

[30] Nika Haghtalab. Bài giảng 9: Sự vất vả của việc học. https://​/​www.cs.cornell.edu/​courses/​cs6781/​2020sp/​lectures/​09-hardness1.pdf, 2020. URL https://​/​www.cs.cornell.edu/ ​courses/​cs6781/​2020sp/​lectures/​09-hardness1.pdf. Ghi chú bài giảng CS6781 - Cơ sở lý thuyết của Học máy.
https://​/​www.cs.cornell.edu/​courses/​cs6781/​2020sp/​lectures/​09-hardness1.pdf

[31] Hsin-Yuan Huang, Richard Kueng và John Preskill. Dự đoán nhiều tính chất của một hệ thống lượng tử từ rất ít phép đo Vật lý Tự nhiên, tháng 2020 năm 10.1038. 41567/​s020-0932-7-XNUMX.
https:/​/​doi.org/​10.1038/​s41567-020-0932-7

[32] Jonathan Katz. Ghi chú về Bài giảng Lý thuyết Độ phức tạp 3. https://​/​www.cs.umd.edu/​ jkatz/​complexity/​f11/​lecture3.pdf, 2011. URL https://​/​www.cs.umd. edu/​ jkatz/​complexity/​f11/​lecture3.pdf. Ghi chú bài giảng cho CS 652 — Lý thuyết phức tạp.
https://​/​www.cs.umd.edu/​~jkatz/​complexity/​f11/​lecture3.pdf

[33] Michael Kharitonov. Độ cứng mật mã của việc học theo phân phối cụ thể. Trong Kỷ yếu của Hội nghị chuyên đề ACM thường niên lần thứ 93 về Lý thuyết máy tính, STOC '372, trang 381–1993, New York, NY, Hoa Kỳ, 0897915917. Hiệp hội Máy tính. ISBN 10.1145. 167088.167197/​XNUMX.
https: / / doi.org/ 10.1145 / 167088.167197

[34] J. Kleinberg và E. Tardos. Thiết kế thuật toán. Pearson Education, 2022. ISBN 9780132131087. URL https://​/​books.google.com/​books?id=GORecgAACAAJ.
https://​/​books.google.com/​books?id=GORecgAACAAJ

[35] Adam Klivans. Mô hình học tập PAC. https://​/​www.cs.utexas.edu/​ klivans/​f06lec2.pdf, 2005. URL https://​/​www.cs.utexas.edu/​ klivans/​f06lec2.pdf. Ghi chú Bài giảng Lý thuyết Học tập Tính toán CS 395T.
https://​/​www.cs.utexas.edu/​~klivans/​f06lec2.pdf

[36] Robert Koenig và John A. Smolin. Làm thế nào để chọn hiệu quả một phần tử nhóm Clifford tùy ý. Tạp chí Vật lý Toán học, 55(12): 122202, Dec 2014. ISSN 1089-7658. 10.1063/​1.4903507.
https: / / doi.org/ 10.1063 / 1.4903507

[37] Richard Kueng và David Gross. Trạng thái bộ ổn định Qubit là thiết kế 3 xạ ảnh phức tạp, 2015.

[38] Ching-Yi Lai và Hao-Chung Cheng. Học mạch lượng tử của một số cổng t. IEEE Giao dịch trên lý thuyết thông tin, trang 1–1, 2022. 10.1109/​TIT.2022.3151760.
https: / / doi.org/ 10.1109 / TIT.2022.3151760

[39] Richard A. Thấp. Học và kiểm tra các thuật toán cho nhóm Clifford. vật lý. Rev. A, 80: 052314, tháng 2009 năm 10.1103. 80.052314/​PhysRevA.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevA.80.052314

[40] Ashley Montanaro. Học các trạng thái ổn định bằng cách lấy mẫu Bell, 2017.

[41] Ryan O'Donnell và John Wright. Chụp cắt lớp lượng tử hiệu quả. Trong Kỷ yếu của Hội nghị chuyên đề ACM thường niên lần thứ 16 về Lý thuyết máy tính, STOC '899, trang 912–2016, New York, NY, Hoa Kỳ, 9781450341325. Hiệp hội Máy tính. ISBN 10.1145. 2897518.2897544/​XNUMX.
https: / / doi.org/ 10.1145 / 2897518.2897544

[42] Ryan O'Donnell và John Wright. Chụp cắt lớp lượng tử hiệu quả ii. Trong Kỷ yếu của Hội nghị chuyên đề ACM SIGACT thường niên lần thứ 49 về Lý thuyết máy tính, STOC 2017, trang 962–974, New York, NY, Hoa Kỳ, 2017. Hiệp hội Máy tính. ISBN 9781450345286. 10.1145/​3055399.3055454.
https: / / doi.org/ 10.1145 / 3055399.3055454

[43] Yihui Quek, Srinivasan Arunachalam, và John A Smolin. Học riêng ngụ ý ổn định lượng tử. Trong M. Ranzato, A. Beygelzimer, Y. Dauphin, PS Liang, và J. Wortman Vaughan, biên tập viên, Những tiến bộ trong Hệ thống xử lý thông tin thần kinh, tập 34, trang 20503–20515. Curran Associates, Inc., 2021. URL https://​/​proceedings.neurips.cc/​paper/​2021/​file/​abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2021/​file/​abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf

[44] Andrea Rocchetto. Các trạng thái ổn định có thể học được PAC một cách hiệu quả. Thông tin & Tính toán Lượng tử, 18 (7-8): 541–552, 2018. 10.26421/​qic18.7-8-1.
https: / / doi.org/ 10.26421 / qic18.7-8-1

[45] Peter W. Shor. Các thuật toán thời gian đa thức để phân tích thừa số nguyên tố và logarit rời rạc trên máy tính lượng tử. Đánh giá SIAM, 41 (2): 303–332, 1999. 10.1137/​S0036144598347011.
https: / / doi.org/ 10.1137 / S0036144598347011

[46] Daniel R. Simon. Về sức mạnh của tính toán lượng tử. Tạp chí Điện toán SIAM, 26 (5): 1474–1483, 1997. 10.1137/​S0097539796298637.
https: / / doi.org/ 10.1137 / S0097539796298637

[47] Leslie G dũng cảm. Một lý thuyết của learnable. Truyền thông của ACM, 27 (11): 1134–1142, 1984. 10.1145/​1968.1972.
https: / / doi.org/ 10.1145 / 1968.1972

[48] Ewout Van Den Berg. Một phương pháp đơn giản để lấy mẫu các toán tử Clifford ngẫu nhiên. Vào năm 2021, Hội nghị Quốc tế IEEE về Điện toán và Kỹ thuật Lượng tử (QCE), trang 54–59, 2021. 10.1109/​QCE52317.2021.00021.
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

[49] Mithuna Yoganathan. Một điều kiện theo đó khả năng mô phỏng cổ điển ngụ ý khả năng học trạng thái hiệu quả, 2019.

[50] Hoàng Quân Châu. Các nhóm vách đá Multiqubit là 3 thiết kế đơn nhất. vật lý. Rev. A, 96: 062336, tháng 2017 năm 10.1103. 96.062336/​PhysRevA.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Trích dẫn

[1] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd và Alioscia Hamma, "Học các bộ giải mã hiệu quả cho các bộ mã hóa lượng tử gần như hỗn loạn", arXiv: 2212.11338, (2022).

[2] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt và Theodore J. Yoder, "Các thuật toán tối ưu để học các trạng thái pha lượng tử", arXiv: 2208.07851, (2022).

[3] Anurag Anshu và Srinivasan Arunachalam, "Một cuộc khảo sát về sự phức tạp của việc học các trạng thái lượng tử", arXiv: 2305.20069, (2023).

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 2023 / 06-07 22:21:42). 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ụ được 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 2023 / 06-07 22:21:40).

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ọ.

Dấu thời gian:

Thêm từ Tạp chí lượng tử