  The quantum Fourier transform (QFT) is a key primitive for quantum computing
that is typically used as a subroutine within a larger computation, for
instance for phase estimation. As such, we may have little control over the
state that is input to the QFT. Thus, in implementing a good QFT, we may
imagine that it needs to perform well on arbitrary input states. Verifying this
worst-case correct behaviour of a QFT-implementation would be exponentially
hard (in the number of qubits) in general, raising the concern that this
verification would be impossible in practice on any useful-sized system. In
this paper we show that, in fact, we only need to have good average-case
performance of the QFT to achieve good worst-case performance for key tasks --
phase estimation, period finding and amplitude estimation. Further we give a
very efficient procedure to verify this required average-case behaviour of the
QFT.
