1QuSoft, Amsterdam, Hà Lan.
2Đại học Amsterdam, Hà Lan.
3Đại học Amsterdam, Hà Lan.
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
Brandão và Svore [14] gần đây đã đưa ra các thuật toán lượng tử để giải gần đúng các chương trình bán hạn, trong một số chế độ nhanh hơn các thuật toán cổ điển tốt nhất có thể về thứ nguyên $ n $ của bài toán và số $ m $ của các ràng buộc, nhưng tệ hơn về các các thông số khác. Trong bài báo này, chúng tôi cải thiện các thuật toán của họ theo một số cách, để có được sự phụ thuộc tốt hơn vào các tham số khác đó. Để đạt được mục đích này, chúng tôi phát triển các kỹ thuật mới cho các thuật toán lượng tử, ví dụ như một cách chung để triển khai hiệu quả các chức năng trơn tru của các Hamiltonians thưa thớt và một quy trình tìm kiếm tối thiểu tổng quát.
Chúng tôi cũng chỉ ra các giới hạn đối với cách tiếp cận này đối với các bộ giải SDP lượng tử, chẳng hạn đối với các bài toán tối ưu hóa tổ hợp có nhiều đối xứng. Cuối cùng, chúng tôi chứng minh một số giới hạn dưới chung cho thấy rằng trong trường hợp xấu nhất, độ phức tạp của mọi bộ giải LP lượng tử (và do đó cũng là bộ giải SDP) phải chia tỷ lệ tuyến tính với $ mn $ khi $ mapprox n $, giống như cổ điển.
Tóm tắt phổ biến
► Dữ liệu BibTeX
► Tài liệu tham khảo
[1] Sanjeev Arora, Elad Hazan và Satyen Kale. Phương pháp cập nhật trọng số nhân: một thuật toán tổng hợp và các ứng dụng. toc, 8 (6): 121–164, 2012.
https: / / doi.org/ 10.4086 / toc.2012.v008a006
[2] Sanjeev Arora và Satyen Kale. Một cách tiếp cận tổ hợp, nguyên thủy-kép đối với các chương trình bán kỳ. jacm, 63 (2): 12: 1–12: 35, 2016. Phiên bản trước đó trong STOC'07.
https: / / doi.org/ 10.1145 / 2837020
[3] Andris Ambainis. Thuật toán đi bộ lượng tử cho tính khác biệt của phần tử. siamjc, 37 (1): 210–239, 2007. Phiên bản trước đó trong FOCS'04. arXiv: quant-ph / 0311001?.
https: / / doi.org/ 10.1137 / S0097539705447311
arXiv: quant-ph / 0311001
[4] Joran van Apeldoorn và András Gilyén. Cải tiến trong giải quyết SDP lượng tử với các ứng dụng. Trong icalp46th, trang 99: 1–99: 15, 2019. arXiv: 1804.05058 ?.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.99
arXiv: 1804.05058
[5] Joran van Apeldoorn và András Gilyén. Các thuật toán lượng tử cho các trò chơi có tổng bằng không. arXiv: 1904.03180 ?, 2019.
arXiv: 1904.03180
[6] Joran van Apeldoorn, András Gilyén, Sander Gribling và Ronald de Wolf. Bộ giải SDP lượng tử: Giới hạn trên và dưới tốt hơn. Trong focs58th, trang 403–414, 2017. arXiv: 1705.01843 ?.
https: / / doi.org/ 10.1109 / FOCS.2017.44
arXiv: 1705.01843
[7] Joran van Apeldoorn, András Gilyén, Sander Gribling và Ronald de Wolf. Tối ưu hóa lồi bằng phép toán lượng tử. quantum, 4: 220, 2020. arXiv: 1809.00643 ?.
https://doi.org/10.22331/q-2020-01-13-220
arXiv: 1809.00643
[8] Noga Alon và Joel H. Spencer. Phương pháp xác suất. Wiley-Interscience, ấn bản thứ ba, 2008.
https: / / doi.org/ 10.1002 / 0471722154
[9] Michel Boyer, Gilles Brassard, Peter Høyer và Alain Tapp. Giới hạn chặt chẽ đối với tìm kiếm lượng tử. Fortschritte der Physik, 46 (4–5): 493–505, 1998. arXiv: quant-ph / 9605034?.
arXiv: quant-ph / 9605034
[10] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari và Rolando D. Somma. Mô phỏng động lực học Hamilton với chuỗi Taylor cắt ngắn. prl, 114 (9): 090502, 2015. arXiv: 1412.4687?.
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502
arXiv: 1412.4687
[11] Dominic W. Berry, Andrew M. Childs và Robin Kothari. Mô phỏng Hamilton với sự phụ thuộc gần như tối ưu vào tất cả các tham số. Trong focs56th, trang 792–809, 2015. arXiv: 1501.01715 ?.
https: / / doi.org/ 10.1109 / FOCS.2015.54
arXiv: 1501.01715
[12] Gilles Brassard, Peter Høyer, Michele Mosca và Alain Tapp. Khuếch đại và ước lượng biên độ lượng tử. Trong Tính toán Lượng tử và Thông tin Lượng tử: Một Khối lượng Thiên niên kỷ, tập 305 của Series Toán học Đương đại, trang 53–74. AMS, 2002. arXiv: quant-ph / 0005055?.
https: / / doi.org/ 10.1090 / conm / 305/05215
arXiv: quant-ph / 0005055
[13] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore và Xiaodi Wu. Bộ giải SDP lượng tử: Tăng tốc độ lớn, tính tối ưu và các ứng dụng cho việc học lượng tử. Trong icalp46th, trang 27: 1–27: 14, 2019. arXiv: 1710.02581 ?.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27
arXiv: 1710.02581
[14] Fernando GSL Brandão và Krysta M. Svore. Tăng tốc lượng tử để giải các chương trình bán kỳ. Trong focs58th, trang 415–426, 2017. arXiv: 1609.05537 ?.
https: / / doi.org/ 10.1109 / FOCS.2017.45
arXiv: 1609.05537
[15] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li và Xiaodi Wu. Các thuật toán lượng tử và các giới hạn thấp hơn để tối ưu hóa độ lồi. quantum, 4: 221, 2020. arXiv: 1809.01731 ?.
https://doi.org/10.22331/q-2020-01-13-221
arXiv: 1809.01731
[16] Richard Cleve, Artur Ekert, Chiara Macchiavello và Michele Mosca. Các thuật toán lượng tử đã được xem lại. rspa, 454 (1969): 339–354, 1998. arXiv: quant-ph / 9708016 ?.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: quant-ph / 9708016
[17] Andrew M. Childs, Robin Kothari và Rolando D. Somma. Thuật toán lượng tử cho các hệ phương trình tuyến tính với sự phụ thuộc vào độ chính xác được cải thiện theo cấp số nhân. siamjc, 46 (6): 1920–1950, 2017. arXiv: 1511.02306 ?.
https: / / doi.org/ 10.1137 / 16M1087072
arXiv: 1511.02306
[18] Anirban Narayan Chowdhury và Rolando D. Somma. Các thuật toán lượng tử để lấy mẫu Gibbs và ước tính thời gian truy cập. qic, 17 (1 & 2): 41–64, 2017. arXiv: 1603.02940 ?.
https: / â € trận / â € doi.org/â $$$ 10.26421 / â € QIC17.1-2
arXiv: 1603.02940
[19] Andrew M. Childs và Nathan Wiebe. Mô phỏng Hamilton sử dụng kết hợp tuyến tính của các phép toán đơn nhất. qic, 12 (11 & 12): 901–924, 2012. arXiv: 1202.5822 ?.
https: / â € trận / â € doi.org/â $$$ 10.26421 / â € QIC12.11-12
arXiv: 1202.5822
[20] George B. Dantzig. Tối đa hóa hàm tuyến tính của các biến chịu bất đẳng thức tuyến tính. Trong Phân tích hoạt động sản xuất và phân bổ, Chuyên khảo số 13 của Ủy ban Cowles, trang 339
–347. John Wiley & Sons Inc., New York, NY, 1951.
[21] Christoph Dürr và Peter Høyer. Một thuật toán lượng tử để tìm giá trị tối thiểu. arXiv: quant-ph / 9607014 ?, 1996.
arXiv: quant-ph / 9607014
[22] Christoph Dürr, Mark Heiligman, Peter Høyer và Mehdi Mhalla. Độ phức tạp của truy vấn lượng tử của một số vấn đề về đồ thị. siamjc, 35 (6): 1310–1328, 2006. Phiên bản trước đó trong ICALP'04. arXiv: quant-ph / 0401091?.
https: / / doi.org/ 10.1137 / 050644719
arXiv: quant-ph / 0401091
[23] Martin Grötschel, László Lovász và Alexander Schrijver. Phương pháp ellipsoid và hệ quả của nó trong tối ưu tổ hợp. comb, 1 (2): 169–197, 1981.
https: / / doi.org/ 10.1007 / BF02579273
[24] Martin Grötschel, László Lovász và Alexander Schrijver. Thuật toán hình học và tối ưu hóa tổ hợp. Springer, 1988.
[25] Yêu Grover và Terry Rudolph. Tạo các chồng chất tương ứng với các phân phối xác suất có thể tích hợp hiệu quả. arXiv: quant-ph / 0208112 ?, năm 2002.
arXiv: quant-ph / 0208112
[26] Yêu K. Grover. Một thuật toán cơ lượng tử nhanh để tìm kiếm cơ sở dữ liệu. Trong stoc28th, trang 212–219, 1996. arXiv: quant-ph / 9605043 ?.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043
[27] 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 stoc51st, trang 193–204, 2019. arXiv: 1806.01838 ?.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838
[28] Michel X. Goemans và David P. Williamson. Các thuật toán xấp xỉ được cải tiến cho các bài toán cắt và thỏa mãn tối đa bằng cách sử dụng lập trình bán kỳ. jacm, 42 (6): 1115–1145, 1995. Phiên bản trước đó trong STOC'94.
https: / / doi.org/ 10.1145 / 227683.227684
[29] 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. prl, 103 (15): 150502, 2009. arXiv: 0811.3171 ?.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: 0811.3171
[30] Shelby Kimmel. Giới hạn đối thủ lượng tử (phía trên). cjtcs, 2013: 4: 1–14, 2013. Phiên bản trước đó trong ICALP'12. arXiv: 1101.0797 ?.
https: / / doi.org/ 10.4086 / cjtcs.2013.004
arXiv: 1101.0797
[31] Subhash Khot, Guy Kindler, Elchanan Mossel và Ryan O'Donnell. Kết quả tối ưu về khả năng không tương thích cho MAX-CUT và các CSP 2 biến khác? siamjc, 37 (1): 319–357, 2007. Phiên bản trước đó trong FOCS'04.
https: / / doi.org/ 10.1137 / S0097539705447372
[32] Iordanis Kerenidis và Anupam Prakash. Một phương pháp điểm bên trong lượng tử cho LP và SDP. arXiv: 1808.09266 ?, 2018.
arXiv: 1808.09266
[33] Guang Hao Low và Isaac L. Chuang. Mô phỏng Hamilton tối ưu bằng xử lý tín hiệu lượng tử. prl, 118 (1): 010501, 2017. arXiv: 1606.02685 ?.
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
arXiv: 1606.02685
[34] Guang Hao Low và Isaac L. Chuang. Mô phỏng Hamilton bằng cách số hóa. quantum, 3: 163, 2019. arXiv: 1610.06546 ?.
https://doi.org/10.22331/q-2019-07-12-163
arXiv: 1610.06546
[35] Yin Tat Lee, Aaron Sidford và Sam Chiu-Wai Wong. Phương pháp mặt phẳng cắt nhanh hơn và ý nghĩa của nó đối với tối ưu hóa tổ hợp và lồi. Trong focs56th, trang 1049–1065, 2015. arXiv: 1508.04874 ?.
https: / / doi.org/ 10.1109 / FOCS.2015.68
arXiv: 1508.04874
[36] Michael A. Nielsen và Isaac L. Chuang. Tính toán lượng tử và thông tin lượng tử. Nhà xuất bản Đại học Cambridge, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667
[37] Y. Nesterov và A. Nemirovski. Các thuật toán đa thức điểm trong trong lập trình lồi, tập 13 của SIAM Nghiên cứu về Toán ứng dụng. Hiệp hội Toán học Ứng dụng và Công nghiệp (SIAM), 1994.
https: / / doi.org/ 10.1137 / 1.9781611970791
[38] David Poulin và Pawel Wocjan. Chuẩn bị trạng thái cơ bản của hệ nhiều cơ thể lượng tử trên máy tính lượng tử. prl, 102 (13): 130503, 2009. arXiv: 0809.2705 ?.
https: / / doi.org/ 10.1103 / PhysRevLett.102.130503
arXiv: 0809.2705
[39] David Poulin và Pawel Wocjan. Lấy mẫu từ trạng thái Gibbs lượng tử nhiệt và đánh giá các chức năng phân vùng bằng máy tính lượng tử. prl, 103 (22): 220502, 2009. arXiv: 0905.2199?.
https: / / doi.org/ 10.1103 / PhysRevLett.103.220502
arXiv: 0905.2199
[40] James Renegar. Các phương pháp dưới cấp “hiệu quả” để tối ưu hóa độ lồi chung. siamjc, 26 (4): 2649–2676, 2016. arXiv: 1605.08712 ?.
https: / / doi.org/ 10.1137 / 15M1027371
arXiv: 1605.08712
[41] James Renegar. Các phương pháp bậc nhất cấp tốc cho lập trình hypebol. Lập trình Toán học, 173 (1): 1–35, 2019. arXiv: 1512.07569 ?.
https: / / doi.org/ 10.1007 / s10107-017-1203-y
arXiv: 1512.07569
[42] Alexander Schrijver. Lý thuyết về lập trình tuyến tính và số nguyên. John Wiley & Sons, Inc., New York, NY, Hoa Kỳ, 1986.
[43] Peter W. Shor. Các thuật toán đa thức thời gian để tính thừa số nguyên tố và logarit rời rạc trên máy tính lượng tử. siamjc, 26 (5): 1484–1509, 1997. Phiên bản trước đó trong FOCS'94. arXiv: quant-ph / 9508027?.
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: quant-ph / 9508027
[44] Koji Tsuda, Gunnar Rätsch và Manfred K. Warmuth. Cập nhật gradient lũy thừa ma trận để học trực tuyến và phép chiếu Bregman. Tạp chí Nghiên cứu Máy học, 6: 995–1018, 2005. Phiên bản trước đó trong NIPS'04.
http: / / jmlr.csail.mit.edu/ paper / volume6 / tsuda05a / tsuda05a.pdf
[45] Manfred K. Warmuth và Dima Kuzmin. Giảm thiểu phương sai trực tuyến. Học máy, 87 (1): 1–32, 2012. Phiên bản trước đó trong COLT'06.
https://doi.org/10.1007/s10994-011-5269-0
Trích dẫn
[1] 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: những cải tiến theo cấp số nhân đối với số học ma trận lượng tử”, arXiv: 1806.01838.
[2] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini và Leonard Wossnig, “Máy học lượng tử: góc nhìn cổ điển”, Kỷ yếu của Hiệp hội Hoàng gia Luân Đôn Series A 474 2209, 20170551 (2018).
[3] Patrick Rebentrost và Seth Lloyd, “Tài chính tính toán lượng tử: thuật toán lượng tử để tối ưu hóa danh mục đầu tư”, arXiv: 1811.03975.
[4] Joran van Apeldoorn và András Gilyén, "Các thuật toán lượng tử cho các trò chơi có tổng bằng XNUMX", arXiv: 1904.03180.
[5] András Gilyén, Srinivasan Arunachalam và Nathan Wiebe, “Tối ưu hóa các thuật toán tối ưu lượng tử thông qua tính toán gradient lượng tử nhanh hơn”, arXiv: 1711.00465.
[6] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, và Seth Lloyd, “Đường xuống gradient lượng tử và phương pháp của Newton để tối ưu hóa đa thức bị ràng buộc”, arXiv: 1612.01789.
[7] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore và Xiaodi Wu, “Bộ giải Quantum SDP: Tốc độ lớn, Tính tối ưu và Ứng dụng vào Học lượng tử”, arXiv: 1710.02581.
[8] Joran van Apeldoorn và András Gilyén, “Những cải tiến trong giải pháp SDP lượng tử với các ứng dụng”, arXiv: 1804.05058.
[9] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin và Chunhao Wang, “Thuật toán thời gian con tuyến tính cổ điển lấy cảm hứng từ lượng tử để giải lập trình bán kỳ hạng thấp thông qua các phương pháp lấy mẫu”, arXiv: 1901.03254.
[10] Simon Apers, “Lấy mẫu đi bộ lượng tử bằng cách trồng bộ hạt giống”, arXiv: 1904.11446.
[11] Joran van Apeldoorn, András Gilyén, Sander Gribling và Ronald de Wolf, “Tối ưu hóa lồi bằng cách sử dụng các phép toán lượng tử”, arXiv: 1809.00643.
[12] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li và Xiaodi Wu, "Các thuật toán lượng tử và giới hạn thấp hơn để tối ưu hóa lồi", arXiv: 1809.01731.
[13] Yimin Ge, Jordi Tura và J. Ignacio Cirac, "Chuẩn bị trạng thái cơ bản nhanh hơn và ước tính năng lượng mặt đất chính xác cao với ít qubit hơn", arXiv: 1712.03193.
[14] Ivan Bardet và Cambyse Rouzé, “Bất đẳng thức siêu điều khiển và logarit Sobolev đối với các bán phân nhóm Markov lượng tử không nguyên thủy và ước tính tỷ lệ giảm liên kết”, arXiv: 1803.05379.
[15] Ashley Montanaro, "Tăng tốc lượng tử của các thuật toán nhánh và giới hạn", arXiv: 1906.10375.
[16] Johannes Bausch, Sathyawageeswar Subramanian, và Stephen Piddock, “Một bộ giải mã tìm kiếm lượng tử để xử lý ngôn ngữ tự nhiên”, arXiv: 1909.05023.
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 2020 / 02-14 09:28:14). 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 2020 / 02-14 09:28:13: Không thể tìm nạp dữ liệu được trích dẫn cho 10.22331 / q-2020 / 02-14-230 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ọ.
Nguồn: https://quantum-journal.org/ con / q-2020 / 02-14-230 /
