Sampling Fourier Transforms on Different Domains

Simple item page
dc.creatorHales, Lisa
dc.creatorHallgren, Sean
dc.date1998-12-21
dc.date.accessioned2026-07-07T06:15:56Z
dc.date.available2026-07-07T06:15:56Z
dc.descriptionWe 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 ${\mathbb Z}_p$ can be efficiently approximated by transforming over ${\mathbb Z}_q$ for any q in a large range. Our result places no restrictions on the superposition to be transformed, generalizing the result implicit in Shor which applies only to periodic superpositions. In addition, our proof easily generalizes to multi-dimensional transforms for any constant number of dimensions.
dc.description17 pages. Preliminary draft
dc.identifierhttps://arxiv.org/abs/quant-ph/9812060
dc.identifierhttp://arxiv.org/abs/quant-ph/9812060
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/93915
dc.subjectQuantum Physics
dc.titleSampling Fourier Transforms on Different Domains
dc.typetext

Files

Collections

arXiv