Real-Time Krylov Theory for Quantum Computing Algorithms

Yizhi Shen1,2,3, Katherine Klymko4, James Sud1,5, David B. Williams-Young6, Wibe A. de Jong6, and Norm M. Tubman1

1NASA Ames Research Center, Moffett Field, CA 94035, USA
2KBR, 601 Jefferson St., Houston, TX 77002
3Department of Chemistry, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
4NERSC, Lawrence Berkeley National Laboratory, Berkeley, California 94720, USA
5USRA Research Institute for Advanced Computer Science, Mountain View, CA 94043, USA
6Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, California 94720, USA

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


Quantum computers provide new avenues to access ground and excited state properties of systems otherwise difficult to simulate on classical hardware. New approaches using subspaces generated by real-time evolution have shown efficiency in extracting eigenstate information, but the full capabilities of such approaches are still not understood. In recent work, we developed the variational quantum phase estimation (VQPE) method, a compact and efficient real-time algorithm to extract eigenvalues on quantum hardware. Here we build on that work by theoretically and numerically exploring a generalized Krylov scheme where the Krylov subspace is constructed through a parametrized real-time evolution, which applies to the VQPE algorithm as well as others. We establish an error bound that justifies the fast convergence of our spectral approximation. We also derive how the overlap with high energy eigenstates becomes suppressed from real-time subspace diagonalization and we visualize the process that shows the signature phase cancellations at specific eigenenergies. We investigate various algorithm implementations and consider performance when stochasticity is added to the target Hamiltonian in the form of spectral statistics. To demonstrate the practicality of such real-time evolution, we discuss its application to fundamental problems in quantum computation such as electronic structure predictions for strongly correlated systems.

Near-term approaches exploiting quantum dynamics have shown great promise in extracting eigenstate information, but the full capabilities of such approaches are still not understood. In this work, we make a timely step forward in understanding their properties by exploring and analyzing a generalized Krylov subspace scheme where the subspace is constructed from a parametrized real-time evolution. We establish an error bound on the spectral convergence, and derive how the overlap with high energy eigenstates becomes rapidly suppressed. In addition, we investigate various algorithmic implementations and consider performance when stochasticity is added to the target Hamiltonian. To demonstrate the practical edge of such real-time methods, we discuss fundamental problems in quantum computation such as electronic structure predictions on strongly correlated materials, highlighting the encouraging efficacy.

► BibTeX data

► References

[1] Bela Bauer, Dave Wecker, Andrew J. Millis, Matthew B. Hastings, and Matthias Troyer. Hybrid quantum-classical approach to correlated materials. Phys. Rev. X, 6: 031045, Sep 2016. https:/​/​​10.1103/​PhysRevX.6.031045.

[2] Jun Li, Xiaodong Yang, Xinhua Peng, and Chang-Pu Sun. Hybrid quantum-classical approach to quantum optimal control. Phys. Rev. Lett., 118: 150503, Apr 2017. https:/​/​​10.1103/​PhysRevLett.118.150503.

[3] D. Zhu, N. M. Linke, M. Benedetti, K. A. Landsman, N. H. Nguyen, C. H. Alderete, A. Perdomo-Ortiz, N. Korda, A. Garfoot, C. Brecque, L. Egan, O. Perdomo, and C. Monroe. Training of quantum circuits on a hybrid quantum computer. Science Advances, 5 (10): eaaw9918, 2019. https:/​/​​10.1126/​sciadv.aaw9918.

[4] 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 (4): 042308, 2017. https:/​/​​10.1103/​PhysRevA.95.042308.

[5] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. https:/​/​​10.1038/​s41586-019-1666-5.

[6] Sam McArdle, Suguru Endo, Alan Aspuru-Guzik, Simon C Benjamin, and Xiao Yuan. Quantum computational chemistry. Reviews of Modern Physics, 92 (1): 015003, 2020. https:/​/​​10.1103/​RevModPhys.92.015003.

[7] Lin Lin and Yu Tong. Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3: 010318, Feb 2022. 10.1103/​PRXQuantum.3.010318.

[8] Dong An, Di Fang, and Lin Lin. Time-dependent unbounded Hamiltonian simulation with vector norm scaling. Quantum, 5: 459, May 2021. ISSN 2521-327X. https:/​/​​10.22331/​q-2021-05-26-459.

[9] Yu Tong, Dong An, Nathan Wiebe, and Lin Lin. Fast inversion, preconditioned quantum linear system solvers, fast green's-function computation, and fast evaluation of matrix functions. Phys. Rev. A, 104: 032422, Sep 2021. https:/​/​​10.1103/​PhysRevA.104.032422.

[10] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik. Quantum chemistry in the age of quantum computing. Chemical Reviews, 119 (19): 10856–10915, 2019. https:/​/​​10.1021/​acs.chemrev.8b00803.

