Quantum Complexity of Parametric Integration

2003/05/19 by Carsten Wiegand, Wiegand, Carsten
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0305103

Paper submitted to the Journal of Complexity, 28 pages

openalex publication_date 2003/05/19 · arxiv created 2003/11/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study parametric integration of functions from the class C^r([0,1]^d₁+d₂) to C([0,1]^d₁) in the quantum model of computation. We analyze the convergence rate of parametric integration in this model and show that it is always faster than the optimal deterministic rate and in some cases faster than the rate of optimal randomized classical algorithms.

Citations

• Quantum Approximation I. Embeddings of Finite Dimensional L_p Spaces

Related

• Randomized and Quantum Algorithms Yield a Speed-Up for Initial-Value Problems
• Quantum Integration in Sobolev Classes
• Optimal Summation and Integration by Deterministic, Randomized, and Quantum Algorithms
• Quantum Algorithms and Complexity for Continuous Problems
• Quantum Summation with an Application to Integration