Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giới hạn dưới cho lỗi tích phân lượng tử trên các lớp Sobolev dị hướng
Tóm tắt
Chúng tôi nghiên cứu sự xấp xỉ của việc tích phân các hàm đa biến trong mô hình tính toán lượng tử. Bằng cách sử dụng một phương pháp giảm thiểu mới, chúng tôi thu được một giới hạn dưới cho lỗi truy vấn tối thiểu n-th trên lớp Sobolev dị hướng ℬ(W
([0, 1]
d
)) (r ∈ ℝ
+
). Sau đó, kết hợp kết quả này với kết quả trước đó, chúng tôi xác định giới hạn tối ưu cho lỗi truy vấn tối thiểu n-th cho lớp Hölder-Nikolskii dị hướng ℬ(H
∞
([0, 1]
d
)) và lớp Sobolev B(W
∞
([0, 1]
d
)). Kết quả cho thấy rằng đối với hai loại lớp này, các thuật toán lượng tử mang lại tốc độ vượt trội so với các thuật toán xác định cổ điển và ngẫu nhiên.
Từ khóa
Tài liệu tham khảo
Grover, L.: A framework for fast quantum mechanical algorithms. In: Proceedings of the 30th Annual ACM Symposium on the theory of Computing, ACM Press, New York, 53–62 (1998)
Nielsen, M. A., Chuang, I. L.: Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2000
Shor, P. W.: Introduction to Quantum Computing Algorithms, Birkhäuser, Boston, 1999
Novak, E.: Quantum complexity of integration. J. Complexity, 17, 2–16 (2001)
Heinrich, S.: Quantum summation with an application to integration. J. Complexity, 18, 1–50 (2002)
Heinrich, S., Novak, E.: On a problem in quantum summation. J. Complexity, 18, 1–18 (2003)
Heinrich, S.: Quantum integration in Sobolev classes. J. Complexity, 19, 19–42 (2003)
Hu, X. F., Ye, P. X.: Quantum complexity of the integration problem for anisotropic classes. J. Comput. Math., 23(3), 233–246 (2005)
Ye, P. X., Hu, X. F.: Optimal integration error on anisotropic classes for restricted Monte Carlo and quantum algorithms. J. Approx. Theory, 150, 24–47 (2008)
Nikolskii, S. M.: Approximation of Functions of Several Variables and Imbedding Theorems, Springer-Verlag, New York, 1975
Temlyakov, V. N.: Approximation of Periodic Functions, Nova Science, New York, 1993
Fang, G. S., Ye, P. X.: Integration error for multivariate functions from anisotropic classes. J. Complexity, 19, 610–627 (2003)
Hochmuth, R.: Nonlinear anisotropic boundary value problems — Regularity results and multi-scale discretizations. Nonlinear Anal., 46, 1–18 (2001)
Heinrich, S.: The quantum query complexity of elliptic PDE. J. Complexity, 22, 691–725 (2006)
Royden, H. L.: Real Analysis, Third Edition, China Machine Press, Beijing, 2004