1Viện Toán học Alfréd Rényi
2Nghiên cứu của Adobe
3Đại học Washington
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
Chúng tôi đưa ra một thuật toán cổ điển cho hồi quy tuyến tính tương tự như thuật toán nghịch đảo ma trận lượng tử [Harrow, Hassidim và Lloyd, Physical Review Letters'09] cho các ma trận hạng thấp [Wossnig, Zhao và Prakash, Physical Review Letters'18], khi ma trận đầu vào $ A $ được lưu trữ trong cấu trúc dữ liệu áp dụng cho việc chuẩn bị trạng thái dựa trên QRAM.
Cụ thể, giả sử chúng ta được cung cấp $ A trong mathbb {C} ^ {mtimes n} $ với giá trị nhỏ nhất khác 2 $ sigma $ hỗ trợ một số truy vấn lấy mẫu quan trọng $ ell_6 $ -norm hiệu quả nhất định, cùng với $ b trong mathbb {C} ^ m $. Sau đó, với một số $ x trong mathbb {C} ^ n $ thỏa mãn $ | x - A ^ + b | leq varepsilon | A ^ + b | $, chúng ta có thể xuất ra số đo $ | xrangle $ trong cơ sở tính toán và xuất ra mục nhập $ x $ với các thuật toán cổ điển chạy trong $ dấu ngã {mathcal {O}} to (frac { | A | _ {mathrm {F}} ^ 6 | A | ^ 12} {sigma ^ {4} varepsilon ^ 6} big) $ và $ dấu ngã {mathcal {O}} to (frac {| A | _ {mathrm {F}} ^ 2 | A | ^ 8} {sigma ^ 4varepsilon ^ 16} big) $ time tương ứng. Điều này cải thiện các thuật toán “lấy cảm hứng từ lượng tử” trước đây trong dòng nghiên cứu này bằng ít nhất hệ số $ frac {| A | ^ {16}} {sigma ^ {2} varepsilon ^ 20} $ [Chia, Gilyén, Li, Lin, Tang và Wang, STOC'12]. Do đó, chúng tôi cho thấy rằng máy tính lượng tử có thể đạt được tốc độ tối đa là XNUMX cho hồi quy tuyến tính trong cài đặt cấu trúc dữ liệu QRAM này và các cài đặt liên quan. Công việc của chúng tôi áp dụng các kỹ thuật từ thuật toán phác thảo và tối ưu hóa cho tài liệu lấy cảm hứng từ lượng tử. Không giống như các công trình trước đó, đây là một con đường đầy hứa hẹn có thể dẫn đến các triển khai khả thi của hồi quy cổ điển trong một cài đặt lấy cảm hứng từ lượng tử, để so sánh với các máy tính lượng tử trong tương lai.
Hình ảnh nổi bật: Độ phức tạp tính toán của thuật toán tốt nhất trước đây cho hồi quy tuyến tính lấy cảm hứng từ lượng tử (như được mô tả trong phần tóm tắt), của Chia, Gilyén, Li, Lin, Tang, Wang, cùng với độ phức tạp của thuật toán đạt được trong công trình này. Cả hai thuật toán đều hoạt động trong các cài đặt chung hơn (công việc trước đây có thể được áp dụng cho khái niệm hồi quy mạnh mẽ hơn và công việc này hỗ trợ việc chính quy hóa), nhưng việc hạn chế cài đặt này không ảnh hưởng đáng kể đến việc so sánh.
Tóm tắt phổ biến
► Dữ liệu BibTeX
► Tài liệu tham khảo
[1] John Preskill. “Máy tính lượng tử trong kỷ nguyên NISQ và hơn thế nữa”. Lượng tử 2, 79 (2018). arXiv: 1801.00862.
https://doi.org/10.22331/q-2018-08-06-79
arXiv: 1801.00862
[2] Andrew M Childs. “Giải phương trình bằng mô phỏng”. Vật lý tự nhiên 5, 861–861 (2009).
https: / / doi.org/ 10.1038 / nphys1473
[3] Scott Aaronson. “Đọc bản in đẹp”. Vật lý tự nhiên 11, 291–293 (2015).
https: / / doi.org/ 10.1038 / nphys3272
[4] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe và Seth Lloyd. “Máy học lượng tử”. Nature 549, 195–202 (2017). arXiv: 1611.09347.
https: / / doi.org/ 10.1038 / thiên nhiên23474
arXiv: 1611.09347
[5] Aram W. Harrow, Avinatan Hassidim và Seth Lloyd. “Thuật toán lượng tử cho hệ phương trình tuyến tính”. Các Thư Ôn tập Vật lý 103, 150502 (2009). arXiv: 0811.3171.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: 0811.3171
[6] András Gilyén, Yuan Su, Guang Hao Low và Nathan Wiebe. “Chuyển đổi giá trị kỳ dị lượng tử và hơn thế nữa: Cải tiến theo cấp số nhân cho số học ma trận lượng tử”. Trong Kỷ yếu Hội thảo ACM lần thứ 51 về Lý thuyết Máy tính (STOC). Trang 193–204. (2019). arXiv: 1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838
[7] Vittorio Giovannetti, Seth Lloyd và Lorenzo Maccone. “Bộ nhớ truy cập ngẫu nhiên lượng tử”. Các Thư Ôn tập Vật lý 100, 160501 (2008). arXiv: 0708.1879.
https: / / doi.org/ 10.1103 / PhysRevLett.100.160501
arXiv: 0708.1879
[8] Anupam Prakash. “Các thuật toán lượng tử cho đại số tuyến tính và học máy”. Luận án Tiến sĩ. Đại học California tại Berkeley. (2014). url: www2.eecs.berkeley.edu/ Pubs / TechRpts / 2014 / EECS-2014-211.pdf.
https: / / www2.eecs.berkeley.edu/ Pubs / TechRpts / 2014 / EECS-2014-211.pdf
[9] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang và Chunhao Wang. “Khung số học ma trận hạng thấp dựa trên lấy mẫu để xác định chất lượng học máy lượng tử”. Trong Kỷ yếu Hội thảo ACM lần thứ 52 về Lý thuyết Máy tính (STOC). Trang 387–400. (Năm 2020). arXiv: 1910.06151.
https: / / doi.org/ 10.1145 / 3357713.3384314
arXiv: 1910.06151
[10] Iordanis Kerenidis và Anupam Prakash. "Hệ thống khuyến nghị lượng tử". Trong Kỷ yếu Hội nghị Khoa học Máy tính Lý thuyết (ITCS) Những đổi mới lần thứ 8. Trang 49: 1–49: 21. (2017). arXiv: 1603.08675.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2017.49
arXiv: 1603.08675
[11] Ewin Tang. “Một thuật toán cổ điển lấy cảm hứng từ lượng tử cho các hệ thống đề xuất”. Trong Kỷ yếu Hội thảo ACM lần thứ 51 về Lý thuyết Máy tính (STOC). Trang 217–228. (2019). arXiv: 1807.04271.
https: / / doi.org/ 10.1145 / 3313276.3316310
arXiv: 1807.04271
[12] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo và Anupam Prakash. “Q-mean: Một thuật toán lượng tử cho học máy không giám sát”. Những tiến bộ trong hệ thống xử lý thông tin thần kinh. Tập 32. (2019). arXiv: 1812.03584.
arXiv: 1812.03584
[13] Iordanis Kerenidis và Anupam Prakash. “Giảm độ dốc lượng tử cho hệ thống tuyến tính và bình phương nhỏ nhất”. Đánh giá vật lý A 101, 022316 (2020). arXiv: 1704.04992.
https: / / doi.org/ 10.1103 / PhysRevA.101.022316
arXiv: 1704.04992
[14] Danial Dervovic, Mark Herbster, Peter Mountney, Simone Severini, Naïri Usher và Leonard Wossnig. “Các thuật toán hệ thống tuyến tính lượng tử: một mồi” (2018). arXiv: 1802.08227.
arXiv: 1802.08227
[15] Leonard Wossnig, Zhikuan Zhao và Anupam Prakash. “Thuật toán hệ thống tuyến tính lượng tử cho ma trận dày đặc”. Các Thư Ôn tập Vật lý 120, 050502 (2018). arXiv: 1704.06174.
https: / / doi.org/ 10.1103 / PhysRevLett.120.050502
arXiv: 1704.06174
[16] Patrick Rebentrost, Masoud Mohseni và Seth Lloyd. “Máy vectơ hỗ trợ lượng tử để phân loại dữ liệu lớn”. Các Thư Ôn tập Vật lý 113, 130503 (2014). arXiv: 1307.0471.
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503
arXiv: 1307.0471
[17] Shantanav Chakraborty, András Gilyén và Stacey Jeffery. “Sức mạnh của sức mạnh ma trận mã hóa khối: Kỹ thuật hồi quy được cải thiện thông qua mô phỏng Hamilton nhanh hơn”. Trong Kỷ yếu của Hội thảo quốc tế lần thứ 46 về Tự động hóa, Ngôn ngữ và Lập trình (ICALP). Trang 33: 1–33: 14. (2019). arXiv: 1804.01973.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.33
arXiv: 1804.01973
[18] Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang và Chunhao Wang. “Các thuật toán lấy cảm hứng từ lượng tử để giải các hệ phương trình tuyến tính cấp thấp với sự phụ thuộc vào lôgarit vào thứ nguyên”. Trong Kỷ yếu của Hội nghị Chuyên đề Quốc tế lần thứ 31 về Thuật toán và Tính toán (ISAAC). Trang 47: 1–47: 17. (Năm 2020). arXiv: 1811.04852 và 1811.04909 (đã hợp nhất).
https: / / doi.org/ 10.4230 / LIPIcs.ISAAC.2020.47
arXiv: 1811.04852 và 1811.04909
(đã hợp nhất)
[19] Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan và Seth Lloyd. “Các thuật toán lấy cảm hứng từ lượng tử trong thực tế”. Lượng tử 4, 307 (năm 2020). arXiv: 1905.10415.
https://doi.org/10.22331/q-2020-08-13-307
arXiv: 1905.10415
[20] Ewin Tang. “Phân tích thành phần chính lượng tử chỉ đạt được tốc độ theo cấp số nhân vì các giả định về trạng thái chuẩn bị của nó”. Các Thư Ôn tập Vật lý 127, 060503 (2021). arXiv: 1811.00414.
https: / / doi.org/ 10.1103 / PhysRevLett.127.060503
arXiv: 1811.00414
[21] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini và Leonard Wossnig. “Máy học lượng tử: một quan điểm cổ điển”. 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 474, 20170551 (2018). arXiv: 1707.08561.
https: / / doi.org/ 10.1098 / rspa.2017.0551
arXiv: 1707.08561
[22] Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O'Connor, Michele Mosca và Priyaa Varshinee Srinivasan. “Về sự mạnh mẽ của RAM lượng tử của lữ đoàn xô”. Tạp chí Vật lý mới 17, 123010 (2015). arXiv: 1502.03450.
https://doi.org/10.1088/1367-2630/17/12/123010
arXiv: 1502.03450
[23] Neha Gupta và Aaron Sidford. “Khai thác số lượng thưa thớt để học tập hiệu quả: Tính toán và hồi quy eigenvector nhanh hơn”. Những tiến bộ trong hệ thống xử lý thông tin thần kinh. Trang 5269–5278. (2018). arXiv: 1811.10866.
arXiv: 1811.10866
[24] Yair Carmon, Yujia Jin, Aaron Sidford và Kevin Tian. “Phối hợp các phương pháp cho trò chơi ma trận”. Vào năm 2020, Hội nghị chuyên đề thường niên lần thứ 61 của IEEE về Nền tảng của Khoa học Máy tính (FOCS). Trang 283–293. IEEE (2020). arXiv: 2009.08447.
https: / / doi.org/ 10.1109 / focs46700.2020.00035
arXiv: 2009.08447
[25] Sébastien Bubeck. “Tối ưu hóa lồi: Thuật toán và độ phức tạp”. Cơ sở và Xu hướng trong Học máy 8, 231–357 (2015). arXiv: 1405.4980.
https: / / doi.org/ 10.1561 / 2200000050
arXiv: 1405.4980
[26] Roy Frostig, Rong Ge, Sham Kakade và Aaron Sidford. “Không điều hòa: Điểm gần gần đúng và các thuật toán ngẫu nhiên nhanh hơn để giảm thiểu rủi ro theo kinh nghiệm”. Trong Hội nghị Quốc tế về Học máy. Trang 2540–2548. (2015). arXiv: 1506.07512.
arXiv: 1506.07512
[27] Francis Bach và Eric Moulines. “Phân tích không tiệm cận của các thuật toán xấp xỉ ngẫu nhiên cho học máy”. Những tiến bộ trong hệ thống xử lý thông tin thần kinh. Trang 451–459. (2011). url: http: / / paper.nips.cc/ paper / 4316-non-asymptotic-analysis-of-stochastic-ước lượng-thuật toán-cho-máy-học.pdf.
http: / / paper.nips.cc/ paper / 4316-non-asymptotic-analysis-of-stochastic-xấp xỉ-giải thuật-cho-máy-học.pdf
[28] András Gilyén, Seth Lloyd và Ewin Tang. “Hồi quy ngẫu nhiên bậc thấp lấy cảm hứng từ lượng tử với sự phụ thuộc vào logarit vào thứ nguyên” (2018). arXiv: 1811.04909.
arXiv: 1811.04909
[29] Nai-Hui Chia, Han-Hsuan Lin và Chunhao Wang. “Các thuật toán cổ điển tuyến tính dưới lấy cảm hứng từ lượng tử để giải các hệ thống tuyến tính cấp thấp” (2018). arXiv: 1811.04852.
arXiv: 1811.04852
[30] David P. Woodruff. “Phác thảo như một công cụ cho đại số tuyến tính số”. Cơ sở và Xu hướng trong Khoa học Máy tính Lý thuyết 10, 1–157 (2014).
https: / / doi.org/ 10.1561 / 0400000060
[31] Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin và David P. Woodruff. “Các thuật toán lấy cảm hứng từ lượng tử từ đại số tuyến tính số ngẫu nhiên” (2020). arXiv: 2011.04125.
arXiv: 2011.04125
[32] Changpeng Shao và Ashley Montanaro. “Các thuật toán lấy cảm hứng từ lượng tử nhanh hơn để giải các hệ thống tuyến tính” (2021). arXiv: 2103.10309.
arXiv: 2103.10309
[33] Thomas Strohmer và Roman Vershynin. “Một thuật toán Kaczmarz ngẫu nhiên với sự hội tụ theo cấp số nhân”. Tạp chí Phân tích và Ứng dụng Fourier 15, 262–278 (2008). arXiv: toán học / 0702226.
https://doi.org/10.1007/s00041-008-9030-4
arXiv: math / 0702226
[34] Deanna Needell, Nathan Srebro và Rachel Ward. “Giảm độ dốc ngẫu nhiên, lấy mẫu có trọng số và thuật toán Kaczmarz ngẫu nhiên”. Lập trình Toán học 155, 549–573 (2015). arXiv: 1310.5715.
https://doi.org/10.1007/s10107-015-0864-7
arXiv: 1310.5715
[35] Petros Drineas, Ravi Kannan và Michael W Mahoney. “Các thuật toán Monte Carlo nhanh cho ma trận II: Tính toán xấp xỉ hạng thấp cho ma trận”. Tạp chí SIAM về Máy tính 36, 158–183 (2006).
https: / / doi.org/ 10.1137 / S0097539704442696
Trích dẫn
[1] Quynh T. Nguyen, Bobak T. Kiani và Seth Lloyd, “Thuật toán lượng tử cho các hạt nhân cấp đặc và đầy đủ sử dụng ma trận phân cấp”, arXiv: 2201.11329.
[2] Benjamin A. Cordier, Nicolas PD Sawaya, Gian G. Guerreschi, và Shannon K. McWeeney, “Sinh học và y học trong bối cảnh của lợi thế lượng tử”, arXiv: 2112.00760.
[3] Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, và Anupam Prakash, “Triển vọng và thách thức của tài chính lượng tử”, arXiv: 2011.06492.
[4] Amirhossein Nourbakhsh, Mark Nicholas Jones, Kaur Kristjuhan, Deborah Carberry, Jay Karon, Christian Beenfeldt, Kyarash Shahriari, Martin P. Andersson, Mojgan A. Jadidi và Seyed Soheil Mansouri, “Tính toán lượng tử: Nguyên tắc cơ bản, xu hướng và quan điểm cho Kỹ sư Hóa học và Sinh hóa ”, arXiv: 2201.02823.
[5] Xiao-Ming Zhang, Tongyang Li và Xiao Yuan, “Chuẩn bị trạng thái lượng tử với độ sâu mạch tối ưu: Triển khai và ứng dụng”, arXiv: 2201.11495.
[6] Bujiao Wu, Maharshi Ray, Liming Zhao, Xiaoming Sun và Patrick Rebentrost, “Các thuật toán cổ điển lượng tử cho các hệ thống tuyến tính lệch với một bài kiểm tra Hadamard được tối ưu hóa”, Đánh giá vật lý A 103 4, 042422 (2021).
[7] Iordanis Kerenidis và Anupam Prakash, “Máy học lượng tử với các trạng thái không gian con”, arXiv: 2202.00054.
[8] Changpeng Shao và Ashley Montanaro, "Các thuật toán lấy cảm hứng từ lượng tử nhanh hơn để giải các hệ thống tuyến tính", arXiv: 2103.10309.
[9] Patrick Rall, “Các thuật toán lượng tử mạch lạc nhanh hơn để ước tính pha, năng lượng và biên độ”, arXiv: 2103.09717.
[10] Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin và David P. Woodruff, “Các thuật toán lấy cảm hứng từ lượng tử từ Đại số tuyến tính số ngẫu nhiên”, arXiv: 2011.04125.
[11] Armando Bellante, Alessandro Luongo và Stefano Zanero, “Các thuật toán lượng tử để phân tích và đại diện dữ liệu”, arXiv: 2104.08987.
[12] Daniel Chen, Yekun Xu, Betis Baheri, Samuel A. Stein, Chuan Bi, Ying Mao, Qiang Quan và Shuai Xu, “Thuật toán cổ điển lấy cảm hứng từ lượng tử để phân tích tính năng chậm”, arXiv: 2012.00824.
[13] Sevag Gharibian và François Le Gall, “Phá bỏ sự biến đổi giá trị đơn lẻ lượng tử: Độ cứng và ứng dụng đối với hóa học lượng tử và phỏng đoán PCP lượng tử”, arXiv: 2111.09079.
[14] Chenyi Zhang, Jiaqi Leng và Tongyang Li, "Các thuật toán lượng tử để thoát khỏi điểm yên ngựa", arXiv: 2007.10253.
[15] Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda và Kazuyoshi Yoshino, "Hồi quy tuyến tính bằng ước lượng biên độ lượng tử và phần mở rộng của nó để tối ưu hóa lồi", Đánh giá vật lý A 104 2, 022430 (2021).
[16] Franco D. Albareti, Thomas Ankenbrand, Denis Bieri, Esther Hänggi, Damian Lötscher, Stefan Stettler và Marcel Schöngens, “Khảo sát có cấu trúc về Máy tính lượng tử cho ngành tài chính”, arXiv: 2204.10026.
[17] Ebrahim Ardeshir-Larijani, "Độ phức tạp tham số của các thuật toán lấy cảm hứng từ lượng tử", arXiv: 2112.11686.
[18] Shantanav Chakraborty, Aditya Morolia, và Anurudh Peduri, “Hình vuông ít nhất được điều chỉnh lượng tử”, arXiv: 2206.13143.
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 / 06-30 13:00:28). 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 đủ.
Không thể tìm nạp Crossref trích dẫn bởi dữ liệu trong lần thử cuối cùng 2022 / 06-30 13:00:26: Không thể tìm nạp dữ liệu được trích dẫn cho 10.22331 / q-2022 / 06-30-754 từ Crossref. Điều này là bình thường nếu DOI đã được đăng ký gần đây.
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ọ.
