|
| related topics |
| {let, theorem, proof} |
| {algorithm, log, probability} |
| {equation, function, exp} |
| {error, code, errors} |
| {cos, sin, state} |
| {qubit, qubits, gate} |
|
Tractability of Approximation for Weighted Korobov Spaces on Classical
and Quantum Computers
E. Novak, I. H. Sloan, H. Wozniakowski
abstract: The paper studies quantum complexity, tractability, and strong tractability
for high dimensional multivariate approximation. We study a space of functions
important in many applications. A function space is weighted if certain
variables are more important than others; the weights show the relative
importance of the variables. In an unweighted space all variables are equally
important and multivariate approximation is intractable. We want to study when
the complexity of multivariate approximation is independent of the number of
variables and depends polynomially on 1/E. The main conclusions are:
Multivariate approximation on a quantum computer can be solved roughly
(1/E)^(1+r) times faster than on a classical computer using randomization.
Here, r is a positive parameter that depends on the weights and may be large.
This means that the speed-up of quantum over classical computers may be much
larger than quadratic. Multivariate approximation on a quantum computer is
exponentially faster than on a classical computer with a worst case assurance
even if the sum of weights is infinite but a certain power of them is finite.
We have designed a quantum algorithm with error at most E that uses about
d+log(1/E) qubits. Hence, we have only linear dependence on the dimension d and
logarithmic dependence on 1/E. Therefore, for some applications the number of
qubits is quite modest.
- oai_identifier:
- oai:arXiv.org:quant-ph/0206023
- categories:
- quant-ph
- comments:
- 37 pages
- arxiv_id:
- quant-ph/0206023
- created:
- 2002-06-04
- updated:
- 2002-06-27
Full article ▸
|
|
| related documents |
| 0008059v3 |
| 0512241v1 |
| 0212096v1 |
| 0405081v1 |
| 0607148v3 |
| 0308142v2 |
| 0410120v1 |
| 0408150v2 |
| 0510185v1 |
| 0504083v2 |
| 0610235v2 |
| 0605239v4 |
| 0410042v1 |
| 0207131v1 |
| 0210077v1 |
| 0703231v2 |
| 0410229v1 |
| 0603135v1 |
| 0401053v1 |
| 0503221v2 |
| 0612089v3 |
| 0403140v2 |
| 0503159v2 |
| 0304131v1 |
| 0307139v1 |
|