An improved quantum Fourier transform algorithm and applications
The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
Abstract
We give an algorithm for approximating the quantum Fourier transform over an arbitrary Z/sub p/ which requires only O(n log n) steps where n=log p to achieve an approximation to within an arbitrary inverse polynomial in n. This improves the method of A.Y. Kitaev (1995) which requires time quadratic in n. This algorithm also leads to a general and efficient Fourier sampling technique which improves upon the quantum Fourier sampling lemma of L. Hales and S. Hallgren (1997). As an application of this technique, we give a quantum algorithm which finds the period of an arbitrary periodic function, i.e. a function which may be many-to-one within each period. We show that this algorithm is efficient (polylogarithmic in the period of the function) for a large class of periodic functions. Moreover, using standard quantum lower-bound techniques, we show that this characterization is right. That is, this is the maximal class of periodic functions with an efficient quantum period-finding algorithm.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Bernstein, E., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300921 · Cited by 1,503
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470 · cited 2×
“Moreover, to produce a superpositionj i such that kj i Fpj ik the largest transform can be taken to be a power of 2 with justO (n+ log(1= )) bits.”
BackgroundCleve, R., Ekert, A., Macchiavello, C., & Mosca, M. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0164 · Cited by 1,299 · cited 1×
“That is, this is the maximal class of periodic functions with an efficient quantum period-finding algorithm.”
BackgroundOn the Power of Quantum Computation
Simon, D. R. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796298637 · Cited by 1,295
Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284 · cited 2×
“We wish to use this behavior to generate a functiong 2 C1=d(n) which has period greater than 1 and which the algorithm cannot distinguish from the all-zeroes function without making lots of queries.”
BackgroundMethodQuantum measurements and the Abelian Stabilizer ProblemPreprint
Kitaev, A. (1995) · arXiv (Cornell University) · Cited by 510
An approximate Fourier transform useful in quantum factoring
Coppersmith, D. (2002) · arXiv · doi:10.48550/arxiv.quant-ph/0201067 · Cited by 343
Quantum Cryptanalysis of Hidden Linear Functions
Boneh, D., & Lipton, R. J. (1995) · Lecture Notes in Computer Science · doi:10.1007/3-540-44750-4_34 · Cited by 161 · cited 2×
“We need the following definition and theorem from [1] Definition 3 Let j ii be the superposition ofAf on inputx at timei.”
BackgroundNormal subgroup reconstruction and quantum computation using group representations
Hallgren, S., Russell, A. C., & Ta‐Shma, A. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335392 · Cited by 133 · cited 1×
“That is, this is the maximal class of periodic functions with an efficient quantum period-finding algorithm.”
BackgroundSelf-citation
Cited by
Shor's discrete logarithm quantum algorithm for elliptic curves
Proos, J., & Zalka, C. (2003) · Quantum Information and Computation · doi:10.26421/qic3.4-3 · Cited by 421
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344
“antum computation, we must implement it (approximately) by a quantum circuit of size poly(log|G|). This can indeed be doneforanyfiniteAbeliangroup( Barenco et al.,1996; Cleve, 1994; Coppersmith, 1994; Hales and Hallgren, 2000; Kitaev, 1995; Shor, 1997). In this section we explain a construction for the case of the grou…”
BackgroundMethodA survey of quantum image representations
Yan, F., Iliyasu, A. M., & Venegas-Andraca, S. E. (2016) · Quantum Information Processing · doi:10.1007/s11128-015-1195-6 · Cited by 310
Efficient quantum walk on a quantum processor
Qiang, X., Loke, T., Montanaro, A., Aungskunsiri, K., Zhou, X., O’Brien, J. L., Wang, J. B., & Matthews, J. C. F. (2016) · Nature Communications · doi:10.1038/ncomms11511 · Cited by 108
Classification with Quantum Machine Learning: A Survey
Abohashima, Z., Elhosen, M., Houssein, E. H., & Mohamed, W. M. (2020) · arXiv · doi:10.48550/arxiv.2006.12270 · Cited by 68
Quantum Computing in Civil Engineering: Potentials and Limitations
Ploennigs, J., Berger, M., Mevissen, M., & Smarsly, K. (2025) · Lecture Notes in Civil Engineering · doi:10.1007/978-3-031-87364-5_2 · Cited by 7
Metadata
- Authors
- Hales, L., & Hallgren, S.
- Venue
- Proceedings 41st Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-07
- Pages
- 515-525
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2156190205
- Cited by
- 162
- References
- 16
- FWCI
- 6.80
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.