A quantum eigensolver for symmetric tridiagonal matrices

The eigenproblem of a symmetric tridiagonal matrix widely appears in physical applications and scientific computing. The classical solvers are the symmetric QR iteration, divide-and-conquer, bisection and inverse iteration, etc. For a symmetric tridiagonal matrix of dimension N, the cost of these methods scales at least as \(O(N^2)\). In this work, we present an efficient quantum algorithm for solving this problem through quantum simulation of resonant transitions. The cost of the algorithm can scale as \(poly(\log \,N)\), provided a good initial guess on the eigenstates of the system is obtained. By coupling a probe qubit to a quantum register that represents a system, resonance dynamics can be observed on the probe qubit when its frequency matches a transition frequency in the system. Energy eigenvalues of the system can be obtained by locating resonant transition frequencies between the probe qubit and transitions from a reference state to eigenstates of the system through observing dynamics of the probe qubit for different frequencies. And the system can be evolved to one of its eigenstate with known eigenvalue by inducing an appropriate resonant transition between the probe qubit and the system.