Approximating the eigenvalues of a Hermitian operator can be solved by a quantum logspace algorithm. We introduce the problem of approximating the eigenvalues of a given matrix in the context of classical space-bounded computation. We show that:- Approximating the second eigenvalue of stochastic operators (in a certain range of parameters) is BPL-complete, and, - We show a BPL algorithm that approximates any eigenvalue of a stochastic and emph{Hermitian} operator with emph{constant} accuracy.
展开▼
