A theory of quantum subspace diagonalization. (English) Zbl 07566190
Summary: Quantum subspace diagonalization methods are an exciting new class of algorithms for solving large-scale eigenvalue problems using quantum computers. Unfortunately, these methods require the solution of an ill-conditioned generalized eigenvalue problem, with a matrix pencil corrupted by a nonnegligible amount of noise that is far above the machine precision. Despite pessimistic predictions from classical worst-case perturbation theories, these methods can perform reliably well if the generalized eigenvalue problem is solved using a standard truncation strategy. By leveraging and advancing classical results in matrix perturbation theory, we provide a theoretical analysis of this surprising phenomenon, proving that under certain natural conditions, a quantum subspace diagonalization algorithm can accurately compute the smallest eigenvalue of a large Hermitian matrix. We give numerical experiments demonstrating the effectiveness of the theory and providing practical guidance for the choice of truncation level. Our new results can also be of independent interest to solving eigenvalue problems outside the context of quantum computation.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 15A22 | Matrix pencils |
| 15A45 | Miscellaneous inequalities involving matrices |
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 81P68 | Quantum computation |
Keywords:
quantum subspace diagonalization; quantum linear algebra; generalized eigenvalue problem; matrix perturbation theorySoftware:
QuSpinReferences:
| [1] | R. Bhatia, Matrix Analysis, Grad. Texts in Math. 169, Springer-Verlag, New York, 1997, https://doi.org/10.1007/978-1-4612-0653-8. |
| [2] | \AA. Björck, Numerical Methods in Matrix Computations, Texts in Appl. Math. 59, Springer International, New York, 2015, https://doi.org/10.1007/978-3-319-05089-8. · Zbl 1322.65047 |
| [3] | Y. Cai, Z. Bai, J. E. Pask, and N. Sukumar, Hybrid preconditioning for iterative diagonalization of ill-conditioned generalized eigenvalue problems in electronic structure calculations, J. Comput. Phys., 255 (2013), pp. 16-30. · Zbl 1349.81204 |
| [4] | A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, Theory of Trotter error with commutator scaling, Phys. Rev. X, 11 (2021), 011020, https://doi.org/10.1103/PhysRevX.11.011020. |
| [5] | 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 (2018), 011021, https://doi.org/10.1103/PhysRevX.8.011021. |
| [6] | C. L. Cortes and S. K. Gray, Quantum Krylov Subspace Algorithms for Ground and Excited State Energy Estimation, https://arxiv.org/abs/2109.06868, 2021. |
| [7] | C. Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal., 7 (1970), pp. 1-46, https://doi.org/10.1137/0707001. · Zbl 0198.47201 |
| [8] | P. Drineas and I. C. F. Ipsen, Low-rank matrix approximations do not need a singular value gap, SIAM J. Matrix Anal. Appl., 40 (2019), pp. 299-319, https://doi.org/10.1137/18M1163658. · Zbl 1455.65066 |
| [9] | A. Emami-Naeini and P. Van Dooren, Computation of zeros of linear multivariable systems, Automatica, 18 (1982), pp. 415-430, https://doi.org/10.1016/0005-1098(82)90070-X. · Zbl 0484.93029 |
| [10] | G. Fix and R. Heiberger, An algorithm for the ill-conditioned generalized eigenvalue problem, SIAM J. Numer. Anal., 9 (1972), pp. 78-88, https://doi.org/10.1137/0709009. · Zbl 0252.65028 |
| [11] | G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, Baltimore, 2013. · Zbl 1268.65037 |
| [12] | L. A. Gribov and B. K. Novosadov, Use of overcomplete basis sets in quantum-chemical calculations, J. Molecular Structure THEOCHEM, 136 (1986), pp. 387-389, https://doi.org/10.1016/0166-1280(86)80152-X. |
| [13] | W. J. Huggins, J. Lee, U. Baek, B. O’Gorman, and K. B. Whaley, A non-orthogonal variational quantum eigensolver, New J. Phys., 22 (2020), 073009, https://doi.org/10.1088/1367-2630/ab867b. |
| [14] | M. Jungen and K. Kaufmann, The Fix-Heiberger procedure for solving the generalized ill-conditioned symmetric eigenvalue problem, Int. J. Quantum Chem., 41 (1992), pp. 387-397. |
| [15] | K. Klymko, C. Mejuto-Zaera, S. J. Cotton, F. Wudarski, M. Urbanek, D. Hait, M. Head-Gordon, K. B. Whaley, J. Moussa, N. Wiebe, W. A. de Jong, and N. M. Tubman, Real Time Evolution for Ultracompact Hamiltonian Eigenstates on Quantum Hardware, https://arxiv.org/abs/2103.08563, 2021. |
| [16] | M. Lotz and V. Noferini, Wilkinson’s bus: Weak condition numbers, with an application to singular polynomial eigenproblems, Found. Comput. Math., 20 (2020), pp. 1439-1473, https://doi.org/10.1007/s10208-020-09455-y. · Zbl 1455.65056 |
| [17] | P.-O. Löwdin, Group algebra, convolution algebra, and applications to quantum mechanics, Rev. Modern Phys., 39 (1967), pp. 259-287, https://doi.org/10.1103/RevModPhys.39.259. · Zbl 0163.21801 |
| [18] | V. A. Mandelshtam and H. S. Taylor, Harmonic inversion of time signals and its applications, J. Chem. Phys., 107 (1997), pp. 6756-6769, https://doi.org/10.1063/1.475324. |
| [19] | R. Mathias and C.-K. Li, The Definite Generalized Eigenvalue Problem: A New Perturbation Theory, T-NAREP 457, Manchester Centre for Computational Mathematics, 2004. |
| [20] | J. R. McClean, M. E. Kimchi-Schwartz, J. Carter, and W. A. de Jong, Hybrid quantum-classical hierarchy for mitigation of decoherence and determination of excited states, Phys. Rev. A, 95 (2017), 042308, https://doi.org/10.1103/PhysRevA.95.042308. |
| [21] | M. Motta, C. Sun, A. T. K. Tan, M. J. O’Rourke, E. Ye, A. J. Minnich, F. G. S. L. Branda͂o, and G. K.-L. Chan, Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution, Nature Physics, 16 (2020), pp. 205-210, https://doi.org/10.1038/s41567-019-0704-4. |
| [22] | G. Nannicini, An introduction to quantum computing, without the physics, SIAM Rev., 62 (2020), pp. 936-981. · Zbl 1512.68096 |
| [23] | J. W. Negele and H. Orland, Quantum Many-Particle Systems, Westview, Boulder, CO, 1988. · Zbl 0984.82503 |
| [24] | M. A. Nielsen and I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, UK, 2000. · Zbl 1049.81015 |
| [25] | B. N. Parlett, The Symmetric Eigenvalue Problem, Classics in Appl. Math. 20, SIAM, Philadelphia, 1998, https://doi.org/10.1137/1.9781611971163. · Zbl 0885.65039 |
| [26] | R. M. Parrish and P. L. McMahon, Quantum Filter Diagonalization: Quantum Eigendecomposition Without Full Quantum Phase Estimation, https://arxiv.org/abs/1909.08925, 2019. |
| [27] | J. Preskill, Quantum computing in the NISQ era and beyond, Quantum, 2 (2018), p. 79. |
| [28] | J. Preskill, Quantum Computing 40 Years Later, https://arxiv.org/abs/2106.10522, 2021. |
| [29] | Y. Saad, On the rates of convergence of the Lanczos and the block-Lanczos methods, SIAM J. Numer. Anal., 17 (1980), pp. 687-706, https://doi.org/10.1137/0717059. · Zbl 0456.65016 |
| [30] | I. Sabzevari, A. Mahajan, and S. Sharma, An accelerated linear method for optimizing non-linear wavefunctions in variational Monte Carlo, J. Chem. Phys., 152 (2020), 024111, https://doi.org/10.1063/1.5125803. |
| [31] | K. Seki and S. Yunoki, Quantum power method by a superposition of time-evolved states, Phys. Rev. X Quantum, 2 (2021), 010333. |
| [32] | N. H. Stair, R. Huang, and F. A. Evangelista, A multireference quantum Krylov algorithm for strongly correlated electrons, J. Chem. Theory Comput., 16 (2020), pp. 2236-2245, https://doi.org/10.1021/acs.jctc.9b01125. |
| [33] | G. W. Stewart, Perturbation bounds for the definite generalized eigenvalue problem, Linear Algebra Appl., 23 (1979), pp. 69-85, https://doi.org/10.1016/0024-3795(79)90094-6. · Zbl 0407.15012 |
| [34] | G. W. Stewart and J.-G. Sun, Matrix Perturbation Theory, Computer Science and Scientific Computing, Academic Press, New York, 1990. · Zbl 0706.65013 |
| [35] | J. A. Tropp, An Introduction to Matrix Concentration Inequalities, Found. Trends Machine Learning 8, Now Publishers, Hanover, 2015, pp. 1-230. · Zbl 1391.15071 |
| [36] | M. R. Wall and D. 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, J. Chem. Phys., 102 (1995), pp. 8011-8022, https://doi.org/10.1063/1.468999. |
| [37] | P. Weinberg and M. Bukov, QuSpin: A Python package for dynamics and exact diagonalisation of quantum many body systems Part I: Spin chains, SciPost Phys., 2 (2017). |
| [38] | P. Weinberg and M. Bukov, QuSpin: A Python package for dynamics and exact diagonalisation of quantum many body systems. Part II: Bosons, fermions and higher spins, SciPost Phys., 7 (2019). |
| [39] | J. H. Wilkinson, Kronecker’s canonical form and the QZ algorithm, Linear Algebra Appl., 28 (1979), pp. 285-303, https://doi.org/10.1016/0024-3795(79)90140-X. · Zbl 0458.65022 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
