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.

The last result falls short of achieving the polynomially-small
accuracy that the quantum algorithm achieves. Thus, at our current
state of knowledge, for stochastic and Hermitian operators we can
achieve polynomially-small accuracy with quantum logspace
algorithms, constant accuracy with probabilistic logspace
algorithms, and no non-trivial result is known for deterministic
logspace algorithms. The quantum algorithm also has the advantage of
working over arbitrary, possibly non-stochastic Hermitian operators.

Our work raises several challenges. First, a derandomization
challenge, trying to achieve a deterministic algorithm approximating
eigenvalues with some non-trivial accuracy. Second, a
de-quantumization challenge trying to decide whether the quantum
logspace model is strictly stronger than the classical probabilistic
model or not. It also casts the probabilistic and
quantum space-bounded models as problems in linear algebra with
differences between operators that are symmetric, stochastic or
both. We therefore believe the problem of approximating the
eigenvalues of a graph is not only natural and important by itself,
but also important for understanding the relative power of
deterministic, probabilistic and quantum logspace computation.

A revised introduction and a generalized result regarding the approximation of the second eigenvalue in BPL.

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.

The last result falls short of achieving the polynomially-small
accuracy that the quantum algorithm achieves. Thus, at our current
state of knowledge, for stochastic and Hermitian operators we can
achieve polynomially-small accuracy with quantum logspace
algorithms, constant accuracy with probabilistic logspace
algorithms, and no non-trivial result is known for deterministic
logspace algorithms. The quantum algorithm also has the advantage of
working over arbitrary, possibly non-stochastic Hermitian operators.

Our work raises several challenges. First, a derandomization
challenge, trying to achieve a deterministic algorithm approximating
eigenvalues with some non-trivial accuracy. Second, a
de-quantumization challenge trying to decide whether the quantum
logspace model is strictly stronger than the classical probabilistic
model or not. It also casts the probabilistic and
quantum space-bounded models as problems in linear algebra with
differences between operators that are symmetric, stochastic or
both. We therefore believe the problem of approximating the
eigenvalues of a graph is not only natural and important by itself,
but also important for understanding the relative power of
deterministic, probabilistic and quantum logspace computation.