[11] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. Quantum algorithms for quantum chemistry and quantum materials science. Chemical Reviews, 120 (22): 12685–12717, 2020. https:/​/​​10.1021/​acs.chemrev.9b00829.

[12] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Andreas Bengtsson, Sergio Boixo, Michael Broughton, Bob B Buckley, et al. Observation of separated dynamics of charge and spin in the fermi-hubbard model. arXiv preprint arXiv:2010.07965, 2020a. https:/​/​​10.48550/​arXiv.2010.07965.

[13] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. https:/​/​​10.1017/​CBO9780511976667.

[14] Alberto Peruzzo, Jarrod R. McClean, Peter J Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy Lloyd O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5, 2014. https:/​/​​10.1038/​ncomms5213.

[15] Dave Wecker, Matthew B Hastings, and Matthias Troyer. Progress towards practical quantum variational algorithms. Physical Review A, 92 (4): 042303, 2015. https:/​/​​10.1103/​PhysRevA.92.042303.

[16] Kevin J Sung, Jiahao Yao, Matthew P Harrigan, Nicholas C Rubin, Zhang Jiang, Lin Lin, Ryan Babbush, and Jarrod R McClean. Using models to improve optimizers for variational quantum algorithms. Quantum Science and Technology, 5 (4): 044008, sep 2020. https:/​/​​10.1088/​2058-9565/​abb6d9.

[17] William James Huggins, Joonho Lee, Unpil Baek, Bryan O'Gorman, and K Birgitta Whaley. A non-orthogonal variational quantum eigensolver. New J. Phys., 2020. https:/​/​​10.1088/​1367-2630/​ab867b.

[18] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B Buckley, David A Buell, et al. Hartree-fock on a superconducting qubit quantum computer. Science, 369 (6507): 1084–1089, 2020b. https:/​/​​10.1126/​science.abb9811.

[19] Dmitry A. Fedorov, Bo Peng, Niranjan Govind, and Yuri Alexeev. VQE method: a short survey and recent developments. Materials Theory, 6 (1): 2, Jan 2022. https:/​/​​10.1186/​s41313-021-00032-6.

[20] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18 (2): 023023, feb 2016. https:/​/​​10.1088/​1367-2630/​18/​2/​023023.

[21] Tyler Takeshita, Nicholas C Rubin, Zhang Jiang, Eunseok Lee, Ryan Babbush, and Jarrod R McClean. Increasing the representation accuracy of quantum simulations of chemistry without extra quantum resources. Phys. Rev. X, 10 (1): 011004, 2020. https:/​/​​10.1103/​PhysRevX.10.011004.

[22] Robert M Parrish, Edward G Hohenstein, Peter L McMahon, and Todd J Martínez. Quantum computation of electronic transitions using a variational quantum eigensolver. Physical review letters, 122 (23): 230401, 2019. https:/​/​​10.1103/​PhysRevLett.122.230401.

[23] Miroslav Urbanek, Daan Camps, Roel Van Beeumen, and Wibe A de Jong. Chemistry on quantum computers with virtual quantum subspace expansion. J. Chem. Theory Comput., 16 (9): 5425, 2020. https:/​/​​10.1021/​acs.jctc.0c00447.

[24] Nicholas H Stair, Renke Huang, and Francesco A Evangelista. A multireference quantum krylov algorithm for strongly correlated electrons. J. Chem. Theory Comput., 16 (4): 2236–2245, 2020. https:/​/​​10.1021/​acs.jctc.9b01125.

[25] Cristian L. Cortes and Stephen K. Gray. Quantum krylov subspace algorithms for ground- and excited-state energy estimation. Phys. Rev. A, 105: 022417, Feb 2022. https:/​/​​10.1103/​PhysRevA.105.022417.

[26] Katherine Klymko, Carlos Mejuto-Zaera, Stephen J Cotton, Filip A. Wudarski, Miroslav Urbánek, Diptarka Hait, Martin Head-Gordon, K. Birgitta Whaley, Jonathan Edward 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:/​/​​10.1103/​PRXQuantum.3.020323.

[27] Tae Jun Park and JC Light. Unitary quantum time evolution by iterative lanczos reduction. The Journal of chemical physics, 85 (10): 5870–5876, 1986. https:/​/​​10.1063/​1.451548.

[28] Daniel Neuhauser. Bound state eigenfunctions from wave packets: Time→ energy resolution. The Journal of chemical physics, 93 (4): 2611–2616, 1990. https:/​/​​10.1063/​1.458900.

[29] Daniel Neuhauser. Circumventing the heisenberg principle: A rigorous demonstration of filter-diagonalization on a licn model. The Journal of chemical physics, 100 (7): 5076–5079, 1994. https:/​/​​10.1063/​1.467224.

