Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Sai số truy vấn tối ưu của phép xấp xỉ lượng tử trên một số lớp Sobolev
Tóm tắt
Chúng tôi nghiên cứu việc xấp xỉ sự nhúng của các hàm từ các lớp Sobolev phi đồng nhất và tổng quát vào không gian L^q ([0, 1]^d) trong mô hình tính toán lượng tử. Dựa trên các thuật toán lượng tử cho việc xấp xỉ sự nhúng hữu hạn từ L đến L, chúng tôi phát triển các thuật toán lượng tử để xấp xỉ sự nhúng từ các lớp Sobolev phi đồng nhất B(W([0, 1]^d)) vào không gian L^q ([0, 1]^d) cho tất cả 1 ≤ q,p ≤ ∞ và chứng minh tính tối ưu của chúng. Kết quả của chúng tôi cho thấy rằng đối với p < q, mô hình tính toán lượng tử có thể mang lại sự tăng tốc khoảng bằng bình phương tốc độ trong các thiết lập quyết định và ngẫu nhiên cổ điển.
Từ khóa
#xấp xỉ lượng tử #lớp Sobolev #mô hình tính toán lượng tử #sai số truy vấn tối ưu #không gian L^qTài liệu tham khảo
Novak E. Quantum complexity of integration. J Complexity, 17: 2–16 (2001)
Novak E, Sloan I H, Woźniakowski H. Tractability of approximation for weighted Korobov spaces on classical and quantum computer. Found Comput Math, 4: 121–156 (2004)
Heinrich S. Quantum approximation I. Imbeddings of finite-dimensional L p spaces. J Complexity, 20: 5–26 (2004)
Heinrich S. Quantum approximation II. Sobolev imbeddings. J Complexity, 20: 27–45 (2004)
Temlyakov V N. Approximation of Periodic Functions. New York: Nova Science, 1993
Heinrich S. Quantum integration in Sobolev classes. J Complexity, 19: 19–42 (2003)
Grover L. A framework for fast quantum mechanical algorithms. In: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing. New York: ACM Press, 1998, 53–62
Shor P W. Introduction to Quantum Computing Algorithms. Boston: Birkhäuser, 1999
Nikolskii S M. Approximation of Functions of Several Variables and Imbedding Theorems. Berlin: Springer-Verlag, 1975
Novak E. Deterministic and stochastic error bound in numerical analysis. Lecture Notes in Maths, Vol. 1349. Berlin: Springer-Verlag, 1988
Dahmen W, DeVore R, Scherer K. Multi-dimensional spline approximation. SIAM J Numer Anal, 17: 380–402 (1980)
Heinrich S, Novak E. On a problem in quantum summation. J Complexity, 18: 1–18 (2003)