Về mã hóa khối lượng tử hiệu quả của các toán tử giả vi phân

Về mã hóa khối lượng tử hiệu quả của các toán tử giả vi phân

Dấu thời gian: ngày 2 tháng 2023 năm 8 45:XNUMX sáng
Nút nguồn: 2694594

Lý Hạo Nha1, Hồng Khang Ni2và Lexing Ying1,2

1Khoa Toán, Đại học Stanford, Stanford, CA 94305
2Viện Kỹ thuật Toán học và Tính toán, Đại học Stanford, Stanford, CA 94305

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ã hóa khối nằm ở cốt lõi của nhiều thuật toán lượng tử hiện có. Trong khi đó, mã hóa khối rõ ràng và hiệu quả của các toán tử dày đặc thường được thừa nhận là một vấn đề đầy thách thức. Bài viết này trình bày một nghiên cứu toàn diện về mã hóa khối của một họ phong phú các toán tử dày đặc: các toán tử giả vi phân (PDO). Đầu tiên, một sơ đồ mã hóa khối cho các PDO chung được phát triển. Sau đó, chúng tôi đề xuất một sơ đồ hiệu quả hơn cho PDO với cấu trúc có thể tách rời. Cuối cùng, chúng tôi chứng minh một thuật toán mã hóa khối rõ ràng và hiệu quả cho các PDO với cấu trúc có thể tách rời hoàn toàn theo kích thước. Phân tích độ phức tạp được cung cấp cho tất cả các thuật toán mã hóa khối được trình bày. Việc áp dụng các kết quả lý thuyết được minh họa bằng các ví dụ đã làm việc, bao gồm biểu diễn toán tử elliptic có hệ số biến thiên và tính toán nghịch đảo của toán tử elliptic mà không cần gọi thuật toán hệ thống tuyến tính lượng tử (QLSA).

Tóm tắt phổ biến

Mã hóa khối nằm ở cốt lõi của nhiều thuật toán lượng tử hiện có. Trong khi đó, mã hóa khối rõ ràng và hiệu quả của các toán tử dày đặc thường được thừa nhận là một vấn đề đầy thách thức. Bài viết này trình bày một nghiên cứu toàn diện về mã hóa khối của một họ phong phú các toán tử dày đặc: các toán tử giả vi phân (PDO). Chúng tôi phát triển các sơ đồ mã hóa khối mới cho ba loại PDO với các cấu trúc khác nhau. Ngoài việc phân tích độ phức tạp kỹ lưỡng, chúng tôi cung cấp các ví dụ rõ ràng trong đó các PDO khác nhau được biểu diễn bằng các lược đồ mã hóa khối được đề xuất.

► Dữ liệu BibTeX

► Tài liệu tham khảo

[1] D. An và L. Lin. Bộ giải hệ thống tuyến tính lượng tử dựa trên điện 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 máy tính lượng tử, 3: 1–28, 2022. 10.1145/​3498331.
https: / / doi.org/ 10.1145 / 3498331

[2] DW Berry, AM Childs, R. Cleve, R. Kothari và RD Somma. Mô phỏng động lực học Hamilton với chuỗi taylor cắt ngắn. Thư đánh giá vật lý, 114: 090502, 2015. 10.1103/​PhysRevLett.114.090502.
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502

[3] G. Beylkin và L. Monzon. Về xấp xỉ của các chức năng bằng cách tính tổng theo cấp số nhân. Phân tích sóng hài ứng dụng và tính toán, 19: 17–48, 2005. 10.1016/​j.acha.2005.01.003.
https: / / doi.org/ 10.1016 / j.acha.2005.01.003

[4] D. Camps và R. Van Beeumen. Truyện ngụ ngôn: Các mạch lượng tử gần đúng nhanh để mã hóa khối. Vào năm 2022, Hội nghị Quốc tế IEEE về Máy tính và Kỹ thuật Lượng tử (QCE), trang 104–113. IEEE, 2022. 10.1109/​QCE53715.2022.00029.
https: / / doi.org/ 10.1109 / QCE53715.2022.00029

[5] D. Camps, L. Lin, R. Van Beeumen, và C. Yang. Mạch lượng tử rõ ràng cho mã hóa khối của ma trận thưa thớt nhất định. bản in trước arXiv arXiv:2203.10236, 2022. 10.48550/​arXiv.2203.10236.
https: / / doi.org/ 10.48550 / arXiv.2203.10236
arXiv: 2203.10236

[6] Y. Cao, A. Papageorgiou, I. Petras, J. Traub, và S. Kais. Thuật toán lượng tử và thiết kế mạch giải phương trình poisson. Tạp chí Vật lý mới, 15(1): 013021, 2013. 10.1088/​1367-2630/​15/​1/​013021.
https:/​/​doi.org/​10.1088/​1367-2630/​15/​1/​013021

