Độ phức tạp của truy vấn lượng tử được cải thiện trên đầu vào dễ dàng hơn

Độ phức tạp của truy vấn lượng tử được cải thiện trên đầu vào dễ dàng hơn

Dấu thời gian: Ngày 8 tháng 2024 năm 11 29:XNUMX sáng

Noel T. Anderson1, Jay U Chung1, Shelby Kimmel1, Da Yeon Koh2, và Tiêu Hàn Diệp1,3

1Cao đẳng Middlebury, Middlebury, VT, Hoa Kỳ
2Đại học Williams, Williamstown, MA, Hoa Kỳ
3Đại học Brown, Providence, RI, Hoa Kỳ

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

Các thuật toán của chương trình khoảng lượng tử để đánh giá hàm đôi khi đã giảm độ phức tạp của truy vấn khi được hứa rằng đầu vào có cấu trúc nhất định. Chúng tôi thiết kế một thuật toán chương trình span đã sửa đổi để cho thấy những cải tiến này vẫn tồn tại ngay cả khi không có lời hứa trước và chúng tôi mở rộng cách tiếp cận này sang vấn đề tổng quát hơn về chuyển đổi trạng thái. Với tư cách là một ứng dụng, chúng tôi chứng minh lợi thế lượng tử theo cấp số nhân và siêu đa thức về độ phức tạp truy vấn trung bình cho một số vấn đề tìm kiếm, khái quát hóa Tìm kiếm với Lời khuyên của Montanaro [Montanaro, TQC 2010].

Cải thiện độ phức tạp của truy vấn lượng tử trên đầu vào dễ dàng hơn Thông tin dữ liệu PlatoBlockchain. Tìm kiếm dọc. Ái.

Hình ảnh nổi bật: Cây quyết định được sử dụng để tạo một trong các thuật toán của chúng tôi.

Tóm tắt phổ biến

Chúng tôi hy vọng rằng các thuật toán lượng tử, giống như các thuật toán cổ điển, sẽ chạy nhanh hơn trên các đầu vào dễ dàng hơn. Ví dụ: nếu bạn đang tìm kiếm một mục trong danh sách không có thứ tự và có nhiều bản sao của mục đó, chúng tôi cho rằng thuật toán lượng tử sẽ chạy nhanh hơn trong trường hợp này so với khi chỉ có một mục được đánh dấu, ngay cả khi không biết số lượng mục tiêu trước thời hạn. Thật vậy, đối với vấn đề tìm kiếm, người ta đã biết cách đạt được lợi thế như vậy với những đầu vào dễ dàng hơn. Tuy nhiên, việc khái quát hóa ý tưởng này cho các vấn đề ngoài tìm kiếm là một thách thức khi không có cách rõ ràng nào để gắn cờ khi quá trình tính toán đã chạy đủ lâu. Chúng tôi sửa đổi một số khung thuật toán phổ biến trong mô hình truy vấn để tạo ra các cờ cảnh báo cho chúng tôi biết liệu quá trình tính toán đã chạy đủ lâu hay chưa, cho phép chúng tôi kết thúc thuật toán sớm với các dữ liệu đầu vào dễ dàng hơn mà không cần biết trước liệu trường hợp đó là dễ hay khó. Là một ứng dụng, với sự phân bổ cả đầu vào dễ và khó cho một vấn đề, chúng ta có thể phân tích độ phức tạp trung bình của truy vấn. Chúng tôi cho thấy rằng việc phân phối đầu vào nhất định cho các vấn đề tìm kiếm mang lại lợi thế lớn cho truy vấn lượng tử trung bình so với các thuật toán cổ điển.

► Dữ liệu BibTeX

► Tài liệu tham khảo

[1] Andris Ambainis và Ronald de Wolf. Độ phức tạp của truy vấn lượng tử trong trường hợp trung bình. Tạp chí Vật lý A: Toán học và Đại cương, 34(35):6741, 2001. doi:10.1088/​0305-4470/​34/​35/​302.
https:/​/​doi.org/​10.1088/​0305-4470/​34/​35/​302

[2] Dorit Aharonov. Tính toán lượng tử. Đánh giá hàng năm về Vật lý tính toán VI, trang 259–346, 1999. doi:10.1142/​9789812815569_0007.
https: / / doi.org/ 10.1142 / IDIA9789812815569_0007

