SEMICLASSICAL FOURIER-TRANSFORM FOR QUANTUM COMPUTATION

It is shown that the Fourier transform preceding the final measurement in Shor's algorithm for factorization on a quantum computer can be ca rried out in a semiclassical way by using the ''classical'' (macroscop ic) signal resulting from measuring one bit to determine the type of m easurement 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 smalle r number of one-bit gates controlled by classical signals. This sugges ts that it may be worthwhile looking for other uses of semiclassical m ethods in quantum computing.