Phương pháp phân chia và chinh phục lai cho các thuật toán tìm kiếm cây

Phương pháp phân chia và chinh phục lai cho các thuật toán tìm kiếm cây

Dấu thời gian: Ngày 23 tháng 2023 năm 9 57:XNUMX sáng
Nút nguồn: 2029300

Mathys Rennela1, Thương hiệu Sebastiaan2, Alfons Laarman2, và Vedran Dunjko2

1Laboratoire de Physique de l'Ecole Normale Supérieure, Inria, CNRS, ENS-PSL, Mines-Paristech, Đại học Sorbonne, Đại học Nghiên cứu PSL, Paris, Pháp
2LIACS, Đại học Leiden, Leiden, 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

Một trong những thách thức của máy tính lượng tử trong thời gian tới và trung hạn là số lượng qubit hạn chế mà chúng ta có thể sử dụng để tính toán. Do đó, việc tìm kiếm các phương pháp đạt được những cải tiến lượng tử hữu ích trong các giới hạn về kích thước là một câu hỏi quan trọng trong lĩnh vực này. Theo xu hướng này, gần đây người ta đã chứng minh rằng một phương pháp lượng tử-cổ điển lai có thể giúp cung cấp khả năng tăng tốc đa thức cho các thuật toán chia để trị cổ điển, ngay cả khi chỉ được cấp quyền truy cập vào một máy tính lượng tử nhỏ hơn nhiều so với bản thân vấn đề. Trong công việc này, chúng tôi nghiên cứu phương pháp phân chia và chinh phục kết hợp trong bối cảnh thuật toán tìm kiếm cây và mở rộng nó bằng cách bao gồm quay lui lượng tử, cho phép kết quả tốt hơn so với các phương pháp dựa trên Grover trước đây. Hơn nữa, chúng tôi cung cấp các tiêu chí chung để tăng tốc đa thức trong ngữ cảnh tìm kiếm cây và cung cấp một số ví dụ về việc tăng tốc đa thức, sử dụng các máy tính lượng tử nhỏ hơn tùy ý, có thể thu được. Chúng tôi cung cấp các điều kiện để tăng tốc cho thuật toán DPLL nổi tiếng và chúng tôi chứng minh khả năng tăng tốc không giới hạn cho thuật toán PPSZ (cốt lõi của bộ giải thỏa mãn Boolean chính xác nhanh nhất) cho các lớp công thức hoạt động tốt. Chúng tôi cũng cung cấp một ví dụ đơn giản trong đó có thể đạt được tốc độ tăng theo kiểu độc lập với thuật toán, theo các giả định lý thuyết về độ phức tạp đã được nghiên cứu kỹ lưỡng nhất định. Cuối cùng, chúng tôi thảo luận ngắn gọn về những hạn chế cơ bản của các phương pháp lai trong việc cung cấp khả năng tăng tốc cho các bài toán lớn hơn.

Tóm tắt phổ biến

Trong ngắn hạn và trung hạn, với các máy tính lượng tử có số lượng qubit hạn chế, một số trường hợp vấn đề nhất định có thể quá lớn để giải quyết trên máy tính lượng tử. Trong bối cảnh này, điều tự nhiên là xem xét các chiến lược chia để trị: chia vấn đề thành các phần đủ nhỏ để giải quyết trên máy tính lượng tử và kết hợp các kết quả sau đó. Đây được gọi là thuật toán lai lượng tử-cổ điển.

Các thuật toán tìm kiếm cây đặc biệt phù hợp với phương pháp kết hợp này. Khi không gian tìm kiếm là một cây nhị phân hoàn chỉnh, thật đơn giản để chia vấn đề thành các phần đủ nhỏ cho một máy tính lượng tử nhất định và vẫn để lại một sự tăng tốc lượng tử (nhỏ hơn) cho vấn đề ban đầu. Tuy nhiên, trong hầu hết các thuật toán tìm kiếm cây cổ điển, các nhánh được cắt tỉa trong quá trình tìm kiếm và một cây thưa thớt hơn vẫn còn. Trong cài đặt này, sẽ trở nên ít rõ ràng hơn nếu vẫn có thể thu được sự tăng tốc đa thức nhỏ bằng thuật toán lai.

Trong bài báo này, chúng tôi nghiên cứu phương pháp phân chia và chinh phục kết hợp này trong ngữ cảnh của các thuật toán tìm kiếm cây, chẳng hạn như các thuật toán được phát triển cho sự thỏa mãn của Boolean. Đóng góp chính của chúng tôi là chúng tôi cung cấp đủ điều kiện để tăng tốc lượng tử và áp dụng chúng cho hai thuật toán thỏa mãn Boolean nổi tiếng.