[3] Michel Boyer, Gilles Brassard, Peter Høyer và Alain Tapp. Giới hạn chặt chẽ về tìm kiếm lượng tử. Fortschritte der Physik, 46(4-5):493–505, 1998. doi:10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2 -P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[4] Aleksandr Belovs. Chương trình mở rộng cho các hàm có chứng chỉ 1 có kích thước không đổi: Bản tóm tắt mở rộng. Trong Kỷ yếu của Hội nghị chuyên đề ACM thường niên lần thứ 12 về Lý thuyết máy tính, STOC '77, trang 84–2012, 10.1145. doi:2213977.2213985/​XNUMX.
https: / / doi.org/ 10.1145 / 2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca và Alain Tapp. Khuếch đại và ước tính biên độ lượng tử. Trong tính toán và thông tin lượng tử, tập 305 của Contemp. Toán., trang 53–74. Amer. Toán học. Soc., Providence, RI, 2002. doi:10.1090/​conm/​305/​05215.
https: / / doi.org/ 10.1090 / conm / 305/05215

[6] Gilles Brassard, Peter Hoyer và Alain Tapp. Đếm lượng tử. Trong Automata, Ngôn ngữ và Lập trình, trang 820–831, 1998. doi:10.1007/​BFb0055105.
https: / / doi.org/ 10.1007 / BFb0055105

[7] Aleksandrs Belovs và Ben W. Reichardt. Các chương trình nhịp và thuật toán lượng tử để phát hiện kết nối st và móng vuốt. Bài giảng Khoa học Máy tính, 7501 LNCS:193–204, 2012. doi:10.1007/​978-3-642-33090-2_18.
https:/​/​doi.org/​10.1007/​978-3-642-33090-2_18

[8] Aleksandrs Belovs và Ansis Rosmanis. Giới hạn dưới lượng tử chặt chẽ để tính gần đúng với các trạng thái lượng tử. 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] Salman Beigi và Leila Taghavi. Tăng tốc lượng tử dựa trên cây quyết định cổ điển. Lượng tử, 4:241, 2020. doi:10.22331/​q-2020-03-02-241.
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

[10] Aleksandrs Belovs và Duyal Yolcu. Tấm vé một chiều đến Las Vegas và kẻ thù lượng tử. 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] Richard. Cleve, Artur. Ekert, Chiara Macchiavello và Michele Mosca. Các thuật toán lượng tử được xem xét lại. Kỷ yếu của Hiệp hội Hoàng gia Luân Đôn. Series A: Khoa học Toán học, Vật lý và Kỹ thuật, 454(1969):339–354, 1998. doi:10.1098/​rspa.1998.0164.
https: / / doi.org/ 10.1098 / rspa.1998.0164

[12] Arjan Cornelissen, Stacey Jeffery, Maris Ozols và Alvaro Piedrafita. Chương trình mở rộng và độ phức tạp thời gian lượng tử. Trong Hội nghị chuyên đề quốc tế lần thứ 45 về cơ sở toán học của khoa học máy tính (MFCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. doi:10.4230/​LIPIcs.MFCS.2020.26.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2020.26

[13] Chris Cade, Ashley Montanaro và Aleksandrs Belovs. Các thuật toán lượng tử hiệu quả về thời gian và không gian để phát hiện các chu kỳ và kiểm tra tính lưỡng cực. Thông tin & Tính toán Lượng tử, 18(1-2):18–50, 2018.

[14] Kai DeLorenzo, Shelby Kimmel và R. Teal Witter. Các ứng dụng của Thuật toán lượng tử cho kết nối st. Trong Hội nghị lần thứ 14 về Lý thuyết tính toán, truyền thông và mật mã lượng tử (TQC 2019), trang 6:1–6:14, 2019. doi:10.4230/​LIPics.TQC.2019.6.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2019.6

[15] Dmitry Grinko, Julien Gacon, Christa Zoufal và Stefan Woerner. Ước tính biên độ lượng tử lặp. Thông tin lượng tử npj, 7(1):52, tháng 2021 năm 10.1038. doi:41534/​s021-00379-1-XNUMX.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] Yêu K. Grover. Cơ học lượng tử giúp tìm kim trong đống cỏ khô. Thư Đánh giá Vật lý, 79(2):325–328, 1997. doi:10.1103/​PhysRevLett.79.325.
https: / / doi.org/ 10.1103 / PhysRevLett.79.325

