{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T20:00:11Z","timestamp":1776283211645,"version":"3.50.1"},"reference-count":40,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T00:00:00Z","timestamp":1727827200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"US Department of Energy (DOE) Office of Advanced Scientific Computing Research","award":["DEAC02-05CH1123"],"award-info":[{"award-number":["DEAC02-05CH1123"]}]},{"name":"National Science Foundation","award":["DMS-2011699"],"award-info":[{"award-number":["DMS-2011699"]}]},{"name":"National Science Foundation","award":["DMS-2208163"],"award-info":[{"award-number":["DMS-2208163"]}]},{"name":"US Department of Energy (DOE) Grant","award":["DE-SC0024124"],"award-info":[{"award-number":["DE-SC0024124"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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 &#x03F5;<\/mml:mi><\/mml:math> 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<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>)<\/mml:mo><\/mml:math>. 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.<\/jats:p>","DOI":"10.22331\/q-2024-10-02-1487","type":"journal-article","created":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T11:28:21Z","timestamp":1727868501000},"page":"1487","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":18,"title":["Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method"],"prefix":"10.22331","volume":"8","author":[{"given":"Zhiyan","family":"Ding","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of California, Berkeley, CA 94720, USA"}]},{"given":"Haoya","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Stanford University, CA 94305, USA"}]},{"given":"Lin","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of California, Berkeley, CA 94720, USA"},{"name":"Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA"},{"name":"Challenge Institute for Quantum Computation, University of California, Berkeley, CA 94720, USA"}]},{"given":"HongKang","family":"Ni","sequence":"additional","affiliation":[{"name":"Institute for Computational and Mathematical Engineering, Stanford University, CA 94305, USA"}]},{"given":"Lexing","family":"Ying","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Stanford University, CA 94305, USA"},{"name":"Institute for Computational and Mathematical Engineering, Stanford University, CA 94305, USA"}]},{"given":"Ruizhe","family":"Zhang","sequence":"additional","affiliation":[{"name":"Simons Institute for the Theory of Computing, University of California, Berkeley, CA 94720, USA"}]}],"member":"9598","published-online":{"date-parts":[[2024,10,2]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Michael A Nielsen and Isaac Chuang. ``Quantum computation and quantum information''. Cambridge Univ. Pr. (2000).","DOI":"10.1017\/CBO9780511976667"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Daniel S Abrams and Seth Lloyd. ``Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors''. Phys. Rev. Lett. 83, 5162 (1999).","DOI":"10.1103\/PhysRevLett.83.5162"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1063\/1.5027484"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Lin Lin and Yu Tong. ``Near-optimal ground state preparation''. Quantum 4, 372 (2020).","DOI":"10.22331\/q-2020-12-14-372"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Lin Lin and Yu Tong. ``Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers''. PRX Quantum 3, 010318 (2022).","DOI":"10.1103\/PRXQuantum.3.010318"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PRXQuantum.3.040305"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Kianna Wan, Mario Berta, and Earl T Campbell. ``Randomized quantum algorithm for statistical phase estimation''. Phys. Rev. Lett. 129, 030503 (2022).","DOI":"10.1103\/PhysRevLett.129.030503"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Ruizhe Zhang, Guoming Wang, and Peter Johnson. ``Computing ground state properties with early fault-tolerant quantum computers''. Quantum 6, 761 (2022).","DOI":"10.22331\/q-2022-07-11-761"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Guoming Wang, Daniel Stilck Fran\u00e7a, 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).","DOI":"10.22331\/q-2023-11-06-1167"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PRXQuantum.4.020331"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Hongkang Ni, Haoya Li, and Lexing Ying. ``On low-depth algorithms for quantum phase estimation''. Quantum (2023).","DOI":"10.22331\/q-2023-11-06-1165"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Nick S. Blunt, Laura Caune, R\u00f3bert Izs\u00e1k, Earl T. Campbell, and Nicole Holzmann. ``Statistical phase estimation and error mitigation on a superconducting quantum processor''. PRX Quantum 4, 040341 (2023).","DOI":"10.1103\/PRXQuantum.4.040341"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Rolando D Somma. ``Quantum eigenvalue estimation via time series analysis''. New J. Phys. 21, 123025 (2019).","DOI":"10.1088\/1367-2630\/ab5c60"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1088\/1367-2630\/ac919c"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Cristian L. Cortes and Stephen K. Gray. ``Quantum Krylov subspace algorithms for ground- and excited-state energy estimation''. Phys. Rev. A 105, 022417 (2022).","DOI":"10.1103\/PhysRevA.105.022417"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Ethan N. Epperly, Lin Lin, and Yuji Nakatsukasa. ``A theory of quantum subspace diagonalization''. SIAM J. Matrix Anal. Appl. 43, 1263\u20131290 (2022).","DOI":"10.1137\/21M145954X"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.22331\/q-2022-10-06-830"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.22331\/q-2023-10-11-1136"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Haoya Li, Hongkang Ni, and Lexing Ying. ``Adaptive low-depth quantum algorithms for robust multiple-phase estimation''. Phys. Rev. A 108, 062408 (2023).","DOI":"10.1103\/PhysRevA.108.062408"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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\u2013303. (2023).","DOI":"10.1109\/QCE57702.2023.10253"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Amara Katabarwa, Katerina Gratsea, Athena Caesura, and Peter D. Johnson. ``Early fault-tolerant quantum computing''. PRX Quantum 5, 020101 (2024).","DOI":"10.1103\/PRXQuantum.5.020101"},{"key":"21","doi-asserted-by":"crossref","unstructured":"Zhiyan Ding, Yulong Dong, Yu Tong, and Lin Lin. ``Robust ground-state energy estimation under depolarizing noise'' (2023).","DOI":"10.21203\/rs.3.rs-3222358\/v1"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Haoya Li, Hongkang Ni, and Lexing Ying. ``A note on spike localization for line spectrum estimation''. Appl. Comput. Harmon. Anal. 67, 101577 (2023).","DOI":"10.1016\/j.acha.2023.101577"},{"key":"23","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1088\/1367-2630\/11\/7\/073023"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.92.062315"},{"key":"25","doi-asserted-by":"publisher","unstructured":"William Huggins, Joonho Lee, Unpil Baek, Bryan O'Gorman, and K Whaley. ``A non-orthogonal variational quantum eigensolver''. New J. Phys. 22 (2020).","DOI":"10.1088\/1367-2630\/ab867b"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PRXQuantum.3.020323"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.95.042308"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Mario Motta, Chong Sun, Adrian Tan, Matthew O\u2019Rourke, Erika Ye, Austin Minnich, Fernando Brand\u00e3o, and Garnet Chan. ``Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution''. Nat. Phys 16, 1\u20136 (2020).","DOI":"10.1038\/s41567-019-0704-4"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Robert M. Parrish and Peter Leonard McMahon. ``Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation''. preprint (2019).","DOI":"10.48550\/arXiv.1909.08925"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Kazuhiro Seki and Seiji Yunoki. ``Quantum power method by a superposition of time-evolved states''. PRX Quantum 2, 010333 (2021).","DOI":"10.1103\/PRXQuantum.2.010333"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Nicholas H. Stair, Renke Huang, and Francesco A. Evangelista. ``A multireference quantum Krylov algorithm for strongly correlated electrons''. J. Chem. Theory Comput. 16, 2236\u20132245 (2020).","DOI":"10.1021\/acs.jctc.9b01125"},{"key":"32","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1088\/1367-2630\/aafb8e"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Richard Roy and Thomas Kailath. ``Esprit-estimation of signal parameters via rotational invariance techniques''. IEEE Trans. Acoust. 37, 984\u2013995 (1989).","DOI":"10.1109\/29.32276"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Weilin Li, Wenjing Liao, and Albert Fannjiang. ``Super-resolution limit of the esprit algorithm''. IEEE Trans. Inf. Theory 66, 4593\u20134608 (2020).","DOI":"10.1109\/TIT.2020.2974174"},{"key":"35","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.48550\/arXiv.2404.03885"},{"key":"36","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PRXQuantum.5.010319"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Sam McArdle, Andr\u00e1s Gily\u00e9n, and Mario Berta. ``Quantum state preparation without coherent arithmetic''. preprint (2022).","DOI":"10.48550\/arXiv.2210.14892"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Samuel L. Braunstein, Carlton M. Caves, and Gerard J. Milburn. ``Generalized uncertainty relations: Theory, examples, and lorentz invariance''. Ann. Phys. 247, 135\u2013173 (1996).","DOI":"10.1006\/aphy.1996.0040"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Quantum metrology''. Phys. Rev. Lett. 96, 010401 (2006).","DOI":"10.1103\/PhysRevLett.96.010401"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-10-02-1487\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T11:28:30Z","timestamp":1727868510000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-10-02-1487\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,2]]},"references-count":40,"URL":"https:\/\/doi.org\/10.22331\/q-2024-10-02-1487","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,2]]},"article-number":"1487"}}