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

Noah Linden; Ronald de Wolf

doi:10.22331/q-2022-12-07-872

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

Noah Linden¹ and Ronald de Wolf²

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

Published:	2022-12-07, volume 6, page 872
Eprint:	arXiv:2109.10215v3
Doi:	https://doi.org/10.22331/q-2022-12-07-872
Citation:	Quantum 6, 872 (2022).

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.

Popular summary

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

@article{Linden2022averagecase,
  doi = {10.22331/q-2022-12-07-872},
  url = {https://doi.org/10.22331/q-2022-12-07-872},
  title = {Average-{C}ase {V}erification of the {Q}uantum {F}ourier {T}ransform {E}nables {W}orst-{C}ase {P}hase {E}stimation},
  author = {Linden, Noah and de Wolf, Ronald},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {872},
  month = dec,
  year = {2022}
}

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