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

Noah Linden1 and Ronald de Wolf2

1School of Mathematics, University of Bristol. n.linden@bristol.ac.uk
2QuSoft, CWI and University of Amsterdam, the Netherlands. rdewolf@cwi.nl

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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.

The quantum Fourier transform (QFT) is a key primitive that is typically used as a subroutine within a larger quantum computation. As such, we may have little control over the state that is input to the QFT. We show that good performance of the QFT on an $average$ input state (1) is efficiently testable, and (2) suffices to achieve good $worst$-$case$ performance for QFT-based tasks such as phase estimation, period finding and amplitude estimation.

► BibTeX data

► References

[1] 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.

[2] 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.

[3] 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.

[4] Chi-Fang Chen and Fernando G. S. L. Brandão. Concentration for Trotter error. arXiv:2111.05324, 9 Nov 2021.

[5] 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.

[6] Don Coppersmith. An approximate Fourier transform useful in quantum factoring. IBM Research Report No. RC19642, quant-ph/​0201067, 1994.

[7] 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.

[8] 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.

[9] Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few Pauli measurements. Physical Review Letters, 106:230501, 2011. arXiv:1104.4695.

[10] 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.

[11] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of 28th ACM STOC, pages 212–219, 1996. quant-ph/​9605043.

[12] 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.

[13] Stephen P. Jordan. Fast quantum algorithm for numerical gradient estimation. Physical Review Letters, 95:050501, 2005. quant-ph/​0405146.

[14] Alexey Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. quant-ph/​9511026, 12 Nov 1995.

[15] 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.

[16] Urmila Mahadev. Classical verification of quantum computations. In Proceedings of 59th IEEE FOCS, pages 259–267, 2018. arXiv:1804.01082.

[17] 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.

[18] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

[19] Patrick Rall. Faster coherent quantum algorithms for phase, energy, and amplitude estimation. Quantum, 5(566), 2021. arXiv:2103.09717.

[20] 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.

[21] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs. Hamiltonian simulation with random inputs. arXiv:2111.04773, 8 Nov 2021.

Cited by

[1] Patrick Rall and Bryce Fuller, "Amplitude Estimation from Quantum Signal Processing", Quantum 7, 937 (2023).

[2] 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).

[3] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini, "Quantum tomography using state-preparation unitaries", arXiv:2207.08800, (2022).

[4] Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, and Sathyawageeswar Subramanian, "Quantum Worst-Case to Average-Case Reductions for All Linear Problems", arXiv:2212.03348, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-24 20:12:31) and SAO/NASA ADS (last updated successfully 2024-05-24 20:12:32). The list may be incomplete as not all publishers provide suitable and complete citation data.