1Trường Toán học, Đại học Bristol. n.linden@bristol.ac.uk
2QuSoft, CWI và Đại học Amsterdam, Hà Lan. rdewolf@cwi.nl
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
Biến đổi Fourier lượng tử (QFT) là một nguyên hàm quan trọng cho điện toán lượng tử thường được sử dụng như một chương trình con trong một phép tính lớn hơn, chẳng hạn như để ước lượng pha. Như vậy, chúng ta có thể có ít quyền kiểm soát đối với trạng thái đầu vào của QFT. Do đó, để triển khai một QFT tốt, chúng ta có thể tưởng tượng rằng nó cần hoạt động tốt trên các trạng thái đầu vào tùy ý. $Xác minh$ hành vi đúng trong trường hợp xấu nhất này của việc triển khai QFT nói chung sẽ khó theo cấp số nhân (về số lượng qubit), làm dấy lên lo ngại rằng việc xác minh này sẽ không thể thực hiện được trên bất kỳ hệ thống có kích thước hữu ích nào. Trong bài báo này, chúng tôi chỉ ra rằng, trên thực tế, chúng ta chỉ cần có hiệu suất $trung bình$-$trường hợp$ tốt của QFT để đạt được hiệu suất $tệ nhất$-$trường hợp$ tốt cho các tác vụ chính – ước tính pha, tìm chu kỳ và ước tính biên độ . Hơn nữa, chúng tôi đưa ra một quy trình rất hiệu quả để xác minh hành vi trường hợp trung bình bắt buộc này của QFT.
Tóm tắt phổ biến
► Dữ liệu BibTeX
► Tài liệu tham khảo
[1] Scott Aaronson và Patrick Rall. Tính gần đúng lượng tử, đơn giản hóa. Trong Kỷ yếu của Hội nghị chuyên đề lần thứ 3 về tính đơn giản trong thuật toán (SOSA), trang 24–32, 2020. arXiv:1908.10846.
https: / / doi.org/ 10.1137 / 1.9781611976014.5
arXiv: 1908.10846
[2] Charles H. Bennett, Ethan Bernstein, Gilles Brassard và Umesh Vazirani. Điểm mạnh và điểm yếu của điện toán lượng tử. SIAM Journal on Computing, 26(5):1510–1523, 1997. quant-ph/9701001.
https: / / doi.org/ 10.1137 / S0097539796300933
arXiv: quant-ph / 9701001
[3] Gilles Brassard, Peter Høyer, Michele Mosca và Alain Tapp. Khuếch đại biên độ lượng tử và ước lượng. Trong Tính toán lượng tử và Thông tin lượng tử: Tập thiên niên kỷ, tập 305 của Bộ sách toán học đương đại AMS, trang 53–74. 2002. quant-ph/0005055.
https: / / doi.org/ 10.1090 / conm / 305/05215
arXiv: quant-ph / 0005055
[4] Chi-Fang Chen và Fernando GSL Brandão. Nồng độ cho lỗi Trotter. arXiv:2111.05324, ngày 9 tháng 2021 năm XNUMX.
https: / / doi.org/ 10.48550 / arXiv.2111.05324
arXiv: 2111.05324
[5] Richard Cleve, Artur Ekert, Chiara Macchiavello và Michele Mosca. Các thuật toán lượng tử được xem xét lại. Trong Kỷ yếu của Hiệp hội Hoàng gia Luân Đôn, tập A454, trang 339–354, 1998. quant-ph/9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: quant-ph / 9708016
[6] Don Coppersmith. Một biến đổi Fourier gần đúng hữu ích trong bao thanh toán lượng tử. Báo cáo nghiên cứu của IBM số RC19642, quant-ph/0201067, 1994.
https: / / doi.org/ 10.48550 / arXiv.quant-ph / 0201067
arXiv: quant-ph / 0201067
[7] Marcus da Silva, Oliver Landon-Cardinal và David Poulin. Đặc tính thực tế của các thiết bị lượng tử mà không cần chụp cắt lớp. Physical Review Letters, 107:210404, 2011. arXiv:1104.3835.
https: / / doi.org/ 10.1103 / PhysRevLett.107.210404
arXiv: 1104.3835
[8] Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud và Elham Kashefi. Chứng nhận lượng tử và điểm chuẩn. Nature Reviews Physics, 2:382–390, 2020. arXiv:1910.06343.
https://doi.org/10.1038/s42254-020-0186-4
arXiv: 1910.06343
[9] Steven T. Flammia và Yi-Kai Liu. Ước tính độ trung thực trực tiếp từ một vài phép đo Pauli. Physical Review Letters, 106:230501, 2011. arXiv:1104.4695.
https: / / doi.org/ 10.1103 / PhysRevLett.106.230501
arXiv: 1104.4695
[10] András Gilyén, Srinivasan Arunachalam, và Nathan Wiebe. Tối ưu hóa các thuật toán tối ưu hóa lượng tử thông qua tính toán gradient lượng tử nhanh hơn. Trong Kỷ yếu của ACM-SIAM SODA lần thứ 30, trang 1425–1444, 2019. arXiv:1711.00465.
https: / / doi.org/ 10.1137 / 1.9781611975482.87
arXiv: 1711.00465
[11] Yêu 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 ACM STOC lần thứ 28, trang 212–219, 1996. quant-ph/9605043.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043
[12] András Gilyén, Yuan Su, Guang Hao Low và Nathan Wiebe. Biế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 Kỷ yếu của ACM STOC lần thứ 51, trang 193–204, 2019. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838
[13] Stephen P. Jordan. Thuật toán lượng tử nhanh để ước tính độ dốc số. Physical Review Letters, 95:050501, 2005. quant-ph/0405146.
https: / / doi.org/ 10.1103 / PhysRevLett.95.050501
arXiv: quant-ph / 0405146
[14] Aleksey Yu. Kitaev. Các phép đo lượng tử và vấn đề ổn định Abelian. quant-ph/9511026, ngày 12 tháng 1995 năm XNUMX.
https: / / doi.org/ 10.48550 / arXiv.quant-ph / 9511026
arXiv: quant-ph / 9511026
[15] Nô-ê Linden và Ronald de Wolf. Phát hiện nhẹ một số lượng nhỏ lỗi lớn trong mạch lượng tử. Lượng tử, 5(436), 2021. arXiv:2009.08840.
https://doi.org/10.22331/q-2021-04-20-436
arXiv: 2009.08840
[16] Urmila Mahadev. Xác minh cổ điển của tính toán lượng tử. Trong Kỷ yếu của IEEE FOCS lần thứ 59, trang 259–267, 2018. arXiv:1804.01082.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
arXiv: 1804.01082
[17] John M. Martyn, Zane M. Rossi, Andrew K. Tan và Isaac L. Chuang. Một sự thống nhất lớn của các thuật toán lượng tử. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[18] 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
[19] Patrick Rall. Các thuật toán lượng tử kết hợp nhanh hơn để ước tính pha, năng lượng và biên độ. Lượng tử, 5(566), 2021. arXiv:2103.09717.
https://doi.org/10.22331/q-2021-10-19-566
arXiv: 2103.09717
[20] Peter W. Shor. Các thuật toán thời gian đa thức để phân tích thừa số nguyên tố và logarit rời rạc trên máy tính lượng tử. SIAM Journal on Computing, 26(5):1484–1509, 1997. Phiên bản cũ hơn trong FOCS'94. quant-ph/9508027.
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: quant-ph / 9508027
[21] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li và Andrew M. Childs. Mô phỏng Hamilton với đầu vào ngẫu nhiên. arXiv:2111.04773, ngày 8 tháng 2021 năm XNUMX.
https: / / doi.org/ 10.48550 / arXiv.2111.04773
arXiv: 2111.04773
Trích dẫn
[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén và Giacomo Nannicini, “Chụp cắt lớp lượng tử sử dụng đơn vị chuẩn bị trạng thái”, arXiv: 2207.08800.
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 2022 / 12-08 04:24:57). 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 2022 / 12-08 04:24:56).
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ọ.
