2026-07-22T04:54:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16879 2024-03-06T10:58:34Z ddc:004 open_access

Space-Bounded Unitary Quantum Computation with Postselection Tani, Seiichiro quantum complexity theory space-bounded computation postselection Space-bounded computation has been a central topic in classical and quantum complexity theory. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343-1356] and Girish, Raz and Zhan [ICALP 2021, pp.73:1-73:20] recently provided the break-through results that the power does not change. This paper shows that a similar result holds for space-bounded quantum computation with postselection. Namely, it is proved possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall, Nishimura and Yakaryilmaz [TQC 2021, pp.10:1-10:17] that logarithmic-space bounded-error quantum computation with intermediate postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. As an application, it is shown that bounded-error space-bounded one-clean qubit computation (DQC1) with postselection is equivalent in computational power to unbounded-error space-bounded probabilistic computation, and the computational supremacy of the bounded-error space-bounded DQC1 is interpreted in complexity-theoretic terms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Seiichiro Tani 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.81 urn:nbn:de:0030-drops-168798 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.81 eng https://creativecommons.org/licenses/by/4.0/legalcode