Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method
1Department of Mathematics, University of California, Berkeley, CA 94720, USA
2Department of Mathematics, Stanford University, CA 94305, USA
3Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
4Challenge Institute for Quantum Computation, University of California, Berkeley, CA 94720, USA
5Institute for Computational and Mathematical Engineering, Stanford University, CA 94305, USA
6Simons Institute for the Theory of Computing, University of California, Berkeley, CA 94720, USA
| Published: | 2024-10-02, volume 8, page 1487 |
| Eprint: | arXiv:2402.01013v2 |
| Doi: | https://doi.org/10.22331/q-2024-10-02-1487 |
| Citation: | Quantum 8, 1487 (2024). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Quantum phase estimation is one of the most powerful quantum primitives. This work proposes a new approach for the problem of multiple eigenvalue estimation: Quantum Multiple Eigenvalue Gaussian filtered Search (QMEGS). QMEGS leverages the Hadamard test circuit structure and only requires simple classical postprocessing. QMEGS is the first algorithm to simultaneously satisfy the following two properties: (1) It can achieve the Heisenberg-limited scaling without relying on any spectral gap assumption. (2) With a positive energy gap and additional assumptions on the initial state, QMEGS can estimate all dominant eigenvalues to $\epsilon$ accuracy utilizing a significantly reduced circuit depth compared to the standard quantum phase estimation algorithm. In the most favorable scenario, the maximal runtime can be reduced to as low as $\log(1/\epsilon)$. This implies that QMEGS serves as an efficient and versatile approach, achieving the best-known results for both gapped and gapless systems. Numerical results validate the efficiency of our proposed algorithm in various regimes.
Featured image: Flowchart of QMEGS. The algorithm involves three steps: Firstly, a sequence of $t_n$ is generated from a truncated Gaussian using a classical computer. In the second step, the Hadamard test circuit is implemented on a quantum computer to produce the dataset ${(t_n,Z_n)}$. Within the Hadamard test circuit, we select $W=I$ or $W=S^\dagger$ (where $S$ is the phase gate) to estimate the real or imaginary part of $\left\langle \psi|\exp(-itH)|\psi\right\rangle$. In the final step, postprocessing is performed on the quantum data ${(t_n,Z_n)}$ for eigenvalue estimation.
Popular summary
► BibTeX data
► References
[1] Michael A Nielsen and Isaac Chuang. ``Quantum computation and quantum information''. Cambridge Univ. Pr. (2000).
https://doi.org/10.1017/CBO9780511976667
[2] Daniel S Abrams and Seth Lloyd. ``Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors''. Phys. Rev. Lett. 83, 5162 (1999).
https://doi.org/10.1103/PhysRevLett.83.5162
[3] Yimin Ge, Jordi Tura, and J Ignacio Cirac. ``Faster ground state preparation and high-precision ground energy estimation with fewer qubits''. J. Math. Phys. 60, 022202 (2019).
https://doi.org/10.1063/1.5027484
[4] Lin Lin and Yu Tong. ``Near-optimal ground state preparation''. Quantum 4, 372 (2020).
https://doi.org/10.22331/q-2020-12-14-372
[5] Lin Lin and Yu Tong. ``Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers''. PRX Quantum 3, 010318 (2022).
https://doi.org/10.1103/PRXQuantum.3.010318
[6] Yulong Dong, Lin Lin, and Yu Tong. ``Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices''. PRX Quantum 3, 040305 (2022).
https://doi.org/10.1103/PRXQuantum.3.040305
[7] Kianna Wan, Mario Berta, and Earl T Campbell. ``Randomized quantum algorithm for statistical phase estimation''. Phys. Rev. Lett. 129, 030503 (2022).
https://doi.org/10.1103/PhysRevLett.129.030503
[8] Ruizhe Zhang, Guoming Wang, and Peter 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
[9] 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).
https://doi.org/10.22331/q-2023-11-06-1167
[10] 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, 020331 (2023).
https://doi.org/10.1103/PRXQuantum.4.020331
[11] Hongkang Ni, Haoya Li, and Lexing Ying. ``On low-depth algorithms for quantum phase estimation''. Quantum (2023).
https://doi.org/10.22331/q-2023-11-06-1165
[12] 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, 040341 (2023).
https://doi.org/10.1103/PRXQuantum.4.040341
[13] Rolando D Somma. ``Quantum eigenvalue estimation via time series analysis''. New J. Phys. 21, 123025 (2019).
https://doi.org/10.1088/1367-2630/ab5c60
[14] M E Stroeks, J Helsen, and B M Terhal. ``Spectral estimation for hamiltonians: a comparison between classical imaginary-time evolution and quantum real-time evolution''. New J. Phys. 24, 103024 (2022).
https://doi.org/10.1088/1367-2630/ac919c
[15] Cristian L. Cortes and Stephen K. Gray. ``Quantum Krylov subspace algorithms for ground- and excited-state energy estimation''. Phys. Rev. A 105, 022417 (2022).
https://doi.org/10.1103/PhysRevA.105.022417
[16] Ethan N. Epperly, Lin Lin, and Yuji Nakatsukasa. ``A theory of quantum subspace diagonalization''. SIAM J. Matrix Anal. Appl. 43, 1263–1290 (2022).
https://doi.org/10.1137/21M145954X
[17] Alicja Dutkiewicz, Barbara M. Terhal, and Thomas E. O'Brien. ``Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits''. Quantum 6, 830 (2022).
https://doi.org/10.22331/q-2022-10-06-830
[18] 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).
https://doi.org/10.22331/q-2023-10-11-1136
[19] Haoya Li, Hongkang Ni, and Lexing Ying. ``Adaptive low-depth quantum algorithms for robust multiple-phase estimation''. Phys. Rev. A 108, 062408 (2023).
https://doi.org/10.1103/PhysRevA.108.062408
[20] Yizhi Shen, Daan Camps, Aaron Szasz, Siva Darbha, Katherine Klymko, David B. Williams-Young, Norm M. Tubman, and Roel Van Beeumen. ``Estimating eigenenergies from quantum dynamics: A unified noise-resilient measurement-driven approach''. In 2023 QCE. Pages 302–303. (2023).
https://doi.org/10.1109/QCE57702.2023.10253
[21] Amara Katabarwa, Katerina Gratsea, Athena Caesura, and Peter D. Johnson. ``Early fault-tolerant quantum computing''. PRX Quantum 5, 020101 (2024).
https://doi.org/10.1103/PRXQuantum.5.020101
[22] Zhiyan Ding, Yulong Dong, Yu Tong, and Lin Lin. ``Robust ground-state energy estimation under depolarizing noise'' (2023).
[23] Haoya Li, Hongkang Ni, and Lexing Ying. ``A note on spike localization for line spectrum estimation''. Appl. Comput. Harmon. Anal. 67, 101577 (2023).
https://doi.org/10.1016/j.acha.2023.101577
[24] 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, 073023 (2009).
https://doi.org/10.1088/1367-2630/11/7/073023
[25] 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).
https://doi.org/10.1103/PhysRevA.92.062315
[26] William Huggins, Joonho Lee, Unpil Baek, Bryan O'Gorman, and K Whaley. ``A non-orthogonal variational quantum eigensolver''. New J. Phys. 22 (2020).
https://doi.org/10.1088/1367-2630/ab867b
[27] Katherine Klymko, Carlos Mejuto-Zaera, Stephen J. Cotton, Filip Wudarski, Miroslav Urbanek, Diptarka Hait, Martin Head-Gordon, K. Birgitta Whaley, Jonathan Moussa, Nathan Wiebe, Wibe A. de Jong, and Norm M. Tubman. ``Real-time evolution for ultracompact Hamiltonian eigenstates on quantum hardware''. PRX Quantum 3, 020323 (2022).
https://doi.org/10.1103/PRXQuantum.3.020323
[28] Jarrod R. McClean, Mollie E. Kimchi-Schwartz, Jonathan Carter, and Wibe A. de Jong. ``Hybrid quantum-classical hierarchy for mitigation of decoherence and determination of excited states''. Phys. Rev. A 95, 042308 (2017).
https://doi.org/10.1103/PhysRevA.95.042308
[29] Mario Motta, Chong Sun, Adrian Tan, Matthew O’Rourke, Erika Ye, Austin Minnich, Fernando Brandão, and Garnet Chan. ``Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution''. Nat. Phys 16, 1–6 (2020).
https://doi.org/10.1038/s41567-019-0704-4
[30] Robert M. Parrish and Peter Leonard McMahon. ``Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation''. preprint (2019).
https://doi.org/10.48550/arXiv.1909.08925
[31] Kazuhiro Seki and Seiji Yunoki. ``Quantum power method by a superposition of time-evolved states''. PRX Quantum 2, 010333 (2021).
https://doi.org/10.1103/PRXQuantum.2.010333
[32] Nicholas H. Stair, Renke Huang, and Francesco A. Evangelista. ``A multireference quantum Krylov algorithm for strongly correlated electrons''. J. Chem. Theory Comput. 16, 2236–2245 (2020).
https://doi.org/10.1021/acs.jctc.9b01125
[33] 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).
https://doi.org/10.1088/1367-2630/aafb8e
[34] Richard Roy and Thomas Kailath. ``Esprit-estimation of signal parameters via rotational invariance techniques''. IEEE Trans. Acoust. 37, 984–995 (1989).
https://doi.org/10.1109/29.32276
[35] Weilin Li, Wenjing Liao, and Albert Fannjiang. ``Super-resolution limit of the esprit algorithm''. IEEE Trans. Inf. Theory 66, 4593–4608 (2020).
https://doi.org/10.1109/TIT.2020.2974174
[36] Zhiyan Ding, Ethan N. Epperly, Lin Lin, and Ruizhe Zhang. ``The ESPRIT algorithm under high noise: Optimal error scaling and noisy super-resolution''. preprint (2024).
https://doi.org/10.48550/arXiv.2404.03885
[37] Dominic W. Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko, and Ryan Babbush. ``Analyzing prospects for quantum advantage in topological data analysis''. PRX Quantum 5, 010319 (2024).
https://doi.org/10.1103/PRXQuantum.5.010319
[38] Sam McArdle, András Gilyén, and Mario Berta. ``Quantum state preparation without coherent arithmetic''. preprint (2022).
https://doi.org/10.48550/arXiv.2210.14892
[39] Samuel L. Braunstein, Carlton M. Caves, and Gerard J. Milburn. ``Generalized uncertainty relations: Theory, examples, and lorentz invariance''. Ann. Phys. 247, 135–173 (1996).
https://doi.org/10.1006/aphy.1996.0040
[40] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Quantum metrology''. Phys. Rev. Lett. 96, 010401 (2006).
https://doi.org/10.1103/PhysRevLett.96.010401
Cited by
[1] Youle Wang, "Resource-efficient quantum phase estimation by randomization", Quantum Science and Technology 10 3, 035036 (2025).
[2] Tyler Kharazi, Torin F. Stetina, Liwen Ko, Guang Hao Low, and K. Birgitta Whaley, "An efficient quantum algorithm for ab initio approximations of non-linear response functions", npj Quantum Information 11 1, 98 (2025).
[3] Timothy Stroschein and Markus Reiher, "After 100 Years of Quantum Mechanics: Toward a Constructive Observation-Centered Perspective", Journal of Chemical Theory and Computation 22 13, 6268 (2026).
[4] Maria Gabriela Jordão Oliveira and Nina Glaser, "Quantum block Krylov subspace projector algorithm for computing low-lying eigenenergies", Physical Review A 112 5, 052442 (2025).
[5] Yizhi Shen, Alex Buzali, Hong-Ye Hu, Katherine Klymko, Daan Camps, Susanne F. Yelin, and Roel Van Beeumen, "Efficient Measurement-Driven Eigenenergy Estimation with Classical Shadows", PRX Quantum 7 1, 010328 (2026).
[6] Michal Krompiec, Josh J. M. Kirsopp, Antonio Márquez Romero, and Vicente P. Soloviev, "A Simple Method for Seniority-Zero Quantum State Preparation", Journal of Chemical Theory and Computation 22 1, 257 (2026).
[7] Hardeep Bassi, Yizhi Shen, Harish S. Bhat, and Roel Van Beeumen, "From noisy observables to accurate ground-state energies: A quantum–classical signal subspace approach with denoising", APL Quantum 2 4, 046103 (2025).
[8] Almudena Carrera Vazquez and Aleksandros Sobczyk, "Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation", Quantum 10, 2067 (2026).
[9] 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).
[10] Nikolay V. Tkachenko, Hang Ren, Wendy M. Billings, Rebecca Tomann, K. Birgitta Whaley, and Martin Head-Gordon, "Beyond real: alternative unitary cluster Jastrow models for molecular electronic structure calculations on near-term quantum computers", Chemical Science 16 47, 22299 (2025).
[11] Shreyas Malpathak, Sangeeth Das Kallullathil, Ignacio Loaiza, Stepan Fomichev, Juan Miguel Arrazola, and Artur F. Izmaylov, "Trotter Simulation of Vibrational Hamiltonians on a Quantum Computer", Journal of Chemical Theory and Computation 22 1, 95 (2026).
[12] Jinzhao Sun, Pei Zeng, Tom Gur, and M. S. Kim, "High-precision and low-depth quantum algorithm design for eigenstate problems", Science Advances 12 3, eaeb1622 (2026).
[13] Grzegorz Rajchel-Mieldzioć, Szymon Pliś, and Emil Zak, "Quantum algorithm for solving generalized eigenvalue problems with application to the Schrödinger equation", Physical Review Research 8 2, 023192 (2026).
[14] Lei Zhang, Jizhe Lai, Xian Wu, and Xin Wang, "Quantum imaginary-time evolution with polynomial resources in evolution time", Quantum Science and Technology 11 3, 035041 (2026).
[15] 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).
[16] Oriel Kiss, Utkarsh Azad, Borja Requena, Alessandro Roggero, David Wakeham, and Juan Miguel Arrazola, "Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation", Quantum 9, 1682 (2025).
[17] Changhao Yi, Cunlu Zhou, and Jun Takahashi, "Quantum Phase Estimation by Compressed Sensing", Quantum 8, 1579 (2024).
[18] Zhiyan Ding, Lin Lin, Yilun Yang, and Ruizhe Zhang, "Quantum Filtering and Analysis of Multiplicities in Eigenvalue Spectra", PRX Quantum 7 2, 020318 (2026).
[19] Davide Castaldo and Markus Reiher, "Utility-Scale Quantum Computational Chemistry", The Journal of Physical Chemistry Letters acs.jpclett.6c00888 (2026).
[20] Yizhi Shen, Daan Camps, Aaron Szasz, Siva Darbha, Katherine Klymko, David B. Williams--Young, Norm M. Tubman, and Roel Van Beeumen, "Estimating Eigenenergies from Quantum Dynamics: A Unified Noise-Resilient Measurement-Driven Approach", Quantum 9, 1836 (2025).
[21] Antonio Márquez Romero, Josh J. M. Kirsopp, Giuseppe Buonaiuto, and Michal Krompiec, "Study of nuclear magnetic resonance spectra with the multi-modal multi-level quantum complex exponential least squares algorithm", Physical Chemistry Chemical Physics 28 13, 7930 (2026).
[22] Eleftherios Mastorakis, Muhammad Umer, Milena Guevara-Bertsch, Juris Ulmanis, Felix Rohde, and Dimitris G Angelakis, "Resource-efficient Hadamard test tailored variational framework for nonlinear dynamics on quantum computers", Quantum Science and Technology 11 1, 015061 (2026).
[23] Daochen Wang, "Energy Spectra of Compressed Quantum States", Physical Review Letters 136 7, 070604 (2026).
[24] 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).
[25] Shreyas Malpathak, Sangeeth Das Kallullathil, Ignacio Loaiza, Stepan Fomichev, Juan Miguel Arrazola, and Artur F. Izmaylov, "Trotter simulation of vibrational Hamiltonians on a quantum computer", arXiv:2508.11865, (2025).
[26] Ming-Zhi Chung, Ali H. Z. Kavaki, Artur Scherer, Abdullah Khalid, Xiangzhou Kong, Toru Kawakubo, Namit Anand, Gebremedhin A Dagnew, Zachary Webb, Allyson Silva, Gaurav Gyawali, Tennin Yan, Keisuke Fujii, Alan Ho, Masoud Mohseni, Pooya Ronagh, and John Martinis, "Partially Fault-Tolerant Quantum Computation for Megaquop Applications", arXiv:2603.13093, (2026).
[27] Jinzhao Sun, Pei Zeng, Tom Gur, and M. S. Kim, "High-precision and low-depth quantum algorithm design for eigenstate problems", arXiv:2406.04307, (2024).
[28] Tyler Kharazi, Torin F. Stetina, Liwen Ko, Guang Hao Low, and K. Birgitta Whaley, "An efficient quantum algorithm for generation of ab initio n-th order susceptibilities for non-linear spectroscopies", arXiv:2404.01454, (2024).
[29] 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).
[30] Jinzhao Sun and Pei Zeng, "Randomised composite linear-combination-of-unitaries: its role in quantum simulation and observable estimation", arXiv:2506.15658, (2025).
[31] Yusen Wu, Yukun Zhang, Chuan Wang, and Xiao Yuan, "Classical Algorithms for Hamiltonian Dynamics Mean Value and Guided Local Hamiltonian Problem", arXiv:2409.04161, (2024).
[32] Ryosuke Kimura and Kosuke Mitarai, "Fisher information based lower bounds on the cost of quantum phase estimation", arXiv:2603.12706, (2026).
[33] Osama M. Raisuddin, Haimeng Zhang, Mario Motta, and Fabian M. Faulstich, "From Promise to Practice: Benchmarking Quantum Chemistry on Quantum Hardware", arXiv:2512.01012, (2025).
[34] Lexing Ying, "A perturbative analysis for noisy spectral estimation", arXiv:2405.00803, (2024).
The above citations are from Crossref's cited-by service (last updated successfully 2026-07-15 10:33:25) and SAO/NASA ADS (last updated successfully 2026-07-14 21:39:59). 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-07-15 10:33:25: 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.