Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation

Understand

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.