zbMATH — the first resource for mathematics

On the de-randomization of space-bounded approximate counting problems. (English) Zbl 1329.68287
Summary: It was recently shown that \(\mathsf{SVD}\) and matrix inversion can be approximated in quantum log-space [A. Ta-Shma, in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM). 881–890 (2013; Zbl 1293.68129)] for well formed matrices. This can be interpreted as a fully logarithmic quantum approximation scheme for both problems. We show that if \(\mathsf{prBQL} = \mathsf{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, \(\mathsf{prBQL}\neq\mathsf{prBPL}\).
On the way we simplify a proof of O. Goldreich [Lect. Notes Comput. Sci. 6650, 191–232 (2011; Zbl 1343.68084)] 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.

68W25 Approximation algorithms
68Q12 Quantum algorithms and complexity in the theory of computing
68W20 Randomized algorithms
Full Text: DOI
[1] Ta-Shma, A., Inverting well conditioned matrices in quantum logspace, (Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, STOC ’13, (2013), ACM New York, NY, USA), 881-890 · Zbl 1293.68129
[2] Halko, N.; Martinsson, P.-G.; Tropp, J. A., Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53, 2, 217-288, (2011) · Zbl 1269.65043
[3] Spielman, D. A.; Teng, S.-H., Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems, preprint · Zbl 1311.65031
[4] Harrow, A. W.; Hassidim, A.; Lloyd, S., Quantum algorithm for linear systems of equations, Phys. Rev. Lett., 103, 15, 150502, (2009)
[5] Stockmeyer, L., On approximation algorithms for #P, SIAM J. Comput., 14, 4, 849-861, (1985) · Zbl 0589.68031
[6] Shaltiel, R.; Umans, C., Pseudorandomness for approximate counting and sampling, Comput. Complex., 15, 4, 298-341, (2006) · Zbl 1125.68058
[7] Jerrum, M.; Sinclair, A.; Vigoda, E., A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM, 51, 4, 671-697, (2004) · Zbl 1204.65044
[8] Goldreich, O., A world of P = BPP, (Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, (2011), Springer), 191-232 · Zbl 1343.68084
[9] Aaronson, S., The complexity zoo, (2014)
[10] van Melkebeek, D.; Watson, T., Time-space efficient simulations of quantum computations, Electron. Colloq. Comput. Complex., 17, 147, (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.