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.
 Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified. In Proceedings of 3rd Symposium on Simplicity in Algorithms (SOSA), pages 24–32, 2020. arXiv:1908.10846.
 Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997. quant-ph/9701001.
 Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pages 53–74. 2002. quant-ph/0005055.
 Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. In Proceedings of the Royal Society of London, volume A454, pages 339–354, 1998. quant-ph/9708016.
 Don Coppersmith. An approximate Fourier transform useful in quantum factoring. IBM Research Report No. RC19642, quant-ph/0201067, 1994.
 Marcus da Silva, Oliver Landon-Cardinal, and David Poulin. Practical characterization of quantum devices without tomography. Physical Review Letters, 107:210404, 2011. arXiv:1104.3835.
 Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. Quantum certification and benchmarking. Nature Reviews Physics, 2:382–390, 2020. arXiv:1910.06343.
 Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few Pauli measurements. Physical Review Letters, 106:230501, 2011. arXiv:1104.4695.
 András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation. In Proceedings of 30th ACM-SIAM SODA, pages 1425–1444, 2019. arXiv:1711.00465.
 Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of 28th ACM STOC, pages 212–219, 1996. quant-ph/9605043.
 András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of 51st ACM STOC, pages 193–204, 2019. arXiv:1806.01838.
 Stephen P. Jordan. Fast quantum algorithm for numerical gradient estimation. Physical Review Letters, 95:050501, 2005. quant-ph/0405146.
 Alexey Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. quant-ph/9511026, 12 Nov 1995.
 Noah Linden and Ronald de Wolf. Lightweight detection of a small number of large errors in a quantum circuit. Quantum, 5(436), 2021. arXiv:2009.08840.
 Urmila Mahadev. Classical verification of quantum computations. In Proceedings of 59th IEEE FOCS, pages 259–267, 2018. arXiv:1804.01082.
 John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. A grand unification of quantum algorithms. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
 Patrick Rall. Faster coherent quantum algorithms for phase, energy, and amplitude estimation. Quantum, 5(566), 2021. arXiv:2103.09717.
 Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. Earlier version in FOCS'94. quant-ph/9508027.
 Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs. Hamiltonian simulation with random inputs. arXiv:2111.04773, 8 Nov 2021.
 Patrick Rall and Bryce Fuller, "Amplitude Estimation from Quantum Signal Processing", Quantum 7, 937 (2023).
 Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).
The above citations are from Crossref's cited-by service (last updated successfully 2023-12-07 08:17:51) and SAO/NASA ADS (last updated successfully 2023-12-07 08:17:52). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.