Semiclassical Fourier Transform for Quantum Computation

Abstract

It is shown that the Fourier transform preceding the final measurement in Shor's algorithm for factorization on a quantum computer can be carried out in a semiclassical way by using the “classical” (macroscopic) signal resulting from measuring one bit to determine the type of measurement carried out on the next bit, and so forth. In this way all the two-bit gates in the Fourier transform can be replaced by a smaller number of one-bit gates controlled by classical signals. This suggests that it may be worthwhile looking for other uses of semiclassical methods in quantum computing.