2026-07-20T05:09:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14005 2024-03-06T10:53:23Z ddc:004 open_access

Quantum Logarithmic Space and Post-Selection Le Gall, François Nishimura, Harumichi Yakaryılmaz, Abuzer computational complexity space-bounded quantum computation post-selection Post-selection, the power of discarding all runs of a computation in which an undesirable event occurs, is an influential concept introduced to the field of quantum complexity theory by Aaronson (Proceedings of the Royal Society A, 2005). In the present paper, we initiate the study of post-selection for space-bounded quantum complexity classes. Our main result shows the identity PostBQL = PL, i.e., the class of problems that can be solved by a bounded-error (polynomial-time) logarithmic-space quantum algorithm with post-selection (PostBQL) is equal to the class of problems that can be solved by unbounded-error logarithmic-space classical algorithms (PL). This result gives a space-bounded version of the well-known result PostBQP = PP proved by Aaronson for polynomial-time quantum computation. As a by-product, we also show that PL coincides with the class of problems that can be solved by bounded-error logarithmic-space quantum algorithms that have no time bound. Schloss Dagstuhl – Leibniz-Zentrum für Informatik François Le Gall and Harumichi Nishimura and Abuzer Yakaryılmaz 2021 Is Part Of LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2021.10 urn:nbn:de:0030-drops-140054 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.10 eng https://creativecommons.org/licenses/by/4.0/legalcode