{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T04:28:49Z","timestamp":1781584129267,"version":"3.54.5"},"reference-count":21,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T00:00:00Z","timestamp":1670371200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"UK Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/R043957\/1, EP\/S005021\/1, EP\/T001062\/1"],"award-info":[{"award-number":["EP\/R043957\/1, EP\/S005021\/1, EP\/T001062\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"crossref","award":["Gravitation-grant Quantum Software Consortium, 024.003.037, and QuantERA ERA-NET Cofund project QuantAlgo 680-91-034"],"award-info":[{"award-number":["Gravitation-grant Quantum Software Consortium, 024.003.037, and QuantERA ERA-NET Cofund project QuantAlgo 680-91-034"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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 \u2013 phase estimation, period finding and amplitude estimation. Further we give a very efficient procedure to verify this required average-case behaviour of the QFT.<\/jats:p>","DOI":"10.22331\/q-2022-12-07-872","type":"journal-article","created":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T16:42:19Z","timestamp":1670431339000},"page":"872","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":4,"title":["Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation"],"prefix":"10.22331","volume":"6","author":[{"given":"Noah","family":"Linden","sequence":"first","affiliation":[{"name":"School of Mathematics, University of Bristol. n.linden@bristol.ac.uk"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronald","family":"de Wolf","sequence":"additional","affiliation":[{"name":"QuSoft, CWI and University of Amsterdam, the Netherlands. rdewolf@cwi.nl"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2022,12,7]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified. In Proceedings of 3rd Symposium on Simplicity in Algorithms (SOSA), pages 24\u201332, 2020. arXiv:1908.10846.","DOI":"10.1137\/1.9781611976014.5"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510\u20131523, 1997. quant-ph\/9701001.","DOI":"10.1137\/S0097539796300933"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Gilles Brassard, Peter H\u00f8yer, 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\u201374. 2002. quant-ph\/0005055.","DOI":"10.1090\/conm\/305\/05215"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Chi-Fang Chen and Fernando G. S. L. Brand\u00e3o. Concentration for Trotter error. arXiv:2111.05324, 9 Nov 2021.","DOI":"10.48550\/arXiv.2111.05324"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. In Proceedings of the Royal Society of London, volume A454, pages 339\u2013354, 1998. quant-ph\/9708016.","DOI":"10.1098\/rspa.1998.0164"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Don Coppersmith. An approximate Fourier transform useful in quantum factoring. IBM Research Report No. RC19642, quant-ph\/0201067, 1994.","DOI":"10.48550\/arXiv.quant-ph\/0201067"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.107.210404"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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\u2013390, 2020. arXiv:1910.06343.","DOI":"10.1038\/s42254-020-0186-4"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few Pauli measurements. Physical Review Letters, 106:230501, 2011. arXiv:1104.4695.","DOI":"10.1103\/PhysRevLett.106.230501"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation. In Proceedings of 30th ACM-SIAM SODA, pages 1425\u20131444, 2019. arXiv:1711.00465.","DOI":"10.1137\/1.9781611975482.87"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of 28th ACM STOC, pages 212\u2013219, 1996. quant-ph\/9605043.","DOI":"10.1145\/237814.237866"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, 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\u2013204, 2019. arXiv:1806.01838.","DOI":"10.1145\/3313276.3316366"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Stephen P. Jordan. Fast quantum algorithm for numerical gradient estimation. Physical Review Letters, 95:050501, 2005. quant-ph\/0405146.","DOI":"10.1103\/PhysRevLett.95.050501"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Alexey Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. quant-ph\/9511026, 12 Nov 1995.","DOI":"10.48550\/arXiv.quant-ph\/9511026"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2021-04-20-436"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Urmila Mahadev. Classical verification of quantum computations. In Proceedings of 59th IEEE FOCS, pages 259\u2013267, 2018. arXiv:1804.01082.","DOI":"10.1109\/FOCS.2018.00033"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PRXQuantum.2.040203"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.","DOI":"10.1017\/CBO9780511976667"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Patrick Rall. Faster coherent quantum algorithms for phase, energy, and amplitude estimation. Quantum, 5(566), 2021. arXiv:2103.09717.","DOI":"10.22331\/q-2021-10-19-566"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484\u20131509, 1997. Earlier version in FOCS&apos;94. quant-ph\/9508027.","DOI":"10.1137\/S0097539795293172"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs. Hamiltonian simulation with random inputs. arXiv:2111.04773, 8 Nov 2021.","DOI":"10.48550\/arXiv.2111.04773"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-12-07-872\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,12,10]],"date-time":"2022-12-10T03:05:43Z","timestamp":1670641543000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-12-07-872\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,7]]},"references-count":21,"URL":"https:\/\/doi.org\/10.22331\/q-2022-12-07-872","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,7]]},"article-number":"872"}}