Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR16-120 | 6th September 2016 17:55

#### On approximating the eigenvalues of stochastic matrices in probabilistic logspace

Revision #1
Authors: Dean Doron, Amir Sarid, Amnon Ta-Shma
Accepted on: 6th September 2016 17:55
Keywords:

Abstract:

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.

Changes to previous version:

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

### Paper:

TR16-120 | 1st August 2016 20:54

#### On approximating the eigenvalues of stochastic matrices in probabilistic logspace

TR16-120
Authors: Dean Doron, Amir Sarid, Amnon Ta-Shma
Publication: 1st August 2016 21:27
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint