---
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 $Q\subset {{\mathbb R}}^d$ with smooth coefficients and homogeneous boundary conditions. We seek to approximate the solution on a smooth submanifold $M\subseteq Q$ of dimension $0\le 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\left((r+2m)/d_1,\,r/d+1\right)}.$$ 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\left((r+2m)/d_1,\,r/d+1/2\right)}.$$
author:
- |
    Stefan Heinrich\
    Department of Computer Science\
    University of Kaiserslautern\
    D-67653 Kaiserslautern, Germany\
    e-mail: heinrich@informatik.uni-kl.de\
    homepage: http://www.uni-kl.de/AG-Heinrich
title: The Quantum Query Complexity of Elliptic PDE
---

Introduction
============

The complexity of solving elliptic problems in the classical deterministic setting was studied in [@Wer91; @Wer96; @Dya96; @DNS05; @DNS05a]. In [@Hei05b] such problems were considered in the classical randomized setting. The quantum complexity of ordinary differential equation was investigated in 