dorsal/arxiv
View SchemaTractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers
| Authors | E. Novak, I. H. Sloan, H. Wozniakowski |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0206023 |
| URL | https://arxiv.org/abs/quant-ph/0206023 |
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.
{
"annotation_id": "aa580cf0-47a0-4c98-8505-17c532dbab06",
"date_created": "2026-03-02T18:01:52.487000Z",
"date_modified": "2026-03-02T18:01:52.487000Z",
"file_hash": "d9e427addb2922ff1ef248fd759c216ff9efcabdfe6d43261315592959c7ca77",
"private": false,
"record": {
"abstract": "The paper studies quantum complexity, tractability, and strong tractability\nfor high dimensional multivariate approximation. We study a space of functions\nimportant in many applications. A function space is weighted if certain\nvariables are more important than others; the weights show the relative\nimportance of the variables. In an unweighted space all variables are equally\nimportant and multivariate approximation is intractable. We want to study when\nthe complexity of multivariate approximation is independent of the number of\nvariables and depends polynomially on 1/E. The main conclusions are:\nMultivariate approximation on a quantum computer can be solved roughly\n(1/E)^(1+r) times faster than on a classical computer using randomization.\nHere, r is a positive parameter that depends on the weights and may be large.\nThis means that the speed-up of quantum over classical computers may be much\nlarger than quadratic. Multivariate approximation on a quantum computer is\nexponentially faster than on a classical computer with a worst case assurance\neven if the sum of weights is infinite but a certain power of them is finite.\nWe have designed a quantum algorithm with error at most E that uses about\nd+log(1/E) qubits. Hence, we have only linear dependence on the dimension d and\nlogarithmic dependence on 1/E. Therefore, for some applications the number of\nqubits is quite modest.",
"arxiv_id": "quant-ph/0206023",
"authors": [
"E. Novak",
"I. H. Sloan",
"H. Wozniakowski"
],
"categories": [
"quant-ph"
],
"title": "Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers",
"url": "https://arxiv.org/abs/quant-ph/0206023"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "61250856-5f75-41d3-ad1e-f6f2a0d56f70",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}