Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation
arXiv:2109.10215 · doi:10.22331/q-2022-12-07-872
Abstract
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.
arXiv comment18 pages LaTeX. Version 3: small changes for final version that will appear in Quantum
References in corpus (15)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Strengths and Weaknesses of Quantum Computing
- Quantum Amplitude Amplification and Estimation
- Quantum Algorithms Revisited
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Direct Fidelity Estimation from Few Pauli Measurements
- Quantum measurements and the Abelian Stabilizer Problem
- A Grand Unification of Quantum Algorithms
- Quantum certification and benchmarking
- An approximate Fourier transform useful in quantum factoring
- Practical characterization of quantum devices without tomography
- Fast quantum algorithm for numerical gradient estimation
- Quantum Approximate Counting, Simplified
- Optimizing quantum optimization algorithms via faster quantum gradient computation
- Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit