Quantum Fourier sampling simplified

Lisa Hales; Sean Hallgren

doi:10.1145/301250.301336

Quantum Fourier sampling simplified

Lisa Hales, Sean Hallgren

Computer Science and Engineering

Research output: Contribution to journal › Conference article › peer-review

14 Scopus citations

Abstract

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 Z_p can be efficiently approximated by transforming over Z_q 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 language	English (US)
Pages (from-to)	330-338
Number of pages	9
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/301250.301336
State	Published - 1999
Event	Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA Duration: May 1 1999 → May 4 1999

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/301250.301336

Cite this

@article{c2c9eccc520947a5a600f3e985d3498e,

title = "Quantum Fourier sampling simplified",

abstract = "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.",

author = "Lisa Hales and Sean Hallgren",

year = "1999",

doi = "10.1145/301250.301336",

language = "English (US)",

pages = "330--338",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 ; Conference date: 01-05-1999 Through 04-05-1999",

}

TY - JOUR

T1 - Quantum Fourier sampling simplified

AU - Hales, Lisa

AU - Hallgren, Sean

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032686325&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032686325&partnerID=8YFLogxK

U2 - 10.1145/301250.301336

DO - 10.1145/301250.301336

M3 - Conference article

AN - SCOPUS:0032686325

SN - 0734-9025

SP - 330

EP - 338

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99

Y2 - 1 May 1999 through 4 May 1999

ER -

Quantum Fourier sampling simplified

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this