|
| related topics |
| {let, theorem, proof} |
| {algorithm, log, probability} |
| {equation, function, exp} |
| {level, atom, field} |
| {operator, operators, space} |
|
Quantum Approximation II. Sobolev Embeddings
Stefan Heinrich
abstract: A basic problem of approximation theory, the approximation of functions from
the Sobolev space W_p^r([0,1]^d) in the norm of L_q([0,1]^d), is considered
from the point of view of quantum computation. We determine the quantum query
complexity of this problem (up to logarithmic factors). It turns out that in
certain regions of the domain of parameters p,q,r,d quantum computation can
reach a speedup of roughly squaring the rate of convergence of classical
deterministic or randomized approximation methods. There are other regions were
the best possible rates coincide for all three settings.
- oai_identifier:
- oai:arXiv.org:quant-ph/0305031
- categories:
- quant-ph
- comments:
- 23 pages, paper submitted to the Journal of Complexity
- arxiv_id:
- quant-ph/0305031
- created:
- 2003-05-06
Full article ▸
|
|
| related documents |
| 0603206v1 |
| 9912114v2 |
| 0606077v1 |
| 0309057v1 |
| 0002058v1 |
| 0305005v1 |
| 9908050v1 |
| 0411027v1 |
| 0406226v1 |
| 0006061v1 |
| 0404051v4 |
| 0312164v1 |
| 0206169v2 |
| 0210141v2 |
| 0512100v1 |
| 0703061v1 |
| 0402060v2 |
| 0609166v1 |
| 0311133v2 |
| 0508156v3 |
| 0608156v1 |
| 0407179v1 |
| 0609160v1 |
| 0504169v1 |
| 0406072v1 |
|