The quantum query complexity of elliptic PDE

DOI10.1016/J.JCO.2006.04.005zbMATH Open1110.65130arXivquant-ph/0512241OpenAlexW4206688793MaRDI QIDQ855898FDOQ855898

Authors: Stefan Heinrich 

Publication date: 7 December 2006

Published in: Journal of Complexity (Search for Journal in Brave)

Abstract: 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 Qsubset R^d with smooth coefficients and homogeneous boundary conditions. We seek to approximate the solution on a smooth submanifold Msubseteq Q of dimension 0le d_1 le d. With the right hand side belonging to C^r(Q), and the error being measured in the L_infty(M) norm, we prove that the n-th minimal quantum error is (up to logarithmic factors) of order n^{-min((r+2m)/d_1,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 d_1, while in the classical randomized setting it is (up to logarithmic factors) n^{-min((r+2m)/d_1,r/d+1/2)}.

Full work available at URL: https://arxiv.org/abs/quant-ph/0512241

Recommendations

• The quantum query complexity of the determinant
• On exact quantum query complexity
• Evaluation of exact quantum query complexities by semidefinite programming
• Quantum complexity of Sobolev imbeddings
• The quantum complexity of computing Schatten \(p\)-norms
• The Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries
• Qubit complexity of continuous problems
• The Quantum Query Complexity of Algebraic Properties
• The quantum query complexity of read-many formulas

zbMATH Keywords

Green's functionquantum algorithmelliptic partial differentialMonte Carlo quadratureweakly singular integrals

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Complexity and performance of numerical algorithms (65Y20) Integral representations of solutions to PDEs (35C15) Boundary value problems for second-order elliptic equations (35J25) Boundary element methods for boundary value problems involving PDEs (65N38)

Cites Work

• From Monte Carlo to quantum computation
• Title not available (Why is that?)
• Estimates near the boundary for solutions of elliptic partial differential equations satisfying general boundary conditions. I
• The complexity of definite elliptic problems with noisy data
• Almost optimal solution of initial-value problems by randomized and quantum algorithms
• Deterministic and stochastic error bounds in numerical analysis
• Optimal approximation of elliptic problems by linear and nonlinear mappings. II
• Local polynomial reproduction and moving least squares approximation
• Title not available (Why is that?)
• Quantum summation with an application to integration.
• Quantum approximation. I: Embeddings of finite-dimensional \(L_{p}\) spaces
• Quantum approximation. II: Sobolev embeddings
• Quantum complexity of integration
• Title not available (Why is that?)
• ISOLATION OF SINGULARITIES OF THE GREEN'S FUNCTION
• Geometric quantum computation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal approximation of elliptic problems by linear and nonlinear mappings. I
• Monte Carlo approximation of weakly singular integral operators
• The randomized information complexity of elliptic PDE
• Worst case complexity of multivariate Feynman--Kac path integration
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum integration in Sobolev classes
• Quantum complexity of parametric integration
• A remark on an a really mean p-valent function
• Title not available (Why is that?)

Cited In (5)

• Optimal approximation of elliptic problems by linear and nonlinear mappings. IV: Errors in \(L_{2}\) and other norms
• Lower bound for quantum integration error on anisotropic Sobolev classes
• Optimal integration error on anisotropic classes for restricted Monte Carlo and quantum algorithms
• Optimal approximation of elliptic problems by linear and nonlinear mappings. II
• The randomized information complexity of elliptic PDE

This page was built for publication: The quantum query complexity of elliptic PDE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q855898)