The quantum query complexity of elliptic PDE

The query complexity of the following numerical problem is studied in the quantum model of computation: consider a general elliptic partial differential equation of order 2m2m in a smooth, bounded domain Q⊂RdQ⊂Rd with smooth coefficients and homogeneous boundary conditions. We seek to approximate the solution on a smooth submanifold M⊆QM⊆Q of dimension 0⩽d1⩽d0⩽d1⩽d. With the right-hand side belonging to Cr(Q)Cr(Q), and the error being measured in the L∞(M)L∞(M) norm, we prove that the nth minimal quantum error is (up to logarithmic factors) of ordern-min((r+2m)/d1,r/d+1).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/dn-r/d, for all d1d1, while in the classical randomized setting it is (up to logarithmic factors)n-min((r+2m)/d1,r/d+1/2).n-min(r+2m)/d1,r/d+1/2.