► Dữ liệu BibTeX

► Tài liệu tham khảo

[1] Vedran Dunjko, Yimin Ge và J Ignacio Cirac. “Tăng tốc tính toán bằng cách sử dụng các thiết bị lượng tử nhỏ”. Thư đánh giá vật lý 121, 250501 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.121.250501

[2] Yimin Ge và Vedran Dunjko. “Khung thuật toán lai cho máy tính lượng tử nhỏ có ứng dụng tìm chu trình Hamilton”. Tạp chí Vật lý Toán 61, 012201 (2020).
https: / / doi.org/ 10.1063 / 1.5119235

[3] Ashley Montanaro. “Tăng tốc độ đi bộ lượng tử của thuật toán quay lui”. Lý thuyết máy tính 14, 1–24 (2018).
https: / / doi.org/ 10.4086 / toc.2018.v014a015

[4] Martin Davis, George Logemann và Donald W Loveland. “Một chương trình máy để chứng minh định lý”. Đại học New York, Viện Khoa học Toán học. (1961).
https: / / doi.org/ 10.1145 / 368273.368557

[5] Ramamohan Paturi, Pavel Pudlák, Michael E Saks và Francis Zane. “Một thuật toán thời gian hàm mũ được cải tiến cho k-SAT”. Tạp chí của ACM (JACM) 52, 337–364 (2005).
https: / / doi.org/ 10.1145 / 1066100.1066101

[6] Bá tước Campbell, Ankur Khurana và Ashley Montanaro. “Áp dụng thuật toán lượng tử để hạn chế bài toán thỏa mãn”. Lượng tử 3, 167 (2019).
https:/​/​doi.org/​10.22331/​q-2019-07-18-167

[7] Simon Martiel và Maxime Remaud. “Triển khai thực tế thuật toán quay lui lượng tử”. Trong Hội nghị quốc tế về xu hướng hiện nay trong lý thuyết và thực hành tin học. Trang 597–606. Mùa xuân (2020).
https:/​/​doi.org/​10.1007/​978-3-030-38919-2_49

[8] Thomas Dueholm Hansen, Haim Kaplan, Or Zamir và Uri Zwick. “Thuật toán k-sat nhanh hơn bằng cách sử dụng thiên vị-ppsz”. 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 578–589. STOC 2019New York, NY, Hoa Kỳ (2019). ACM.
https: / / doi.org/ 10.1145 / 3313276.3316359

[9] Armin Biere, Marijn Heule và Hans van Maaren. “Sổ tay về sự hài lòng”. Tập 185. Báo chí iOS. (2009).

[10] Marc Mezard, Marc Mezard và Andrea Montanari. “Thông tin, vật lý và tính toán”. Nhà xuất bản Đại học Oxford. (2009).
https: / / doi.org/ 10.1063 / 1.3397047

[11] Martin Davis và Hilary Putnam. “Quy trình tính toán cho lý thuyết định lượng”. J. ACM 7, 201–215 (1960).
https: / / doi.org/ 10.1145 / 321033.321034

[12] Marijn JH Heule, Matti Juhani Järvisalo, Martin Suda và những người khác. “Mô tả bộ giải và điểm chuẩn”. Trong Kỷ yếu cuộc thi SAT 2018. Khoa Khoa học Máy tính, Đại học Helsinki (2018). url: http://​/​hdl.handle.net/​10138/​237063.
http: / / hdl.handle.net/ 10138/237063

[13] Robert Nieuwenhuis, Albert Oliveras và Cesare Tinelli. “Các lý thuyết modulo DPLL trừu tượng và DPLL trừu tượng”. Trong Hội nghị quốc tế về logic lập trình trí tuệ nhân tạo và lý luận. Trang 36–50. Mùa xuân (2005).
https:/​/​doi.org/​10.1007/​978-3-540-32275-7_3

[14] Jasmin Christian Blanchette, Sascha Böhme và Lawrence C Paulson. “Mở rộng Búa tạ bằng bộ giải SMT”. Tạp chí lý luận tự động 51, 109–128 (2013).
https:/​/​doi.org/​10.1007/​s10817-013-9278-5

[15] Daniel Rolf. “Việc loại bỏ ngẫu nhiên PPSZ cho duy nhất-k-SAT”. Trong Hội nghị quốc tế về lý thuyết và ứng dụng của kiểm tra sự hài lòng. Trang 216–225. Mùa xuân (2005).
https: / / doi.org/ 10.1007 / IDIA11499107_16

