کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4609206 | 1338435 | 2006 | 35 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The quantum query complexity of elliptic PDE The quantum query complexity of elliptic PDE](/preview/png/4609206.png)
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.
Journal: Journal of Complexity - Volume 22, Issue 5, October 2006, Pages 691–725