@article {1818,
title = {Space-Efficient Error Reduction for Unitary Quantum Computations},
journal = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
volume = {55},
year = {2016},
month = {2016/04/27},
pages = {14:1--14:14},
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\ 2\−p, the most space-efficient method known requires extra workspace of\ O(plog1c\−s)\ 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(logpc\−s)\ 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.

},
isbn = {978-3-95977-013-2},
issn = {1868-8969},
doi = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.14},
url = {http://drops.dagstuhl.de/opus/volltexte/2016/6297},
author = {Bill Fefferman and Hirotada Kobayashi and Cedric Yen-Yu Lin and Tomoyuki Morimae and Harumichi Nishimura}
}