# 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.

### 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.

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.

### ► 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.
https:/​/​doi.org/​10.1137/​1.9781611976014.5
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.
https:/​/​doi.org/​10.1137/​S0097539796300933
arXiv: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.
https:/​/​doi.org/​10.1090/​conm/​305/​05215
arXiv:quant-ph/0005055

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

[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.
https:/​/​doi.org/​10.1098/​rspa.1998.0164
arXiv:quant-ph/9708016

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

[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.
https:/​/​doi.org/​10.1103/​PhysRevLett.107.210404
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.
https:/​/​doi.org/​10.1038/​s42254-020-0186-4
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.
https:/​/​doi.org/​10.1103/​PhysRevLett.106.230501
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.
https:/​/​doi.org/​10.1137/​1.9781611975482.87
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.
https:/​/​doi.org/​10.1145/​237814.237866
arXiv: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.
https:/​/​doi.org/​10.1145/​3313276.3316366
arXiv:1806.01838

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

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

[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.
https:/​/​doi.org/​10.22331/​q-2021-04-20-436
arXiv:2009.08840

[16] Urmila Mahadev. Classical verification of quantum computations. In Proceedings of 59th IEEE FOCS, pages 259–267, 2018. arXiv:1804.01082.
https:/​/​doi.org/​10.1109/​FOCS.2018.00033
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.
https:/​/​doi.org/​10.1103/​PRXQuantum.2.040203

[18] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.
https:/​/​doi.org/​10.1017/​CBO9780511976667

[19] Patrick Rall. Faster coherent quantum algorithms for phase, energy, and amplitude estimation. Quantum, 5(566), 2021. arXiv:2103.09717.
https:/​/​doi.org/​10.22331/​q-2021-10-19-566
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.
https:/​/​doi.org/​10.1137/​S0097539795293172
arXiv: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.
https:/​/​doi.org/​10.48550/​arXiv.2111.04773
arXiv:2111.04773

### Cited by

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

[2] 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 SAO/NASA ADS (last updated successfully 2023-02-07 15:49:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-02-07 15:49:47).