Sampling Error Analysis in Quantum Krylov Subspace Diagonalization

Gwonhak Lee; Dongkeun Lee; Joonsuk Huh

doi:10.22331/q-2024-09-19-1477

Sampling Error Analysis in Quantum Krylov Subspace Diagonalization

Gwonhak Lee¹, Dongkeun Lee^2,3, and Joonsuk Huh^1,2,4

¹SKKU Advanced Institute of Nanotechnology, Sungkyunkwan University, Suwon 16419, Republic of Korea
²Department of Chemistry, Sungkyunkwan University, Suwon 16419, Republic of Korea
³Center for Quantum Information R&D, Korea Institute of Science and Technology Information, Daejeon 34141, Republic of Korea
⁴Institute of Quantum Biophysics, Sungkyunkwan University, Suwon 16419, Republic of Korea

Published:	2024-09-19, volume 8, page 1477
Eprint:	arXiv:2307.16279v3
Doi:	https://doi.org/10.22331/q-2024-09-19-1477
Citation:	Quantum 8, 1477 (2024).

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

Abstract

Quantum Krylov subspace diagonalization (QKSD) is an emerging method used in place of quantum phase estimation in the early fault-tolerant era, where limited quantum circuit depth is available. In contrast to the classical Krylov subspace diagonalization (KSD) or the Lanczos method, QKSD exploits the quantum computer to efficiently estimate the eigenvalues of large-size Hamiltonians through a faster Krylov projection. However, unlike classical KSD, which is solely concerned with machine precision, QKSD is inherently accompanied by errors originating from a finite number of samples. Moreover, due to difficulty establishing an artificial orthogonal basis, ill-conditioning problems are often encountered, rendering the solution vulnerable to noise. In this work, we present a nonasymptotic theoretical framework to assess the relationship between sampling noise and its effects on eigenvalues. We also propose an optimal solution to cope with large condition numbers by eliminating the ill-conditioned bases. Numerical simulations of the one-dimensional Hubbard model demonstrate that the error bound of finite samplings accurately predicts the experimental errors in well-conditioned regions.

► BibTeX data

@article{Lee2024samplingerror,
  doi = {10.22331/q-2024-09-19-1477},
  url = {https://doi.org/10.22331/q-2024-09-19-1477},
  title = {Sampling {E}rror {A}nalysis in {Q}uantum {K}rylov {S}ubspace {D}iagonalization},
  author = {Lee, Gwonhak and Lee, Dongkeun and Huh, Joonsuk},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1477},
  month = sep,
  year = {2024}
}

► References

[1] Richard P Feynman. ``Simulating physics with computers''. Int. J. Theor. Phys. 21, 467–488 (1982).
https://doi.org/10.1007/bf02650179

[2] Seth Lloyd. ``Universal Quantum Simulators''. Science 273, 1073–1078 (1996).
https://doi.org/10.1126/science.273.5278.1073

[3] Daniel S. Abrams and Seth Lloyd. ``Simulation of Many-Body Fermi Systems on a Universal Quantum Computer''. Phys. Rev. Lett. 79, 2586–2589 (1997).
https://doi.org/10.1103/physrevlett.79.2586

[4] Daniel S Abrams and Seth Lloyd. ``Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and Eigenvectors''. Phys. Rev. Lett. 83, 5162–5165 (1999).
https://doi.org/10.1103/physrevlett.83.5162

[5] John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[6] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik. ``Noisy intermediate-scale quantum algorithms''. Rev. Mod. Phys. 94, 015004 (2022).
https://doi.org/10.1103/revmodphys.94.015004

[7] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. ``Variational quantum algorithms''. Nat. Rev. Phys. 3, 625–644 (2021).
https://doi.org/10.1038/s42254-021-00348-9

[8] 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''. Nat. Commun. 5, 4213 (2014).
https://doi.org/10.1038/ncomms5213

[9] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A Quantum Approximate Optimization Algorithm'' (2014). arXiv:1411.4028.
arXiv:1411.4028

[10] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. ``Barren plateaus in quantum neural network training landscapes''. Nat. Commun. 9, 4812 (2018).
https://doi.org/10.1038/s41467-018-07090-4

[11] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles. ``Cost function dependent barren plateaus in shallow parametrized quantum circuits''. Nat. Commun. 12, 1791 (2021).
https://doi.org/10.1038/s41467-021-21728-w

