Các thuật toán lượng tử được cải thiện cho các phương trình vi phân tuyến tính và phi tuyến tính

Các thuật toán lượng tử được cải thiện cho các phương trình vi phân tuyến tính và phi tuyến tính

Các thuật toán lượng tử được cải tiến cho các phương trình vi phân tuyến tính và phi tuyến PlatoBlockchain Data Intelligence. Tìm kiếm dọc. Ái.

Hari Krovi

Nghiên cứu Riverlane, Cambridge, MA

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 trình bày các thuật toán lượng tử được cải tiến và tổng quát hóa đáng kể so với công việc trước đây cho các phương trình vi phân thông thường tuyến tính và phi tuyến tính không đồng nhất (ODE). Cụ thể, chúng tôi chỉ ra cách định mức của hàm mũ ma trận đặc trưng cho thời gian chạy của các thuật toán lượng tử đối với các ODE tuyến tính, mở ra cơ hội ứng dụng cho một lớp ODE tuyến tính và phi tuyến rộng hơn. Trong Berry và cộng sự, (2017), một thuật toán lượng tử cho một loại ODE tuyến tính nhất định được đưa ra, trong đó ma trận liên quan cần phải chéo hóa được. Thuật toán lượng tử cho các ODE tuyến tính được trình bày ở đây mở rộng cho nhiều loại ma trận không chéo hóa được. Thuật toán ở đây cũng nhanh hơn theo cấp số nhân so với các giới hạn bắt nguồn từ Berry và cộng sự, (2017) đối với một số loại ma trận có thể chéo hóa nhất định. Thuật toán ODE tuyến tính của chúng tôi sau đó được áp dụng cho các phương trình vi phân phi tuyến bằng cách sử dụng tuyến tính hóa Carleman (một cách tiếp cận được chúng tôi thực hiện gần đây trong Liu et al., (2021)). Sự cải thiện so với kết quả đó là gấp đôi. Đầu tiên, chúng tôi có được sự phụ thuộc tốt hơn theo cấp số nhân vào lỗi. Loại phụ thuộc logarit vào sai số này cũng đã được Xue và cộng sự, (2021) đạt được, nhưng chỉ đối với các phương trình phi tuyến thuần nhất. Thứ hai, thuật toán hiện tại có thể xử lý bất kỳ ma trận thưa thớt, khả nghịch nào (mô hình phân tán mô hình đó) nếu nó có log-norm âm (bao gồm cả ma trận không chéo hóa được), trong khi Liu và cộng sự, (2021) và Xue và cộng sự, (2021) ) cũng yêu cầu tính quy tắc.

Các phương trình vi phân là một phần quan trọng của nhiều mô hình vật lý từ vật lý năng lượng cao đến động lực học chất lỏng và vật lý plasma. Có một số thuật toán lượng tử giải phương trình vi phân bằng cách tạo ra trạng thái lượng tử tỷ lệ với nghiệm. Tuy nhiên, các thuật toán lượng tử này chỉ áp dụng được cho một số loại phương trình vi phân nhất định. Cụ thể, đối với các ODE tuyến tính, chúng áp đặt các điều kiện như tính quy tắc hoặc khả năng chéo hóa trên ma trận $A$ mã hóa ODE tuyến tính. Công trình này phát triển các thuật toán lượng tử có thể được áp dụng cho một lớp phương trình vi phân thường tuyến tính và phi tuyến tính lớn hơn đáng kể. Chúng tôi loại bỏ điều kiện về khả năng chéo hóa và thay thế nó bằng điều kiện đã được nghiên cứu trong lý thuyết về tính ổn định của phương trình vi phân, cụ thể là chuẩn của hàm mũ của ma trận $A$. Điều này sau đó có thể được sử dụng để đưa ra một thuật toán lượng tử cũng áp dụng cho lớp phương trình vi phân phi tuyến lớn hơn.

► Dữ liệu BibTeX

► Tài liệu tham khảo

[1] DW Berry, AM Childs, A. Ostrander, và G. Wang, “Thuật toán lượng tử cho các phương trình vi phân tuyến tính với sự phụ thuộc được cải thiện theo cấp số nhân vào độ chính xác,” Communications in Mathematical Physics, tập. 356, không. 3, trang 1057–1081, 2017. https://​/​doi.org/​10.1007/​s00220-017-3002-y.
https: / / doi.org/ 10.1007 / s00220-017-3002-y

