Quantum Phase Estimation by Compressed Sensing

Changhao Yi; Cunlu Zhou; Jun Takahashi

doi:10.22331/q-2024-12-27-1579

Quantum Phase Estimation by Compressed Sensing

Changhao Yi^1,2,3, Cunlu Zhou^4,5, and Jun Takahashi^6,5

¹State Key Laboratory of Surface Physics, Department of Physics, and Center for Field Theory and Particle Physics, Fudan University, Shanghai, China
²Institute for Nanoelectronic Devices and Quantum Computing, Fudan University, Shanghai, China
³Shanghai Research Center for Quantum Sciences, Shanghai, China
⁴Department of Computer Science & Institut Quantique, Université de Sherbrooke, QC, Canada
⁵Center for Quantum Information and Control & Department of Physics and Astronomy, University of New Mexico, NM, USA
⁶Institute of Solid State Physics, University of Tokyo, Chiba, Japan

Published:	2024-12-27, volume 8, page 1579
Eprint:	arXiv:2306.07008v5
Doi:	https://doi.org/10.22331/q-2024-12-27-1579
Citation:	Quantum 8, 1579 (2024).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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 $\mathcal{O}(\epsilon^{-1}\text{poly}\log (\epsilon^{-1}))$, where $\epsilon$ is the desired accuracy. Additionally, the maximum runtime satisfies $T_{\max}\epsilon \ll \pi$, 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.

Featured image: The quantum circuit of Hadamard test

► BibTeX data

@article{Yi2024quantumphase,
  doi = {10.22331/q-2024-12-27-1579},
  url = {https://doi.org/10.22331/q-2024-12-27-1579},
  title = {Quantum {P}hase {E}stimation by {C}ompressed {S}ensing},
  author = {Yi, Changhao and Zhou, Cunlu and Takahashi, Jun},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1579},
  month = dec,
  year = {2024}
}

► References

[1] Alexei Y Kitaev. ``Quantum measurements and the Abelian stabilizer problem''. quant-ph/9511026 (1995).
https://doi.org/10.48550/arXiv.quant-ph/9511026
arXiv:quant-ph/9511026

[2] Peter W Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM review 41, 303–332 (1999).
https://doi.org/10.1137/S0097539795293172

[3] 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

[4] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C Benjamin, and Xiao Yuan. ``Quantum computational chemistry''. Rev. Mod. Phys. 92, 015003 (2020).
https://doi.org/10.1103/RevModPhys.92.015003

[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] 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

[7] Rolando D Somma. ``Quantum eigenvalue estimation via time series analysis''. New J. Phys. 21, 123025 (2019).
https://doi.org/10.1088/1367-2630/ab5c60

[8] 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

[9] 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/qv-2022-07-22-65

[10] 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

[11] Michael A Nielsen and Isaac L Chuang. ``Quantum computation and quantum information''. Cambridge university press. (2010).
https://doi.org/10.1017/CBO9780511976667

[12] 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

[13] Hongkang Ni, Haoya Li, and Lexing Ying. ``On low-depth algorithms for quantum phase estimation''. Quantum 7, 1165 (2023).
https://doi.org/10.22331/q-2023-11-06-1165

[14] Iulia M Georgescu, Sahel Ashhab, and Franco Nori. ``Quantum simulation''. Rev. Mod. Phys. 86, 153 (2014).
https://doi.org/10.1103/RevModPhys.86.153

[15] 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).
https://doi.org/10.1103/PhysRevX.11.011020

[16] 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

[17] 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

[18] 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).
https://doi.org/10.22331/q-2024-10-02-1487

[19] 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).
https://doi.org/10.1088/1742-5468/2016/03/033301

[20] Andrew M Childs and Yuan Su. ``Nearly optimal lattice simulation by product formulas''. Phys. Rev. Lett. 123, 050503 (2019).
https://doi.org/10.1103/PhysRevLett.123.050503

[21] 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–578. (2012).
https://doi.org/10.1145/2213977.2214029

[22] Wenjing Liao and Albert Fannjiang. ``MUSIC for single-snapshot spectral estimation: Stability and super-resolution''. Appl. Comput. Harmon. Anal. 40, 33–67 (2016).
https://doi.org/10.1016/j.acha.2014.12.003

[23] 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–1425. IEEE (2023).

[24] 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–2366. IEEE (2024).
https://doi.org/10.1109/FOCS61266.2024.00137

[25] 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–1674 (1967).
https://doi.org/10.1109/PROC.1967.5957

[26] 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).
https://doi.org/10.1117/12.615931

[27] 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–499. SIAM (2014).
https://doi.org/10.1109/FOCS.2019.00092

[28] 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).
https://doi.org/10.1088/1367-2630/11/7/073023