[16] Dominik Scheder và John P Steinberger. “PPSZ dành cho k-SAT chung giúp phân tích của Hertli đơn giản hơn và 3-SAT nhanh hơn”. Trong Hội nghị về độ phức tạp tính toán lần thứ 32 (CCC 2017). Tập 79, trang 9:1–9:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017).
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.9

[17] Daniel Rolf. “Cải thiện giới hạn cho PPSZ/​thuật toán phân lớp cho 3-SAT”. Tạp chí về sự hài lòng, mô hình hóa và tính toán Boolean 1, 111–122 (2006).
https://​/​doi.org/​10.3233/​SAT190005

[18] Timon Hertli. “3-SAT nhanh hơn và đơn giản hơn—giới hạn SAT duy nhất cho việc giữ PPSZ nói chung”. Tạp chí SIAM về Máy tính 43, 718–729 (2014).
https: / / doi.org/ 10.1137 / 120868177

[19] Timon Hertli. “Phá vỡ rào cản PPSZ cho 3-SAT độc nhất”. Trong Automata, Ngôn ngữ và Lập trình: Hội thảo quốc tế lần thứ 41, ICALP 2014, Copenhagen, Đan Mạch, ngày 8-11 tháng 2014 năm 41, Kỷ yếu, Phần I 600. Trang 611–2014. Mùa xuân (XNUMX).
https:/​/​doi.org/​10.1007/​978-3-662-43948-7_50

[20] Người lập kế hoạch Dominik. “PPSZ tốt hơn bạn nghĩ”. Vào năm 2021, Hội nghị chuyên đề thường niên lần thứ 62 của IEEE về Nền tảng Khoa học Máy tính (FOCS). Trang 205–216. (2022).
https: / / doi.org/ 10.1109 / FOCS52979.2021.00028

[21] Lov K Grover. “Một thuật toán cơ học lượng tử nhanh để tìm kiếm cơ sở dữ liệu”. Trong Kỷ yếu của hội nghị chuyên đề ACM thường niên lần thứ 212 về Lý thuyết máy tính. Trang 219–1996. (XNUMX).
https: / / doi.org/ 10.1145 / 237814.237866

[22] Andris Ambainis. “Thuật toán tìm kiếm lượng tử”. Tin tức ACM SIGACT 35, 22–35 (2004).
https: / / doi.org/ 10.1145 / 992287.992296

[23] Andris Ambainis và Martins Kokaines. “Thuật toán lượng tử để ước tính kích thước cây, với các ứng dụng quay lui và trò chơi 2 người chơi”. 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. Trang 989–1002. (2017).
https: / / doi.org/ 10.1145 / 3055399.3055444

[24] Michael Jarret và Kianna Wan. “Các thuật toán theo dõi ngược lượng tử được cải tiến bằng cách sử dụng các ước tính điện trở hiệu quả”. Đánh giá vật lý A 97, 022337 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022337

[25] Dominic J. Moylett, Noah Linden và Ashley Montanaro. “Tăng tốc lượng tử của bài toán người bán hàng du lịch đối với đồ thị mức độ giới hạn”. Vật lý. Mục sư A 95, 032323 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.032323

[26] Neil D. Jones và William T. Laaser. “Hoàn thành các bài toán về thời gian đa thức xác định”. Khoa học máy tính lý thuyết 3, 105 – 117 (1976).
https:/​/​doi.org/​10.1016/​0304-3975(76)90068-2

[27] Raymond Greenlaw, H James Hoover, Walter L Ruzzo, và những người khác. “Giới hạn tính toán song song: Lý thuyết P-đầy đủ”. Nhà xuất bản Đại học Oxford theo yêu cầu. (1995).

[28] Thomas Lengauer và Robert E Tarjan. “Các giới hạn tiệm cận chặt chẽ về sự đánh đổi không gian-thời gian trong trò chơi ném sỏi”. Tạp chí của ACM (JACM) 29, 1087–1130 (1982).
https: / / doi.org/ 10.1145 / 322344.322354

[29] Charles H Bennett. “Sự đánh đổi thời gian/không gian để tính toán thuận nghịch”. Tạp chí SIAM về Máy tính 18, 766–776 (1989).
https: / / doi.org/ 10.1137 / 0218053

[30] T. Altman và Y. Igarashi. “Sắp xếp đại khái: Cách tiếp cận tuần tự và song song”. J. Inf. Quá trình. 12, 154–158 (1989). url: http://​/​id.nii.ac.jp/​1001/​00059782/​.
http://​/​id.nii.ac.jp/​1001/​00059782/​

