Abstract

This paper develops general space-efficient methods for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness c and soundnesss, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most 2p, the most space-efficient method known requires extra workspace of O(plog1cs) qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper presents error-reduction methods for unitary quantum computations (i.e., computations without intermediate measurements) that require extra workspace of just O(logpcs) qubits. This in particular gives the first methods 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.

Publication Details
Publication Type
Journal Article
Year of Publication
2016
Volume
55
Number of Pages
14:1–14:14
ISSN Number
1868-8969
DOI
10.4230/LIPIcs.ICALP.2016.14
URL
http://drops.dagstuhl.de/opus/volltexte/2016/6297
Journal
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Contributors
Groups
Date Published
04/2016