文章基本信息

标题：Space-Efficient Error Reduction for Unitary Quantum Computations
本地全文：下载
作者：Bill Fefferman ; Hirotada Kobayashi ; Cedric Yen-Yu Lin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：14:1-14:14
DOI：10.4230/LIPIcs.ICALP.2016.14
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：space-bounded computation; quantum Merlin-Arthur proof systems; error reduction; quantum computing