1Department of Mathematics, University of California, Berkeley, CA 94720, USA
2Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
3Challenge Institute of Quantum Computation, University of California, Berkeley, CA 94720, USA
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We introduce a multi-modal, multi-level quantum complex exponential least squares (MM-QCELS) method to simultaneously estimate multiple eigenvalues of a quantum Hamiltonian on early fault-tolerant quantum computers. Our theoretical analysis demonstrates that the algorithm exhibits Heisenberg-limited scaling in terms of circuit depth and total cost. Notably, the proposed quantum circuit utilizes just one ancilla qubit, and with appropriate initial state conditions, it achieves significantly shorter circuit depths compared to circuits based on quantum phase estimation (QPE). Numerical results suggest that compared to QPE, the circuit depth can be reduced by around two orders of magnitude under several settings for estimating ground-state and excited-state energies of certain quantum systems.
Featured image: Multi-modal, Multi-level QCELS
Popular summary
In our paper, we introduce the multi-modal, multi-level quantum complex exponential least squares (MM-QCELS) method for estimating multiple eigenvalues of a quantum Hamiltonian. Our approach employs a simple quantum circuit with only one ancilla qubit. We prove that the circuit depth and total cost of our method satisfies the Heisenberg-limited scaling. Furthermore, with suitable initial-state conditions, our circuit depth can be significantly shorter than that of quantum phase estimation (QPE) circuits. Therefore, this method is especially suitable for early fault-tolerant quantum computers.
► BibTeX data
► References
[1] D. W. Berry, B. L. Higgins, S. D. Bartlett, M. W. Mitchell, G. J. Pryde, and H. M. Wiseman. How to perform the most accurate possible phase measurements. Phys. Rev. A, 80(5):052114, 2009. doi:10.1103/PhysRevA.80.052114.
https://doi.org/10.1103/PhysRevA.80.052114
[2] P. Boufounos, V. Cevher, A. C. Gilbert, Y. Li, and M. J. Strauss. What’s the frequency, kenneth?: Sublinear Fourier sampling off the grid. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 61–72, 2012. doi:10.1007/s00453-014-9918-0.
https://doi.org/10.1007/s00453-014-9918-0
[3] E. J. Candès and C. Fernandez-Granda. Towards a mathematical theory of super-resolution. Communications on Pure and Applied Mathematics, 67(6):906–956, 2014. doi:10.1002/cpa.21455.
https://doi.org/10.1002/cpa.21455
[4] S. Chen and A. Moitra. Algorithmic foundations for the diffraction limit. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, page 490–503, 2021. doi:10.1145/3406325.3451078.
https://doi.org/10.1145/3406325.3451078
[5] C. L. Cortes and S. 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.
https://doi.org/10.1103/PhysRevA.105.022417
[6] Z. Ding and L. 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, May 2023. doi:10.1103/PRXQuantum.4.020331.
https://doi.org/10.1103/PRXQuantum.4.020331
[7] Y. Dong, L. Lin, and Y. 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.
https://doi.org/10.1103/PRXQuantum.3.040305
[8] M. F. Duarte and R. G. Baraniuk. Spectral compressive sensing. Applied and Computational Harmonic Analysis, 35(1):111–129, 2013. doi:10.1016/j.acha.2012.08.003.
https://doi.org/10.1016/j.acha.2012.08.003
[9] A. Dutkiewicz, B. M. Terhal, and T. 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.
https://doi.org/10.22331/q-2022-10-06-830
[10] E. N. Epperly, L. Lin, and Y. Nakatsukasa. A theory of quantum subspace diagonalization. SIAM Journal on Matrix Analysis and Applications, 43(3):1263–1290, 2022. doi:10.1137/21M145954X.
https://doi.org/10.1137/21M145954X
[11] V. Giovannetti, S. Lloyd, and L. Maccone. Advances in quantum metrology. Nature Photonics, 5(4):222–229, 2011. doi:10.1038/nphoton.2011.35.
https://doi.org/10.1038/nphoton.2011.35
[12] R. B. Griffiths and C.-S. Niu. Semiclassical Fourier transform for quantum computation. Phys. Rev. Lett., 76:3228–3231, 1996. doi:10.1103/PhysRevLett.76.3228.
https://doi.org/10.1103/PhysRevLett.76.3228
[13] B. L. Higgins, D. W. Berry, S. D. Bartlett, H. M. Wiseman, and G. J. Pryde. Entanglement-free Heisenberg-limited phase estimation. Nature, 450(7168):393–396, 2007. doi:10.1038/nature06257.
https://doi.org/10.1038/nature06257
[14] W. Huggins, J. Lee, U. Baek, B. O’Gorman, and K. Whaley. A non-orthogonal variational quantum eigensolver. New Journal of Physics, 22, 2020. doi:10.1088/1367-2630/ab867b.
https://doi.org/10.1088/1367-2630/ab867b
[15] Y. Jin, D. Liu, and Z. Song. Super-resolution and robust sparse continuous Fourier transform in any constant dimension: nearly linear time and sample complexity. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4667–4767, 2023. doi:10.1137/1.9781611977554.ch176.
https://doi.org/10.1137/1.9781611977554.ch176
[16] M. Kapralov. Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, page 264–277, 2016. doi:10.1145/2897518.2897650.
https://doi.org/10.1145/2897518.2897650
[17] A. Y. Kitaev, A. Shen, and M. N. Vyalyi. Classical and quantum computation. American Mathematical Soc., 2002.
[18] K. Klymko, C. Mejuto-Zaera, S. J. Cotton, F. Wudarski, M. Urbanek, D. Hait, M. Head-Gordon, K. B. Whaley, J. Moussa, N. Wiebe, W. A. de Jong, and N. M. Tubman. Real-time evolution for ultracompact Hamiltonian eigenstates on quantum hardware. PRX Quantum, 3:020323, 2022. doi:10.1103/PRXQuantum.3.020323.
https://doi.org/10.1103/PRXQuantum.3.020323
[19] E. Knill, G. Ortiz, and R. D. Somma. Optimal quantum measurements of expectation values of observables. Phys. Rev. A, 75:012328, 2007. doi:10.1103/PhysRevA.75.012328.
https://doi.org/10.1103/PhysRevA.75.012328
[20] H. Li, H. Ni, and L. Ying. A note on spike localization for line spectrum estimation. preprint, 2023. doi:10.48550/arXiv.2303.00946.
https://doi.org/10.48550/arXiv.2303.00946
[21] H. Li, H. Ni, and L. Ying. On low-depth quantum algorithms for robust multiple-phase estimation. preprint, 2023. doi:10.48550/arXiv.2303.08099.
https://doi.org/10.48550/arXiv.2303.08099
[22] W. Li, W. Liao, and A. Fannjiang. Super-resolution limit of the esprit algorithm. IEEE Transactions on Information Theory, 66(7):4593–4608, 2020. doi:10.1109/TIT.2020.2974174.
https://doi.org/10.1109/TIT.2020.2974174
[23] L. Lin and Y. Tong. Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3:010318, 2022. doi:10.1103/PRXQuantum.3.010318.
https://doi.org/10.1103/PRXQuantum.3.010318
[24] J. R. McClean, M. E. Kimchi-Schwartz, J. Carter, and W. 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.
https://doi.org/10.1103/PhysRevA.95.042308
[25] M. Motta, C. Sun, A. Tan, M. O’Rourke, E. Ye, A. Minnich, F. Brandão, and G. Chan. Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nature Physics, 16:1–6, 2020. doi:10.1038/s41567-019-0704-4.
https://doi.org/10.1038/s41567-019-0704-4
[26] D. Nagaj, P. Wocjan, and Y. Zhang. Fast amplification of QMA. Quantum Inf. Comput., 9(11), 2009. doi:10.5555/2012098.2012106.
https://doi.org/10.5555/2012098.2012106
[27] H. Ni, H. Li, and L. Ying. On low-depth algorithms for quantum phase estimation. preprint, 2023. doi:10.48550/arXiv.2302.02454.
https://doi.org/10.48550/arXiv.2302.02454
[28] M. A. Nielsen and I. Chuang. Quantum computation and quantum information. Cambridge Univ. Pr., 2000. doi:10.5555/1972505.
https://doi.org/10.5555/1972505
[29] T. E. O’Brien, B. Tarasinski, and B. M. Terhal. Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments. New J. Phys., 21(2):023022, 2019. doi:10.1088/1367-2630/aafb8e.
https://doi.org/10.1088/1367-2630/aafb8e
[30] R. M. Parrish and P. L. McMahon. Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation. preprint, 2019. doi:10.48550/arXiv.1909.08925.
https://doi.org/10.48550/arXiv.1909.08925
[31] D. Poulin and P. Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. Phys. Rev. Lett., 103:220502, Nov 2009. doi:10.1103/PhysRevLett.103.220502.
https://doi.org/10.1103/PhysRevLett.103.220502
[32] E. Price and Z. Song. A robust sparse Fourier transform in the continuous setting. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 583–600, 10 2015. doi:10.1109/FOCS.2015.42.
https://doi.org/10.1109/FOCS.2015.42
[33] K. Seki and S. Yunoki. Quantum power method by a superposition of time-evolved states. PRX Quantum, 2:010333, 2021. doi:10.1103/PRXQuantum.2.010333.
https://doi.org/10.1103/PRXQuantum.2.010333
[34] R. D. Somma. Quantum eigenvalue estimation via time series analysis. New J. Phys., 21(12):123025, 2019. doi:10.1088/1367-2630/ab5c60.
https://doi.org/10.1088/1367-2630/ab5c60
[35] N. H. Stair, R. Huang, and F. A. Evangelista. A multireference quantum Krylov algorithm for strongly correlated electrons. Journal of Chemical Theory and Computation, 16(4):2236–2245, 2020. doi:10.1021/acs.jctc.9b01125.
https://doi.org/10.1021/acs.jctc.9b01125
[36] 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 Journal of Physics, 24(10):103024, 2022. doi:10.1088/1367-2630/ac919c.
https://doi.org/10.1088/1367-2630/ac919c
[37] Y. Subaşı, R. D. Somma, and D. Orsucci. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Phys. Rev. Lett., 122:060504, 2019. doi:10.1103/PhysRevLett.122.060504.
https://doi.org/10.1103/PhysRevLett.122.060504
[38] G. Tang, B. N. Bhaskar, P. Shah, and B. Recht. Compressed sensing off the grid. IEEE Transactions on Information Theory, 59(11):7465–7490, 2013. doi:10.1109/TIT.2013.2277451.
https://doi.org/10.1109/TIT.2013.2277451
[39] G. Wang, D. Stilck-Franca, R. Zhang, S. Zhu, and P. D. Johnson. Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision. preprint, 2022. doi:10.48550/arXiv.2209.06811.
https://doi.org/10.48550/arXiv.2209.06811
[40] Z. Yang and L. Xie. Achieving high resolution for super-resolution via reweighted atomic norm minimization. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3646–3650, 2015. doi:10.1109/ICASSP.2015.7178651.
https://doi.org/10.1109/ICASSP.2015.7178651
[41] M. Zwierz, C. A. Pérez-Delgado, and P. Kok. General optimality of the Heisenberg limit for quantum metrology. Phys. Rev. Lett., 105:180402, 2010. doi:10.1103/PhysRevLett.105.180402.
https://doi.org/10.1103/PhysRevLett.105.180402
[42] M. Zwierz, C. A. Pérez-Delgado, and P. Kok. Ultimate limits to quantum metrology and the meaning of the Heisenberg limit. Phys. Rev. A, 85:042112, 2012. doi:10.1103/PhysRevA.85.042112.
https://doi.org/10.1103/PhysRevA.85.042112
Cited by
[1] Yizhi Shen, Daan Camps, Siva Darbha, Aaron Szasz, 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”, arXiv:2306.01858, (2023).
[2] Hirofumi Nishi, Taichi Kosugi, Yusuke Nishiya, and Yu-ichiro Matsushita, “Quadratic acceleration of multi-step probabilistic algorithms for state preparation”, arXiv:2308.03605, (2023).
[3] Haoya Li, Hongkang Ni, and Lexing Ying, “On adaptive low-depth quantum algorithms for robust multiple-phase estimation”, arXiv:2303.08099, (2023).
[4] Kenji Sugisaki, “Projective Quantum Phase Difference Estimation Algorithm for the Direct Computation of Eigenenergy Gaps on a Quantum Computer”, arXiv:2307.09825, (2023).
[5] Changhao Yi, Cunlu Zhou, and Jun Takahashi, “Quantum Phase Estimation by Compressed Sensing”, arXiv:2306.07008, (2023).
The above citations are from SAO/NASA ADS (last updated successfully 2023-10-11 16:01:29). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2023-10-11 16:01:28: Could not fetch cited-by data for 10.22331/q-2023-10-11-1136 from Crossref. This is normal if the DOI was registered recently.
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.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-10-11-1136/
