  The quantum Fourier transform (QFT) plays an important role in many known
quantum algorithms such as Shor's algorithm for prime factorisation. In this
paper we show that the QFT algorithm can, on a restricted set of input states,
be de-quantised into a classical algorithm which is both more efficient and
simpler than the quantum algorithm. By working directly with the algorithm
instead of the circuit, we develop a simple classical version of the quantum
basis-state algorithm. We formulate conditions for a separable state to remain
separable after the QFT is performed, and use these conditions to extend the
de-quantised algorithm to work on all such states without loss of efficiency.
Our technique highlights the linearity of quantum mechanics as the fundamental
feature accounting for the difference between quantum and de-quantised
algorithms, and that it is this linearity which makes the QFT such a useful
tool in quantum computation.
