The Krylov subspace methods, being one category of the most important classical numerical methods for linear algebra problems, can be much more powerful when generalised to quantum computing. However, quantum Krylov subspace algorithms are prone to errors due to inevitable statistical fluctuations in quantum measurements. To address this problem, we develop a general theoretical framework to analyse the statistical error and measurement cost. Based on the framework, we propose a quantum algorithm to construct the Hamiltonian-power Krylov subspace that can minimise the measurement cost. In our algorithm, the product of power and Gaussian functions of the Hamiltonian is expressed as an integral of the real-time evolution, such that it can be evaluated on a quantum computer. We compare our algorithm with other established quantum Krylov subspace algorithms in solving two prominent examples. To achieve an error comparable to that of the classical Lanczos algorithm at the same subspace dimension, our algorithm typically requires orders of magnitude fewer measurements than others. Such an improvement can be attributed to the reduced cost of composing projectors onto the ground state. These results show that our algorithm is exceptionally robust to statistical fluctuations and promising for practical applications.
[1] Elbio Dagotto. ``Correlated electrons in high-temperature superconductors''. Reviews of Modern Physics 66, 763 (1994).
https://doi.org/10.1103/RevModPhys.66.763
[2] 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, 8011–8022 (1995).
https://doi.org/10.1063/1.468999
[3] Etienne Caurier, Gabriel Martínez-Pinedo, Fréderic Nowacki, Alfredo Poves, and AP Zuker. ``The shell model as a unified view of nuclear structure''. Reviews of modern Physics 77, 427 (2005).
https://doi.org/10.1103/RevModPhys.77.427
[4] 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://doi.org/10.6028/jres.045.026
[5] Yousef Saad. ``Numerical methods for large eigenvalue problems''. Society for Industrial and Applied Mathematics. (2011).
https://doi.org/10.1137/1.9781611970739
[6] Åke Björck. ``Numerical methods in matrix computations''. Volume 59 of Texts in Applied Mathematics. Springer. (2015).
https://doi.org/10.1007/978-3-319-05089-8
[7] Adolfo Avella and Ferdinando Mancini. ``Strongly correlated systems''. Volume 176 of Springer Series in Solid-State Sciences. Springer. (2013).
https://doi.org/10.1007/978-3-642-35106-8
[8] Mario Motta, Chong Sun, Adrian T. K. Tan, Matthew J. O'Rourke, Erika Ye, Austin J. Minnich, Fernando G. S. L. Brandão, and Garnet Kin-Lic Chan. ``Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution''. Nature Physics 16, 205–210 (2019).
https://doi.org/10.1038/s41567-019-0704-4
[9] 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–8 (2020).
https://doi.org/10.1038/s41534-020-00290-1
[10] Robert M. Parrish and Peter L. McMahon. ``Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation'' (2019). arXiv:1909.08925.
arXiv:1909.08925
[11] Nicholas H. Stair, Renke Huang, and Francesco A. Evangelista. ``A multireference quantum krylov algorithm for strongly correlated electrons''. Journal of Chemical Theory and Computation 16, 2236–2245 (2020).
https://doi.org/10.1021/acs.jctc.9b01125
[12] Tatiana A Bespalova and Oleksandr Kyriienko. ``Hamiltonian operator approximation for energy measurement and ground-state preparation''. PRX Quantum 2, 030318 (2021).
https://doi.org/10.1103/PRXQuantum.2.030318
[13] Jeffrey Cohn, Mario Motta, and Robert M Parrish. ``Quantum filter diagonalization with compressed double-factorized hamiltonians''. PRX Quantum 2, 040352 (2021).
https://doi.org/10.1103/PRXQuantum.2.040352
[14] Katherine Klymko, Carlos Mejuto-Zaera, Stephen J Cotton, Filip Wudarski, Miroslav Urbanek, Diptarka Hait, Martin Head-Gordon, K Birgitta Whaley, Jonathan Moussa, Nathan Wiebe, et al. ``Real-time evolution for ultracompact hamiltonian eigenstates on quantum hardware''. PRX Quantum 3, 020323 (2022).
https://doi.org/10.1103/PRXQuantum.3.020323
[15] Cristian L Cortes and Stephen K Gray. ``Quantum krylov subspace algorithms for ground-and excited-state energy estimation''. Physical Review A 105, 022417 (2022).
https://doi.org/10.1103/PhysRevA.105.022417
[16] Ethan N Epperly, Lin Lin, and Yuji Nakatsukasa. ``A theory of quantum subspace diagonalization''. SIAM Journal on Matrix Analysis and Applications 43, 1263–1290 (2022).
https://doi.org/10.1137/21M145954X
[17] Yizhi Shen, Katherine Klymko, James Sud, David B. Williams-Young, Wibe A. de Jong, and Norm M. Tubman. ``Real-Time Krylov Theory for Quantum Computing Algorithms''. Quantum 7, 1066 (2023).
https://doi.org/10.22331/q-2023-07-25-1066
[18] Oleksandr Kyriienko. ``Quantum inverse iteration algorithm for programmable quantum simulators''. npj Quantum Information 6, 1–8 (2020).
https://doi.org/10.1038/s41534-019-0239-7
[19] Kazuhiro Seki and Seiji Yunoki. ``Quantum power method by a superposition of time-evolved states''. PRX Quantum 2, 010333 (2021).
https://doi.org/10.1103/PRXQuantum.2.010333
[20] William Kirby, Mario Motta, and Antonio Mezzacapo. ``Exact and efficient Lanczos method on a quantum computer''. Quantum 7, 1018 (2023).
https://doi.org/10.22331/q-2023-05-23-1018
[21] Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. ``Encoding electronic spectra in quantum circuits with linear t complexity''. Phys. Rev. X 8, 041015 (2018).
https://doi.org/10.1103/PhysRevX.8.041015
[22] Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush. ``Even more efficient quantum computations of chemistry through tensor hypercontraction''. PRX Quantum 2, 030305 (2021).
https://doi.org/10.1103/PRXQuantum.2.030305
[23] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nature communications 5, 4213 (2014).
https://doi.org/10.1038/ncomms5213
[24] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. ``Barren plateaus in quantum neural network training landscapes''. Nature communications 9, 4812 (2018).
https://doi.org/10.1038/s41467-018-07090-4
[25] Beresford N. Parlett. ``The symmetric eigenvalue problem''. Society for Industrial and Applied Mathematics. (1998).
https://doi.org/10.1137/1.9781611971163
[26] 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, 230401 (2019).
https://doi.org/10.1103/PhysRevLett.122.230401
[27] Ken M Nakanishi, Kosuke Mitarai, and Keisuke Fujii. ``Subspace-search variational quantum eigensolver for excited states''. Physical Review Research 1, 033062 (2019).
https://doi.org/10.1103/PhysRevResearch.1.033062
[28] William J Huggins, Joonho Lee, Unpil Baek, Bryan O’Gorman, and K Birgitta Whaley. ``A non-orthogonal variational quantum eigensolver''. New Journal of Physics 22, 073009 (2020).
https://doi.org/10.1088/1367-2630/ab867b
[29] Nicholas H. Stair, Cristian L. Cortes, Robert M. Parrish, Jeffrey Cohn, and Mario Motta. ``Stochastic quantum krylov protocol with double-factorized hamiltonians''. Phys. Rev. A 107, 032414 (2023).
https://doi.org/10.1103/PhysRevA.107.032414
[30] 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).
https://doi.org/10.1103/PhysRevA.95.042308
[31] Jarrod R McClean, Zhang Jiang, Nicholas C Rubin, Ryan Babbush, and Hartmut Neven. ``Decoding quantum errors with subspace expansions''. Nature communications 11, 636 (2020).
https://doi.org/10.1038/s41467-020-14341-w
[32] Nobuyuki Yoshioka, Hideaki Hakoshima, Yuichiro Matsuzaki, Yuuki Tokunaga, Yasunari Suzuki, and Suguru Endo. ``Generalized quantum subspace expansion''. Phys. Rev. Lett. 129, 020502 (2022).
https://doi.org/10.1103/PhysRevLett.129.020502
[33] Artur K Ekert, Carolina Moura Alves, Daniel KL Oi, Michał Horodecki, Paweł Horodecki, and Leong Chuan Kwek. ``Direct estimations of linear and nonlinear functionals of a quantum state''. Physical review letters 88, 217901 (2002).
https://doi.org/10.1103/PhysRevLett.88.217901
[34] Mingxia Huo and Ying Li. ``Error-resilient monte carlo quantum simulation of imaginary time''. Quantum 7, 916 (2023).
https://doi.org/10.22331/q-2023-02-09-916
[35] Pei Zeng, Jinzhao Sun, and Xiao Yuan. ``Universal quantum algorithmic cooling on a quantum computer'' (2021). arXiv:2109.15304.
arXiv:2109.15304
[36] Andrew M Childs and Nathan Wiebe. ``Hamiltonian simulation using linear combinations of unitary operations''. Quantum Information & Computation 12, 901–924 (2012).
https://doi.org/10.26421/QIC12.11-12-1
[37] Paul K. Faehrmann, Mark Steudtner, Richard Kueng, Maria Kieferova, and Jens Eisert. ``Randomizing multi-product formulas for Hamiltonian simulation''. Quantum 6, 806 (2022).
https://doi.org/10.22331/q-2022-09-19-806
[38] Thomas E O’Brien, Stefano Polla, Nicholas C Rubin, William J Huggins, Sam McArdle, Sergio Boixo, Jarrod R McClean, and Ryan Babbush. ``Error mitigation via verified phase estimation''. PRX Quantum 2, 020317 (2021).
https://doi.org/10.1103/PRXQuantum.2.020317
[39] Sirui Lu, Mari Carmen Bañuls, and J Ignacio Cirac. ``Algorithms for quantum simulation at finite energies''. PRX Quantum 2, 020321 (2021).
https://doi.org/10.1103/PRXQuantum.2.020321
[40] G.B. Arfken, H.J. Weber, and F.E. Harris. ``Mathematical methods for physicists: A comprehensive guide''. Elsevier. (2012).
https://doi.org/10.1016/C2009-0-30629-7
[41] Seth Lloyd. ``Universal quantum simulators''. Science 273, 1073–1078 (1996).
https://doi.org/10.1126/science.273.5278.107
[42] Dominic W Berry, Graeme Ahokas, Richard Cleve, and Barry C Sanders. ``Efficient quantum algorithms for simulating sparse hamiltonians''. Communications in Mathematical Physics 270, 359–371 (2007).
https://doi.org/10.1007/s00220-006-0150-x
[43] Nathan Wiebe, Dominic Berry, Peter Høyer, and Barry C Sanders. ``Higher order decompositions of ordered operator exponentials''. Journal of Physics A: Mathematical and Theoretical 43, 065203 (2010).
https://doi.org/10.1088/1751-8113/43/6/065203
[44] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. ``Simulating hamiltonian dynamics with a truncated taylor series''. Physical review letters 114, 090502 (2015).
https://doi.org/10.1103/PhysRevLett.114.090502
[45] Richard Meister, Simon C. Benjamin, and Earl T. Campbell. ``Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries''. Quantum 6, 637 (2022).
https://doi.org/10.22331/q-2022-02-02-637
[46] Earl Campbell. ``Random compiler for fast hamiltonian simulation''. Physical review letters 123, 070503 (2019).
https://doi.org/10.1103/PhysRevLett.123.070503
[47] Yongdan Yang, Bing-Nan Lu, and Ying Li. ``Accelerated quantum monte carlo with mitigated error on noisy quantum computer''. PRX Quantum 2, 040361 (2021).
https://doi.org/10.1103/PRXQuantum.2.040361
[48] Philip W Anderson. ``The resonating valence bond state in la2cuo4 and superconductivity''. science 235, 1196–1198 (1987).
https://doi.org/10.1126/science.235.4793.1196
[49] Patrick A Lee, Naoto Nagaosa, and Xiao-Gang Wen. ``Doping a mott insulator: Physics of high-temperature superconductivity''. Reviews of modern physics 78, 17 (2006).
https://doi.org/10.1103/RevModPhys.78.17
[50] Kazuhiro Seki, Tomonori Shirakawa, and Seiji Yunoki. ``Symmetry-adapted variational quantum eigensolver''. Phys. Rev. A 101, 052340 (2020).
https://doi.org/10.1103/PhysRevA.101.052340
[51] Roger A. Horn and Charles R. Johnson. ``Matrix analysis''. Cambridge University Press. (2012). 2 edition.
https://doi.org/10.1017/CBO9781139020411
[52] Germund Dahlquist and Åke Björck. ``Numerical methods in scientific computing, volume i''. Society for Industrial and Applied Mathematics. (2008).
https://doi.org/10.1137/1.9780898717785
[53] William Kirby. ``Analysis of quantum krylov algorithms with errors'' (2024). arXiv:2401.01246.
arXiv:2401.01246
[54] https://github.com/ZongkangZhang/QKSD.
https://github.com/ZongkangZhang/QKSD
[55] Wassily Hoeffding. ``Probability inequalities for sums of bounded random variables''. Journal of the American Statistical Association 58, 13–30 (1963).
https://doi.org/10.1080/01621459.1963.10500830
[56] Joel A. Tropp. ``An introduction to matrix concentration inequalities''. Foundations and Trends® in Machine Learning 8, 1–230 (2015).
https://doi.org/10.1561/2200000048
[57] Raymundo Albert and Cecilia G. Galarza. ``Model order selection for sum of complex exponentials''. In 2021 IEEE URUCON. Pages 561–565. (2021).
https://doi.org/10.1109/URUCON53396.2021.9647257
[58] D. Babusci, G. Dattoli, and M. Quattromini. ``On integrals involving hermite polynomials''. Applied Mathematics Letters 25, 1157–1160 (2012).
https://doi.org/10.1016/j.aml.2012.02.043
[59] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. ``Classical and quantum computation''. Graduate studies in mathematics. American Mathematical Society. (2002).
https://doi.org/10.1090/gsm/047
[60] Julia Kempe, Alexei Kitaev, and Oded Regev. ``The complexity of the local hamiltonian problem''. Siam journal on computing 35, 1070–1097 (2006).
https://doi.org/10.1137/S0097539704445226
[61] Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans. ``Improved Hardness Results for the Guided Local Hamiltonian Problem''. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:19. Dagstuhl, Germany (2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ICALP.2023.32
[62] Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, et al. ``Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry''. Nature communications 14, 1952 (2023).
https://doi.org/10.1038/s41467-023-37587-6
