Exact And Efficient Lanczos Method On A Quantum Computer

William Kirby^1,2, Mario Motta³, and Antonio Mezzacapo⁴

¹IBM Quantum, IBM Research Cambridge, Cambridge, MA 02142, USA
²Department of Physics and Astronomy, Tufts University, Medford, MA 02155, USA
³IBM Quantum, IBM Research Almaden, San Jose, CA 95120, USA
⁴IBM Quantum, T. J. Watson Research Center, Yorktown Heights, NY 10598, USA

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

Abstract

We present an algorithm that uses block encoding on a quantum computer to exactly construct a Krylov space, which can be used as the basis for the Lanczos method to estimate extremal eigenvalues of Hamiltonians. While the classical Lanczos method has exponential cost in the system size to represent the Krylov states for quantum systems, our efficient quantum algorithm achieves this in polynomial time and memory. The construction presented is exact in the sense that the resulting Krylov space is identical to that of the Lanczos method, so the only approximation with respect to the exact method is due to finite sample noise. This is possible because, unlike previous quantum Krylov methods, our algorithm does not require simulating real or imaginary time evolution. We provide an explicit error bound for the resulting ground state energy estimate in the presence of noise. For our method to be successful efficiently, the only requirement on the input problem is that the overlap of the initial state with the true ground state must be $Omega(1/text{poly}(n))$ for $n$ qubits.

Featured image: The circuits required to generate a Krylov space of dimension $D$, expressed in terms of the input block encoding operators.

► BibTeX data

