Revision #1 Authors: Dean Doron, Amir Sarid, Amnon Ta-Shma

Accepted on: 6th September 2016 17:55

Downloads: 900

Keywords:

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.

TR16-120 Authors: Dean Doron, Amir Sarid, Amnon Ta-Shma

Publication: 1st August 2016 21:27

Downloads: 1470

Keywords:

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.