Abstract
We deal with quantum and randomized algorithms for approximating a class of linear continuous functionals. The functionals are defined on a Hölder space of functions f of d variables with r continuous partial derivatives, the rth derivative being a Hölder function with exponent ρ. For a certain class of such linear problems (which includes the integration problem), we define algorithms based on partitioning the domain of f into a large number of small subdomains, and making use of the well-known quantum or randomized algorithms for summation of real numbers. For N information evaluations (quantum queries in the quantum setting), we show upper bounds on the error of order N −(γ+1) in the quantum setting, and N −(γ+1/2) in the randomized setting, where γ = (r + ρ)/d is the regularity parameter. Hence, we obtain for a wider class of linear problems the same upper bounds as those known for the integration problem. We give examples of functionals satisfying the assumptions, among which we discuss functionals defined on the solution of Fredholm integral equations of the second kind, with complete information about the kernel. We also provide lower bounds, showing in some cases sharpness of the obtained results, and compare the power of quantum, randomized and deterministic algorithms for the exemplary problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Brassard, G., H⊘yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation (2000) http://arXiv.org/abs/quant-ph/0005055
Emelyanov K.V., Ilin A.M.: On the number of arithmetic operations, necessary for the approximate solution of fredholm integral equations of the second kind. Zh Vychisl. Mat i Mat. Fiz. 7, 59–267 (1967)
Heinrich S.: Quantum summation with an application to integration. J. Complex. 18, 1–50 (2002)
Heinrich, S.: Quantum approximation II. Sobolev embeddings. J. Complex. 20(1), 27–45 (2004) http://arXiv.org/abs/quant-ph/0305031
Heinrich S., Mathé P.: The Monte Carlo complexity of Fredholm integral equations. Math. Comp. 60(201), 257–278 (1993)
Kacewicz, B.: Almost optimal solution of initial-value problems by randomized and quantum algorithms. J. Complex. 22(5), 676–690 (2006) http://arXiv.org/abs/quant-ph/0510045
Mathé P.: The optimal error of Monte Carlo integration. J. Complex. 11(4), 394–415 (1995)
Nayak, A., Wu, F.: The quantum query complexity of approximating the median and related statistics. STOC, May 1999 pp. 384–393 (1999) http://arXiv.org/abs/quant-ph/9804066
Nielsen M.A., Chuang I.L.: Quantum Computation and Quantum Information. Cambridge University Press, United Kingdom (2000)
Novak E.: Deterministic and Stochastic Error Bounds in Numerical Analysis, Lecture Notes in Mathematics. Springer, Berlin (1988)
Novak, E.: Quantum complexity of integration. J. Complex. 17, 2–16 (2001) http://arXiv.org/abs/quant-ph/0008124
Traub J.F., Wasilkowski G.W., Woźniakowski H.: Information-Based Complexity. Academic Press, New York (1988)
Traub, J.F., Woźniakowski, H.: Path integration on a quantum computer. Quantum Inf. Process. 1(5), 365–388 (2002) http://arXiv.org/abs/quant-ph/0109113
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partly supported by the Ministry of Science and Higher Education grant No. NN 201 547738 and AGH grant No. 10.420.03.
Rights and permissions
About this article
Cite this article
Kacewicz, B. On the quantum and randomized approximation of linear functionals on function spaces. Quantum Inf Process 10, 279–296 (2011). https://doi.org/10.1007/s11128-010-0195-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11128-010-0195-9