[2] J.-P. Liu, H. Ø. Kolden, HK Krovi, NF Loureiro, K. Trivisa, và AM Childs, “Thuật toán lượng tử hiệu quả cho các phương trình vi phân phi tuyến tiêu tan,” Kỷ yếu của Viện Hàn lâm Khoa học Quốc gia, tập. 118, không. 35, 2021. https://​/​doi.org/​10.1073/​pnas.2026805118.
https: / / doi.org/ 10.1073 / pnas.2026805118

[3] C. Xue, Y.-C. Wu, và G.-P. Guo, “Phương pháp nhiễu loạn homotopy lượng tử cho các phương trình vi phân thường tiêu tán phi tuyến,” Tạp chí Vật lý Mới, tập. 23, tr. 123035, tháng 2021 năm 10.1088. https://​/​doi.org/​1367/​2630-3/​acXNUMXeff.
https://​/​doi.org/​10.1088/​1367-2630/​ac3eff

[4] S. Lloyd, “Mô phỏng lượng tử phổ quát,” Khoa học, tập. 273, không. 5278, trang 1073–1078, 1996. https://​/​doi.org/​10.1126/​science.273.5278.1073.
https: / / doi.org/ 10.1126 / khoa học.273.5278.1073

[5] DW Berry, G. Ahokas, R. Cleve và BC Sanders, “Các thuật toán lượng tử hiệu quả để mô phỏng những người Hamilton thưa thớt,” Communications in Mathematical Physics, tập. 270, tr. 359–371, 2007. https://​/​doi.org/​10.1007/​s00220-006-0150-x.
https: / / doi.org/ 10.1007 / s00220-006-0150-x

[6] GH Low và IL Chuang, “Mô phỏng hamiltonian tối ưu bằng xử lý tín hiệu lượng tử,” Phys. Mục sư Lett., tập. 118, tr. 010501, tháng 2017 năm 10.1103. https://​/​doi.org/​118.010501/​PhysRevLett.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[7] GH Low và IL Chuang, “Mô phỏng Hamilton bằng Qubitization,” Quantum, vol. 3, tr. 163, tháng 2019 năm 10.22331. https://​/​doi.org/​2019/​q-07-12-163-XNUMX.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163

[8] S. Chakraborty, A. Gilyén và S. Jeffery, “Sức mạnh của ma trận mã hóa khối: Các kỹ thuật hồi quy được cải thiện thông qua mô phỏng Hamilton nhanh hơn,” trong Hội thảo quốc tế lần thứ 46 về Automata, Ngôn ngữ và Lập trình (ICALP 2019) (C. Baier, I. Chatzigiannakis, P. Flocchini, và S. Leonardi, chủ biên), tập. 132 của Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Đức), trang 33:1–33:14, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. https://​/​doi.org/​10.4230 /​LIPIcs.ICALP.2019.33.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.33

[9] J. van Apeldoorn, A. Gilyén, S. Gribling và R. de Wolf, “Bộ giải SDP lượng tử: Giới hạn trên và dưới tốt hơn,” Lượng tử, tập. 4, tr. 230, tháng 2020 năm 10.22331. https://​/​doi.org/​2020/​q-02-14-230-XNUMX.
https:/​/​doi.org/​10.22331/​q-2020-02-14-230

[10] A. Gilyén, Y. Su, GH Low và N. Wiebe, “Biến đổi giá trị đơn lẻ lượng tử và hơn thế nữa: Cải tiến theo hàm mũ cho số học ma trận lượng tử,” 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 điện toán, STOC 2019, ( New York, NY, Mỹ), tr. 193–204, Hiệp hội Máy tính, 2019. https://​/​doi.org/​10.1145/​3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366

[11] AW Harrow, A. Hassidim, và S. Lloyd, “Thuật toán lượng tử cho các hệ phương trình tuyến tính,” Physical Review Letters, tập. 103, không. 15, tr. 150502, 2009. https://​/​doi.org/​10.1103/​PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[12] DW Berry, “Thuật toán lượng tử bậc cao để giải các phương trình vi phân tuyến tính,” Tạp chí Vật lý A: Toán học và Lý thuyết, tập. 47, không. 10, tr. 105301, 2014. https://​/​doi.org/​10.1088/​1751-8113/​47/​10/​105301.
https:/​/​doi.org/​10.1088/​1751-8113/​47/​10/​105301