[7] G. Castelazo, QT Nguyen, G. De Palma, D. Englund, S. Lloyd, và BT Kiani. Các thuật toán lượng tử cho tích chập nhóm, tương quan chéo và biến đổi tương đương. Đánh giá Vật lý A, 106: 032402, 2022. 10.1103/​PhysRevA.106.032402.
https: / / doi.org/ 10.1103 / PhysRevA.106.032402

[8] R. Chao, D. Ding, A. Gilyen, C. Huang và M. Szegedy. Tìm góc xử lý tín hiệu lượng tử với độ chính xác của máy. bản in trước arXiv arXiv:2003.02831, 2020. 10.48550/​arXiv.2003.02831.
https: / / doi.org/ 10.48550 / arXiv.2003.02831
arXiv: 2003.02831

[9] 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, 46: 1920–1950, 2017. 10.1137/​16M1087072.
https: / / doi.org/ 10.1137 / 16M1087072

[10] AM Childs, J.-P. Liu và A. Ostrander. Thuật toán lượng tử độ chính xác cao cho phương trình đạo hàm riêng. Lượng tử, 5: 574, 2021. 10.22331/​q-2021-11-10-574.
https:/​/​doi.org/​10.22331/​q-2021-11-10-574

[11] D. Thợ đồng. Một biến đổi phạm vi gần đúng hữu ích trong bao thanh toán lượng tử. arXiv bản in trước quant-ph/​0201067, 2002. 10.48550/​arXiv.quant-ph/​0201067.
https: / / doi.org/ 10.48550 / arXiv.quant-ph / 0201067
arXiv: quant-ph / 0201067

[12] PC Costa, S. Jordan và A. Ostrander. Thuật toán lượng tử để mô phỏng phương trình sóng. Đánh giá Vật lý A, 99: 012323, 2019. 10.1103/​PhysRevA.99.012323.
https: / / doi.org/ 10.1103 / PhysRevA.99.012323

[13] 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, 3: 040303, 2022. 10.1103/​PRXQuantum.3.040303.
https: / / doi.org/ 10.1103 / PRXQuantum.3.040303

[14] AJ da Silva và DK Park. Các mạch lượng tử có độ sâu tuyến tính cho các cổng được điều khiển đa qubit. Đánh giá Vật lý A, 106: 042602, 2022. 10.1103/​PhysRevA.106.042602.
https: / / doi.org/ 10.1103 / PhysRevA.106.042602

[15] L. Demanet và L. Ying. Phép tính ký hiệu rời rạc. Đánh giá SIAM, 53: 71–104, 2011. 10.1137/​080731311.
https: / / doi.org/ 10.1137 / 080731311

[16] Y. Dong, X. Meng, KB Whaley và L. Lin. Đánh giá hệ số pha hiệu quả trong xử lý tín hiệu lượng tử. Đánh giá Vật lý A, 103: 042419, 2021. 10.1103/​PhysRevA.103.042419.
https: / / doi.org/ 10.1103 / PhysRevA.103.042419

[17] Y. Dong, L. Lin, H. Ni và J. Wang. Xử lý tín hiệu lượng tử vô hạn. bản in trước arXiv arXiv:2209.10162, 2022. 10.48550/​arXiv.2209.10162.
https: / / doi.org/ 10.48550 / arXiv.2209.10162
arXiv: 2209.10162

[18] A. Gilyén, Y. Su, GH Low, và N. 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ử. 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, 2019. 10.1145/​3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366

[19] L. Grover và T. 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 bản in trước quant-ph/​0208112, 2002. 10.48550/​arXiv.quant-ph/​0208112.
https: / / doi.org/ 10.48550 / arXiv.quant-ph / 0208112
arXiv: quant-ph / 0208112

[20] J. ha hả. Phân tích sản phẩm của các hàm tuần hoàn trong xử lý tín hiệu lượng tử. Lượng tử, 3: 190, 2019. 10.22331/​q-2019-10-07-190.
https:/​/​doi.org/​10.22331/​q-2019-10-07-190

[21] AW Harrow, A. Hassidim và S. Lloyd. Thuật toán lượng tử cho hệ phương trình tuyến tính. Thư đánh giá vật lý, 103: 150502, 2009. 10.1103/​PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[22] AY Kitaev. Tính toán lượng tử: thuật toán và sửa lỗi. Khảo sát Toán học Nga, 52: 1191, 1997. 10.1070/​RM1997v052n06ABEH002155.
https:/​/​doi.org/​10.1070/​RM1997v052n06ABEH002155

[23] AY Kitaev, A. Shen, MN Vyalyi và MN Vyalyi. Tính toán cổ điển và lượng tử. Hiệp hội Toán học Hoa Kỳ, 2002. 10.1090/​gsm/​047.
https: / / doi.org/ 10.1090 / gsm / 047

[24] 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ử. Lượng tử, 4: 361, 2020. 10.22331/​q-2020-11-11-361.
https:/​/​doi.org/​10.22331/​q-2020-11-11-361