[17] Wassily Hoeffding. bất bình đẳng xác suất cho các khoản tiền của các biến ngẫu nhiên bị chặn. Tạp chí của Hiệp hội Thống kê Hoa Kỳ, 58(301):13–30, 1963. doi:10.1080/​01621459.1963.10500830.
https: / / doi.org/ 10.1080 / 01621459.1963.10500830

[18] Tsuyoshi Ito và Stacey Jeffery. Các chương trình khoảng cách gần đúng. Thuật toán, 81(6):2158–2195, 2019. doi:10.1007/​s00453-018-0527-1.
https:/​/​doi.org/​10.1007/​s00453-018-0527-1

[19] Michael Jarret, Stacey Jeffery, Shelby Kimmel và Alvaro Piedrafita. Thuật toán lượng tử cho khả năng kết nối và các vấn đề liên quan. Trong Hội nghị chuyên đề châu Âu thường niên lần thứ 26 về thuật toán (ESA 2018), trang 49:1–49:13, 2018. doi:10.4230/​LIPics.ESA.2018.49.
https://​/​doi.org/​10.4230/​LIPIcs.ESA.2018.49

[20] Alexei Y. Kitaev. Các phép đo lượng tử và bài toán ổn định Abelian. 1995. arXiv:quant-ph/​9511026.
arXiv: quant-ph / 9511026

[21] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek và Mario Szegedy. Độ phức tạp truy vấn lượng tử của chuyển đổi trạng thái. Năm 2011, Hội nghị chuyên đề thường niên lần thứ 52 của IEEE về Cơ sở Khoa học Máy tính, trang 344–353, 2011. doi:10.1109/​FOCS.2011.75.
https: / / doi.org/ 10.1109 / FOCS.2011.75

[22] Frédéric Magniez, Ashwin Nayak, Jérémie Roland và Miklos Santha. Tìm kiếm qua Quantum Walk. Tạp chí Máy tính SIAM, 40(1):142–164, 2011. doi:10.1137/​090745854.
https: / / doi.org/ 10.1137 / 090745854

[23] Ashley Montanaro. Tìm kiếm lượng tử với lời khuyên. Trong Hội thảo về Tính toán lượng tử, Truyền thông và Mật mã, trang 77–93. Springer, 2010. doi:10.1007/​978-3-642-18073-6_7.
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_7

[24] Ben W. Reichardt. Các chương trình mở rộng và độ phức tạp của truy vấn lượng tử: Giới hạn đối thủ chung gần như chặt chẽ đối với mọi hàm boolean. Hội nghị chuyên đề thường niên lần thứ 50 của IEEE về Cơ sở Khoa học Máy tính, trang 544–551, 2009. doi:10.1109/​FOCS.2009.55.
https: / / doi.org/ 10.1109 / FOCS.2009.55

[25] Ben W. Reichardt. Phản ánh cho các thuật toán truy vấn lượng tử. Trong Kỷ yếu của Hội nghị chuyên đề ACM-SIAM thường niên năm 2011 về Thuật toán rời rạc, Kỷ yếu, trang 560–569. 2011. doi:10.1137/​1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44

[26] Leila Taghavi. Thuật toán lượng tử đơn giản hóa cho bài toán nhận dạng tiên tri. Trí tuệ máy lượng tử, 4(2):19, 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

Trích dẫn

[1] Stacey Jeffery, Shelby Kimmel và Alvaro Piedrafita, “Thuật toán lượng tử để lấy mẫu cạnh đường dẫn”, arXiv: 2303.03319, (2023).

[2] Michael Czekanski, Shelby Kimmel và R. Teal Witter, “Thuật toán truy vấn lượng tử đối thủ kép mạnh mẽ và hiệu quả về mặt không gian”, arXiv: 2306.15040, (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 2024 / 04-11 15:45:18). 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 2024 / 04-11 15:45:17).

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ử