Quantum Fourier sampling simplified

Lisa Hales, Sean Hallgren

Research output: Contribution to journalConference articlepeer-review

14 Scopus citations


We isolate and generalize a technique implicit in many quantum algorithms, including Shor's algorithms for factoring and discrete log. In particular, we show that the distribution sampled after a Fourier transform over Zp can be efficiently approximated by transforming over Zq for any q in a large range. Our result places no restrictions on the superposition to be transformed, generalizing previous applications. In addition, our proof easily generalizes to multi-dimensional transforms for any constant number of dimensions.

Original languageEnglish (US)
Pages (from-to)330-338
Number of pages9
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 1999
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Quantum Fourier sampling simplified'. Together they form a unique fingerprint.

Cite this