[13] AM Childs, J.-P. Liu, và A. Ostrander, “Các thuật toán lượng tử có độ chính xác cao cho các phương trình vi phân từng phần,” Quantum, vol. 5, tr. 574, tháng 2021 năm 10.22331. https://​/​doi.org/​2021/​q-11-10-574-XNUMX.
https:/​/​doi.org/​10.22331/​q-2021-11-10-574

[14] AM Childs và J.-P. Liu, “Các phương pháp quang phổ lượng tử cho các phương trình vi phân,” Communications in Mathematical Physics, vol. 375, trang 1427–1457, 2020. https://​/​doi.org/​10.1007/​s00220-020-03699-z.
https: / / doi.org/ 10.1007 / s00220-020-03699-z

[15] S. Lloyd, G. De Palma, C. Gokler, B. Kiani, Z.-W. Liu, M. Marvian, F. Tennie và T. Palmer, “Thuật toán lượng tử cho phương trình vi phân phi tuyến,” năm 2020. https://​/​doi.org/​10.48550/​arXiv.2011.06571.
https: / / doi.org/ 10.48550 / arXiv.2011.06571

[16] A. Ambainis, “Các thuật toán lượng tử và khuếch đại biên độ thời gian thay đổi cho các bài toán đại số tuyến tính,” trong Hội nghị chuyên đề quốc tế lần thứ 29 về các khía cạnh lý thuyết của khoa học máy tính (STACS 2012) (C. Dürr và T. Wilke, eds.), tập. 14 của Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Đức), trang 636–647, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012. https://​/​doi.org/​10.4230/​LIPIcs. STACS.2012.636.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2012.636

[17] AM Childs, R. Kothari, và RD 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 được cải thiện theo cấp số nhân vào độ chính xác,” Tạp chí SIAM về Điện toán, tập. 46, không. 6, tr. 1920–1950, 2017. https://​/​doi.org/​10.1137/​16M1087072.
https: / / doi.org/ 10.1137 / 16M1087072

[18] Y. Subasi, RD Somma và D. Orsucci, “Các thuật toán lượng tử cho các hệ phương trình tuyến tính lấy cảm hứng từ điện toán lượng tử đoạn nhiệt,” Phys. Mục sư Lett., tập. 122, tr. 060504, ngày 2 năm 2019. https://​/​doi.org/​10.1103/​PhysRevLett.122.060504.
https: / / doi.org/ 10.1103 / PhysRevLett.122.060504

[19] D. An và L. Lin, “Bộ giải hệ thống tuyến tính lượng tử dựa trên tính toán lượng tử đoạn nhiệt tối ưu theo thời gian và thuật toán tối ưu hóa gần đúng lượng tử,” Giao dịch ACM trên Điện toán lượng tử, tập. 3, 3 2022. https://​/​doi.org/​10.1145/​3498331.
https: / / doi.org/ 10.1145 / 3498331

[20] L. Lin và Y. Tong, “Lọc trạng thái riêng lượng tử dựa trên đa thức tối ưu với ứng dụng để giải các hệ tuyến tính lượng tử,” Quantum, tập. 4, tr. 361, ngày 11 năm 2020. https://​/​doi.org/​10.22331/​q-2020-11-11-361.
https:/​/​doi.org/​10.22331/​q-2020-11-11-361

[21] PC Costa, D. An, YR Sanders, Y. Su, R. Babbush, và DW Berry, “Bộ giải hệ thống tuyến tính lượng tử chia tỷ lệ tối ưu thông qua định lý đoạn nhiệt rời rạc,” PRX Quantum, tập. 3, tr. 040303, tháng 2022 năm 10.1103. https://​/​doi.org/​3.040303/​PRXQuantum.XNUMX.
https: / / doi.org/ 10.1103 / PRXQuantum.3.040303

[22] SK Leyton và TJ Osborne, “Thuật toán lượng tử để giải các phương trình vi phân phi tuyến,” 2008. https://​/​doi.org/​10.48550/​arXiv.0812.4423.
https: / / doi.org/ 10.48550 / arXiv.0812.4423

