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)}.
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
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 3696612 (Why is no real title available?)
- scientific article; zbMATH DE number 44104 (Why is no real title available?)
- scientific article; zbMATH DE number 50734 (Why is no real title available?)
- scientific article; zbMATH DE number 515830 (Why is no real title available?)
- scientific article; zbMATH DE number 2103524 (Why is no real title available?)
- scientific article; zbMATH DE number 919117 (Why is no real title available?)
- scientific article; zbMATH DE number 5049912 (Why is no real title available?)
- A remark on an a really mean p-valent function
- Almost optimal solution of initial-value problems by randomized and quantum algorithms
- Deterministic and stochastic error bounds in numerical analysis
- Estimates near the boundary for solutions of elliptic partial differential equations satisfying general boundary conditions. I
- From Monte Carlo to quantum computation
- Geometric quantum computation
- ISOLATION OF SINGULARITIES OF THE GREEN'S FUNCTION
- Local polynomial reproduction and moving least squares approximation
- Monte Carlo approximation of weakly singular integral operators
- Optimal approximation of elliptic problems by linear and nonlinear mappings. I
- Optimal approximation of elliptic problems by linear and nonlinear mappings. II
- Quantum approximation. I: Embeddings of finite-dimensional \(L_{p}\) spaces
- Quantum approximation. II: Sobolev embeddings
- Quantum complexity of integration
- Quantum complexity of parametric integration
- Quantum integration in Sobolev classes
- Quantum summation with an application to integration.
- The complexity of definite elliptic problems with noisy data
- The randomized information complexity of elliptic PDE
- Worst case complexity of multivariate Feynman--Kac path integration
Cited in
(5)- Optimal approximation of elliptic problems by linear and nonlinear mappings. II
- Optimal approximation of elliptic problems by linear and nonlinear mappings. IV: Errors in \(L_{2}\) and other norms
- The randomized information complexity of elliptic PDE
- Optimal integration error on anisotropic classes for restricted Monte Carlo and quantum algorithms
- Lower bound for quantum integration error on anisotropic Sobolev classes
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)