[12] Lennart Bittel and Martin Kliesch. ``Training Variational Quantum Algorithms Is NP-Hard''. Phys. Rev. Lett. 127, 120502 (2021).
https://doi.org/10.1103/physrevlett.127.120502

[13] Robert M. Parrish and Peter L. McMahon. ``Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation'' (2019). arXiv:1909.08925.
arXiv:1909.08925

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

[15] 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''. Nat. Phys. 16, 205–210 (2020).
https://doi.org/10.1038/s41567-019-0704-4

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

[17] Cristian L. Cortes and Stephen K. Gray. ``Quantum krylov subspace algorithms for ground- and excited-state energy estimation''. Phys. Rev. A 105, 022417 (2022).
https://doi.org/10.1103/PhysRevA.105.022417

[18] Katherine Klymko, Carlos Mejuto-Zaera, Stephen J. Cotton, Filip Wudarski, Miroslav Urbanek, Diptarka Hait, Martin Head-Gordon, K. Birgitta Whaley, Jonathan 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://doi.org/10.1103/PRXQuantum.3.020323

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

[20] Cristian L. Cortes, A. Eugene DePrince, and Stephen K. Gray. ``Fast-forwarding quantum simulation with real-time quantum Krylov subspace algorithms''. Phys. Rev. A 106, 042409 (2022).
https://doi.org/10.1103/physreva.106.042409

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

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

[23] Ethan N. Epperly, Lin Lin, and Yuji Nakatsukasa. ``A theory of quantum subspace diagonalization''. SIAM J. Matrix Anal. Appl. 43, 1263–1290 (2022).
https://doi.org/10.1137/21M145954X

[24] Roy Mathias and Chi-Kwong Li. ``The definite generalized eigenvalue problem : A new perturbation theory'' (2004).

[25] Y. Saad. ``On the rates of convergence of the lanczos and the block-lanczos methods''. SIAM J. Numer. Anal. 17, 687–706 (1980).
https://doi.org/10.1137/0717059

[26] Beresford N. Parlett. ``The symmetric eigenvalue problem''. SIAM. Philadelphia, PA (1998).
https://doi.org/10.1137/1.9781611971163

[27] Artur F. Izmaylov, Tzu-Ching Yen, Robert A. Lang, and Vladyslav Verteletskyi. ``Unitary partitioning approach to the measurement problem in the variational quantum eigensolver method''. J. Chem. Theory Comput. 16, 190–195 (2020).
https://doi.org/10.1021/acs.jctc.9b00791

[28] Andrew Zhao, Andrew Tranter, William M. Kirby, Shu Fay Ung, Akimasa Miyake, and Peter J. Love. ``Measurement reduction in variational quantum algorithms''. Phys. Rev. A 101, 062322 (2020).
https://doi.org/10.1103/PhysRevA.101.062322

[29] Masuo Suzuki. ``Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations''. Phys. Lett. A 146, 319–323 (1990).
https://doi.org/10.1016/0375-9601(90)90962-n

[30] Naomichi Hatano and Masuo Suzuki. ``Finding exponential product formulas of higher orders''. Pages 37–68. Springer. Berlin, Heidelberg (2005).
https://doi.org/10.1007/11526216_2

[31] G.W. Stewart. ``Pertubation bounds for the definite generalized eigenvalue problem''. Linear Algebra Appl. 23, 69–85 (1979).
https://doi.org/10.1016/0024-3795(79)90094-6

[32] Ji guang Sun. ``A note on stewart's theorem for definite matrix pairs''. Linear Algebra Appl. 48, 331–339 (1982).
https://doi.org/10.1016/0024-3795(82)90119-7

[33] Ji-guang Sun. ``Perturbation analysis for the generalized eigenvalue and the generalized singular value problem''. In Bo Kågström and Axel Ruhe, editors, Matrix Pencils. Pages 221–244. Berlin, Heidelberg (1983). Springer.
https://doi.org/10.1007/BFb0062105

[34] Joel A. Tropp. ``An introduction to matrix concentration inequalities''. Found. Trends Mach. Learn. 8, 1–230 (2015).
https://doi.org/10.1561/2200000048

[35] Roman Vershynin. ``High-dimensional probability: An introduction with applications in data science''. Camb. Ser. Stat. Probab. Math. Cambridge Univ. Press. Cambridge, U.K. (2018).
https://doi.org/10.1017/9781108231596

[36] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. ``Concentration Inequalities: A Nonasymptotic Theory of Independence''. Oxford Univ. Press. (2013).
https://doi.org/10.1093/acprof:oso/9780199535255.001.0001

