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.