[23] A. Engel, G. Smith, và SE Parker, “Thuật toán lượng tử cho phương trình Vlasov,” Tạp chí Vật lý A, tập. 100, không. 6, tr. 062315, 2019. https://​/​doi.org/​10.1103/​PhysRevA.100.062315.
https: / / doi.org/ 10.1103 / PhysRevA.100.062315

[24] IY Dodin và EA Startsev, “Về các ứng dụng của điện toán lượng tử cho các mô phỏng plasma,” Vật lý của Plasmas, tập. 28, không. 9, tr. 092101, 2021. https://​/​doi.org/​10.1063/​5.0056974.
https: / / doi.org/ 10.1063 / 5.0056974

[25] A. Engel, G. Smith, và SE Parker, “Sự nhúng tuyến tính của các hệ động lực phi tuyến và triển vọng cho các thuật toán lượng tử hiệu quả,” Vật lý của Plasmas, tập. 28, không. 6, tr. 062305, 2021. https://​/​doi.org/​10.1063/​5.0040313.
https: / / doi.org/ 10.1063 / 5.0040313

[26] I. Joseph, “Cách tiếp cận Koopman–von neumann đối với mô phỏng lượng tử của động lực học cổ điển phi tuyến,” Phys. Mục sư Res., tập. 2, tr. 043102, tháng 2020 năm 10.1103. https://​/​doi.org/​2.043102/​PhysRevResearch.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevResearch.2.043102

[27] I. Novikau, EA Startsev và IY Dodin, “Xử lý tín hiệu lượng tử để mô phỏng sóng plasma lạnh,” Phys. Mục sư A, tập. 105, tr. 062444, tháng 2022 năm 10.1103. https://​/​doi.org/​105.062444/​PhysRevA.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevA.105.062444

[28] J. Hubisz, B. Sambasivam, và J. Unmuth-Yockey, “Các thuật toán lượng tử cho lý thuyết trường mạng tinh thể mở,” Tạp chí Vật lý A, tập. 104, 11 2021. https://​/​doi.org/​10.1103/​physreva.104.052420.
https: / / doi.org/ 10.1103 / Physreva.104.052420

[29] D. An, D. Fang, S. Jordan, J.-P. Liu, GH Low và J. Wang, “Thuật toán lượng tử hiệu quả cho phương trình khuếch tán phản ứng phi tuyến tính và ước tính năng lượng,” năm 2022. https://​/​doi.org/​10.48550/​arXiv.2205.01141.
https: / / doi.org/ 10.48550 / arXiv.2205.01141

[30] D. Fang, L. Lin và Y. Tong, “Các bộ giải lượng tử dựa trên thời gian cho các phương trình vi phân tuyến tính phụ thuộc thời gian,” 2022. https://​/​doi.org/​10.48550/​arXiv.2208.06941.
https: / / doi.org/ 10.48550 / arXiv.2208.06941

[31] DW Berry, AM Childs, Y. Su, X. Wang và N. Wiebe, “Mô phỏng Hamilton phụ thuộc vào thời gian với tỷ lệ $L^1$-norm,” Quantum, tập. 4, tr. 254, tháng 2020 năm 10.22331. https://​/​doi.org/​2020/​q-04-20-254-XNUMX.
https:/​/​doi.org/​10.22331/​q-2020-04-20-254

[32] D. An, J.-P. Liu, D. Wang và Q. Zhao, “Lý thuyết về bộ giải phương trình vi phân lượng tử: giới hạn và chuyển tiếp nhanh,” năm 2022. https://​/​doi.org/​10.48550/​ARXIV.2211.05246.
https: / / doi.org/ 10.48550 / ARXIV.2211.05246

[33] W. Coppel, Tính ổn định và Hành vi tiệm cận của các phương trình vi phân. Heath chuyên khảo toán học, Heath, 1965.

[34] CF Vân Loan, “Một nghiên cứu về hàm mũ ma trận,” tech. rep., Đại học Manchester, 2006.

[35] GG Dahlquist, “Một bài toán ổn định đặc biệt cho các phương pháp nhiều bước tuyến tính,” BIT Numerical Mathematics, tập. 3, tr. 27–43, tháng 1963 năm 10.1007. https://​/​doi.org/​01963532/​BFXNUMX.
https: / / doi.org/ 10.1007 / BF01963532

[36] L. Trefethen, M. Embree, và M. Embree, Spectra và Pseudospectra: Hành vi của ma trận và toán tử không bình thường. Nhà xuất bản Đại học Princeton, 2005. https://​/​doi.org/​10.2307/​j.ctvzxx9kj.
https://​/​doi.org/​10.2307/​j.ctvzxx9kj

