We consider the problem of computing a few of the smallest eigenvalues of the Hermitian eigenvalue problem

\begin{equation} H x = \lambda x, \label {eq:hep} \end{equation}

where \(H\) is a Hermitian matrix of exponential dimension \(N = 2^n\). This problem is of critical importance in fields such as condensed matter physics, quantum chemistry, and materials science, where solving such eigenvalue problems yields ground and excited state energies of quantum many-body Hamiltonians.

Classical numerical methods based on Krylov subspaces rank among the most successful techniques in numerical linear algebra. In this talk, we introduce various quantum Krylov methods for solving the Hermitian eigenvalue problem (1). These quantum subspace techniques present promising tools within the growing field of hybrid quantum-classical algorithms. Hybrid strategies deploy a quantum computer for the tasks where it excels, for example evolving a wavefunction with unitary operators, while offloading other parts of the computation to a classical computer. The hybrid quantum-classical paradigm allows to bridge the gap between the current noisy intermediate-scale quantum (NISQ) devices with all their limitations and the era of large-scale fault-tolerant quantum computers. We focus on quantum eigenvalue algorithms that are particularly well-suited for near-term applications on NISQ hardware.

The first and oldest class of hybrid quantum-classical methods for solving (1) are variational quantum algorithms [1]. In these algorithms, we employ a parameterized ansatz eigenvector \(x(\theta )\) and optimize the Rayleigh quotient

\begin{equation} R(H,x(\theta )) = x(\theta )^* H x(\theta ), \end{equation}

which can be measured on a quantum computer as the expectation value of the observable corresponding to \(H\) when the system is in state \(x(\theta )\). A classical optimizer iteratively updates the parameters \(\theta \) based on the expectation values measured on the quantum computer. However, variational quantum algorithms face challenges, notably the phenomenon of barren plateaus, where the gradient of the optimization landscape vanishes exponentially, making it difficult for classical optimizers to converge [7].

Recently, quantum subspace methods have emerged as a robust alternative class of hybrid eigenvalue algorithms [2, 3, 5]. These methods operate within subspaces, rather than iteratively optimizing a single vector, and often achieve faster convergence than variational quantum algorithms. We focus on quantum Krylov subspaces constructed via real-time evolution

\begin{equation} v_0 \to e^{-iHt} v_0, \end{equation}

a unitary operation native to quantum hardware and well-suited for NISQ implementations, via, for example, Trotterization using Lie product formulas [4]. The corresponding Krylov subspace is constructed as follows

\begin{equation} \mathcal {K}_m(U,v_0) = \left [ v_0, U v_0, U^2 v_0, \ldots , U^{m-1} v_0 \right ], \label {eq:krylov} \end{equation}

where \(U^k = e^{-iHk\Delta {t}}\) is the unitary obtained from evolving \(H\) over time \(t = k\Delta {t}\).

Unlike classical Krylov subspace methods, we do not construct the subspace explicitly on the quantum computer. Instead, we obtain the projected eigenvalue problem through quantum measurements and solve this small projected problem classically. To compute the matrix elements of the projected Hamiltonian \(\hat {H}\), we start by preparing the initial quantum state \(v_0\) and evolving it over time \(k\Delta {t}\), resulting in \(v_k = e^{-iHk\Delta {t}} v_0\). We then measure the matrix elements

\begin{equation} \hat {H}_{j,k} = v_j^* H v_k. \end{equation}

Because orthogonalizing vectors on a quantum computer is challenging and definitely impossible in the NISQ era, quantum subspace methods utilize non-orthogonal bases. Consequently, we also need to measure the inner products

\begin{equation} \hat {S}_{j,k} = v_j^* v_k, \end{equation}

leading to the projected generalized eigenvalue problem

\begin{equation} \hat {H} x = \lambda \hat {S} x. \label {eq:gep} \end{equation}

However, solving for the Ritz values of this generalized eigenvalue problem (7) is often challenging due to the ill-conditioning of the problem. To address this issue, we present a dynamic mode decomposition approach, a method designed to circumvent this ill-conditioning and capable of robustly obtaining eigenvalue estimations from noise quantum observables [5]. In this talk, we present a numerical linear algebra perspective on quantum subspace algorithms, discuss strategies to avoid ill-conditioned eigenvalue problems, and provide both theoretical and numerical evidence of convergence. Additionally, we introduce strategies to enhance robustness, particularly in noisy quantum environments.

A third class of hybrid quantum-classical eigenvalue methods leverages rational functions, which offer rapid convergence in scientific computing but remain underexplored in quantum algorithms. We present efficient implementations of rational transformations on quantum hardware [6]. By using integral representations of the resolvent, we can efficiently perform quantum rational transformations through Hamiltonian simulations and the linear-combination-of-unitaries (LCU) method. We introduce two complementary LCU-based strategies—discrete-time and continuous-time—offering flexible approaches for quantum rational transformations. We also illustrate these novel methods through numerical simulations on spin systems, achieving precise calculations of low-lying eigenvalues.

References

• [1]  M. Cerezo, A. Arrasmith, R. Babbush, S.C. Benjamin, S. Endo, K. Fujii, J.R. McClean, et al., Variational quantum algorithms, Nature Reviews Physics, 3 (2021), pp. 625–644.

• [2]  E.N. Epperly, L. Lin, and Y. Nakatsukasa, A theory of quantum subspace diagonalization, SIAM Journal on Matrix Analysis and Applications, 43 (2022), pp. 1263–1290.

• [3]  W. Kirby, M. Motta, and A. Mezzacapo, Exact and efficient Lanczos method on a quantum computer, Quantum, 7 (2023), p. 1018.

• [4]  K. Klymko, C. Mejuto-Zaera, S.J. Cotton, F. Wudarski, M. Urbanek, D. Hait, M. Head-Gordon, et al., Real-time evolution for ultracompact Hamiltonian eigenstates on quantum hardware, PRX Quantum, 3 (2022), p. 20323.

• [5]  Y. Shen, D. Camps, A. Szasz, S. Darbha, K. Klymko, D.B. Williams-Young, N.M. Tubman, and R. Van Beeumen, Estimating eigenenergies from quantum dynamics: A unified noise-resilient measurement-driven approach, 2023, arXiv.2306.01858.

• [6]  Y. Shen, N. Van Buggenhout, D. Camps, K. Klymko, and R. Van Beeumen, Quantum rational transformation using linear combinations of Hamiltonian simulations, 2024, arXiv.2408.07742.

• [7]  S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P.J. Coles, Noise-induced barren plateaus in variational quantum algorithms, Nature Communications, 12 (2021), p. 6961.