标题： 无需对数因子的高效空间量子误差缩减 显示英文标题

标题： Space-Efficient Quantum Error Reduction without log Factors

摘要： 给定一个以有界误差输出正确答案的算法，例如$1/3$，有时希望将此误差减少到任意小的$\varepsilon$——例如，如果想要多次调用该算法作为子程序。量子和随机算法通常使用一种称为多数投票的程序，这会带来调用该算法多次的乘法开销$O(\log\frac{1}{\varepsilon})$。最近的一篇论文引入了一种称为\emph{转换器}的量子计算模型，并展示了如何仅使用类似于多数投票的构造\emph{纯化}，就能任意减少“误差”。即使无误差的转换器也映射到有界误差的量子算法，因此这并不能免费降低算法误差，但它允许有界误差的量子算法组合而不产生对数因子。在本文中，我们提出了一种净化器的新高度简化的构造，可以理解为类似于多数投票的随机游走解释的线性加权行走。除了提供一种更容易与多数投票对比的新视角外，我们的净化器在空间复杂度上比之前的方案指数级更好，并且对算法的可靠性-完备性差距的依赖关系二次方更好。我们的新净化器具有几乎最优的查询复杂度，甚至达到常数级别，这在将量子算法组合到超常数深度时非常重要。 显示英文摘要

摘要： Given an algorithm that outputs the correct answer with bounded error, say $1/3$, it is sometimes desirable to reduce this error to some arbitrarily small $\varepsilon$ -- for example, if one wants to call the algorithm many times as a subroutine. The usual method, for both quantum and randomized algorithms, is a procedure called majority voting, which incurs a multiplicative overhead of $O(\log\frac{1}{\varepsilon})$ from calling the algorithm this many times. A recent paper introduced a model of quantum computation called \emph{transducers}, and showed how to reduce the ``error'' of a transducer arbitrarily with only constant overhead, using a construction analogous to majority voting called \emph{purification}. Even error-free transducers map to bounded-error quantum algorithms, so this does not let you reduce algorithmic error for free, but it does allow bounded-error quantum algorithms to be composed without incurring log factors. In this paper, we present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. In addition to providing a new perspective that is easier to contrast with majority voting, our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified. Our new purifier has nearly optimal query complexity, even down to the constant, which matters when one composes quantum algorithms to super-constant depth.