[31] Hong-Yu Liang và Jing He. “Sự hài lòng với sự phụ thuộc chỉ số”. Tạp chí Khoa học và Công nghệ Máy tính 27, 668–677 (2012).
https:/​/​doi.org/​10.1007/​978-3-642-17517-6_7

[32] Marcello Benedetti, John Realpe-Gómez và Alejandro Perdomo-Ortiz. “Máy Helmholtz được hỗ trợ lượng tử: Khung học sâu cổ điển lượng tử dành cho các bộ dữ liệu công nghiệp trong các thiết bị ngắn hạn”. Khoa học và Công nghệ Lượng tử 3, 034007 (2018).
https: / / doi.org/ 10.1088 / 2058-9565 / aabd98

[33] Aram W. Harrow. “Máy tính lượng tử nhỏ và tập dữ liệu cổ điển lớn” (2020) arXiv:2004.00026.
arXiv: 2004.00026

[34] Michael A Nielsen và Isaac Chuang. “Tính toán lượng tử và thông tin lượng tử”. Hiệp hội giáo viên vật lý Hoa Kỳ. (2002).
https: / / doi.org/ 10.1017 / CBO9780511976667

[35] Robert B. Griffiths và Chi-Sheng Niu. “Biến đổi phạm vi bán cổ điển cho tính toán lượng tử”. Vật lý. Linh mục Lett. 76, 3228–3231 (1996).
https: / / doi.org/ 10.1103 / PhysRevLett.76.3228

[36] Robert Raussendorf và Hans J. Briegel. “Máy tính lượng tử một chiều”. vật lý. Mục sư Lett. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[37] Thomas E O'Brien, Brian Tarasinski và Barbara M Terhal. “Ước tính pha lượng tử của nhiều giá trị riêng cho các thí nghiệm quy mô nhỏ (ồn ào)”. Tạp chí Vật lý mới số 21, 023022 (2019).
https://​/​doi.org/​10.1088/​1367-2630/​aafb8e

[38] Akshay Ajagekar, Travis Humble và Fengqi You. “Các chiến lược giải pháp hỗn hợp dựa trên điện toán lượng tử cho các vấn đề tối ưu hóa liên tục-rời rạc quy mô lớn”. Máy tính & Kỹ thuật Hóa học 132, 106630 (2020).
https://​/​doi.org/​10.1016/​j.compchemeng.2019.106630

[39] Tianyi Peng, Aram W Harrow, Maris Ozols và Xiaodi Wu. “Mô phỏng các mạch lượng tử lớn trên một máy tính lượng tử nhỏ”. Thư đánh giá vật lý 125, 150504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.150504

[40] Sergey Bravyi, Graeme Smith và John A. Smolin. “Kinh doanh tài nguyên tính toán cổ điển và lượng tử”. Đánh giá vật lý X 6 (2016).
https: / / doi.org/ 10.1103 / Physrevx.6.021043

[41] Martijn Swenne. “Giải SAT trên máy tính lượng tử ồn ào”. https://​/​theses.liacs.nl/​1725 (2019). Luận án cử nhân.
https://​/​theses.liacs.nl/​1725

[42] Theodore J Yoder, Quang Hào Low và Isaac L Chuang. “Tìm kiếm lượng tử điểm cố định với số lượng truy vấn tối ưu”. Thư đánh giá vật lý 113 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.210501

[43] Alessandro Cosentino, Robin Kothari và Adam Paetznick. “Khử lượng tử các công thức lượng tử đọc một lần”. Trong Hội nghị lần thứ 8 về Lý thuyết tính toán lượng tử, truyền thông và mật mã (TQC 2013). Tập 22 của Kỷ yếu Tin học Quốc tế Leibniz (LIPIcs), trang 80–92. Dagstuhl, Đức (2013). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2013.80

[44] 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 NC1”. Tạp chí Khoa học Hệ thống và Máy tính 38, 150–164 (1989).
https:/​/​doi.org/​10.1016/​0022-0000(89)90037-8

Trích dẫn

[1] Casper Gurik, Chris Cade và Vedran Dunjko, “Hướng tới lợi thế lượng tử thông qua phân tích dữ liệu tôpô”, arXiv: 2005.02607, (2020).

[2] Kyle EC Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield và Eleanor Rieffel, “Lập trình ràng buộc tăng tốc lượng tử”, Lượng tử 5, 550 (2021).

[3] Casper Gurik, Chris Cade và Vedran Dunjko, “Hướng tới lợi thế lượng tử thông qua phân tích dữ liệu tôpô”, Lượng tử 6, 855 (2022).

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 / 03-25 02:02:00). 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 2023 / 03-25 02:01:59).

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ử