Quantum Summation with an Application to Integration
Abstrak
We study summation of sequences and integration in the quantum model of computation. We develop quantum algorithms for computing the mean of sequences that satisfy a p-summability condition and for integration of functions from Lebesgue spaces Lp(0, 1]d), and analyze their convergence rates. We also prove lower bounds showing that the proposed algorithms are, in many cases, optimal within the setting of quantum computing. This extends recent results of G. Brassard et al. (2000, “Quantum Amplitude Amplification and Estimation,” Technical Report, http://arXiv.org/abs/quant-ph/0005055) on computing the mean for bounded sequences and complements results of E. Novak (2001, J. Complexity17, 2?16) on integration of functions from Holder classes. The analysis requires an appropriate model of quantum computation, capable of covering the typical features of numerical problems such as dealing with real numbers and real-valued functions and with vector and function spaces. We develop and study such a model, which can be viewed as a quantum setting for information-based complexity theory.
Topik & Kata Kunci
Penulis (1)
S. Heinrich
Akses Cepat
- Tahun Terbit
- 2001
- Bahasa
- en
- Total Sitasi
- 153×
- Sumber Database
- Semantic Scholar
- DOI
- 10.1006/JCOM.2001.0629
- Akses
- Open Access ✓