Information-Based Complexity of Integration in the Randomized and Quantum Computation Model

Wen Hua Gao; Li Qin Duan; Wei Zhou; Pei Xin Ye

doi:10.4028/www.scientific.net/AMR.403-408.367

Paper Titles

Empirical Analysis on the Influence Factors of Inflation in China
p.348

An Empirical Analysis on the Influence Factors of Stock Market
p.353

Empirical Analysis of the Influence Factors on Chinese Consumption Expenditures
p.358

The Game Analysis of Financing Problem about Small and Medium-Sized Enterprises
p.363

Information-Based Complexity of Integration in the Randomized and Quantum Computation Model
p.367

An Empirical Research of Relationship between Regional Information and Human Capital
p.372

To Construct a Management System for Tourism Resources of Intangible Cultural Heritage
p.377

Dynamic Complexity of E-Commerce Systems Base on Synergy Field
p.383

Study on the Model of Individual Customer Retention in Consumer Durables Market Considering Service Input
p.389

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 403-408Information-Based Complexity of Integration in the...

Information-Based Complexity of Integration in the Randomized and Quantum Computation Model

Abstract:

In this paper, we investigate the integration of the Hölder-Nikolskii classes in the randomized and quantum computation model. We develop randomized and quantum algorithms for integration of functions from this class and analyze their convergence rates. Comparing our result with the convergence rates in the deterministic setting, we see that quantum computing can reach an exponential speedup over deterministic classical computation and a quadratic speedup over randomized classical computation.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 403-408)

Pages:

367-371

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.403-408.367

Citation:

Cite this paper

Online since:

November 2011

Authors:

Wen Hua Gao, Li Qin Duan, Wei Zhou, Pei Xin Ye

Keywords:

Convergence Rate, Hölder-Nikolskii Class, Quantum Algorithm, Randomized Algorithm

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Bakhvalov N. S., On a rate of convergence of indeterministic integration processes within the functional classes , Theory. Probab. Appl., 7(1962), 227.

Google Scholar

[2] Dubinin V. V., On optimal quadrature formulae for classes of functions with bounded mixed difference, Mat. Zametki, 49(1991), 149-151.

Google Scholar

[3] Heinrich S., Random approximation in numerical analysis, In K.D. Bierstedt, et al., editor, Functional Analysis: Proceedings of the Essen Conference, Volume 150 of Lect. Notes in pure and appl. Math., (1994), 123-171.

Google Scholar

[4] S. Heinrich, Quantum integration in Sobolev classes,J. Complexity 19(2003)19-42.

Google Scholar

[5] S. Heinrich, Quantum summation with an application to integration, J. Complexity 18(2002)1-50.

Google Scholar

[6] Novak E., Sloan I. H. and Woźniakowski H., Tractability of approximation for weighted Korobov spaces on classical and Quantum computers, Found. Comput. Math., 4(2004), 121-156.

DOI: 10.1007/s10208-002-0074-6

Google Scholar

[7] Sard A., Best approximate integration formulas; best approximation formulas, Amer. J. Math., 71(1949), 80-91.

DOI: 10.2307/2372095

Google Scholar

[8] Temlyakov V. N., Approximation of Periodic Functions, Nova Science, New York, (1993).

Google Scholar

[9] Traub J. F., Wasilkowski G. W. and Woźniakowski H., Information-based Complexity. Academic Press, New York, (1988).

Google Scholar