@article{Kirby2023exactefficient, doi = {10.22331/q-2023-05-23-1018}, url = {https://doi.org/10.22331/q-2023-05-23-1018}, title = {Exact and efficient {L}anczos method on a quantum computer}, author = {Kirby, William and Motta, Mario and Mezzacapo, Antonio}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {1018}, month = may, year = {2023}<br /> }

► References

[1] Alán Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-Gordon. “Simulated quantum computation of molecular energies”. Science 309, 1704–1707 (2005).
https://doi.org/10.1126/science.1113479

[2] 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 EP – (2014).
https://doi.org/10.1038/ncomms5213

[3] P. J. J. O’Malley, R. Babbush, I. D. Kivlichan, J. Romero, J. R. McClean, R. Barends, J. Kelly, P. Roushan, A. Tranter, N. Ding, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. G. Fowler, E. Jeffrey, E. Lucero, A. Megrant, J. Y. Mutus, M. Neeley, C. Neill, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, P. V. Coveney, P. J. Love, H. Neven, A. Aspuru-Guzik, and J. M. Martinis. “Scalable quantum simulation of molecular energies”. Phys. Rev. X 6, 031007 (2016).
https://doi.org/10.1103/PhysRevX.6.031007

[4] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. “Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets”. Nature 549, 242–246 (2017).
https://doi.org/10.1038/nature23879

[5] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan. “Quantum computational chemistry”. Rev. Mod. Phys. 92, 015003 (2020).
https://doi.org/10.1103/RevModPhys.92.015003

[6] Yuan Su, Dominic W. Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush. “Fault-tolerant quantum simulations of chemistry in first quantization”. PRX Quantum 2, 040332 (2021).
https://doi.org/10.1103/PRXQuantum.2.040332

[7] Alexei Y. Kitaev. “Quantum measurements and the abelian stabilizer problem” (1995). url: doi.org/10.48550/arXiv.quant-ph/9511026.
https://doi.org/10.48550/arXiv.quant-ph/9511026
arXiv:quant-ph/9511026

[8] Seth Lloyd. “Universal quantum simulators”. Science 273, 1073–1078 (1996).
https://doi.org/10.1126/science.273.5278.1073

[9] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. “Quantum computation by adiabatic evolution” (2000). url: doi.org/10.48550/arXiv.quant-ph/0001106.
https://doi.org/10.48550/arXiv.quant-ph/0001106
arXiv:quant-ph/0001106

[10] R. Somma, G. Ortiz, J. E. Gubernatis, E. Knill, and R. Laflamme. “Simulating physical phenomena by quantum networks”. Phys. Rev. A 65, 042323 (2002).
https://doi.org/10.1103/PhysRevA.65.042323

[11] James D. Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik. “Simulation of electronic structure hamiltonians using quantum computers”. Molecular Physics 109, 735–750 (2011).
https://doi.org/10.1080/00268976.2011.552441

[12] Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven, and Garnet Kin-Lic Chan. “Low-depth quantum simulation of materials”. Phys. Rev. X 8, 011044 (2018).
https://doi.org/10.1103/PhysRevX.8.011044

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

[14] J. I. Colless, V. V. Ramasesh, D. Dahlen, M. S. Blok, M. E. Kimchi-Schwartz, J. R. McClean, J. Carter, W. A. de Jong, and I. Siddiqi. “Computation of molecular spectra on a quantum processor with an error-resilient algorithm”. Phys. Rev. X 8, 011021 (2018).
https://doi.org/10.1103/PhysRevX.8.011021

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

[16] 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 (2020).
https://doi.org/10.1038/s41567-019-0704-4

[17] Robert M. Parrish and Peter L. McMahon. “Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation” (2019). url: doi.org/10.48550/arXiv.1909.08925.
https://doi.org/10.48550/arXiv.1909.08925

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

[19] 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, 011004 (2020).
https://doi.org/10.1103/PhysRevX.10.011004

[20] Lin Lin and Yu Tong. “Near-optimal ground state preparation”. Quantum 4, 372 (2020).
https://doi.org/10.22331/q-2020-12-14-372

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

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

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

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

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

[26] Unpil Baek, Diptarka Hait, James Shee, Oskar Leimkuhler, William J. Huggins, Torin F. Stetina, Martin Head-Gordon, and K. Birgitta Whaley. “Say no to optimization: A non-orthogonal quantum eigensolver” (2022). url: doi.org/10.48550/arXiv.2205.09039.
https://doi.org/10.48550/arXiv.2205.09039

[27] Nikolay V. Tkachenko, Yu Zhang, Lukasz Cincio, Alexander I. Boldyrev, Sergei Tretiak, and Pavel A. Dub. “Quantum davidson algorithm for excited states” (2022). url: doi.org/10.48550/arXiv.2204.10741.
https://doi.org/10.48550/arXiv.2204.10741

[28] Lin Lin and Yu Tong. “Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers”. PRX Quantum 3, 010318 (2022).
https://doi.org/10.1103/PRXQuantum.3.010318

[29] 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 (2022).
https://doi.org/10.1103/PRXQuantum.3.040305

[30] Alexei Kitaev, A. H. Shen, and M. N. Vyalyi. “Classical and quantum computation”. Volume 47 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI. (2002).
https://doi.org/10.1090/gsm/047

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

[32] 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, No. 4 (1950).
https://doi.org/10.6028/jres.045.026

[33] Jane K Cullum and Ralph A Willoughby. “Lanczos algorithms for large symmetric eigenvalue computations: Vol. i: Theory”. Society for Industrial and Applied Mathematics. (2002).
https://doi.org/10.1137/1.9780898719192

[34] Shmuel Kaniel. “Estimates for some computational techniques in linear algebra”. Mathematics of Computation 20, 369–378 (1966).
https://doi.org/10.2307/2003590

[35] Christopher Conway Paige. “The computation of eigenvalues and eigenvectors of very large sparse matrices”. PhD thesis. University of London. (1971). url: ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.307848.
https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.307848

[36] Y. Saad. “On the rates of convergence of the lanczos and the block-lanczos methods”. SIAM Journal on Numerical Analysis 17, 687–706 (1980).
https://doi.org/10.1137/0717059

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

[38] Guang Hao Low and Isaac L. Chuang. “Hamiltonian Simulation by Qubitization”. Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163

[39] Guang Hao Low and Isaac L. Chuang. “Optimal hamiltonian simulation by quantum signal processing”. Phys. Rev. Lett. 118, 010501 (2017).
https://doi.org/10.1103/PhysRevLett.118.010501

[40] Iordanis Kerenidis and Anupam Prakash. “Quantum Recommendation Systems”. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:21. Dagstuhl, Germany (2017). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2017.49

[41] Mark Steudtner and Stephanie Wehner. “Estimating exact energies in quantum simulation without toffoli gates”. Phys. Rev. A 101, 052329 (2020).
https://doi.org/10.1103/PhysRevA.101.052329

[42] Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. “Explicit quantum circuits for block encodings of certain sparse matrices” (2022). url: doi.org/10.48550/arXiv.2203.10236.
https://doi.org/10.48550/arXiv.2203.10236

[43] Daan Camps and Roel Van Beeumen. “Fable: Fast approximate quantum circuits for block-encodings”. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 104–113. (2022).
https://doi.org/10.1109/QCE53715.2022.00029

[44] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. “Quantum fingerprinting”. Phys. Rev. Lett. 87, 167902 (2001).
https://doi.org/10.1103/PhysRevLett.87.167902

[45] Dorit Aharonov, Vaughan Jones, and Zeph Landau. “A polynomial quantum algorithm for approximating the jones polynomial”. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing. Pages 427–436. New York, NY, USA (2006). Association for Computing Machinery.
https://doi.org/10.1145/1132516.1132579

[46] Charles Hadfield, Sergey Bravyi, Rudy Raymond, and Antonio Mezzacapo. “Measurements of quantum hamiltonians with locally-biased classical shadows”. Communications in Mathematical Physics 391, 951–967 (2022).
https://doi.org/10.1007/s00220-022-04343-8

[47] Hsin-Yuan Huang, Richard Kueng, and John Preskill. “Efficient estimation of pauli observables by derandomization”. Phys. Rev. Lett. 127, 030503 (2021).
https://doi.org/10.1103/PhysRevLett.127.030503

[48] Bujiao Wu, Jinzhao Sun, Qi Huang, and Xiao Yuan. “Overlapped grouping measurement: A unified framework for measuring quantum states”. Quantum 7, 896 (2023).
https://doi.org/10.22331/q-2023-01-13-896

[49] Stefan Hillmich, Charles Hadfield, Rudy Raymond, Antonio Mezzacapo, and Robert Wille. “Decision diagrams for quantum measurements with shallow circuits”. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 24–34. (2021).
https://doi.org/10.1109/QCE52317.2021.00018

[50] Charles Hadfield. “Adaptive pauli shadows for energy estimation” (2021). url: doi.org/10.48550/arXiv.2105.12207.
https://doi.org/10.48550/arXiv.2105.12207

[51] Ariel Shlosberg, Andrew J. Jena, Priyanka Mukhopadhyay, Jan F. Haase, Felix Leditzky, and Luca Dellantonio. “Adaptive estimation of quantum observables”. Quantum 7, 906 (2023).
https://doi.org/10.22331/q-2023-01-26-906

[52] Tzu-Ching Yen, Aadithya Ganeshram, and Artur F. Izmaylov. “Deterministic improvements of quantum measurements with grouping of compatible operators, non-local transformations, and covariance estimates”. npj Quantum Information 9, 14 (2023).
https://doi.org/10.1038/s41534-023-00683-y

[53] Bernhard Beckermann and Alex Townsend. “On the singular values of matrices with displacement structure”. SIAM Journal on Matrix Analysis and Applications 38, 1227–1248 (2017).
https://doi.org/10.1137/16M1096426

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

[55] Alexey Uvarov and Jacob Biamonte. “On barren plateaus and cost function locality in variational quantum algorithms”. Journal of Physics A: Mathematical and Theoretical (2021).
https://doi.org/10.1088/1751-8121/abfac7

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

[57] Samson Wang, Enrico Fontana, M. Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J. Coles. “Noise-induced barren plateaus in variational quantum algorithms”. Nature Communications 12, 6961 (2021).
https://doi.org/10.1038/s41467-021-27045-6

[58] Junyu Liu, Zexi Lin, and Liang Jiang. “Laziness, barren plateau, and noise in machine learning” (2022). url: doi.org/10.48550/arXiv.2206.09313.
https://doi.org/10.48550/arXiv.2206.09313

[59] Å. Björck. “Numerical methods in matrix computations”. Texts in Applied Mathematics. Springer International Publishing. (2014).
https://doi.org/10.1007/978-3-319-05089-8

[60] Daniel Gottesman. “Stabilizer codes and quantum error correction” (1997). url: doi.org/10.48550/arXiv.quant-ph/9705052.
https://doi.org/10.48550/arXiv.quant-ph/9705052
arXiv:quant-ph/9705052

[61] Emanuel Knill and Raymond Laflamme. “Theory of quantum error-correcting codes”. Phys. Rev. A 55, 900–911 (1997).
https://doi.org/10.1103/PhysRevA.55.900

Cited by

[1] Dian Wu, Riccardo Rossi, Filippo Vicentini, Nikita Astrakhantsev, Federico Becca, Xiaodong Cao, Juan Carrasquilla, Francesco Ferrari, Antoine Georges, Mohamed Hibat-Allah, Masatoshi Imada, Andreas M. Läuchli, Guglielmo Mazzola, Antonio Mezzacapo, Andrew Millis, Javier Robledo Moreno, Titus Neupert, Yusuke Nomura, Jannes Nys, Olivier Parcollet, Rico Pohle, Imelda Romero, Michael Schmid, J. Maxwell Silvester, Sandro Sorella, Luca F. Tocchio, Lei Wang, Steven R. White, Alexander Wietek, Qi Yang, Yiqi Yang, Shiwei Zhang, and Giuseppe Carleo, “Variational Benchmarks for Quantum Many-Body Problems”, arXiv:2302.04919, (2023).

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

[3] Keita Kanno, Masaya Kohda, Ryosuke Imai, Sho Koh, Kosuke Mitarai, Wataru Mizukami, and Yuya O. Nakagawa, “Quantum-Selected Configuration Interaction: classical diagonalization of Hamiltonians in subspaces selected by quantum computers”, arXiv:2302.11320, (2023).

[4] Nobuyuki Yoshioka, Tsuyoshi Okubo, Yasunari Suzuki, Yuki Koizumi, and Wataru Mizukami, “Hunting for quantum-classical crossover in condensed matter problems”, arXiv:2210.14109, (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] Benchen Huang, Nan Sheng, Marco Govoni, and Giulia Galli, “Quantum simulations of Fermionic Hamiltonians with efficient encoding and ansatz schemes”, arXiv:2212.01912, (2022).

[7] Shi Jin and Nana Liu, “Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation”, arXiv:2304.02865, (2023).

[8] Jakob S. Kottmann and Francesco Scala, “Compact Effective Basis Generation: Insights from Interpretable Circuit Design”, arXiv:2302.10660, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-05-23 14:35:41). 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-05-23 14:35:40: Could not fetch cited-by data for 10.22331/q-2023-05-23-1018 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.
PlatoAiStream. Web3 Data Intelligence. Knowledge Amplified. Access Here.
Minting the Future w Adryenn Ashley. Access Here.
Buy and Sell Shares in PRE-IPO Companies with PREIPO®. Access Here.
Source: https://quantum-journal.org/papers/q-2023-05-23-1018/

Generative Data Intelligence

Exact and efficient Lanczos method on a quantum computer

Abstract

► BibTeX data

► References

Cited by

DOJ Disputes Roman Storm’s Characterization of Tornado Cash Operations in New Filing

Top 5 Crypto Presales: BDAG Leads the Pack with 30,000x ROI Potential

Latest Intelligence

Forbes Unveils 20 Crypto ‘Zombies,’ Declares Ripple And XRP Among The Undead

Consob, Italy’s Watchdog, Bans Additional Forex And Cryptocurrency Trading Websites – CryptoInfoNet

Fed’s Inflation Gauge Heats Up, Rate Cuts on Hold as Bitcoin and Stocks Slide

Explore Top 6 Cryptos for 2024: BlockDAG Leads with Unprecedented ROI Potential

Franklin Templeton’s Ethereum spot ETF listed on DTCC

Bitcoin Bloodbath: Crypto Analyst Spots ‘Death Cross’ After 8% Price Drop

Chat with us