[25] GH Low và IL Chuang. Mô phỏng Hamilton tối ưu bằng xử lý tín hiệu lượng tử. Thư đánh giá vật lý, 118: 010501, 2017. 10.1103/​PhysRevLett.118.010501.
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[26] A. Mahasinghe và J. Wang. Mạch lượng tử hiệu quả cho ma trận toeplitz và hankel. Tạp chí Vật lý A: Toán học và Lý thuyết, 49: 275301, 2016. 10.1088/​1751-8113/​49/​27/​275301.
https:/​/​doi.org/​10.1088/​1751-8113/​49/​27/​275301

[27] S. McArdle, A. Gilyén và M. Berta. Chuẩn bị trạng thái lượng tử mà không cần số học mạch lạc. bản in trước arXiv arXiv:2210.14892, 2022. 10.48550/​arXiv.2210.14892.
https: / / doi.org/ 10.48550 / arXiv.2210.14892
arXiv: 2210.14892

[28] A. Montanaro và S. Pallister. Thuật toán lượng tử và phương pháp phần tử hữu hạn. Đánh giá Vật lý A, 93: 032324, 2016. 10.1103/​PhysRevA.93.032324.
https: / / doi.org/ 10.1103 / PhysRevA.93.032324

[29] Y. Nam, Y. Su và D. Maslov. Biến đổi phạm vi lượng tử gần đúng với các cổng o (n log (n)) t. Thông tin Lượng tử NPJ, 6: 26, 2020. 10.1038/​s41534-020-0257-5.
https:/​/​doi.org/​10.1038/​s41534-020-0257-5

[30] QT Nguyễn, BT Kiani, và S. Lloyd. Thuật toán lượng tử cho các hạt nhân dày đặc và hạng đầy đủ sử dụng ma trận phân cấp. Lượng tử, 6: 876, 2022. 10.22331/​q-2022-12-13-876.
https:/​/​doi.org/​10.22331/​q-2022-12-13-876

[31] MA Nielsen và I. 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. 10.1119/​1.1463744.
https: / / doi.org/ 10.1119 / 1.1463744

[32] EG Rieffel và WH Polak. Điện toán lượng tử: Giới thiệu nhẹ nhàng. MIT Press, 2011. 10.1063/​PT.3.1442.
https: / / doi.org/ 10.1063 / PT.3.1442

[33] S. Sachdeva, NK Vishnoi, et al. Các thuật toán nhanh hơn thông qua lý thuyết xấp xỉ. Cơ sở và Xu hướng trong Khoa học Máy tính Lý thuyết, 9: 125–210, 2014. 10.1561/​0400000065.
https: / / doi.org/ 10.1561 / 0400000065

[34] EM Stein và TS Murphy. Phân tích điều hòa: phương pháp biến thực, tính trực giao và tích phân dao động, tập 3. Nhà xuất bản Đại học Princeton, 1993. ISBN 9780691032160. URL https://​/​press.princeton.edu/​books/​bìa cứng/​9780691032160/​harmonic -analysis-pms-43-volume-43.
https://​/​press.princeton.edu/​books/​bìa cứng/​9780691032160/​harmonic-analysis-pms-43-volume-43

[35] Y. Tong, D. An, N. Wiebe và L. Lin. Đảo ngược nhanh, bộ giải hệ thống tuyến tính lượng tử có điều kiện trước, tính toán hàm xanh nhanh và đánh giá nhanh các hàm ma trận. Đánh giá Vật lý A, 104, 2021. 10.1103/​PhysRevA.104.032422.
https: / / doi.org/ 10.1103 / PhysRevA.104.032422

[36] R. Vale, TMD Azevedo, I. Araújo, IF Araujo, và AJ da Silva. Phân tách các cổng qubit đơn nhất đặc biệt đa điều khiển. bản in trước arXiv arXiv:2302.06377, 2023. 10.48550/​arXiv.2302.06377.
https: / / doi.org/ 10.48550 / arXiv.2302.06377
arXiv: 2302.06377

[37] MW Vương. Giới thiệu về toán tử giả vi phân. Khoa học Thế giới, 1999. 10.1142/​4047.
https: / / doi.org/ 10.1142 / 4047

[38] Nằm. Yếu tố ổn định cho các yếu tố pha của xử lý tín hiệu lượng tử. Lượng tử, 6: 842, 2022. 10.22331/​q-2022-10-20-842.
https:/​/​doi.org/​10.22331/​q-2022-10-20-842

Trích dẫn

[1] David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T Sornborger và Yiğit Subaşı, “Thuật toán bộ giải tuyến tính lượng tử hiệu quả với chi phí vận hành chi tiết”, arXiv: 2305.11352, (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 2023 / 06-02 12:49:58). 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 2023 / 06-02 12:49:57: Không thể tìm nạp dữ liệu được trích dẫn cho 10.22331 / q-2023 / 06-02-1031 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ọ.

Dấu thời gian:

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