[30] Michael R Wall and Daniel Neuhauser. Extraction, through filter-diagonalization, of general quantum eigenvalues or classical normal mode frequencies from a small number of residues or a short-time segment of a signal. i. theory and application to a quantum-dynamics model. The Journal of chemical physics, 102 (20): 8011–8022, 1995. https:/​/​​10.1063/​1.468999.

[31] Cornelius Lanczos. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. Journal of research of the National Bureau of Standards, 45: 255–282, 1950. https:/​/​​10.6028/​jres.045.026.

[32] B.N. Parlett. The Symmetric Eigenvalue Problem. Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, 1980. ISBN 9780898714029. https:/​/​​10.1137/​1.9781611971163.

[33] H. D. Meyer and S. Pal. A band-lanczos method for computing matrix elements of a resolvent. J. Chem. Phys., 91: 6195, 1989. https:/​/​​10.1063/​1.457438.

[34] Salvatore R Manmana, Alejandro Muramatsu, and Reinhard M Noack. Time evolution of one-dimensional quantum many body systems. In AIP Conference Proceedings, volume 789, pages 269–278. American Institute of Physics, 2005. https:/​/​​10.1063/​1.2080353.

[35] E. Pavarini, E. Koch, D. Vollhardt, and A. Lichtenstein, editors. The LDA+DMFT approach to strongly correlated materials, chapter 8, pages 235–264. Verlag des Forschungszentrum Jülich, 2011. ISBN 978-3-89336-734-4.

[36] R. V. Mises and H. Pollaczek-Geiringer. Praktische verfahren der gleichungsauflösung. ZAMM - Journal of Applied Mathematics and Mechanics /​ Zeitschrift für Angewandte Mathematik und Mechanik, 9 (2): 152–164, 1929. https:/​/​​10.1002/​zamm.19290090206.

