caa a22 4500 445886528 CHVBK 20180317145601.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s11128-010-0195-9 doi (NATIONALLICENCE)springer-10.1007/s11128-010-0195-9 Kacewicz Bolesław Faculty of Applied Mathematics, AGH University of Science and Technology, Al. Mickiewicza 30, paw. A3/A4, III p., pok. 301, 30-059, Cracow, Poland aut On the quantum and randomized approximation of linear functionals on function spaces [Elektronische Daten] [Bolesław Kacewicz] 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. Springer Science+Business Media, LLC, 2010 Linear functionals nationallicence Approximation nationallicence Quantum algorithms nationallicence Randomized algorithms nationallicence Upper and lower bounds nationallicence Quantum Information Processing Springer US; http://www.springer-ny.com 10/3(2011-06-01), 279-296 1570-0755 10:3<279 2011 10 11128 https://doi.org/10.1007/s11128-010-0195-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11128-010-0195-9 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Kacewicz Bolesław Faculty of Applied Mathematics, AGH University of Science and Technology, Al. Mickiewicza 30, paw. A3/A4, III p., pok. 301, 30-059, Cracow, Poland aut NATIONALLICENCE 773 0- Quantum Information Processing Springer US; http://www.springer-ny.com 10/3(2011-06-01), 279-296 1570-0755 10:3<279 2011 10 11128 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer