The quantum query complexity of elliptic PDE

DOI10.1016/J.JCO.2006.04.005MaRDI QIDQ855898zbMATH OpenOpenAlexFDO

Authors Stefan Heinrich

Publication date 7 December 2006

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

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

zbMATH Keywords

elliptic partial differentialGreen's functionMonte Carlo quadraturequantum algorithmweakly singular integrals

Mathematics Subject Classification ID

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

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)}.

Review text

For an elliptic partial differential equation (PDE) \(Lu = f\) on a bounded domain \(\Omega\) with homogeneous boundary conditions, suppose that one knows the Green's function \(k(x, y)\) such that \(u(x) = \int_\Omega f(y) k(x, y)\, dy\). The author obtains estimates of the complexity of computing such integrals using a Monte Carlo quadrature method on a quantum computer.

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

• 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
• 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?)
• 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 integration error on anisotropic classes for restricted Monte Carlo and quantum algorithms
• The randomized information complexity of elliptic PDE
• 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
• 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)