dorsal/arxiv
View SchemaFast Quantum Fourier Transforms for a Class of Non-abelian Groups
| Authors | Markus Pueschel, Martin Roetteler, Thomas Beth |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9807064 |
| URL | https://arxiv.org/abs/quant-ph/9807064 |
| Journal | Proceedings 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC'99), Honolulu, Hawaii, Springer LNCS, pp. 148-159, 1999 |
Abstract
An algorithm is presented allowing the construction of fast Fourier transforms for any solvable group on a classical computer. The special structure of the recursion formula being the core of this algorithm makes it a good starting point to obtain systematically fast Fourier transforms for solvable groups on a quantum computer. The inherent structure of the Hilbert space imposed by the qubit architecture suggests to consider groups of order 2^n first (where n is the number of qubits). As an example, fast quantum Fourier transforms for all 4 classes of non-abelian 2-groups with cyclic normal subgroup of index 2 are explicitly constructed in terms of quantum circuits. The (quantum) complexity of the Fourier transform for these groups of size 2^n is O(n^2) in all cases.
{
"annotation_id": "fda61b96-e45e-443f-9ada-eae2e8fd29a7",
"date_created": "2026-03-02T18:02:44.603000Z",
"date_modified": "2026-03-02T18:02:44.603000Z",
"file_hash": "d139655027ed39f6705abeff134e8b7220aa82ee438109a196e685153213f1b4",
"private": false,
"record": {
"abstract": "An algorithm is presented allowing the construction of fast Fourier\ntransforms for any solvable group on a classical computer. The special\nstructure of the recursion formula being the core of this algorithm makes it a\ngood starting point to obtain systematically fast Fourier transforms for\nsolvable groups on a quantum computer. The inherent structure of the Hilbert\nspace imposed by the qubit architecture suggests to consider groups of order\n2^n first (where n is the number of qubits). As an example, fast quantum\nFourier transforms for all 4 classes of non-abelian 2-groups with cyclic normal\nsubgroup of index 2 are explicitly constructed in terms of quantum circuits.\nThe (quantum) complexity of the Fourier transform for these groups of size 2^n\nis O(n^2) in all cases.",
"arxiv_id": "quant-ph/9807064",
"authors": [
"Markus Pueschel",
"Martin Roetteler",
"Thomas Beth"
],
"categories": [
"quant-ph",
"cs.ET"
],
"journal_ref": "Proceedings 13th International Symposium on Applied Algebra,\n Algebraic Algorithms and Error-Correcting Codes (AAECC\u002799), Honolulu, Hawaii,\n Springer LNCS, pp. 148-159, 1999",
"title": "Fast Quantum Fourier Transforms for a Class of Non-abelian Groups",
"url": "https://arxiv.org/abs/quant-ph/9807064"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1cf31b17-5347-48f7-b708-2266ea049505",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}