dorsal/arxiv
View SchemaThe Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
| Authors | Lisa R. Hales |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0212002 |
| URL | https://arxiv.org/abs/quant-ph/0212002 |
Abstract
The quantum Fourier transform (QFT) has emerged as the primary tool in quantum algorithms which achieve exponential advantage over classical computation and lies at the heart of the solution to the abelian hidden subgroup problem, of which Shor's celebrated factoring and discrete log algorithms are a special case. We begin by addressing various computational issues surrounding the QFT and give improved parallel circuits for both the QFT over a power of 2 and the QFT over an arbitrary cyclic group. These circuits are based on new insight into the relationship between the discrete Fourier transform over different cyclic groups. We then exploit this insight to extend the class of hidden subgroup problems with efficient quantum solutions. First we relax the condition that the underlying hidden subgroup function be distinct on distinct cosets of the subgroup in question and show that this relaxation can be solved whenever G is a finitely-generated abelian group. We then extend this reasoning to the hidden cyclic subgroup problem over the reals, showing how to efficiently generate the bits of the period of any sufficiently piecewise-continuous function on R. Finally, we show that this problem of period-finding over R, viewed as an oracle promise problem, is strictly harder than its integral counterpart. In particular, period-finding over R lies outside the complexity class MA, a class which contains period-finding over the integers.
{
"annotation_id": "ef86d66b-1fb1-4e32-9513-58b4a65a160a",
"date_created": "2026-03-02T18:01:55.798000Z",
"date_modified": "2026-03-02T18:01:55.798000Z",
"file_hash": "3c91399b81574d0968b72133636fabffc925a49a5e9ded15be264037dd90b0be",
"private": false,
"record": {
"abstract": "The quantum Fourier transform (QFT) has emerged as the primary tool in\nquantum algorithms which achieve exponential advantage over classical\ncomputation and lies at the heart of the solution to the abelian hidden\nsubgroup problem, of which Shor\u0027s celebrated factoring and discrete log\nalgorithms are a special case. We begin by addressing various computational\nissues surrounding the QFT and give improved parallel circuits for both the QFT\nover a power of 2 and the QFT over an arbitrary cyclic group. These circuits\nare based on new insight into the relationship between the discrete Fourier\ntransform over different cyclic groups. We then exploit this insight to extend\nthe class of hidden subgroup problems with efficient quantum solutions. First\nwe relax the condition that the underlying hidden subgroup function be distinct\non distinct cosets of the subgroup in question and show that this relaxation\ncan be solved whenever G is a finitely-generated abelian group. We then extend\nthis reasoning to the hidden cyclic subgroup problem over the reals, showing\nhow to efficiently generate the bits of the period of any sufficiently\npiecewise-continuous function on R. Finally, we show that this problem of\nperiod-finding over R, viewed as an oracle promise problem, is strictly harder\nthan its integral counterpart. In particular, period-finding over R lies\noutside the complexity class MA, a class which contains period-finding over the\nintegers.",
"arxiv_id": "quant-ph/0212002",
"authors": [
"Lisa R. Hales"
],
"categories": [
"quant-ph"
],
"title": "The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem",
"url": "https://arxiv.org/abs/quant-ph/0212002"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cdd1605a-bc42-4409-8a04-0a6930fbe959",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}