Title | Space-Efficient Error Reduction for Unitary Quantum Computations |

Publication Type | Journal Article |

Year of Publication | 2016 |

Authors | Fefferman, B, Kobayashi, H, Lin, CYen-Yu, Morimae, T, Nishimura, H |

Journal | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |

Volume | 55 |

Pages | 14:1--14:14 |

Date Published | 2016/04/27 |

ISSN | 1868-8969 |

ISBN Number | 978-3-95977-013-2 |

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. |

URL | http://drops.dagstuhl.de/opus/volltexte/2016/6297 |

DOI | 10.4230/LIPIcs.ICALP.2016.14 |