[37] R. Bhatia, Phân tích ma trận. Văn bản sau đại học về Toán học, Springer New York, 1996. https://​/​doi.org/​10.1007/​978-1-4612-0653-8.
https:/​/​doi.org/​10.1007/​978-1-4612-0653-8

[38] NF Loureiro, W. Dorland, L. Fazendeiro, A. Kanekar, A. Mallet, MS Vilelas, và A. Zocco, “Viriato: Mã quang phổ Fourier–Hermite cho động lực học plasma động học chất lỏng bị từ hóa mạnh,” Truyền thông Vật lý Máy tính, tập 206, tr. 45–63, 2016. https://​/​doi.org/​10.1016/​j.cpc.2016.05.004.
https: / / doi.org/ 10.1016 / j.cpc.2016.05.004

[39] RA Bertlmann, W. Grimus, và BC Hiesmayr, “Công thức hệ thống lượng tử mở của sự phân rã hạt,” Phys. Mục sư A, tập. 73, tr. 054101, tháng 2006 năm 10.1103. https://​/​doi.org/​73.054101/​PhysRevA.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevA.73.054101

[40] B. Kågström, “Các giới hạn và giới hạn nhiễu loạn cho hàm mũ ma trận,” BIT Numerical Mathematics, tập. 17, tr. 39–57, tháng 1977 năm 10.1007. https://​/​doi.org/​01932398/​BFXNUMX.
https: / / doi.org/ 10.1007 / BF01932398

[41] L. Elsner và M. Paardekooper, “Về độ đo tính không chuẩn hóa của ma trận,” Đại số tuyến tính và các ứng dụng của nó, tập. 92, trang 107–123, 1987. https://​/​doi.org/​10.1016/​0024-3795(87)90253-9.
https:/​/​doi.org/​10.1016/​0024-3795(87)90253-9

[42] N. Higham, Chức năng của ma trận: Lý thuyết và tính toán. Các tiêu đề khác trong Toán học Ứng dụng, Hiệp hội Toán học Công nghiệp và Ứng dụng (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104), 2008. https://​/​doi.org/​10.1137/​1.9780898717778.
https: / / doi.org/ 10.1137 / 1.9780898717778

[43] E. Hairer, S. Nørsett, và G. Wanner, Giải các phương trình vi phân thông thường I: Các bài toán không cứng. Springer Series in Computational Mathematics, Springer Berlin Heidelberg, 2008. https://​/​doi.org/​10.1007/​978-3-540-78862-1.
https:/​/​doi.org/​10.1007/​978-3-540-78862-1

[44] MM Gilles Brassard, Peter Høyer và A. Tapp, “Ước tính và khuếch đại biên độ lượng tử,” trong Tính toán và Thông tin Lượng tử (J. Samuel J. Lomonaco và HE Brandt, eds.), tập. 305, trang 53–74, Toán học đương đại, 2002. https://​/​doi.org/​10.1090/​conm/​305/​05215.
https: / / doi.org/ 10.1090 / conm / 305/05215

Trích dẫn

[1] Cheng Xue, Xiao-Fan Xu, Yu-Chun Wu và Guo-Ping Guo, “Thuật toán lượng tử để giải hệ phương trình phi tuyến bậc hai”, Đánh giá vật lý A 106 3, 032427 (2022).

[2] Dong An, Di Fang, Stephen Jordan, Jin-Peng Liu, Guang Hao Low, and Jiasu Wang, “Thuật toán lượng tử hiệu quả cho các phương trình khuếch tán phản ứng phi tuyến tính và ước tính năng lượng”, arXiv: 2205.01141, (2022).

[3] Dominic W. Berry và Pedro CS Costa, “Thuật toán lượng tử cho phương trình vi phân phụ thuộc thời gian sử dụng chuỗi Dyson”, arXiv: 2212.03544, (2022).

[4] Koichi Miyamoto và Hiroshi Ueda, “Trích xuất một hàm được mã hóa theo biên độ của trạng thái lượng tử bằng mạng tensor và mở rộng hàm trực giao”, arXiv: 2208.14623, (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 / 02-03 04:56:43). 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 / 02-03 04:56:41).

Dấu thời gian:

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