کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428498 | 686785 | 2015 | 4 صفحه PDF | دانلود رایگان |
• Revisiting the problem of de-randomizing approximate counting.
• We study approximation problems in the space-bounded model motivated by quantum algorithms for linear algebraic problems.
• Deterministic logspace approximation schemes under de-randomization assumptions.
• Randomized logspace approximation schemes under de-quantumization assumptions.
It was recently shown that SVDSVD 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=prBPLprBQL=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≠prBPLprBQL≠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.
Journal: Information Processing Letters - Volume 115, Issue 10, October 2015, Pages 750–753