Simplified proof of the Fourier Sampling Theorem

Scott Aaronson

Benjamin Johnson

Lisa Hales, Sean Hallgren

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 Z, 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.

Bernd Thaller

Matthew McKague

We consider the recursive Fourier sampling problem (RFS), and show that there exists an interactive proof for RFS with an efficient classical verifier and efficient quantum prover.

Carlo Jacoboni