On low-depth algorithms for quantum phase estimation
1Institute for Computational and Mathematical Engineering, Stanford University, Stanford, CA 94305
2Department of Mathematics, Stanford University, Stanford, CA 94305
| Published: | 2023-11-06, volume 7, page 1165 |
| Eprint: | arXiv:2302.02454v4 |
| Doi: | https://doi.org/10.22331/q-2023-11-06-1165 |
| Citation: | Quantum 7, 1165 (2023). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Quantum phase estimation is one of the critical building blocks of quantum computing. For early fault-tolerant quantum devices, it is desirable for a quantum phase estimation algorithm to (1) use a minimal number of ancilla qubits, (2) allow for inexact initial states with a significant mismatch, (3) achieve the Heisenberg limit for the total resource used, and (4) have a diminishing prefactor for the maximum circuit length when the overlap between the initial state and the target state approaches one. In this paper, we prove that an existing algorithm from quantum metrology can achieve the first three requirements. As a second contribution, we propose a modified version of the algorithm that also meets the fourth requirement, which makes it particularly attractive for early fault-tolerant quantum devices.

Featured image: The top panel illustrates the simple process of iterative improvement of estimation. The bottom panels showcase our proposed method's superior or comparable performance to the previously proposed QCELS method and its superiority over the textbook-version QPE.
► BibTeX data
► References
[1] D. Aharonov and T. Naveh. Quantum NP-a survey. arXiv preprint quant-ph/0210077, 2002. https://doi.org/10.48550/arXiv.quant-ph/0210077.
https://doi.org/10.48550/arXiv.quant-ph/0210077
arXiv:quant-ph/0210077
[2] F. Belliardo and V. Giovannetti. Achieving Heisenberg scaling with maximally entangled states: An analytic upper bound for the attainable root-mean-square error. Physical Review A, 102 (4): 042613, 2020. https://doi.org/10.1103/PhysRevA.102.042613.
https://doi.org/10.1103/PhysRevA.102.042613
[3] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical review letters, 114 (9): 090502, 2015. https://doi.org/10.1103/PhysRevLett.114.090502.
https://doi.org/10.1103/PhysRevLett.114.090502
[4] R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454 (1969): 339–354, 1998. https://doi.org/10.1098/rspa.1998.0164.
https://doi.org/10.1098/rspa.1998.0164
[5] Z. Ding and L. Lin. Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation. PRX Quantum, 4 (2): 020331, 2023a. https://doi.org/10.1103/PRXQuantum.4.020331.
https://doi.org/10.1103/PRXQuantum.4.020331
[6] Z. Ding and L. Lin. Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers. Quantum, 7: 1136, 2023b. https://doi.org/10.22331/q-2023-10-11-1136.
https://doi.org/10.22331/q-2023-10-11-1136
[7] Y. Dong, L. Lin, and Y. Tong. Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices. PRX Quantum, 3 (4): 040305, 2022. https://doi.org/10.1103/PRXQuantum.3.040305.
https://doi.org/10.1103/PRXQuantum.3.040305
[8] V. Giovannetti, S. Lloyd, and L. Maccone. Quantum metrology. Physical review letters, 96 (1): 010401, 2006. https://doi.org/10.1103/PhysRevLett.96.010401.
https://doi.org/10.1103/PhysRevLett.96.010401
[9] B. L. Higgins, D. W. Berry, S. D. Bartlett, H. M. Wiseman, and G. J. Pryde. Entanglement-free Heisenberg-limited phase estimation. Nature, 450 (7168): 393–396, 2007. https://doi.org/10.1038/nature06257.
https://doi.org/10.1038/nature06257
[10] H.-Y. Huang, Y. Tong, D. Fang, and Y. Su. Learning many-body hamiltonians with heisenberg-limited scaling. Physical Review Letters, 130 (20): 200403, 2023. https://doi.org/10.1103/PhysRevLett.130.200403.
https://doi.org/10.1103/PhysRevLett.130.200403
[11] J. Kempe, A. Kitaev, and O. Regev. The complexity of the local Hamiltonian problem. Siam journal on computing, 35 (5): 1070–1097, 2006. https://doi.org/10.1137/S0097539704445226.
https://doi.org/10.1137/S0097539704445226
[12] S. Kimmel, G. H. Low, and T. J. Yoder. Robust calibration of a universal single-qubit gate set via robust phase estimation. Physical Review A, 92 (6): 062315, 2015. https://doi.org/10.1103/PhysRevA.92.062315.
https://doi.org/10.1103/PhysRevA.92.062315
[13] A. Y. Kitaev. Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph/9511026, 1995. https://doi.org/10.48550/arXiv.quant-ph/9511026.
https://doi.org/10.48550/arXiv.quant-ph/9511026
arXiv:quant-ph/9511026
[14] A. Y. Kitaev, A. Shen, M. N. Vyalyi, and M. N. Vyalyi. Classical and quantum computation. American Mathematical Soc., 2002. http://dx.doi.org/10.1090/gsm/047.
https://doi.org/10.1090/gsm/047
[15] E. Knill, G. Ortiz, and R. D. Somma. Optimal quantum measurements of expectation values of observables. Physical Review A, 75 (1): 012328, 2007. https://doi.org/10.1103/PhysRevA.75.012328.
https://doi.org/10.1103/PhysRevA.75.012328
[16] H. Li, H. Ni, and L. Ying. On low-depth quantum algorithms for robust multiple-phase estimation. arXiv preprint arXiv:2303.08099, 2023. https://doi.org/10.48550/arXiv.2303.08099.
https://doi.org/10.48550/arXiv.2303.08099
arXiv:2303.08099
[17] L. Lin and Y. Tong. Near-optimal ground state preparation. Quantum, 4: 372, 2020. https://doi.org/10.22331/q-2020-12-14-372.
https://doi.org/10.22331/q-2020-12-14-372
[18] L. Lin and Y. Tong. Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3 (1): 010318, 2022. https://doi.org/10.1103/PRXQuantum.3.010318.
https://doi.org/10.1103/PRXQuantum.3.010318
[19] A. Lumino, E. Polino, A. S. Rab, G. Milani, N. Spagnolo, N. Wiebe, and F. Sciarrino. Experimental phase estimation enhanced by machine learning. Physical Review Applied, 10 (4): 044033, 2018. https://doi.org/10.1103/PhysRevApplied.10.044033.
https://doi.org/10.1103/PhysRevApplied.10.044033
[20] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. http://dx.doi.org/10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667
[21] T. E. O’Brien, B. Tarasinski, and B. M. Terhal. Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments. New Journal of Physics, 21 (2): 023022, 2019. 10.1088/1367-2630/aafb8e.
https://doi.org/10.1088/1367-2630/aafb8e
[22] D. Poulin and P. Wocjan. Sampling from the thermal quantum gibbs state and evaluating partition functions with a quantum computer. Physical review letters, 103 (22): 220502, 2009. https://doi.org/10.1103/PhysRevLett.103.220502.
https://doi.org/10.1103/PhysRevLett.103.220502
[23] K. Rudinger, S. Kimmel, D. Lobser, and P. Maunz. Experimental demonstration of a cheap and accurate phase estimation. Physical review letters, 118 (19): 190502, 2017. https://doi.org/10.1103/PhysRevLett.118.190502.
https://doi.org/10.1103/PhysRevLett.118.190502
[24] A. E. Russo, K. M. Rudinger, B. C. Morrison, and A. D. Baczewski. Evaluating energy differences on a quantum computer with robust phase estimation. Physical review letters, 126 (21): 210501, 2021. https://doi.org/10.1103/PhysRevLett.126.210501.
https://doi.org/10.1103/PhysRevLett.126.210501
[25] Y. Tong. A tight query complexity lower bound for phase estimation under circuit depth constraint, 2021. URL https://math.berkeley.edu/ yu_tong/lower_bound_low_depth_phase_est.pdf.
https://math.berkeley.edu/~yu_tong/lower_bound_low_depth_phase_est.pdf
[26] K. Wan, M. Berta, and E. T. Campbell. Randomized quantum algorithm for statistical phase estimation. Physical Review Letters, 129 (3): 030503, 2022. https://doi.org/10.1103/PhysRevLett.129.030503.
https://doi.org/10.1103/PhysRevLett.129.030503
[27] G. Wang, D. Stilck-França, R. Zhang, S. Zhu, and P. D. Johnson. Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision. arXiv preprint arXiv:2209.06811, 2022. https://doi.org/10.48550/arXiv.2209.06811.
https://doi.org/10.48550/arXiv.2209.06811
arXiv:2209.06811
[28] R. Zhang, G. Wang, and P. Johnson. Computing ground state properties with early fault-tolerant quantum computers. Quantum, 6: 761, 2022. https://doi.org/10.22331/q-2022-07-11-761.
https://doi.org/10.22331/q-2022-07-11-761
[29] S. Zhou, M. Zhang, J. Preskill, and L. Jiang. Achieving the Heisenberg limit in quantum metrology using quantum error correction. Nature communications, 9 (1): 78, 2018. https://doi.org/10.1038/s41467-017-02510-3.
https://doi.org/10.1038/s41467-017-02510-3
[30] M. Zwierz, C. A. Pérez-Delgado, and P. Kok. General optimality of the Heisenberg limit for quantum metrology. Physical review letters, 105 (18): 180402, 2010. https://doi.org/10.1103/PhysRevLett.105.180402.
https://doi.org/10.1103/PhysRevLett.105.180402
Cited by
[1] Changhao Yi, Cunlu Zhou, and Jun Takahashi, "Quantum Phase Estimation by Compressed Sensing", Quantum 8, 1579 (2024).
[2] Dhrumil Patel, Shi Jie Samuel Tan, Yiğit Subaşı, and Andrew T. Sornborger, "Optimal Coherent Quantum Phase Estimation Via Tapering", PRX Quantum 7 2, 020302 (2026).
[3] Zhiyan Ding, Yulong Dong, Yu Tong, and Lin Lin, "Robust ground-state energy estimation under depolarizing noise", APL Computational Physics 2 2, 026111 (2026).
[4] Lexing Ying, "A perturbative analysis for noisy spectral estimation", Applied and Computational Harmonic Analysis 74, 101716 (2025).
[5] Mancheon Han, Hyowon Park, and Sangkook Choi, "Quantum Zeno Monte Carlo for computing observables", npj Quantum Information 11 1, 46 (2025).
[6] Alicja Dutkiewicz, Stefano Polla, Maximilian Scheurer, Christian Gogolin, William J. Huggins, and Thomas E. O’Brien, "Error Mitigation and Circuit Division for Early Fault-Tolerant Quantum Phase Estimation", PRX Quantum 6 4, 040318 (2025).
[7] Yongdan Yang, Ying Li, Xiaosi Xu, and Xiao Yuan, "Resource-efficient quantum-classical hybrid algorithm for energy gap evaluation", Physical Review A 109 5, 052416 (2024).
[8] Xian Lu, Xinying Li, Yongmei Li, Xin Yi, Shuai Hou, and Chengkang Pan, 2025 IEEE 4th International Conference on Computing, Communication, Perception and Quantum Technology (CCPQT) 1 (2025) ISBN:979-8-3315-2583-5.
[9] Jacob S. Nelson and Andrew D. Baczewski, "Assessment of quantum phase estimation protocols for early fault-tolerant quantum computers", Physical Review A 110 4, 042420 (2024).
[10] Marek Gluza, Jeongrak Son, Bi Hong Tiang, René Zander, Raphael Seidel, Yudai Suzuki, Zoë Holmes, and Nelly H. Y. Ng, "Double-Bracket Quantum Algorithms for Quantum Imaginary-Time Evolution", Physical Review Letters 136 2, 020601 (2026).
[11] Davide Castaldo and Markus Reiher, "Utility-Scale Quantum Computational Chemistry", The Journal of Physical Chemistry Letters 17 29, 8140 (2026).
[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] Haoya Li, Hongkang Ni, and Lexing Ying, "Adaptive low-depth quantum algorithms for robust multiple-phase estimation", Physical Review A 108 6, 062408 (2023).
[14] Dominic W. Berry, Yu Tong, Tanuj Khattar, Alec White, Tae In Kim, Guang Hao Low, Sergio Boixo, Zhiyan Ding, Lin Lin, Seunghoon Lee, Garnet Kin-Lic Chan, Ryan Babbush, and Nicholas C. Rubin, "Rapid Initial-State Preparation for the Quantum Simulation of Strongly Correlated Molecules", PRX Quantum 6 2, 020327 (2025).
[15] Ersin Elbasi, Yehia Ibrahim Alzoubi, Greeshma Varghese, and Ahmet E. Topcu, Studies in Computational Intelligence 1256, 1 (2026) ISBN:978-981-95-6275-6.
[16] R Au-Yeung, B Camino, O Rathore, and V Kendon, "Quantum algorithms for scientific computing", Reports on Progress in Physics 87 11, 116001 (2024).
[17] Arjun Mirani and Patrick Hayden, "Learning interacting fermionic Hamiltonians at the Heisenberg limit", Physical Review A 110 6, 062421 (2024).
[18] Erenay Karacan, Yanbin Chen, and Christian B. Mendl, "Enhancing Scalability of Quantum Eigenvalue Transformation of Unitary Matrices for Ground State Preparation through Adaptive Finer Filtering", Quantum 9, 1624 (2025).
[19] Qiyao Liang, Yiqing Zhou, Archismita Dalal, and Peter Johnson, "Modeling the performance of early fault-tolerant quantum algorithms", Physical Review Research 6 2, 023118 (2024).
[20] Waldemir Cambiucci, Regina Melo Silveira, and Wilson Vicente Ruggiero, 2025 International Conference on Quantum Communications, Networking, and Computing (QCNC) 655 (2025) ISBN:979-8-3315-3159-1.
[21] Riki Toshio, Yutaro Akahoshi, Jun Fujisaki, Hirotaka Oshima, Shintaro Sato, and Keisuke Fujii, "Practical Quantum Advantage on Partially Fault-Tolerant Quantum Computer", Physical Review X 15 2, 021057 (2025).
[22] Erenay Karacan, "Phase estimation with compressed controlled time evolution", Physical Review A 113 4, 042420 (2026).
[23] Calvin Ku, Yu-Cheng Chen, Alice Hu, and Min-Hsiu Hsieh, "Benchmarking quantum simulation of chemical Hamiltonians using the sorted-list encoding", Physical Review Research 8 3, 033091 (2026).
[24] Yukun Zhang, Yifei Huang, Jinzhao Sun, Dingshun Lv, and Xiao Yuan, "Quantum computing quantum Monte Carlo algorithm", Physical Review A 112 2, 022428 (2025).
[25] Alok Shukla and Prakash Vedula, "Toward Practical Quantum Phase Estimation: A Modular, Scalable, and Adaptive Approach", Advanced Quantum Technologies 9 3, e00683 (2026).
[26] Su Direkci, Ran Finkelstein, Manuel Endres, and Tuvia Gefen, "Heisenberg-limited Bayesian phase estimation with low-depth digital quantum circuits", npj Quantum Information 12 1, 31 (2026).
[27] Yulong Dong, Jonathan A. Gross, and Murphy Yuezhen Niu, "Optimal low-depth quantum signal-processing phase estimation", Nature Communications 16 1, 1504 (2025).
[28] Zhiyan Ding, Haoya Li, Lin Lin, HongKang Ni, Lexing Ying, and Ruizhe Zhang, "Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method", Quantum 8, 1487 (2024).
[29] Giuliana Siddi Moreau, Lorenzo Pisani, Manuela Profir, Carlo Podda, Lidia Leoni, and Giacomo Cao, "Quantum Artificial Intelligence Scalability in the NISQ Era: Pathways to Quantum Utility", Advanced Quantum Technologies 8 10, 2400716 (2025).
[30] Yukun Zhang, Xiaoming Zhang, Jinzhao Sun, Heng Lin, Yifei Huang, Dingshun Lv, and Xiao Yuan, "Quantum Algorithms for Quantum Molecular Systems: A Survey", WIREs Computational Molecular Science 15 3, e70020 (2025).
[31] Zhong-Xia Shang, Dong An, and Changpeng Shao, "Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties", Reports on Progress in Physics 89 5, 057602 (2026).
[32] Fouad Ayoub and James D. Baeder, "High-entanglement capabilities for variational quantum algorithms: the Poisson equation case", Quantum Information Processing 24 8, 229 (2025).
[33] Yilun Yang, Arthur Christianen, Mari Carmen Bañuls, Dominik S. Wild, and J. Ignacio Cirac, "Phase-Sensitive Quantum Measurement without Controlled Operations", Physical Review Letters 132 22, 220601 (2024).
[34] Leah P. Weisburn, Minsik Cho, Moritz Bensberg, Oinam Romesh Meitei, Markus Reiher, and Troy Van Voorhis, "Multiscale Embedding for Quantum Computing", Journal of Chemical Theory and Computation 21 9, 4591 (2025).
[35] Suleiman Onimisi Aliyu and Hongji Yang, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 1033 (2025) ISBN:979-8-3315-5736-2.
[36] Mauro Cainelli, Reo Baba, and Yuki Kurashige, "Numerical Investigation of the Quantum Inverse Algorithm on Small Molecules", Journal of Chemical Theory and Computation acs.jctc.4c00483 (2024).
[37] Chao Lu, Muralikrishnan Gopalakrishnan Meena, and Kalyana C. Gottiparthi, "LuGo: An enhanced quantum phase estimation implementation", Future Generation Computer Systems 178, 108270 (2026).
[38] Haoya Li, Yu Tong, Tuvia Gefen, Hongkang Ni, and Lexing Ying, "Heisenberg-limited Hamiltonian learning for interacting bosons", npj Quantum Information 10 1, 83 (2024).
[39] Rutuja Kshirsagar, Amara Katabarwa, and Peter D. Johnson, "On proving the robustness of algorithms for early fault-tolerant quantum computers", Quantum 8, 1531 (2024).
[40] Mauro E. S. Morales, Lirandë Pira, Philipp Schleich, Kelvin Koor, Pedro C. S. Costa, Dong An, Alán Aspuru-Guzik, Lin Lin, Patrick Rebentrost, and Dominic W. Berry, "Quantum linear system solvers: A survey of algorithms and applications", Reviews of Modern Physics 98 2, 025005 (2026).
[41] Zhiyan Ding, Lin Lin, Yilun Yang, and Ruizhe Zhang, "Quantum Filtering and Analysis of Multiplicities in Eigenvalue Spectra", PRX Quantum 7 2, 020318 (2026).
[42] Guoming Wang, Daniel Stilck França, Gumaro Rendon, and Peter D. Johnson, "Efficient ground-state-energy estimation and certification on early fault-tolerant quantum computers", Physical Review A 111 1, 012426 (2025).
[43] Baptiste Claudon, Pablo Rodenas-Ruiz, Jean-Philip Piquemal, and Pierre Monmarché, "Quantum circuits for the Metropolis–Hastings algorithm", Journal of Physics A: Mathematical and Theoretical 59 30, 305304 (2026).
[44] Kaijie Wei, Hideharu Amano, Ryohei Niwase, Yoshiki Yamaguchi, and Takefumi Miyoshi, "Qu-Trefoil: Large-Scale Quantum Circuit Simulator Working on FPGA With SATA Storages", IEEE Transactions on Computers 74 4, 1306 (2025).
[45] Erenay Karacan, Conor Mc Keever, Michael Foss-Feig, David Hayes, and Michael Lubasch, "Filter-enhanced adiabatic quantum computing on a digital quantum processor", Physical Review Research 7 3, 033153 (2025).
[46] Jakob Günther, Freek Witteveen, Alexander Schmidhuber, Marek Miller, Matthias Christandl, and Aram W. Harrow, "Phase Estimation with Partially Randomized Time Evolution", PRX Quantum 7 2, 020332 (2026).
[47] Amara Katabarwa, Katerina Gratsea, Athena Caesura, and Peter D. Johnson, "Early Fault-Tolerant Quantum Computing", PRX Quantum 5 2, 020101 (2024).
[48] Zhiyan Ding and Lin Lin, "Even Shorter Quantum Circuit for Phase Estimation on Early Fault-Tolerant Quantum Computers with Applications to Ground-State Energy Estimation", PRX Quantum 4 2, 020331 (2023).
[49] Guoming Wang, Daniel Stilck França, Ruizhe Zhang, Shuchen Zhu, and Peter D. Johnson, "Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision", Quantum 7, 1167 (2023).
[50] Zhiyan Ding and Lin Lin, "Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers", Quantum 7, 1136 (2023).
[51] Daan Camps, Ermal Rrapaj, Katherine Klymko, Hyeongjin Kim, Kevin Gott, Siva Darbha, Jan Balewski, Brian Austin, and Nicholas J. Wright, "Quantum Computing Technology Roadmaps and Capability Assessment for Scientific Computing -- An analysis of use cases from the NERSC workload", arXiv:2509.09882, (2025).
[52] Davide Castaldo, Soran Jahangiri, Agostino Migliore, Juan Miguel Arrazola, and Stefano Corni, "A differentiable quantum phase estimation algorithm", Quantum Science and Technology 9 4, 045026 (2024).
[53] Akash Kundu, "Reinforcement learning-assisted quantum architecture search for variational quantum algorithms", arXiv:2402.13754, (2024).
[54] Pei-Kai Tsai and Shruti Puri, "A Unitary Encoder for Surface Codes", arXiv:2506.04084, (2025).
[55] Zhenning Liu, Xiantao Li, Chunhao Wang, and Jin-Peng Liu, "Toward end-to-end quantum simulation for protein dynamics", arXiv:2411.03972, (2024).
[56] Maximilian Mandelt Buxadé, Stefan Langer, and Philipp Bekemeyer, "Solving Nonlinear Partial Differential Equations via a Hybrid Newton Method Using Quantum Linear System Solver", arXiv:2603.23258, (2026).
[57] S. P. Kish, H. J. Vallury, J. Pieprzyk, C. Thapa, and S. Camtepe, "Quantum Spectral Authentication under Public Unitary Challenges", arXiv:2603.24868, (2026).
[58] Zikang Jia, Suying Liu, and Yulong Dong, "Programmable Signal Design for Quantum Phase Estimation via Quantum Signal Processing", arXiv:2604.01205, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-07 16:13:43) and SAO/NASA ADS (last updated successfully 2026-08-07 16:13:45). 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.