2026-07-22T16:11:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6297 2024-03-06T10:37:39Z ddc:004 open_access

Space-Efficient Error Reduction for Unitary Quantum Computations Fefferman, Bill Kobayashi, Hirotada Yen-Yu Lin, Cedric Morimae, Tomoyuki Nishimura, Harumichi space-bounded computation quantum Merlin-Arthur proof systems error reduction quantum computing This paper presents a general space-efficient method for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness c and soundness s, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most 2^{-p}, the most space-efficient method known requires extra workspace of O(p*log(1/(c-s))) qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper shows an errorreduction method for unitary quantum computations (i.e., computations without intermediate measurements) that requires extra workspace of just O(log(p/(c-s))) qubits. This in particular gives the first method of strong amplification for logarithmic-space unitary quantum computations with two-sided bounded error. This also leads to a number of consequences in complexity theory, such as the uselessness of quantum witnesses in bounded-error logarithmic-space unitary quantum computations, the PSPACE upper bound for QMA with exponentially-small completeness-soundness gap, and strong amplification for matchgate computations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bill Fefferman and Hirotada Kobayashi and Cedric Yen-Yu Lin and Tomoyuki Morimae and Harumichi Nishimura 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.14 urn:nbn:de:0030-drops-62975 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.14 eng https://creativecommons.org/licenses/by/3.0/legalcode