dorsal/arxiv
View SchemaGeneric Quantum Fourier Transforms
| Authors | Cristopher Moore, Daniel Rockmore, Alexander Russell |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0304064 |
| URL | https://arxiv.org/abs/quant-ph/0304064 |
Abstract
The quantum Fourier transform (QFT) is the principal algorithmic tool underlying most efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by ``quantizing'' the separation of variables technique that has been so successful in the study of classical Fourier transform computations. Specifically, this framework applies the existence of computable Bratteli diagrams, adapted factorizations, and Gel'fand-Tsetlin bases to offer efficient quantum circuits for the QFT over a wide variety a finite Abelian and non-Abelian groups, including all group families for which efficient QFTs are currently known and many new group families. Moreover, the method gives rise to the first subexponential-size quantum circuits for the QFT over the linear groups GL_k(q), SL_k(q), and the finite groups of Lie type, for any fixed prime power q.
{
"annotation_id": "9e8d7e4f-7c0d-4b14-8908-6bf08c003df0",
"date_created": "2026-03-02T18:01:59.335000Z",
"date_modified": "2026-03-02T18:01:59.335000Z",
"file_hash": "15875801d35b1e5d83f22a1833716ceaf59c8159a95fb8737d54ad8487c41260",
"private": false,
"record": {
"abstract": "The quantum Fourier transform (QFT) is the principal algorithmic tool\nunderlying most efficient quantum algorithms. We present a generic framework\nfor the construction of efficient quantum circuits for the QFT by\n``quantizing\u0027\u0027 the separation of variables technique that has been so\nsuccessful in the study of classical Fourier transform computations.\nSpecifically, this framework applies the existence of computable Bratteli\ndiagrams, adapted factorizations, and Gel\u0027fand-Tsetlin bases to offer efficient\nquantum circuits for the QFT over a wide variety a finite Abelian and\nnon-Abelian groups, including all group families for which efficient QFTs are\ncurrently known and many new group families. Moreover, the method gives rise to\nthe first subexponential-size quantum circuits for the QFT over the linear\ngroups GL_k(q), SL_k(q), and the finite groups of Lie type, for any fixed prime\npower q.",
"arxiv_id": "quant-ph/0304064",
"authors": [
"Cristopher Moore",
"Daniel Rockmore",
"Alexander Russell"
],
"categories": [
"quant-ph"
],
"title": "Generic Quantum Fourier Transforms",
"url": "https://arxiv.org/abs/quant-ph/0304064"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "74595a49-4d22-40cb-867a-31106afb9e21",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}