dorsal/arxiv
View SchemaImproved Bounds for the Approximate QFT
| Authors | Donny Cheung |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0403071 |
| URL | https://arxiv.org/abs/quant-ph/0403071 |
| Journal | Proc. of the Winter Intl Symposium of Information and Communication Technologies (WISICT 2004), pp. 192-197 |
Abstract
It has previously been established that the logarithmic-depth approximate quantum Fourier transform (AQFT) provides a suitable replacement for the regular QFT in many quantum algorithms. Since the AQFT is less accurate by definition, polynomially many more applications of the AQFT are required to achieve the original accuracy. However, in many quantum algorithms, the smaller size of the AQFT circuit yields a net improvement over using the QFT. This paper presents a more thorough analysis of the AQFT circuit, which leads to the surprising conclusion that for sufficiently large input sizes, the difference between the QFT and the logarithmic-depth AQFT is negligible. In effect, the AQFT can be used as an direct replacement for the QFT, yielding improvements in any application which does not require exact quantum computation.
{
"annotation_id": "6f55e8f0-677a-4eb2-8987-36dc831bbf3d",
"date_created": "2026-03-02T18:02:06.510000Z",
"date_modified": "2026-03-02T18:02:06.510000Z",
"file_hash": "e43d0406442706d815f03467ab25c9f89252a870cf5d09c5f55ad56903f7d81f",
"private": false,
"record": {
"abstract": "It has previously been established that the logarithmic-depth approximate\nquantum Fourier transform (AQFT) provides a suitable replacement for the\nregular QFT in many quantum algorithms. Since the AQFT is less accurate by\ndefinition, polynomially many more applications of the AQFT are required to\nachieve the original accuracy. However, in many quantum algorithms, the smaller\nsize of the AQFT circuit yields a net improvement over using the QFT.\n This paper presents a more thorough analysis of the AQFT circuit, which leads\nto the surprising conclusion that for sufficiently large input sizes, the\ndifference between the QFT and the logarithmic-depth AQFT is negligible. In\neffect, the AQFT can be used as an direct replacement for the QFT, yielding\nimprovements in any application which does not require exact quantum\ncomputation.",
"arxiv_id": "quant-ph/0403071",
"authors": [
"Donny Cheung"
],
"categories": [
"quant-ph"
],
"journal_ref": "Proc. of the Winter Intl Symposium of Information and\n Communication Technologies (WISICT 2004), pp. 192-197",
"title": "Improved Bounds for the Approximate QFT",
"url": "https://arxiv.org/abs/quant-ph/0403071"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1b051313-52a2-49bd-bdd7-bccf2cba01c9",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}