Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation PlatoBlockchain Data Intelligence. Vertical Search. Ai.

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

Time Stamp: December 7, 2022 11:15 AM

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.

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

â–º 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.

The above citations are from SAO/NASA ADS (last updated successfully 2022-12-08 04:24:57). 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 2022-12-08 04:24:56).

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.

Time Stamp:

More from Quantum Journal