2005/12/27 by Stefan Heinrich, Heinrich, Stefan
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Cryptography and Data Security #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0512241
45 pages, submitted to the Journal of Complexity
arxiv created 2005/12/27 · openalex publication_date 2005/12/27 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The complexity of the following numerical problem is studied in the quantum model of computation: Consider a general elliptic partial differential equation of order 2m in a smooth, bounded domain Q⊂ \Rd with smooth coefficients and homogeneous boundary conditions. We seek to approximate the solution on a smooth submanifold M⊆ Q of dimension 0≤ d1 ≤ d. With the right hand side belonging to Cr(Q), and the error being measured in the L_∞(M) norm, we prove that the n-th minimal quantum error is (up to logarithmic factors) of order n-min((r+2m)/d1,r/d+1). For comparison, in the classical deterministic setting the n-th minimal error is known to be of order n-r/d, for all d1, while in the classical randomized setting it is (up to logarithmic factors) n-min((r+2m)/d1,r/d+1/2).