Average-case verification of the quantum Fourier transform enables worst-case phase estimation
Quantum , Volume 6 p. 872.1- 872.18
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.
|Organisation||Algorithms and Complexity|
Linden, N, & de Wolf, R.M. (2022). Average-case verification of the quantum Fourier transform enables worst-case phase estimation. Quantum, 6, 872.1–872.18. doi:10.22331/q-2022-12-07-872