Quantum Approximation I. Embeddings of Finite Dimensional L_p Spaces

2003/05/06 by Stefan Heinrich, Heinrich, Stefan · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #advanced mathematical theories #quant-ph

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

27 pages, paper submitted to the Journal of Complexity

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

Abstract

We study approximation of embeddings between finite dimensional L_p spaces in the quantum model of computation. For the quantum query complexity of this problem matching (up to logarithmic factors) upper and lower bounds are obtained. The results show that for certain regions of the parameter domain quantum computation can essentially improve the rate of convergence of classical deterministic or randomized approximation, while there are other regions where the best possible rates coincide for all three settings. These results serve as a crucial building block for analyzing approximation in function spaces in a subsequent paper.

Citations

• Introduction to Quantum Algorithms
• Sharp Error Bounds on Quantum Boolean Summation in Various Settings
• Quantum Lower Bounds by Polynomials

Cited by

• Quantum Complexity of Parametric Integration

Related

• Quantum Approximation II. Sobolev Embeddings
• Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers
• Quantum Lower Bounds by Entropy Numbers
• Approximation by Quantum Circuits
• Understanding Quantum Algorithms via Query Complexity