{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T00:36:10Z","timestamp":1783989370773,"version":"3.55.0"},"reference-count":42,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,12,27]],"date-time":"2024-12-27T00:00:00Z","timestamp":1735257600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["92165109"],"award-info":[{"award-number":["92165109"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Key Research and Development Program of China","award":["2022YFA1404204"],"award-info":[{"award-number":["2022YFA1404204"]}]},{"DOI":"10.13039\/100000001","name":"U.S. National Science Foundation","doi-asserted-by":"crossref","award":["2116246"],"award-info":[{"award-number":["2116246"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"As a signal recovery algorithm, compressed sensing is particularly effective when the data has low complexity and samples are scarce, which aligns natually with the task of quantum phase estimation (QPE) on early fault-tolerant quantum computers. In this work, we present a new Heisenberg-limited, robust QPE algorithm based on compressed sensing, which requires only sparse and discrete sampling of times. Specifically, given multiple copies of a suitable initial state and queries to a specific unitary matrix, our algorithm can recover the phase with a total runtime of O<\/mml:mi><\/mml:mrow>(<\/mml:mo>&#x03F5;<\/mml:mi>&#x2212;<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:msup>poly<\/mml:mtext>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>&#x03F5;<\/mml:mi>&#x2212;<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo>)<\/mml:mo><\/mml:math>, where &#x03F5;<\/mml:mi><\/mml:math> is the desired accuracy. Additionally, the maximum runtime satisfies T<\/mml:mi>max<\/mml:mo><\/mml:mrow><\/mml:msub>&#x03F5;<\/mml:mi>&#x226A;<\/mml:mo>&#x03C0;<\/mml:mi><\/mml:math>, making it comparable to state-of-the-art algorithms. Furthermore, our result resolves the basis mismatch problem in certain cases by introducing an additional parameter to the traditional compressed sensing framework.<\/jats:p>","DOI":"10.22331\/q-2024-12-27-1579","type":"journal-article","created":{"date-parts":[[2024,12,27]],"date-time":"2024-12-27T17:08:35Z","timestamp":1735319315000},"page":"1579","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":4,"title":["Quantum Phase Estimation by Compressed Sensing"],"prefix":"10.22331","volume":"8","author":[{"given":"Changhao","family":"Yi","sequence":"first","affiliation":[{"name":"State Key Laboratory of Surface Physics, Department of Physics, and Center for Field Theory and Particle Physics, Fudan University, Shanghai, China"},{"name":"Institute for Nanoelectronic Devices and Quantum Computing, Fudan University, Shanghai, China"},{"name":"Shanghai Research Center for Quantum Sciences, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cunlu","family":"Zhou","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Institut Quantique, Universit\u00e9 de Sherbrooke, QC, Canada"},{"name":"Center for Quantum Information and Control & Department of Physics and Astronomy, University of New Mexico, NM, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jun","family":"Takahashi","sequence":"additional","affiliation":[{"name":"Institute of Solid State Physics, University of Tokyo, Chiba, Japan"},{"name":"Center for Quantum Information and Control & Department of Physics and Astronomy, University of New Mexico, NM, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2024,12,27]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Alexei Y Kitaev. ``Quantum measurements and the Abelian stabilizer problem''. quant-ph\/9511026 (1995).","DOI":"10.48550\/arXiv.quant-ph\/9511026"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Peter W Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM review 41, 303\u2013332 (1999).","DOI":"10.1137\/S0097539795293172"},{"key":"2","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":"3","doi-asserted-by":"publisher","unstructured":"Sam McArdle, Suguru Endo, Al\u00e1n Aspuru-Guzik, Simon C Benjamin, and Xiao Yuan. ``Quantum computational chemistry''. Rev. Mod. Phys. 92, 015003 (2020).","DOI":"10.1103\/RevModPhys.92.015003"},{"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":"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":"6","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":"7","doi-asserted-by":"publisher","unstructured":"Thomas E O\u2019Brien, 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":"8","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\/qv-2022-07-22-65"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Alicja Dutkiewicz, Barbara M Terhal, and Thomas E O\u2019Brien. ``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":"10","doi-asserted-by":"publisher","unstructured":"Michael A Nielsen and Isaac L Chuang. ``Quantum computation and quantum information''. Cambridge university press. (2010).","DOI":"10.1017\/CBO9780511976667"},{"key":"11","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":"12","doi-asserted-by":"publisher","unstructured":"Hongkang Ni, Haoya Li, and Lexing Ying. ``On low-depth algorithms for quantum phase estimation''. Quantum 7, 1165 (2023).","DOI":"10.22331\/q-2023-11-06-1165"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Iulia M Georgescu, Sahel Ashhab, and Franco Nori. ``Quantum simulation''. Rev. Mod. Phys. 86, 153 (2014).","DOI":"10.1103\/RevModPhys.86.153"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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 (2021).","DOI":"10.1103\/PhysRevX.11.011020"},{"key":"15","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":"16","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":"17","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.22331\/q-2024-10-02-1487"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Itai Arad, Tomotaka Kuwahara, and Zeph Landau. ``Connecting global and local energy distributions in quantum spin models on a lattice''. J. Stat. Mech. Theor. Exp. 2016, 033301 (2016).","DOI":"10.1088\/1742-5468\/2016\/03\/033301"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Andrew M Childs and Yuan Su. ``Nearly optimal lattice simulation by product formulas''. Phys. Rev. Lett. 123, 050503 (2019).","DOI":"10.1103\/PhysRevLett.123.050503"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. ``Nearly optimal sparse Fourier transform''. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing. Pages 563\u2013578. (2012).","DOI":"10.1145\/2213977.2214029"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Wenjing Liao and Albert Fannjiang. ``MUSIC for single-snapshot spectral estimation: Stability and super-resolution''. Appl. Comput. Harmon. Anal. 40, 33\u201367 (2016).","DOI":"10.1016\/j.acha.2014.12.003"},{"key":"22","doi-asserted-by":"crossref","unstructured":"Zhao Song, Baocheng Sun, Omri Weinstein, and Ruizhe Zhang. ``Quartic samples suffice for Fourier interpolation''. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1414\u20131425. IEEE (2023).","DOI":"10.1109\/FOCS57990.2023.00087"},{"key":"23","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''. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 2344\u20132366. IEEE (2024).","DOI":"10.1109\/FOCS61266.2024.00137"},{"key":"24","doi-asserted-by":"publisher","unstructured":"William T Cochran, James W Cooley, David L Favin, Howard D Helms, Reginald A Kaenel, William W Lang, George C Maling, David E Nelson, Charles M Rader, and Peter D Welch. ``What is the fast Fourier transform?''. Proceedings of the IEEE 55, 1664\u20131674 (1967).","DOI":"10.1109\/PROC.1967.5957"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Anna C Gilbert, Shan Muthukrishnan, and Martin Strauss. ``Improved time bounds for near-optimal sparse Fourier representations''. In Manos Papadakis, Andrew F. Laine, and Michael A. Unser, editors, Wavelets XI. Volume 5914, page 59141A. International Society for Optics and PhotonicsSPIE (2005).","DOI":"10.1117\/12.615931"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Piotr Indyk, Michael Kapralov, and Eric Price. ``(Nearly) sample-optimal sparse Fourier transform''. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Pages 480\u2013499. SIAM (2014).","DOI":"10.1109\/FOCS.2019.00092"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Brendon L Higgins, Dominic W Berry, Stephen D Bartlett, Morgan W Mitchell, Howard M Wiseman, and Geoff 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":"28","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":"29","doi-asserted-by":"publisher","unstructured":"Federico Belliardo and Vittorio Giovannetti. ``Achieving Heisenberg scaling with maximally entangled states: An analytic upper bound for the attainable root-mean-square error''. Phys. Rev. A 102 (2020).","DOI":"10.1103\/physreva.102.042613"},{"key":"30","doi-asserted-by":"publisher","unstructured":"T Tony Cai and Lie Wang. ``Orthogonal matching pursuit for sparse signal recovery with noise''. IEEE Transactions on Information theory 57, 4680\u20134688 (2011).","DOI":"10.1109\/TIT.2011.2146090"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Emmanuel J Cand\u00e8s and Terence Tao. ``Near-optimal signal recovery from random projections: Universal encoding strategies?''. IEEE transactions on information theory 52, 5406\u20135425 (2006).","DOI":"10.1109\/TIT.2006.885507"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Emmanuel J Cand\u00e8s. ``The restricted isometry property and its implications for compressed sensing''. Comptes rendus. Mathematique 346, 589\u2013592 (2008).","DOI":"10.1016\/j.crma.2008.03.014"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Emmanuel J Cand\u00e8s, Justin Romberg, and Terence Tao. ``Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information''. IEEE Transactions on information theory 52, 489\u2013509 (2006).","DOI":"10.1109\/TIT.2005.862083"},{"key":"34","doi-asserted-by":"publisher","unstructured":"David Gross, Yi-Kai Liu, Steven T Flammia, Stephen Becker, and Jens Eisert. ``Quantum state tomography via compressed sensing''. Phys. Rev. Lett. 105, 150401 (2010).","DOI":"10.1103\/PhysRevLett.105.150401"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Easwar Magesan, Alexandre Cooper, and Paola Cappellaro. ``Compressing measurements in quantum dynamic parameter estimation''. Phys. Rev. A 88, 062109 (2013).","DOI":"10.1103\/PhysRevA.88.062109"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Aaron Smith, Riofr\u00edo Carlos, Brielle Evelyn Anderson, Hector Sosa Martinez, Ivan H Deutsch, and Poul Jessen. ``Quantum state tomography by continuous measurement and compressed sensing''. Phys. Rev. A 87, 030102 (2013).","DOI":"10.1103\/PhysRevA.87.030102"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Amir Kalev, Robert L Kosut, and Ivan H Deutsch. ``Quantum tomography protocols with positivity are compressed sensing protocols''. Npj Quantum Inf. 1, 15018 (2015).","DOI":"10.1038\/npjqi.2015.18"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah, and Benjamin Recht. ``Compressed sensing off the grid''. IEEE transactions on information theory 59, 7465\u20137490 (2013).","DOI":"10.1109\/TIT.2013.2277451"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Juditsky Anatoli, Kilinc Karzan Fatma, and Nermirovski Arkadi. ``Randomized first order algorithms with applications to $\\ell_1$-minimization''. Math. Program. 142, 269\u2013310 (2013).","DOI":"10.1007\/s10107-012-0575-2"},{"key":"40","unstructured":"https:\/\/github.com\/CYI1995\/QEEP\/tree\/main\/Paper_QPE."},{"key":"41","doi-asserted-by":"publisher","unstructured":"Mark Rudelson and Roman Vershynin. ``On sparse reconstruction from Fourier and Gaussian measurements''. Comm. Pure Appl. Math. 61, 1025\u20131045 (2008).","DOI":"10.1002\/cpa.20227"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-12-27-1579\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,27]],"date-time":"2024-12-27T17:08:54Z","timestamp":1735319334000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-12-27-1579\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,27]]},"references-count":42,"URL":"https:\/\/doi.org\/10.22331\/q-2024-12-27-1579","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,27]]},"article-number":"1579"}}