{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T00:32:04Z","timestamp":1773189124566,"version":"3.50.1"},"reference-count":43,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["NRF-2022M3H3A106307411"],"award-info":[{"award-number":["NRF-2022M3H3A106307411"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["NRF- 2022M3K2A1083890"],"award-info":[{"award-number":["NRF- 2022M3K2A1083890"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["NRF-2023M3K5A1094805"],"award-info":[{"award-number":["NRF-2023M3K5A1094805"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["NRF-2023M3K5A1094813"],"award-info":[{"award-number":["NRF-2023M3K5A1094813"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100010418","name":"Institute for Information & communications Technology Promotion","doi-asserted-by":"crossref","award":["No. 2019-0-00003"],"award-info":[{"award-number":["No. 2019-0-00003"]}],"id":[{"id":"10.13039\/501100010418","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.22331\/q-2024-09-19-1477","type":"journal-article","created":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T13:23:02Z","timestamp":1726752182000},"page":"1477","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":11,"title":["Sampling Error Analysis in Quantum Krylov Subspace Diagonalization"],"prefix":"10.22331","volume":"8","author":[{"given":"Gwonhak","family":"Lee","sequence":"first","affiliation":[{"name":"SKKU Advanced Institute of Nanotechnology, Sungkyunkwan University, Suwon 16419, Republic of Korea"}]},{"given":"Dongkeun","family":"Lee","sequence":"additional","affiliation":[{"name":"Department of Chemistry, Sungkyunkwan University, Suwon 16419, Republic of Korea"},{"name":"Center for Quantum Information R&D, Korea Institute of Science and Technology Information, Daejeon 34141, Republic of Korea"}]},{"given":"Joonsuk","family":"Huh","sequence":"additional","affiliation":[{"name":"SKKU Advanced Institute of Nanotechnology, Sungkyunkwan University, Suwon 16419, Republic of Korea"},{"name":"Department of Chemistry, Sungkyunkwan University, Suwon 16419, Republic of Korea"},{"name":"Institute of Quantum Biophysics, Sungkyunkwan University, Suwon 16419, Republic of Korea"}]}],"member":"9598","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Richard P Feynman. ``Simulating physics with computers&apos;&apos;. Int. J. Theor. Phys. 21, 467\u2013488 (1982).","DOI":"10.1007\/bf02650179"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Seth Lloyd. ``Universal Quantum Simulators&apos;&apos;. Science 273, 1073\u20131078 (1996).","DOI":"10.1126\/science.273.5278.1073"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Daniel S. Abrams and Seth Lloyd. ``Simulation of Many-Body Fermi Systems on a Universal Quantum Computer&apos;&apos;. Phys. Rev. Lett. 79, 2586\u20132589 (1997).","DOI":"10.1103\/physrevlett.79.2586"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Daniel S Abrams and Seth Lloyd. ``Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and Eigenvectors&apos;&apos;. Phys. Rev. Lett. 83, 5162\u20135165 (1999).","DOI":"10.1103\/physrevlett.83.5162"},{"key":"4","doi-asserted-by":"publisher","unstructured":"John Preskill. ``Quantum Computing in the NISQ era and beyond&apos;&apos;. Quantum 2, 79 (2018).","DOI":"10.22331\/q-2018-08-06-79"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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\u00e1n Aspuru-Guzik. ``Noisy intermediate-scale quantum algorithms&apos;&apos;. Rev. Mod. Phys. 94, 015004 (2022).","DOI":"10.1103\/revmodphys.94.015004"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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&apos;&apos;. Nat. Rev. Phys. 3, 625\u2013644 (2021).","DOI":"10.1038\/s42254-021-00348-9"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Al\u00e1n Aspuru-Guzik, and Jeremy L. O\u2019Brien. ``A variational eigenvalue solver on a photonic quantum processor&apos;&apos;. Nat. Commun. 5, 4213 (2014).","DOI":"10.1038\/ncomms5213"},{"key":"8","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A Quantum Approximate Optimization Algorithm&apos;&apos; (2014). arXiv:1411.4028."},{"key":"9","doi-asserted-by":"publisher","unstructured":"Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. ``Barren plateaus in quantum neural network training landscapes&apos;&apos;. Nat. Commun. 9, 4812 (2018).","DOI":"10.1038\/s41467-018-07090-4"},{"key":"10","doi-asserted-by":"publisher","unstructured":"M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles. ``Cost function dependent barren plateaus in shallow parametrized quantum circuits&apos;&apos;. Nat. Commun. 12, 1791 (2021).","DOI":"10.1038\/s41467-021-21728-w"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Lennart Bittel and Martin Kliesch. ``Training Variational Quantum Algorithms Is NP-Hard&apos;&apos;. Phys. Rev. Lett. 127, 120502 (2021).","DOI":"10.1103\/physrevlett.127.120502"},{"key":"12","unstructured":"Robert M. Parrish and Peter L. McMahon. ``Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation&apos;&apos; (2019). arXiv:1909.08925."},{"key":"13","doi-asserted-by":"publisher","unstructured":"Kazuhiro Seki and Seiji Yunoki. ``Quantum power method by a superposition of time-evolved states&apos;&apos;. PRX Quantum 2, 010333 (2021).","DOI":"10.1103\/PRXQuantum.2.010333"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Mario Motta, Chong Sun, Adrian T. K. Tan, Matthew J. O&apos;Rourke, Erika Ye, Austin J. Minnich, Fernando G. S. L. Brand\u00e3o, and Garnet Kin-Lic Chan. ``Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution&apos;&apos;. Nat. Phys. 16, 205\u2013210 (2020).","DOI":"10.1038\/s41567-019-0704-4"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Nicholas H. Stair, Renke Huang, and Francesco A. Evangelista. ``A multireference quantum krylov algorithm for strongly correlated electrons&apos;&apos;. J. Chem. Theory Comput. 16, 2236\u20132245 (2020).","DOI":"10.1021\/acs.jctc.9b01125"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Cristian L. Cortes and Stephen K. Gray. ``Quantum krylov subspace algorithms for ground- and excited-state energy estimation&apos;&apos;. Phys. Rev. A 105, 022417 (2022).","DOI":"10.1103\/PhysRevA.105.022417"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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&apos;&apos;. PRX Quantum 3, 020323 (2022).","DOI":"10.1103\/PRXQuantum.3.020323"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Jeffrey Cohn, Mario Motta, and Robert M. Parrish. ``Quantum Filter Diagonalization with Compressed Double-Factorized Hamiltonians&apos;&apos;. PRX Quantum 2, 040352 (2021).","DOI":"10.1103\/prxquantum.2.040352"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Cristian L. Cortes, A. Eugene DePrince, and Stephen K. Gray. ``Fast-forwarding quantum simulation with real-time quantum Krylov subspace algorithms&apos;&apos;. Phys. Rev. A 106, 042409 (2022).","DOI":"10.1103\/physreva.106.042409"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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&apos;&apos;. Quantum 7, 1066 (2023).","DOI":"10.22331\/q-2023-07-25-1066"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Nicholas H. Stair, Cristian L. Cortes, Robert M. Parrish, Jeffrey Cohn, and Mario Motta. ``Stochastic quantum krylov protocol with double-factorized hamiltonians&apos;&apos;. Phys. Rev. A 107, 032414 (2023).","DOI":"10.1103\/PhysRevA.107.032414"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Ethan N. Epperly, Lin Lin, and Yuji Nakatsukasa. ``A theory of quantum subspace diagonalization&apos;&apos;. SIAM J. Matrix Anal. Appl. 43, 1263\u20131290 (2022).","DOI":"10.1137\/21M145954X"},{"key":"23","unstructured":"Roy Mathias and Chi-Kwong Li. ``The definite generalized eigenvalue problem : A new perturbation theory&apos;&apos; (2004)."},{"key":"24","doi-asserted-by":"publisher","unstructured":"Y. Saad. ``On the rates of convergence of the lanczos and the block-lanczos methods&apos;&apos;. SIAM J. Numer. Anal. 17, 687\u2013706 (1980).","DOI":"10.1137\/0717059"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Beresford N. Parlett. ``The symmetric eigenvalue problem&apos;&apos;. SIAM. Philadelphia, PA (1998).","DOI":"10.1137\/1.9781611971163"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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&apos;&apos;. J. Chem. Theory Comput. 16, 190\u2013195 (2020).","DOI":"10.1021\/acs.jctc.9b00791"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Andrew Zhao, Andrew Tranter, William M. Kirby, Shu Fay Ung, Akimasa Miyake, and Peter J. Love. ``Measurement reduction in variational quantum algorithms&apos;&apos;. Phys. Rev. A 101, 062322 (2020).","DOI":"10.1103\/PhysRevA.101.062322"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Masuo Suzuki. ``Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations&apos;&apos;. Phys. Lett. A 146, 319\u2013323 (1990).","DOI":"10.1016\/0375-9601(90)90962-n"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Naomichi Hatano and Masuo Suzuki. ``Finding exponential product formulas of higher orders&apos;&apos;. Pages 37\u201368. Springer. Berlin, Heidelberg (2005).","DOI":"10.1007\/11526216_2"},{"key":"30","doi-asserted-by":"publisher","unstructured":"G.W. Stewart. ``Pertubation bounds for the definite generalized eigenvalue problem&apos;&apos;. Linear Algebra Appl. 23, 69\u201385 (1979).","DOI":"10.1016\/0024-3795(79)90094-6"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Ji guang Sun. ``A note on stewart&apos;s theorem for definite matrix pairs&apos;&apos;. Linear Algebra Appl. 48, 331\u2013339 (1982).","DOI":"10.1016\/0024-3795(82)90119-7"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Ji-guang Sun. ``Perturbation analysis for the generalized eigenvalue and the generalized singular value problem&apos;&apos;. In Bo K\u00e5gstr\u00f6m and Axel Ruhe, editors, Matrix Pencils. Pages 221\u2013244. Berlin, Heidelberg (1983). Springer.","DOI":"10.1007\/BFb0062105"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Joel A. Tropp. ``An introduction to matrix concentration inequalities&apos;&apos;. Found. Trends Mach. Learn. 8, 1\u2013230 (2015).","DOI":"10.1561\/2200000048"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Roman Vershynin. ``High-dimensional probability: An introduction with applications in data science&apos;&apos;. Camb. Ser. Stat. Probab. Math. Cambridge Univ. Press. Cambridge, U.K. (2018).","DOI":"10.1017\/9781108231596"},{"key":"35","doi-asserted-by":"publisher","unstructured":"St\u00e9phane Boucheron, G\u00e1bor Lugosi, and Pascal Massart. ``Concentration Inequalities: A Nonasymptotic Theory of Independence&apos;&apos;. Oxford Univ. Press. (2013).","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Lloyd N. Trefethen and David Bau, III. ``Numerical linear algebra&apos;&apos;. SIAM. Philadelphia, PA (1997).","DOI":"10.1137\/1.9780898719574"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Qiyao Liang, Yiqing Zhou, Archismita Dalal, and Peter Johnson. ``Modeling the performance of early fault-tolerant quantum algorithms&apos;&apos;. Phys. Rev. Res. 6, 023118 (2024).","DOI":"10.1103\/PhysRevResearch.6.023118"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Mingpu Qin, Thomas Sch\u00e4fer, Sabine Andergassen, Philippe Corboz, and Emanuel Gull. ``The hubbard model: A computational perspective&apos;&apos;. Annu. Rev. Condens. Matter Phys. 13, 275\u2013302 (2022).","DOI":"10.1146\/annurev-conmatphys-090921-033948"},{"key":"39","doi-asserted-by":"publisher","unstructured":"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&apos;&apos;. Quantum 5, 385 (2021).","DOI":"10.22331\/q-2021-01-20-385"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Alexander Miessen, Pauline J. Ollitrault, and Ivano Tavernelli. ``Quantum algorithms for quantum dynamics: A performance study on the spin-boson model&apos;&apos;. Phys. Rev. Res. 3, 043212 (2021).","DOI":"10.1103\/PhysRevResearch.3.043212"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Kishor Bharti and Tobias Haug. ``Quantum-assisted simulator&apos;&apos;. Phys. Rev. A 104, 042418 (2021).","DOI":"10.1103\/PhysRevA.104.042418"},{"key":"42","doi-asserted-by":"crossref","unstructured":"Jonathan Novak. ``Truncations of random unitary matrices and young tableaux&apos;&apos; (2006). arXiv:math\/0608108.","DOI":"10.37236\/939"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-09-19-1477\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T13:23:09Z","timestamp":1726752189000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-09-19-1477\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,19]]},"references-count":43,"URL":"https:\/\/doi.org\/10.22331\/q-2024-09-19-1477","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,19]]},"article-number":"1477"}}