Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
1Instituut-Lorentz, Universiteit Leiden, 2300 RA Leiden, The Netherlands
2QuTech, Delft University of Technology, P.O. Box 5046, 2600 GA Delft, The Netherlands and JARA Institute for Quantum Information, Forschungszentrum Juelich, D-52425 Juelich, Germany
3Google Quantum AI, 80636 Munich, Germany
| Published: | 2022-10-06, volume 6, page 830 |
| Eprint: | arXiv:2107.04605v3 |
| Doi: | https://doi.org/10.22331/q-2022-10-06-830 |
| Citation: | Quantum 6, 830 (2022). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Quantum phase estimation is a cornerstone in quantum algorithm design, allowing for the inference of eigenvalues of exponentially-large sparse matrices.The maximum rate at which these eigenvalues may be learned, –known as the Heisenberg limit–, is constrained by bounds on the circuit complexity required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estimation that do not require coherence between experiments have garnered interest in recent years due to lower circuit depth and minimal qubit overhead. In this work we show that these methods can achieve the Heisenberg limit, $also$ when one is unable to prepare eigenstates of the system. Given a quantum subroutine which provides samples of a `phase function' $g(k)=\sum_j A_j e^{i \phi_j k}$ with unknown eigenphases $\phi_j$ and overlaps $A_j$ at quantum cost $O(k)$, we show how to estimate the phases $\{\phi_j\}$ with (root-mean-square) error $\delta$ for total quantum cost $T=O(\delta^{-1})$. Our scheme combines the idea of Heisenberg-limited multi-order quantum phase estimation for a single eigenvalue phase [Higgins et al (2009) and Kimmel et al (2015)] with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem [Somma (2019)] or the matrix pencil method. For our algorithm which adaptively fixes the choice for $k$ in $g(k)$ we prove Heisenberg-limited scaling when we use the time-series/QEEP subroutine. We present numerical evidence that using the matrix pencil technique the algorithm can achieve Heisenberg-limited scaling as well.

Featured image: A Heisenberg-limited scheme for detecting multiple phases $\phi_j$. First, an initial estimate of $\phi_j\in[0,2\pi]$ is made from a time series $\{\langle U\rangle, \langle U^2\rangle \ldots\}$. Then, an estimate is made of $k\phi_j$ for some $k>1$, using $\{\langle U^{k}\rangle, \langle U^{2k}\rangle,\ldots \}$. This generates a more-accurate estimate of $\phi_j$ (smaller error bars), but modulo $2\pi/k$. Data from the first estimation is used to stabilize this estimate and remove unwanted aliases (dashed lines). This is repeated for ever-larger values of $k$ to achieve the Heisenberg limit. The multiplier $k$ is chosen based on the previous estimates to enable unambiguous estimation.
Popular summary
► BibTeX data
► References
[1] B. L. Higgins, D. W. Berry, S. D. Bartlett, M. W. Mitchell, H. M. Wiseman, and G. J. Pryde. Demonstrating Heisenberg-limited unambiguous phase estimation without adaptive measurements. New J. Phys., 11 (7): 073023, 2009. 10.1088/1367-2630/11/7/073023. URL https://arxiv.org/abs/0809.3308.
https://doi.org/10.1088/1367-2630/11/7/073023
arXiv:0809.3308
[2] Shelby Kimmel, Guang Hao Low, and Theodore J. Yoder. Robust calibration of a universal single-qubit gate-set via robust phase estimation. Phys. Rev. A, 92: 062315, 2015. 10.1103/PhysRevA.92.062315. URL https://arxiv.org/abs/1502.02677.
https://doi.org/10.1103/PhysRevA.92.062315
arXiv:1502.02677
[3] Rolando D. Somma. Quantum eigenvalue estimation via time series analysis. New J. Phys., 21: 123025, 2019. 10.1088/1367-2630/ab5c60. URL https://iopscience.iop.org/article/10.1088/1367-2630/ab5c60/pdf.
https://doi.org/10.1088/1367-2630/ab5c60
[4] Pawel Wocjan and Shengyu Zhang. Several natural BQP-complete problems. ArXiv:quant-ph/0606179, 2006. 10.48550/arXiv.quant-ph/0606179. URL https://arxiv.org/abs/quant-ph/0606179.
https://doi.org/10.48550/arXiv.quant-ph/0606179
arXiv:quant-ph/0606179
[5] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Sci. Stat. Comp., 26: 1484, 1997. 10.1137/S0097539795293172. URL https://arxiv.org/abs/quant-ph/9508027.
https://doi.org/10.1137/S0097539795293172
arXiv:quant-ph/9508027
[6] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for solving linear systems of equations. Phys. Rev. Lett., 15 (103): 150502, 2009. 10.1103/PhysRevLett.103.150502. URL https://arxiv.org/abs/0811.3171.
https://doi.org/10.1103/PhysRevLett.103.150502
arXiv:0811.3171
[7] James D. Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik. Simulation of electronic structure Hamiltonians using quantum computers. Mol. Phys., 109: 735–750, 2011. 10.1080/00268976.2011.552441. URL https://arxiv.org/abs/1001.3855.
https://doi.org/10.1080/00268976.2011.552441
arXiv:1001.3855
[8] M.A. Nielsen and I.L. Chuang. Quantum Computation and Quantum Information. Cambridge Series on Information and the Natural Sciences. Cambridge University Press, 2000. ISBN 9780521635035. 10.1017/CBO9780511976667. URL https://books.google.de/books?id=65FqEKQOfP8C.
https://doi.org/10.1017/CBO9780511976667
https://books.google.de/books?id=65FqEKQOfP8C
[9] 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. 10.1098/rspa.1998.0164. URL https://royalsocietypublishing.org/doi/abs/10.1098/rspa.1998.0164.
https://doi.org/10.1098/rspa.1998.0164
[10] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum metrology. Physical review letters, 96 (1): 010401, 2006. 10.1103/PhysRevLett.96.010401. URL https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.96.010401.
https://doi.org/10.1103/PhysRevLett.96.010401
[11] Wim van Dam, G. Mauro D'Ariano, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Optimal quantum circuits for general phase estimation. Phys. Rev. Lett., 98: 090501, Mar 2007. 10.1103/PhysRevLett.98.090501. URL https://link.aps.org/doi/10.1103/PhysRevLett.98.090501.
https://doi.org/10.1103/PhysRevLett.98.090501
[12] Dominic W Berry, Brendon L Higgins, Stephen D Bartlett, Morgan W Mitchell, Geoff J Pryde, and Howard M Wiseman. How to perform the most accurate possible phase measurements. Physical Review A, 80 (5): 052114, 2009. 10.1103/PhysRevA.80.052114.
https://doi.org/10.1103/PhysRevA.80.052114
[13] Robert B. Griffiths and Chi-Sheng Niu. Semiclassical Fourier transform for quantum computation. Physical Review Letters, 76 (17): 3228–3231, Apr 1996. ISSN 1079-7114. 10.1103/physrevlett.76.3228. URL 10.1103/PhysRevLett.76.3228.
https://doi.org/10.1103/physrevlett.76.3228
http://10.1103/PhysRevLett.76.3228
[14] A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. ArXiv:quant-ph/9511026, 1995. 10.48550/arXiv.quant-ph/9511026. URL https://arxiv.org/abs/quant-ph/9511026.
https://doi.org/10.48550/arXiv.quant-ph/9511026
arXiv:quant-ph/9511026
[15] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Comm. Math. Phys., 270 (359), 2007. 10.1007/s00220-006-0150-x. URL https://arxiv.org/abs/quant-ph/0508139.
https://doi.org/10.1007/s00220-006-0150-x
arXiv:quant-ph/0508139
[16] Nathan Wiebe and Chris Granade. Efficient Bayesian phase estimation. Phys. Rev. Lett., 117: 010503, 2016. 10.1103/PhysRevLett.117.010503. URL https://arxiv.org/abs/1508.00869.
https://doi.org/10.1103/PhysRevLett.117.010503
arXiv:1508.00869
[17] Krysta M. Svore, Matthew B. Hastings, and Michael Freedman. Faster phase estimation. Quant. Inf. Comp., 14 (3-4): 306–328, 2013. 10.48550/arXiv.1304.0741. URL https://arxiv.org/abs/1304.0741.
https://doi.org/10.48550/arXiv.1304.0741
arXiv:1304.0741
[18] Ewout van den Berg. Efficient Bayesian phase estimation using mixed priors. ArXiv:2007.11629, 2020. 10.22331/q-2021-06-07-469. URL https://arxiv.org/abs/2007.11629.
https://doi.org/10.22331/q-2021-06-07-469
arXiv:2007.11629
[19] Thomas E O'Brien, Brian Tarasinski, and Barbara M Terhal. Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments. New J. Phys., 21: 023022, 2019. 10.1088/1367-2630/aafb8e. URL https://iopscience.iop.org/article/10.1088/1367-2630/aafb8e.
https://doi.org/10.1088/1367-2630/aafb8e
[20] David C. Rife and Robert R. Boorstyn. Single-tone parameter estimation from discrete-time observations. IEEE Trans. Inf. Th., 20 (5): 591–598, 1974. 10.1109/TIT.1974.1055282. URL https://ieeexplore.ieee.org/document/1055282.
https://doi.org/10.1109/TIT.1974.1055282
https://ieeexplore.ieee.org/document/1055282
[21] Sirui Lu, Mari Carmen Bañuls, and J. Ignacio Cirac. Algorithms for quantum simulation at finite energies. PRX Quantum, 2: 020321, 2020. 10.1103/PRXQuantum.2.020321. URL https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.2.020321.
https://doi.org/10.1103/PRXQuantum.2.020321
[22] T.E. O'Brien, S. Polla, N.C. Rubin, W.J. Huggins, S. McArdle, S. Boixo, J.R. McClean, and R. Babbush. Error mitigation via verified phase estimation. ArXiv:2010.02538, 2020. 10.1103/PRXQuantum.2.020317. URL https://arxiv.org/abs/2010.02538.
https://doi.org/10.1103/PRXQuantum.2.020317
arXiv:2010.02538
[23] Alessandro Roggero. Spectral density estimation with the Gaussian integral transform. ArXiv:2004.04889, 2020. 10.1103/PhysRevA.102.022409. URL https://arxiv.org/abs/2004.04889.
https://doi.org/10.1103/PhysRevA.102.022409
arXiv:2004.04889
[24] 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 the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 193–204, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367059. 10.1145/3313276.3316366. URL 10.1145/3313276.3316366.
https://doi.org/10.1145/3313276.3316366
[25] O. Regev. A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. ArXiv:quant-ph/0406151, 2004. 10.48550/arXiv.quant-ph/0406151. URL https://arxiv.org/abs/quant-ph/0406151.
https://doi.org/10.48550/arXiv.quant-ph/0406151
arXiv:quant-ph/0406151
[26] Lin Lin and Yu Tong. Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers. ArXiv:2102.11340, 2021. 10.1103/PRXQuantum.3.010318. URL https://arxiv.org/abs/2102.11340.
https://doi.org/10.1103/PRXQuantum.3.010318
arXiv:2102.11340
[27] Valentin Gebhart, Augusto Smerzi, and Luca Pezzè. Heisenberg-limited bayesian multiphase estimation algorithm. ArXiv:2010.09075, 2020. 10.1103/PhysRevApplied.16.014035. URL https://arxiv.org/abs/2010.09075.
https://doi.org/10.1103/PhysRevApplied.16.014035
arXiv:2010.09075
[28] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. Theory of trotter error with commutator scaling. Phys. Rev. X, 11: 011020, Feb 2021. 10.1103/PhysRevX.11.011020. URL https://link.aps.org/doi/10.1103/PhysRevX.11.011020.
https://doi.org/10.1103/PhysRevX.11.011020
[29] Harald Cramér. Mathematical Methods of Statistics. Princeton University Press, 1946. ISBN 0691080046. 10.1515/9781400883868. URL https://archive.org/details/in.ernet.dli.2015.223699.
https://doi.org/10.1515/9781400883868
https://archive.org/details/in.ernet.dli.2015.223699
[30] Calyampudi Radakrishna Rao. Information and the accuracy attainable in the estimation of statistical parameters. Bull. Calcutta Math. Soc., 37: 81–89, 1945. 10.1007/978-1-4612-0919-5_16. URL https://link.springer.com/chapter/10.1007/978-1-4612-0919-5_16.
https://doi.org/10.1007/978-1-4612-0919-5_16
[31] Yingbo Hua and Tapan Sarkar. Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise. IEEE Transactions on Acoustic Speech and Signal Processing, 38 (5), 1990. 10.1109/29.56027. URL https://ieeexplore.ieee.org/document/56027.
https://doi.org/10.1109/29.56027
https://ieeexplore.ieee.org/document/56027
[32] Ankur Moitra. Super-resolution, extremal functions and the condition number of Vandermonde matrices. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, page 821–830, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450335362. 10.1145/2746539.2746561. URL 10.1145/2746539.2746561.
https://doi.org/10.1145/2746539.2746561
[33] Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4: 372, December 2020. ISSN 2521-327X. 10.22331/q-2020-12-14-372. URL 10.22331/q-2020-12-14-372.
https://doi.org/10.22331/q-2020-12-14-372
Cited by
[1] 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).
[2] Changhao Yi, Cunlu Zhou, and Jun Takahashi, "Quantum Phase Estimation by Compressed Sensing", Quantum 8, 1579 (2024).
[3] Hao-En Li, Yongtao Zhan, and Lin Lin, "Dissipative ground state preparation in ab initio electronic structure theory", npj Quantum Information 11 1, 183 (2025).
[4] 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).
[5] Haoya Li, Hongkang Ni, and Lexing Ying, "Adaptive low-depth quantum algorithms for robust multiple-phase estimation", Physical Review A 108 6, 062408 (2023).
[6] Juan Borge, Unai Aseguinolaza, Nahual Sobrino, Gabriel Sobrino, and Joaquim Jornet-Somoza, "Error Estimation in Current Noisy Quantum Computers", (2023).
[7] Davide Castaldo and Markus Reiher, "Utility-Scale Quantum Computational Chemistry", The Journal of Physical Chemistry Letters 17 29, 8140 (2026).
[8] Yuan-De Jin, Shi-Yu Zhang, and Wen-Long Ma, "Channel-based framework for phase estimation of multiple eigenvalues", Physical Review A 111 2, 022406 (2025).
[9] 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).
[10] 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).
[11] Shu Kanno, Kenji Sugisaki, Rei Sakuma, Jumpei Kato, Hajime Nakamura, and Naoki Yamamoto, "Tensor-based phase difference estimation on time-series analysis", Physical Review A 113 5, 052433 (2026).
[12] Andrés Gómez and Javier Mas, "Hermitian matrix definiteness from quantum phase estimation", Quantum Information Processing 21 6, 213 (2022).
[13] 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).
[14] Amara Katabarwa, Katerina Gratsea, Athena Caesura, and Peter D. Johnson, "Early Fault-Tolerant Quantum Computing", PRX Quantum 5 2, 020101 (2024).
[15] Kaito Wada, Kazuma Fukuchi, and Naoki Yamamoto, "Quantum-enhanced mean value estimation via adaptive measurement", Quantum 8, 1463 (2024).
[16] Zhiyan Ding, Ethan N. Epperly, Lin Lin, and Ruizhe Zhang, 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 2344 (2024) ISBN:979-8-3315-1674-1.
[17] Kaito Wada, Naoki Yamamoto, and Nobuyuki Yoshioka, "Heisenberg-Limited Adaptive Gradient Estimation for Multiple Observables", PRX Quantum 6 2, 020308 (2025).
[18] Xiaoyu Liu, Benjamin F. Schiffer, and Jordi Tura, "Preparing low-variance states using a distributed quantum algorithm", Quantum 9, 1838 (2025).
[19] Cristian L. Cortes, Dario Rocca, Jérôme F. Gonthier, Pauline J. Ollitrault, Robert M. Parrish, Gian-Luca R. Anselmetti, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, and Michael Streif, "Assessing the query complexity limits of quantum phase estimation using symmetry-aware spectral bounds", Physical Review A 110 2, 022420 (2024).
[20] Unai Aseguinolaza, Nahual Sobrino, Gabriel Sobrino, Joaquim Jornet-Somoza, and Juan Borge, "Error estimation in current noisy quantum computers", Quantum Information Processing 23 5, 181 (2024).
[21] Woo-Ram Lee, Nathan M. Myers, and V. W. Scarola, "Noise-resilient and resource-efficient hybrid algorithm for robust quantum gap estimation", Physical Review A 111 2, 022421 (2025).
[22] 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).
[23] Sven Danz, Mario Berta, Stefan Schröder, Pascal Kienast, Frank K. Wilhelm, and Alessandro Ciani, "Calculating response functions of coupled oscillators using quantum phase estimation", Physical Review Research 7 2, 023264 (2025).
[24] Casper Gyurik, Chris Cade, and Vedran Dunjko, "Towards quantum advantage via topological data analysis", Quantum 6, 855 (2022).
[25] Alicja Dutkiewicz, Thomas E. O'Brien, and Thomas Schuster, "The advantage of quantum control in many-body Hamiltonian learning", Quantum 8, 1537 (2024).
[26] Liubov A. Markovich, Attaallah Almasi, Sina Zeytinoğlu, and Johannes Borregaard, "Quantum memory assisted observable estimation", Quantum 9, 1655 (2025).
[27] 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).
[28] Nick S. Blunt, Laura Caune, Róbert Izsák, Earl T. Campbell, and Nicole Holzmann, "Statistical Phase Estimation and Error Mitigation on a Superconducting Quantum Processor", PRX Quantum 4 4, 040341 (2023).
[29] Yanwu Gu, Yunheng Ma, Nicolò Forcellini, and Dong E. Liu, "Noise-Resilient Phase Estimation with Randomized Compiling", Physical Review Letters 130 25, 250601 (2023).
[30] 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).
[31] Kianna Wan, Mario Berta, and Earl T. Campbell, "Randomized Quantum Algorithm for Statistical Phase Estimation", Physical Review Letters 129 3, 030503 (2022).
[32] Benjamin F. Schiffer, Dominik S. Wild, Nishad Maskara, Mikhail D. Lukin, and J. Ignacio Cirac, "Hardware-Efficient Quantum Phase Estimation via Local Control", PRX Quantum 6 4, 040348 (2025).
[33] Adam Callison and Dan E. Browne, "Improved maximum-likelihood quantum amplitude estimation", arXiv:2209.03321, (2022).
[34] Yuki Izumi and Hitoshi Kawahara, "Standard Quantum Phase Estimation Detects All Eigenvalues via Randomized Initial States", arXiv:2604.00475, (2026).
[35] Amit Surana and Brandon Allen, "Statistical Quantum Phase Estimation: Extensions and Practical Considerations", arXiv:2605.18876, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-07 08:10:00) and SAO/NASA ADS (last updated successfully 2026-08-06 18:55:37). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch ADS cited-by data during last attempt 2026-08-07 08:09:59: Cannot retrieve data from ADS due to rate limitations.
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.