[37] Mario Motta, Chong Sun, Adrian TK Tan, Matthew J O`Rourke, Erika Ye, Austin J Minnich, Fernando GSL Brandao, and Garnet Kin Lic Chan. Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nature Physics, 16 (2): 205–210, 2020. https:/​/​​10.1038/​s41567-019-0704-4.

[38] Kübra Yeter-Aydeniz, Raphael C Pooser, and George Siopsis. Practical quantum computation of chemical and nuclear energy levels using quantum imaginary time evolution and lanczos algorithms. npj Quantum Information, 6 (1): 1–8, 2020. https:/​/​​10.1038/​s41534-020-00290-1.

[39] William J Huggins, Bryan A O’Gorman, Nicholas C Rubin, David R Reichman, Ryan Babbush, and Joonho Lee. Unbiasing fermionic quantum monte carlo with a quantum computer. Nature, 603 (7901): 416–420, 2022. https:/​/​​10.1038/​s41586-021-04351-z.

[40] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC '96, page 212–219, New York, NY, USA, 1996. Association for Computing Machinery. ISBN 0897917855. https:/​/​​10.1145/​237814.237866.

[41] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Info. Comput., 12 (11–12): 901–924, nov 2012. ISSN 1533-7146. https:/​/​​10.26421/​QIC12.11-12-1.

[42] Desmond J Higham and Nicholas J Higham. Structured backward error and condition of generalized eigenvalue problems. SIAM Journal on Matrix Analysis and Applications, 20 (2): 493–512, 1998. https:/​/​​10.1137/​S0895479896313188.

[43] Christopher C. Paige. The computation of eigenvalues and eigenvectors of very large sparse matrices. 1971.

[44] Y. Saad. On the rates of convergence of the lanczos and the block-lanczos methods. SIAM Journal on Numerical Analysis, 17 (5): 687–706, 1980. ISSN 00361429. https:/​/​​10.1137/​0717059.

[45] Ethan N. Epperly, Lin Lin, and Yuji Nakatsukasa. A theory of quantum subspace diagonalization. SIAM Journal on Matrix Analysis and Applications, 43 (3): 1263–1290, 2022. https:/​/​​10.1137/​21M145954X.

[46] Christine Schmid and Kyle J. DeMars. Angular correlation using rogers-szegő-chaos. Mathematics, 8 (2), 2020. ISSN 2227-7390. https:/​/​​10.3390/​math8020171.

[47] Mama Foupouagnigni and Wolfram Koepf. Orthogonal Polynomials: 2nd AIMS-Volkswagen Stiftung Workshop, Douala, Cameroon, 5-12 October, 2018. 01 2020. ISBN 978-3-030-36743-5. https:/​/​​10.1007/​978-3-030-36744-2.

[48] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012. https:/​/​​10.1017/​CBO9780511810817.

[49] Florian Weigend and Reinhart Ahlrichs. Balanced basis sets of split valence, triple zeta valence and quadruple zeta valence quality for h to rn: Design and assessment of accuracy. Phys. Chem. Chem. Phys., 7: 3297, 2005. 10.1039/​b508541a.

[50] Norm M. Tubman, Joonho Lee, Tyler Y. Takeshita, Martin Head-Gordon, and K. Birgitta Whaley. A deterministic alternative to the full configuration interaction quantum monte carlo method. J. Chem. Phys., 145 (4): 044112, 2016. https:/​/​​10.1063/​1.4955109.

[51] Norm M Tubman, Daniel S Levine, Diptarka Hait, Martin Head-Gordon, and K Birgitta Whaley. An efficient deterministic perturbation theory for selected configuration interaction methods. arXiv preprint arXiv:1808.02049v1, 2018. https:/​/​​10.48550/​arXiv.1808.02049.

[52] Norm M Tubman, C Daniel Freeman, Daniel S Levine, Diptarka Hait, Martin Head-Gordon, and K Birgitta Whaley. Modern approaches to exact diagonalization and selected configuration interaction with the adaptive sampling ci method. Journal of chemical theory and computation, 16 (4): 2139–2159, 2020. https:/​/​​10.1021/​acs.jctc.8b00536.

[53] Robert M Parrish and Peter L McMahon. Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation. arXiv preprint arXiv:1909.08925, 2019. https:/​/​​10.48550/​arXiv.1909.08925.

[54] 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, Oct 2022. https:/​/​​10.1103/​PRXQuantum.3.040305.

[55] Peter W Atkins and Ronald S Friedman. Molecular quantum mechanics, 5th edition. Oxford university press, 2011. https:/​/​​10.1080/​00107514.2012.678277.

[56] P.A. Absil, R. Mahony, and R. Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2009. ISBN 9781400830244. https:/​/​​10.1515/​9781400830244.

[57] Nguyen Thanh Son, P.-A. Absil, Bin Gao, and Tatjana Stykel. Computing symplectic eigenpairs of symmetric positive-definite matrices via trace minimization and riemannian optimization. SIAM Journal on Matrix Analysis and Applications, 42 (4): 1732–1757, 2021. https:/​/​​10.1137/​21M1390621.

[58] C. G. Baker, P.-A. Absil, and K. A. Gallivan. An implicit Riemannian trust-region method for the symmetric generalized eigenproblem. In Computational Science – ICCS 2006, volume 3991 of LNCS, pages 210–217. Springer, 2006. https:/​/​​10.1007/​11758501_32.

[59] Jérémie Roland and Nicolas J. Cerf. Noise resistance of adiabatic quantum computation using random matrix theory. Phys. Rev. A, 71: 032330, Mar 2005. https:/​/​​10.1103/​PhysRevA.71.032330.

[60] Siddharth Muthukrishnan, Tameem Albash, and Daniel A. Lidar. Sensitivity of quantum speedup by quantum annealing to a noisy oracle. Phys. Rev. A, 99: 032324, Mar 2019. https:/​/​​10.1103/​PhysRevA.99.032324.

Cited by

[1] Yuchen Wang and David A. Mazziotti, "Electronic excited states from a variance-based contracted quantum eigensolver", Physical Review A 108 2, 022814 (2023).

[2] Zongkang Zhang, Anbang Wang, Xiaosi Xu, and Ying Li, "Measurement-efficient quantum Krylov subspace diagonalisation", arXiv:2301.13353, (2023).

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

[4] Akhil Francis, Anjali A. Agrawal, Jack H. Howard, Efekan Kökcü, and A. F. Kemper, "Subspace Diagonalization on Quantum Computers using Eigenvector Continuation", arXiv:2209.10571, (2022).

[5] Nicholas H. Stair, Cristian L. Cortes, Robert M. Parrish, Jeffrey Cohn, and Mario Motta, "Stochastic quantum Krylov protocol with double-factorized Hamiltonians", Physical Review A 107 3, 032414 (2023).

[6] Ruyu Yang, Tianren Wang, Bing-Nan Lu, Ying Li, and Xiaosi Xu, "Shadow-based quantum subspace algorithm for the nuclear shell model", arXiv:2306.08885, (2023).

[7] Gwonhak Lee, Dongkeun Lee, and Joonsuk Huh, "Sampling Error Analysis in Quantum Krylov Subspace Diagonalization", arXiv:2307.16279, (2023).

[8] Amanda Bowman, "Nuclear Spectra from Quantum Lanczos Algorithm with Real-Time Evolution and Multiple Reference States", arXiv:2309.00759, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-22 14:33:09) and SAO/NASA ADS (last updated successfully 2023-09-22 14:33:10). The list may be incomplete as not all publishers provide suitable and complete citation data.