Tight Bounds for Quantum Phase Estimation and Related Problems
Summarize this article with:
AbstractPhase estimation, due to Kitaev [17], is one of the most fundamental subroutines in quantum computing. In the basic scenario, one is given black-box access to a unitary $U$, and an eigenstate $\lvert \psi \rangle$ of $U$ with unknown eigenvalue $e^{i\theta}$, and the task is to estimate the eigenphase $\theta$ within $\pm\delta$, with high probability. The cost of an algorithm for us is the number of applications of $U$ and $U^{-1}$. We tightly characterize the cost of several variants of phase estimation where we are no longer given an eigenstate, but are required to estimate the maximum eigenphase of $U$, aided by advice in the form of states (or a unitary preparing those states) which are promised to have at least a certain overlap $\gamma$ with the top eigenspace. We give algorithms and nearly matching lower bounds for all ranges of parameters. We show that a small number of copies of the advice state (or of an advice-preparing unitary) are not significantly better than having no advice at all. We also show that having lots of advice (applications of the advice-preparing unitary) does not significantly reduce cost, and neither does knowledge of the eigenbasis of $U$. We immediately obtain a lower bound on the complexity of the Unitary recurrence time problem, resolving an open question of She and Yuen [29]. Lastly, we study how efficiently one can reduce the error probability in the basic phase-estimation scenario. We show that a phase-estimation algorithm with precision $\delta$ and error probability $\epsilon$ has cost $\Omega\left(\frac{1}{\delta}\log\frac{1}{\epsilon}\right)$, matching an easy upper bound. This contrasts with some other scenarios in quantum computing (e.g., search) where error-probability reduction costs only a factor $O(\sqrt{\log(1/\epsilon)})$. Our lower bound uses a variant of the polynomial method with trigonometric polynomials.► BibTeX data@article{Mande2026tightboundsquantum, doi = {10.22331/q-2026-06-15-2140}, url = {https://doi.org/10.22331/q-2026-06-15-2140}, title = {Tight {B}ounds for {Q}uantum {P}hase {E}stimation and {R}elated {P}roblems}, author = {Mande, Nikhil S. and Wolf, Ronald de}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2140}, month = jun, year = {2026} }► References [1] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. Quantum, 4:230, 2020. arXiv:1705.01843. Earlier version in FOCS'17. doi:10.22331/q-2020-02-14-230. https://doi.org/10.22331/q-2020-02-14-230 arXiv:1705.01843 [2] Andris Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750–767, 2002. Earlier version in STOC'00. doi:10.1006/jcss.2002.1826. https://doi.org/10.1006/jcss.2002.1826 [3] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. quant-ph/9802049. Earlier version in FOCS'98. doi:10.1145/502090.502097. https://doi.org/10.1145/502090.502097 arXiv:quant-ph/9802049 [4] Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. Bounds for small-error and zero-error quantum algorithms. In Proceedings of 40th IEEE FOCS, pages 358–368, 1999. arXiv:cs/9904019. doi:10.1109/SFFCS.1999.814607. https://doi.org/10.1109/SFFCS.1999.814607 arXiv:cs/9904019 [5] Peter Borwein and Tamás Erdélyi. Polynomials and polynomial inequalities, volume 161. Springer Science & Business Media, 1995. doi:10.1007/978-1-4612-0793-1. https://doi.org/10.1007/978-1-4612-0793-1 [6] Arvid J. Bessen. Lower bound for quantum phase estimation. Physical Review A, 71(4):042313, 2005. doi:10.1103/PhysRevA.71.042313. https://doi.org/10.1103/PhysRevA.71.042313 [7] 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. arXiv:quant-ph/0005055. https://doi.org/10.1090/conm/305/05215 arXiv:quant-ph/0005055 [8] 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. doi:10.1098/rspa.1998.0164. https://doi.org/10.1098/rspa.1998.0164 arXiv:quant-ph/9708016 [9] Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans. Improved hardness results for the guided local hamiltonian problem. In Proceedings of 50th ICALP, pages 32:1–32:19, 2023. arXiv:2207.10250. doi:10.4230/LIPICS.ICALP.2023.32. https://doi.org/10.4230/LIPICS.ICALP.2023.32 arXiv:2207.10250 [10] Yanlin Chen and Ronald de Wolf. Quantum algorithms and lower bounds for linear regression with norm constraints. In Proceedings of 50th ICALP, volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1–38:21, 2023. arXiv:2110.13086. doi:10.4230/LIPIcs.ICALP.2023.38. https://doi.org/10.4230/LIPIcs.ICALP.2023.38 arXiv:2110.13086 [11] Sevag Gharibian and François Le Gall. Dequantizing the quantum singular value transformation: Hardness and applications to quantum chemistry and the quantum PCP conjecture. SIAM Journal on Computing, 52(4):1009–1038, 2023. Earlier version in STOC'22. doi:10.1137/22M1513721. https://doi.org/10.1137/22M1513721 [12] András Gilyén.
Quantum Singular Value Transformation & Its Algorithmic Applications. PhD thesis, University of Amsterdam, 2019. URL: https://pure.uva.nl/ws/files/35292358/Thesis.pdf. https://pure.uva.nl/ws/files/35292358/Thesis.pdf [13] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of 28th ACM STOC, pages 212–219, 1996. quant-ph/9605043. doi:10.1145/237814.237866. https://doi.org/10.1145/237814.237866 arXiv:quant-ph/9605043 [14] 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. doi:10.1145/3313276.3316366. https://doi.org/10.1145/3313276.3316366 arXiv:1806.01838 [15] Yimin Ge, Jordi Tura, and J. Ignacio Cirac. Faster ground state preparation and high-precision ground energy estimation with fewer qubits. Journal of Mathematical Physics, 60(2):022202, 2019. arXiv:1712.03193. doi:10.1063/1.5027484. https://doi.org/10.1063/1.5027484 arXiv:1712.03193 [16] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for solving linear systems of equations.
Physical Review Letters, 103(15):150502, 2009. arXiv:0811.3171. URL: https://doi.org/10.1103/PhysRevLett.103.150502. https://doi.org/10.1103/PhysRevLett.103.150502 arXiv:0811.3171 [17] A. Yu. Kitaev. Quantum measurements and the abelian stabilizer problem, 1995. arXiv:quant-ph/9511026. arXiv:quant-ph/9511026 [18] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J. Yoder. Hamiltonian simulation with optimal sample complexity. npj Quantum Information, 3(13), 2017. arXiv:1608.00281. doi:10.1038/s41534-017-0013-7. https://doi.org/10.1038/s41534-017-0013-7 arXiv:1608.00281 [19] Yao-Ting Lin. A note on quantum phase estimation. 2023. arXiv:2304.02241. arXiv:2304.02241 [20] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10:631–633, 2013. arXiv:1307.0401. doi:10.1038/nphys3029. https://doi.org/10.1038/nphys3029 arXiv:1307.0401 [21] Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4(372), 2020. arXiv:2002.12508. doi:10.22331/q-2020-12-14-372. https://doi.org/10.22331/q-2020-12-14-372 arXiv:2002.12508 [22] Lin Lin and Yu Tong. Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3(010318), 2022. arXiv:2102.11340. doi:10.1103/PRXQuantum.3.010318. https://doi.org/10.1103/PRXQuantum.3.010318 arXiv:2102.11340 [23] Noah Linden and Ronald de Wolf. Average-case verification of the quantum Fourier transform enables worst-case phase estimation. Quantum, 6(872), 2022. arXiv:2109.10215. doi:10.22331/q-2022-12-07-872. https://doi.org/10.22331/q-2022-12-07-872 arXiv:2109.10215 [24] Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of 31st ACM STOC, pages 384–393, 1999. doi:10.1145/301250.301349. https://doi.org/10.1145/301250.301349 [25] Alberto Peruzzo, Jerrad McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter Love, Alán Aspuru-Guzik, and Jeremy O’Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 3:24, 2014. arXiv:1304.3061. doi:10.1038/ncomms5213. https://doi.org/10.1038/ncomms5213 arXiv:1304.3061 [26] David Poulin and Pawel Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer.
Physical Review Letters, 103(22):220502, 2009. arXiv:0905.2199. doi:10.1103/PhysRevLett.103.220502. https://doi.org/10.1103/PhysRevLett.103.220502 arXiv:0905.2199 [27] 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. https://doi.org/10.22331/q-2021-10-19-566 arXiv:2103.09717 [28] 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. doi:10.1137/S0097539795293172. https://doi.org/10.1137/S0097539795293172 arXiv:quant-ph/9508027 [29] Adrian She and Henry Yuen. Unitary property testing lower bounds by polynomials. In Proceedings of 14th ITCS, volume 251, pages 96:1–96:17, 2023. arXiv:2210.05885. doi:10.4230/LIPIcs.ITCS.2023.96. https://doi.org/10.4230/LIPIcs.ITCS.2023.96 arXiv:2210.05885 [30] Kianna Wan, Mario Berta, and Earl T. Campbell. A randomized quantum algorithm for statistical phase estimation.
Physical Review Letters, 129(030503), 2022. arXiv:2110.12071. doi:10.1103/PhysRevLett.129.030503. https://doi.org/10.1103/PhysRevLett.129.030503 arXiv:2110.12071 [31] Jordi Weggemans, Marten Folkertsma, and Chris Cade.
Guidable Local Hamiltonian problems with implications to heuristic ansatz state preparation and the quantum PCP conjecture. In Proceedings of 19th TQC, pages 10:1–10:24, 2024. arXiv:2302.11578. doi:10.4230/LIPIcs.TQC.2024.10. https://doi.org/10.4230/LIPIcs.TQC.2024.10 arXiv:2302.11578 [32] Ronald de Wolf. A note on quantum algorithms and the minimal degree of $\varepsilon$-error polynomials for symmetric functions. Quantum Information and Computation, 8(10):943–950, 2008. arXiv:0802.1816. arXiv:0802.1816 [33] Ronald de Wolf. Quantum computing: Lecture notes, 2019. arXiv:1907.09415, version 5. URL: http://arxiv.org/abs/1907.09415. arXiv:1907.09415Cited by[1] 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). [2] Kapil Goswami, Peter Schmelcher, and Rick Mukherjee, "Qudit-based scalable quantum algorithm for solving the integer programming problem", arXiv:2508.13906, (2025). [3] Matthew P. Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D. Malone, Ryan Babbush, and Nicholas C. Rubin, "Expressing and Analyzing Quantum Algorithms with Qualtran", arXiv:2409.04643, (2024). [4] Muhammad Shaeer Moeed, James Brown, Alexander Ibrahim, Estêvão V. B. de Oliveira, and Pierre-Nicholas Roy, "Qubit encodings for lattices of dipolar planar rotors", Journal of Chemical Physics 163 17, 174103 (2025). [5] Hikaru Wakaura, "Quantum Reservoir GAN", arXiv:2508.05716, (2025). [6] Qisheng Wang and Zhicheng Zhang, "Quantum Lower Bounds by Sample-to-Query Lifting", arXiv:2308.01794, (2023). [7] Alexander M. Dalzell, András Gilyén, Connor T. Hann, Sam McArdle, Grant Salton, Quynh T. Nguyen, Aleksander Kubica, and Fernando G. S. L. Brandão, "A distillation-teleportation protocol for fault-tolerant QRAM", arXiv:2505.20265, (2025). [8] Alexander Zlokapa and Rolando D. Somma, "Hamiltonian simulation for low-energy states with optimal time dependence", Quantum 8, 1449 (2024). [9] Alex Kerzner, Vlad Gheorghiu, Michele Mosca, Thomas Guilbaud, Federico Carminati, Fabio Fracas, and Luca Dellantonio, "A square-root speedup for finding the smallest eigenvalue", Quantum Science and Technology 9 4, 045025 (2024). [10] George T. Fleming, Prasanth Shyamsundar, and Judah Unmuth-Yockey, "Fermion determinants on a quantum computer", Physical Review D 111 5, 054509 (2025). [11] Matthias Deiml and Daniel Peterseim, "Quantum Realization of the Finite Element Method", arXiv:2403.19512, (2024). [12] Mihael Erakovic, Freek Witteveen, Dylan Harley, Jakob Günther, Moritz Bensberg, Oinam Romesh Meitei, Minsik Cho, Troy Van Voorhis, Markus Reiher, and Matthias Christandl, "High Ground State Overlap via Quantum Embedding Methods", PRX Life 3 1, 013003 (2025). [13] Jordi Weggemans, "Lower Bounds for Unitary Property Testing with Proofs and Advice", Quantum 9, 1717 (2025). [14] Robbie King, Guang Hao Low, Ryan Babbush, Rolando D. Somma, and Nicholas C. Rubin, "Quantum Simulation with Sum-of-Squares Spectral Amplification", Physical Review Letters 136 11, 110601 (2026). [15] Matthias Deiml and Daniel Peterseim, "Nonlinear quantum computation by amplified encodings", arXiv:2411.16435, (2024). [16] Emanuele Costa and Javier Menendez, "Improved quasiparticle nuclear Hamiltonians for quantum computing", arXiv:2604.11381, (2026). [17] Yukun Zhang, Xiaoming Zhang, Jinzhao Sun, Heng Lin, Yifei Huang, Dingshun Lv, and Xiao Yuan, "Fault-tolerant quantum algorithms for quantum molecular systems: A survey", arXiv:2502.02139, (2025). [18] Dan Li and Lei Zhong, "Efficient preparation method for arbitrary multiqubit states based on quantum walk", Quantum Information Processing 24 11, 343 (2025). [19] Hikaru Wakaura, "Generative Adversarial Variational Quantum Kolmogorov-Arnold Network", arXiv:2512.11014, (2025). [20] Sophia Simon, Dominic W. Berry, and Rolando D. Somma, "Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems", arXiv:2605.16195, (2026). The above citations are from SAO/NASA ADS (last updated successfully 2026-06-15 14:10:16). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-06-15 14:10:15: Could not fetch cited-by data for 10.22331/q-2026-06-15-2140 from Crossref. This is normal if the DOI was registered recently.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. AbstractPhase estimation, due to Kitaev [17], is one of the most fundamental subroutines in quantum computing. In the basic scenario, one is given black-box access to a unitary $U$, and an eigenstate $\lvert \psi \rangle$ of $U$ with unknown eigenvalue $e^{i\theta}$, and the task is to estimate the eigenphase $\theta$ within $\pm\delta$, with high probability. The cost of an algorithm for us is the number of applications of $U$ and $U^{-1}$. We tightly characterize the cost of several variants of phase estimation where we are no longer given an eigenstate, but are required to estimate the maximum eigenphase of $U$, aided by advice in the form of states (or a unitary preparing those states) which are promised to have at least a certain overlap $\gamma$ with the top eigenspace. We give algorithms and nearly matching lower bounds for all ranges of parameters. We show that a small number of copies of the advice state (or of an advice-preparing unitary) are not significantly better than having no advice at all. We also show that having lots of advice (applications of the advice-preparing unitary) does not significantly reduce cost, and neither does knowledge of the eigenbasis of $U$. We immediately obtain a lower bound on the complexity of the Unitary recurrence time problem, resolving an open question of She and Yuen [29]. Lastly, we study how efficiently one can reduce the error probability in the basic phase-estimation scenario. We show that a phase-estimation algorithm with precision $\delta$ and error probability $\epsilon$ has cost $\Omega\left(\frac{1}{\delta}\log\frac{1}{\epsilon}\right)$, matching an easy upper bound. This contrasts with some other scenarios in quantum computing (e.g., search) where error-probability reduction costs only a factor $O(\sqrt{\log(1/\epsilon)})$. Our lower bound uses a variant of the polynomial method with trigonometric polynomials.► BibTeX data@article{Mande2026tightboundsquantum, doi = {10.22331/q-2026-06-15-2140}, url = {https://doi.org/10.22331/q-2026-06-15-2140}, title = {Tight {B}ounds for {Q}uantum {P}hase {E}stimation and {R}elated {P}roblems}, author = {Mande, Nikhil S. and Wolf, Ronald de}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2140}, month = jun, year = {2026} }► References [1] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. Quantum, 4:230, 2020. arXiv:1705.01843. Earlier version in FOCS'17. doi:10.22331/q-2020-02-14-230. https://doi.org/10.22331/q-2020-02-14-230 arXiv:1705.01843 [2] Andris Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750–767, 2002. Earlier version in STOC'00. doi:10.1006/jcss.2002.1826. https://doi.org/10.1006/jcss.2002.1826 [3] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. quant-ph/9802049. Earlier version in FOCS'98. doi:10.1145/502090.502097. https://doi.org/10.1145/502090.502097 arXiv:quant-ph/9802049 [4] Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. Bounds for small-error and zero-error quantum algorithms. In Proceedings of 40th IEEE FOCS, pages 358–368, 1999. arXiv:cs/9904019. doi:10.1109/SFFCS.1999.814607. https://doi.org/10.1109/SFFCS.1999.814607 arXiv:cs/9904019 [5] Peter Borwein and Tamás Erdélyi. Polynomials and polynomial inequalities, volume 161. Springer Science & Business Media, 1995. doi:10.1007/978-1-4612-0793-1. https://doi.org/10.1007/978-1-4612-0793-1 [6] Arvid J. Bessen. Lower bound for quantum phase estimation. Physical Review A, 71(4):042313, 2005. doi:10.1103/PhysRevA.71.042313. https://doi.org/10.1103/PhysRevA.71.042313 [7] 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. arXiv:quant-ph/0005055. https://doi.org/10.1090/conm/305/05215 arXiv:quant-ph/0005055 [8] 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. doi:10.1098/rspa.1998.0164. https://doi.org/10.1098/rspa.1998.0164 arXiv:quant-ph/9708016 [9] Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans. Improved hardness results for the guided local hamiltonian problem. In Proceedings of 50th ICALP, pages 32:1–32:19, 2023. arXiv:2207.10250. doi:10.4230/LIPICS.ICALP.2023.32. https://doi.org/10.4230/LIPICS.ICALP.2023.32 arXiv:2207.10250 [10] Yanlin Chen and Ronald de Wolf. Quantum algorithms and lower bounds for linear regression with norm constraints. In Proceedings of 50th ICALP, volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1–38:21, 2023. arXiv:2110.13086. doi:10.4230/LIPIcs.ICALP.2023.38. https://doi.org/10.4230/LIPIcs.ICALP.2023.38 arXiv:2110.13086 [11] Sevag Gharibian and François Le Gall. Dequantizing the quantum singular value transformation: Hardness and applications to quantum chemistry and the quantum PCP conjecture. SIAM Journal on Computing, 52(4):1009–1038, 2023. Earlier version in STOC'22. doi:10.1137/22M1513721. https://doi.org/10.1137/22M1513721 [12] András Gilyén.
Quantum Singular Value Transformation & Its Algorithmic Applications. PhD thesis, University of Amsterdam, 2019. URL: https://pure.uva.nl/ws/files/35292358/Thesis.pdf. https://pure.uva.nl/ws/files/35292358/Thesis.pdf [13] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of 28th ACM STOC, pages 212–219, 1996. quant-ph/9605043. doi:10.1145/237814.237866. https://doi.org/10.1145/237814.237866 arXiv:quant-ph/9605043 [14] 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. doi:10.1145/3313276.3316366. https://doi.org/10.1145/3313276.3316366 arXiv:1806.01838 [15] Yimin Ge, Jordi Tura, and J. Ignacio Cirac. Faster ground state preparation and high-precision ground energy estimation with fewer qubits. Journal of Mathematical Physics, 60(2):022202, 2019. arXiv:1712.03193. doi:10.1063/1.5027484. https://doi.org/10.1063/1.5027484 arXiv:1712.03193 [16] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for solving linear systems of equations.
Physical Review Letters, 103(15):150502, 2009. arXiv:0811.3171. URL: https://doi.org/10.1103/PhysRevLett.103.150502. https://doi.org/10.1103/PhysRevLett.103.150502 arXiv:0811.3171 [17] A. Yu. Kitaev. Quantum measurements and the abelian stabilizer problem, 1995. arXiv:quant-ph/9511026. arXiv:quant-ph/9511026 [18] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J. Yoder. Hamiltonian simulation with optimal sample complexity. npj Quantum Information, 3(13), 2017. arXiv:1608.00281. doi:10.1038/s41534-017-0013-7. https://doi.org/10.1038/s41534-017-0013-7 arXiv:1608.00281 [19] Yao-Ting Lin. A note on quantum phase estimation. 2023. arXiv:2304.02241. arXiv:2304.02241 [20] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10:631–633, 2013. arXiv:1307.0401. doi:10.1038/nphys3029. https://doi.org/10.1038/nphys3029 arXiv:1307.0401 [21] Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4(372), 2020. arXiv:2002.12508. doi:10.22331/q-2020-12-14-372. https://doi.org/10.22331/q-2020-12-14-372 arXiv:2002.12508 [22] Lin Lin and Yu Tong. Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3(010318), 2022. arXiv:2102.11340. doi:10.1103/PRXQuantum.3.010318. https://doi.org/10.1103/PRXQuantum.3.010318 arXiv:2102.11340 [23] Noah Linden and Ronald de Wolf. Average-case verification of the quantum Fourier transform enables worst-case phase estimation. Quantum, 6(872), 2022. arXiv:2109.10215. doi:10.22331/q-2022-12-07-872. https://doi.org/10.22331/q-2022-12-07-872 arXiv:2109.10215 [24] Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of 31st ACM STOC, pages 384–393, 1999. doi:10.1145/301250.301349. https://doi.org/10.1145/301250.301349 [25] Alberto Peruzzo, Jerrad McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter Love, Alán Aspuru-Guzik, and Jeremy O’Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 3:24, 2014. arXiv:1304.3061. doi:10.1038/ncomms5213. https://doi.org/10.1038/ncomms5213 arXiv:1304.3061 [26] David Poulin and Pawel Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer.
Physical Review Letters, 103(22):220502, 2009. arXiv:0905.2199. doi:10.1103/PhysRevLett.103.220502. https://doi.org/10.1103/PhysRevLett.103.220502 arXiv:0905.2199 [27] 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. https://doi.org/10.22331/q-2021-10-19-566 arXiv:2103.09717 [28] 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. doi:10.1137/S0097539795293172. https://doi.org/10.1137/S0097539795293172 arXiv:quant-ph/9508027 [29] Adrian She and Henry Yuen. Unitary property testing lower bounds by polynomials. In Proceedings of 14th ITCS, volume 251, pages 96:1–96:17, 2023. arXiv:2210.05885. doi:10.4230/LIPIcs.ITCS.2023.96. https://doi.org/10.4230/LIPIcs.ITCS.2023.96 arXiv:2210.05885 [30] Kianna Wan, Mario Berta, and Earl T. Campbell. A randomized quantum algorithm for statistical phase estimation.
Physical Review Letters, 129(030503), 2022. arXiv:2110.12071. doi:10.1103/PhysRevLett.129.030503. https://doi.org/10.1103/PhysRevLett.129.030503 arXiv:2110.12071 [31] Jordi Weggemans, Marten Folkertsma, and Chris Cade.
Guidable Local Hamiltonian problems with implications to heuristic ansatz state preparation and the quantum PCP conjecture. In Proceedings of 19th TQC, pages 10:1–10:24, 2024. arXiv:2302.11578. doi:10.4230/LIPIcs.TQC.2024.10. https://doi.org/10.4230/LIPIcs.TQC.2024.10 arXiv:2302.11578 [32] Ronald de Wolf. A note on quantum algorithms and the minimal degree of $\varepsilon$-error polynomials for symmetric functions. Quantum Information and Computation, 8(10):943–950, 2008. arXiv:0802.1816. arXiv:0802.1816 [33] Ronald de Wolf. Quantum computing: Lecture notes, 2019. arXiv:1907.09415, version 5. URL: http://arxiv.org/abs/1907.09415. arXiv:1907.09415Cited by[1] 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). [2] Kapil Goswami, Peter Schmelcher, and Rick Mukherjee, "Qudit-based scalable quantum algorithm for solving the integer programming problem", arXiv:2508.13906, (2025). [3] Matthew P. Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D. Malone, Ryan Babbush, and Nicholas C. Rubin, "Expressing and Analyzing Quantum Algorithms with Qualtran", arXiv:2409.04643, (2024). [4] Muhammad Shaeer Moeed, James Brown, Alexander Ibrahim, Estêvão V. B. de Oliveira, and Pierre-Nicholas Roy, "Qubit encodings for lattices of dipolar planar rotors", Journal of Chemical Physics 163 17, 174103 (2025). [5] Hikaru Wakaura, "Quantum Reservoir GAN", arXiv:2508.05716, (2025). [6] Qisheng Wang and Zhicheng Zhang, "Quantum Lower Bounds by Sample-to-Query Lifting", arXiv:2308.01794, (2023). [7] Alexander M. Dalzell, András Gilyén, Connor T. Hann, Sam McArdle, Grant Salton, Quynh T. Nguyen, Aleksander Kubica, and Fernando G. S. L. Brandão, "A distillation-teleportation protocol for fault-tolerant QRAM", arXiv:2505.20265, (2025). [8] Alexander Zlokapa and Rolando D. Somma, "Hamiltonian simulation for low-energy states with optimal time dependence", Quantum 8, 1449 (2024). [9] Alex Kerzner, Vlad Gheorghiu, Michele Mosca, Thomas Guilbaud, Federico Carminati, Fabio Fracas, and Luca Dellantonio, "A square-root speedup for finding the smallest eigenvalue", Quantum Science and Technology 9 4, 045025 (2024). [10] George T. Fleming, Prasanth Shyamsundar, and Judah Unmuth-Yockey, "Fermion determinants on a quantum computer", Physical Review D 111 5, 054509 (2025). [11] Matthias Deiml and Daniel Peterseim, "Quantum Realization of the Finite Element Method", arXiv:2403.19512, (2024). [12] Mihael Erakovic, Freek Witteveen, Dylan Harley, Jakob Günther, Moritz Bensberg, Oinam Romesh Meitei, Minsik Cho, Troy Van Voorhis, Markus Reiher, and Matthias Christandl, "High Ground State Overlap via Quantum Embedding Methods", PRX Life 3 1, 013003 (2025). [13] Jordi Weggemans, "Lower Bounds for Unitary Property Testing with Proofs and Advice", Quantum 9, 1717 (2025). [14] Robbie King, Guang Hao Low, Ryan Babbush, Rolando D. Somma, and Nicholas C. Rubin, "Quantum Simulation with Sum-of-Squares Spectral Amplification", Physical Review Letters 136 11, 110601 (2026). [15] Matthias Deiml and Daniel Peterseim, "Nonlinear quantum computation by amplified encodings", arXiv:2411.16435, (2024). [16] Emanuele Costa and Javier Menendez, "Improved quasiparticle nuclear Hamiltonians for quantum computing", arXiv:2604.11381, (2026). [17] Yukun Zhang, Xiaoming Zhang, Jinzhao Sun, Heng Lin, Yifei Huang, Dingshun Lv, and Xiao Yuan, "Fault-tolerant quantum algorithms for quantum molecular systems: A survey", arXiv:2502.02139, (2025). [18] Dan Li and Lei Zhong, "Efficient preparation method for arbitrary multiqubit states based on quantum walk", Quantum Information Processing 24 11, 343 (2025). [19] Hikaru Wakaura, "Generative Adversarial Variational Quantum Kolmogorov-Arnold Network", arXiv:2512.11014, (2025). [20] Sophia Simon, Dominic W. Berry, and Rolando D. Somma, "Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems", arXiv:2605.16195, (2026). The above citations are from SAO/NASA ADS (last updated successfully 2026-06-15 14:10:16). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-06-15 14:10:15: Could not fetch cited-by data for 10.22331/q-2026-06-15-2140 from Crossref. This is normal if the DOI was registered recently.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.