dorsal/arxiv
View SchemaQuantum Approximation I. Embeddings of Finite Dimensional L_p Spaces
| Authors | Stefan Heinrich |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0305030 |
| URL | https://arxiv.org/abs/quant-ph/0305030 |
Abstract
We study approximation of embeddings between finite dimensional L_p spaces in the quantum model of computation. For the quantum query complexity of this problem matching (up to logarithmic factors) upper and lower bounds are obtained. The results show that for certain regions of the parameter domain quantum computation can essentially improve the rate of convergence of classical deterministic or randomized approximation, while there are other regions where the best possible rates coincide for all three settings. These results serve as a crucial building block for analyzing approximation in function spaces in a subsequent paper.
{
"annotation_id": "b18754ef-79a8-4e6e-9e01-b6cf9cdbc0bf",
"date_created": "2026-03-02T18:01:59.615000Z",
"date_modified": "2026-03-02T18:01:59.615000Z",
"file_hash": "1f549ee8bdc31ff584dabf4651044c964c8ef60a4d5c1ddb08ab278cd22b23b4",
"private": false,
"record": {
"abstract": "We study approximation of embeddings between finite dimensional L_p spaces in\nthe quantum model of computation. For the quantum query complexity of this\nproblem matching (up to logarithmic factors) upper and lower bounds are\nobtained. The results show that for certain regions of the parameter domain\nquantum computation can essentially improve the rate of convergence of\nclassical deterministic or randomized approximation, while there are other\nregions where the best possible rates coincide for all three settings. These\nresults serve as a crucial building block for analyzing approximation in\nfunction spaces in a subsequent paper.",
"arxiv_id": "quant-ph/0305030",
"authors": [
"Stefan Heinrich"
],
"categories": [
"quant-ph"
],
"title": "Quantum Approximation I. Embeddings of Finite Dimensional L_p Spaces",
"url": "https://arxiv.org/abs/quant-ph/0305030"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c9a1358a-c13a-4c70-8b88-2a9b506ce1dd",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}