[37] Lloyd N. Trefethen and David Bau, III. ``Numerical linear algebra''. SIAM. Philadelphia, PA (1997).
https://doi.org/10.1137/1.9780898719574

[38] Qiyao Liang, Yiqing Zhou, Archismita Dalal, and Peter Johnson. ``Modeling the performance of early fault-tolerant quantum algorithms''. Phys. Rev. Res. 6, 023118 (2024).
https://doi.org/10.1103/PhysRevResearch.6.023118

[39] Mingpu Qin, Thomas Schäfer, Sabine Andergassen, Philippe Corboz, and Emanuel Gull. ``The hubbard model: A computational perspective''. Annu. Rev. Condens. Matter Phys. 13, 275–302 (2022).
https://doi.org/10.1146/annurev-conmatphys-090921-033948

[40] Ophelia Crawford, Barnaby Straaten, Daochen Wang, Thomas Parks, Earl Campbell, and Stephen Brierley. ``Efficient quantum measurement of pauli operators in the presence of finite sampling error''. Quantum 5, 385 (2021).
https://doi.org/10.22331/q-2021-01-20-385

[41] Alexander Miessen, Pauline J. Ollitrault, and Ivano Tavernelli. ``Quantum algorithms for quantum dynamics: A performance study on the spin-boson model''. Phys. Rev. Res. 3, 043212 (2021).
https://doi.org/10.1103/PhysRevResearch.3.043212

[42] Kishor Bharti and Tobias Haug. ``Quantum-assisted simulator''. Phys. Rev. A 104, 042418 (2021).
https://doi.org/10.1103/PhysRevA.104.042418

[43] Jonathan Novak. ``Truncations of random unitary matrices and young tableaux'' (2006). arXiv:math/0608108.
arXiv:math/0608108

Cited by

[1] Nobuyuki Yoshioka, Mirko Amico, William Kirby, Petar Jurcevic, Arkopal Dutt, Bryce Fuller, Shelly Garion, Holger Haas, Ikko Hamamura, Alexander Ivrii, Ritajit Majumdar, Zlatko Minev, Mario Motta, Bibek Pokharel, Pedro Rivero, Kunal Sharma, Christopher J. Wood, Ali Javadi-Abhari, and Antonio Mezzacapo, "Krylov diagonalization of large many-body Hamiltonians on a quantum processor", Nature Communications 16 1, 5014 (2025).

[2] Tom O'Leary, Lewis W. Anderson, Dieter Jaksch, and Martin Kiffner, "Partitioned Quantum Subspace Expansion", Quantum 9, 1726 (2025).

[3] Reinis Irmejs and Raul A. Santos, "Approximating dynamical correlation functions with constant depth quantum circuits", Quantum 9, 1639 (2025).

[4] Gwonhak Lee, Seonghoon Choi, Joonsuk Huh, and Artur F. Izmaylov, "Efficient strategies for reducing sampling error in quantum Krylov subspace diagonalization", Digital Discovery 4 4, 954 (2025).

[5] Karl Michael Ziems, Erik Rosendahl Kjellgren, Stephan P. A. Sauer, Jacob Kongsted, and Sonia Coriani, "Understanding and mitigating noise in molecular quantum linear response for spectroscopic properties on quantum computers", Chemical Science 16 10, 4456 (2025).

[6] Hang Ren, Yipei Zhang, Wendy M. Billings, Rebecca Tomann, Nikolay V. Tkachenko, Mingyu Kang, Martin Head-Gordon, and K. Birgitta Whaley, "Error-mitigated nonorthogonal quantum eigensolver via shadow tomography", Physical Review Research 8 1, 013268 (2026).

[7] Sijia Yu and Yifan Zhou, 2025 IEEE Power & Energy Society General Meeting (PESGM) 1 (2025) ISBN:979-8-3315-0995-8.

[8] Gian Gentinetta, Friederike Metz, William Kirby, and Giuseppe Carleo, "Quantum finite-temperature Lanczos method", Physical Review Research 8 2, 023285 (2026).

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

[10] Maria Gabriela Jordão Oliveira and Nina Glaser, "Quantum block Krylov subspace projector algorithm for computing low-lying eigenenergies", Physical Review A 112 5, 052442 (2025).

[11] Oumarou Oumarou, Pauline J. Ollitrault, Cristian L. Cortes, Maximilian Scheurer, Robert M. Parrish, and Christian Gogolin, "Molecular Properties from Quantum Krylov Subspace Diagonalization", Journal of Chemical Theory and Computation 21 9, 4543 (2025).