[29] 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

[30] 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).
https://doi.org/10.1103/physreva.102.042613

[31] T Tony Cai and Lie Wang. ``Orthogonal matching pursuit for sparse signal recovery with noise''. IEEE Transactions on Information theory 57, 4680–4688 (2011).
https://doi.org/10.1109/TIT.2011.2146090

[32] Emmanuel J Candès and Terence Tao. ``Near-optimal signal recovery from random projections: Universal encoding strategies?''. IEEE transactions on information theory 52, 5406–5425 (2006).
https://doi.org/10.1109/TIT.2006.885507

[33] Emmanuel J Candès. ``The restricted isometry property and its implications for compressed sensing''. Comptes rendus. Mathematique 346, 589–592 (2008).
https://doi.org/10.1016/j.crma.2008.03.014

[34] Emmanuel J Candès, Justin Romberg, and Terence Tao. ``Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information''. IEEE Transactions on information theory 52, 489–509 (2006).
https://doi.org/10.1109/TIT.2005.862083

[35] 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).
https://doi.org/10.1103/PhysRevLett.105.150401

[36] Easwar Magesan, Alexandre Cooper, and Paola Cappellaro. ``Compressing measurements in quantum dynamic parameter estimation''. Phys. Rev. A 88, 062109 (2013).
https://doi.org/10.1103/PhysRevA.88.062109

[37] Aaron Smith, Riofrío 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).
https://doi.org/10.1103/PhysRevA.87.030102

[38] Amir Kalev, Robert L Kosut, and Ivan H Deutsch. ``Quantum tomography protocols with positivity are compressed sensing protocols''. Npj Quantum Inf. 1, 15018 (2015).
https://doi.org/10.1038/npjqi.2015.18

[39] Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah, and Benjamin Recht. ``Compressed sensing off the grid''. IEEE transactions on information theory 59, 7465–7490 (2013).
https://doi.org/10.1109/TIT.2013.2277451

[40] Juditsky Anatoli, Kilinc Karzan Fatma, and Nermirovski Arkadi. ``Randomized first order algorithms with applications to $\ell_1$-minimization''. Math. Program. 142, 269–310 (2013).
https://doi.org/10.1007/s10107-012-0575-2

[41] https://github.com/CYI1995/QEEP/tree/main/Paper_QPE.
https://github.com/CYI1995/QEEP/tree/main/Paper_QPE

[42] Mark Rudelson and Roman Vershynin. ``On sparse reconstruction from Fourier and Gaussian measurements''. Comm. Pure Appl. Math. 61, 1025–1045 (2008).
https://doi.org/10.1002/cpa.20227

Cited by

[1] Davide Castaldo and Markus Reiher, "Utility-Scale Quantum Computational Chemistry", The Journal of Physical Chemistry Letters 17 29, 8140 (2026).

[2] Zhiyan Ding, Lin Lin, Yilun Yang, and Ruizhe Zhang, "Quantum Filtering and Analysis of Multiplicities in Eigenvalue Spectra", PRX Quantum 7 2, 020318 (2026).

[3] Thamaraimanalan T, Anandakumar Haldorai, Arulmurugan Ramu, and Mariyappan K, "Performance Evaluation of Shor Algorithm on Simulated Quantum Hardware with Circuit Level Analysis", Journal of Machine and Computing 1944 (2025).

[4] Smik Patel, Praveen Jayakumar, Tzu-Ching Yen, and Artur F. Izmaylov, "Quantum Measurement for Quantum Chemistry on a Quantum Computer", Chemical Reviews 125 16, 7490 (2025).

[5] Kévin Hémery, Khaldoon Ghanem, Eleanor Crane, Sara L. Campbell, Joan M. Dreiling, Caroline Figgatt, Cameron Foltz, John P. Gaebler, Jacob Johansen, Michael Mills, Steven A. Moses, Juan M. Pino, Anthony Ransford, Mary Rowe, Peter Siegfried, Russell P. Stutz, Henrik Dreyer, Alexander Schuckert, and Ramil Nigmatullin, "Measuring the Loschmidt Amplitude for Finite-Energy Properties of the Fermi-Hubbard Model on an Ion-Trap Quantum Computer", PRX Quantum 5 3, 030323 (2024).

[6] 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).

[7] N. V. Panokin, I. A. Kostin, A. V. Averin, A. V. Karlovskii, D. I. Orelkina, and A. Yu. Nalivaiko, "Application of Sparse Representation of Complex Data in Railway Positioning and Collision Alert Systems Using Millimeter-Wave Radar", Gyroscopy and Navigation 15 1, 59 (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-08 03:41:48) and SAO/NASA ADS (last updated successfully 2026-08-08 03:41:49). 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.