On the de-randomization of space-bounded approximate counting problems

It was recently shown that $‐{SVD}$ and matrix inversion can be approximated in quantum log‐space [1] for well formed matrices. This can be interpreted as a fully logarithmic quantum approximation scheme for both problems. We show that if $‐{prBQL}=‐{prBPL}$ then every fully logarithmic quantum approximation scheme can be replaced by a probabilistic one. Hence, if classical algorithms cannot approximate the above functions in logarithmic space, then there is a gap already for languages, namely, $‐{prBQL}\ne ‐{prBPL}$ . On the way we simplify a proof of Goldreich for a similar statement for time bounded probabilistic algorithms. We show that our simplified algorithm works also in the space bounded setting (for a large set of functions) whereas Goldreich's approach does not seem to apply in the space bounded setting.