[12] Bryce Fuller, Mario Motta, Stuart M. Harwood, Chetan Murthy, Tanvi P. Gujarati, Antonio Mezzacapo, and Dimitar Trenev, "Adiabatic state preparation from general initial states", Molecular Physics 124 2, e2526723 (2026).

[13] Mario Motta, William Kirby, Ieva Liepuoniute, Kevin J. Sung, Jeffrey Cohn, Antonio Mezzacapo, Katherine Klymko, Nam Nguyen, Nobuyuki Yoshioka, and Julia E. Rice, "Subspace methods for electronic structure simulations on quantum computers", Electronic Structure 6 1, 013001 (2024).

[14] Yuri Alexeev, Maximilian Amsler, Paul Baity, Marco Antonio Barroca, Sanzio Bassini, Torey Battelle, Daan Camps, David Casanova, Young Jai Choi, Frederic T. Chong, Charles Chung, Chris Codella, Antonio D. Corcoles, James Cruise, Alberto Di Meglio, Jonathan Dubois, Ivan Duran, Thomas Eckl, Sophia Economou, Stephan Eidenbenz, Bruce Elmegreen, Clyde Fare, Ismael Faro, Cristina Sanz Fernández, Rodrigo Neumann Barros Ferreira, Keisuke Fuji, Bryce Fuller, Laura Gagliardi, Giulia Galli, Jennifer R. Glick, Isacco Gobbi, Pranav Gokhale, Salvador de la Puente Gonzalez, Johannes Greiner, Bill Gropp, Michele Grossi, Emanuel Gull, Burns Healy, Benchen Huang, Travis S. Humble, Nobuyasu Ito, Artur F. Izmaylov, Ali Javadi-Abhari, Douglas Jennewein, Shantenu Jha, Liang Jiang, Barbara Jones, Wibe Albert de Jong, Petar Jurcevic, William Kirby, Stefan Kister, Masahiro Kitagawa, Joel Klassen, Katherine Klymko, Kwangwon Koh, Masaaki Kondo, Doga Murat Kurkcuoglu, Krzysztof Kurowski, Teodoro Laino, Ryan Landfield, Matt Leininger, Vicente Leyton-Ortega, Ang Li, Meifeng Lin, Junyu Liu, Nicolas Lorente, Andre Luckow, Simon Martiel, Francisco Martin-Fernandez, Margaret Martonosi, Claire Marvinney, Arcesio Castaneda Medina, Dirk Merten, Antonio Mezzacapo, Kristel Michielsen, Abhishek Mitra, Tushar Mittal, Kyungsun Moon, Joel Moore, Mario Motta, Young-Hye Na, Yunseong Nam, Prineha Narang, Yu-ya Ohnishi, Daniele Ottaviani, Matthew Otten, Scott Pakin, Vincent R. Pascuzzi, Ed Penault, Tomasz Piontek, Jed Pitera, Patrick Rall, Gokul Subramanian Ravi, Niall Robertson, Matteo Rossi, Piotr Rydlichowski, Hoon Ryu, Georgy Samsonidze, Mitsuhisa Sato, Nishant Saurabh, Vidushi Sharma, Kunal Sharma, Soyoung Shin, George Slessman, Mathias Steiner, Iskandar Sitdikov, In-Saeng Suh, Eric Switzer, Wei Tang, Joel Thompson, Synge Todo, Minh Tran, Dimitar Trenev, Christian Trott, Huan-Hsin Tseng, Esin Tureci, David García Valinas, Sofia Vallecorsa, Christopher Wever, Konrad Wojciechowski, Xiaodi Wu, Shinjae Yoo, Nobuyuki Yoshioka, Victor Wen-zhe Yu, Seiji Yunoki, Sergiy Zhuk, and Dmitry Zubarev, "Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions", arXiv:2312.09733, (2023).

[15] William Kirby, "Analysis of quantum Krylov algorithms with errors", Quantum 8, 1457 (2024).

[16] Taehee Ko, Hyowon Park, and Sangkook Choi, "Quantum random power method for ground state computation", arXiv:2408.08556, (2024).

[17] Emil Otis Rosanowski, Jurek Eisinger, Lena Funcke, Ulrich Poschinger, and Ferdinand Schmidt-Kaler, "Sample-Based Krylov Quantum Diagonalization for the Schwinger Model on Trapped-Ion and Superconducting Quantum Processors", arXiv:2510.26951, (2025).

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