论文标题
量子日志空间算法，用于用有限规范供电矩阵
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm
论文作者
论文摘要
我们给出了用于为收缩矩阵供电的量子日志空间算法，即具有光谱标准的矩阵最多〜1。该算法作为输入作为一个任意$ n \ times n $收缩矩阵$ a $，而参数$ t \ leq \ leq \ mathrm {poly}（n）$，并输出$ a^t $的条目，最多为（任意）多项式的小附加错误。该算法仅适用统一操作员，而无需中间测量。我们展示了此结果的各种含义和应用： 首先，我们使用该算法表明，只有量子存储器和中间测量的量子日志空间算法等同于仅具有中间测量的量子记忆的量子logspace算法类别。这表明递延测量原理是量子计算的基本原理，也适用于量子日志空间算法（无经典记忆）。更一般而言，我们给出一种带有空格$ O（S + \ log T）$的量子算法，该算法是输入带有量子空间$ s $ s $ s＆time $ t $的量子算法的描述，并具有中间测量（没有经典内存），并用多个误差误差，无中等程度的测量。 由于单位转换是可逆的（而测量值不可逆的），因此该结果的一个有趣的方面是，它表明可以通过可逆的量子logspace算法模拟任何量子日志空间算法（无经典内存）。这证明了Lange，McKenzie和Tapp结果的量子类似物表明，确定性日志空间等于可逆的Logspace [LMT00]。 最后，我们使用结果来显示量子日志空间学习算法的非平凡的经典模拟。
We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most~1. The algorithm gets as an input an arbitrary $n\times n$ contraction matrix $A$, and a parameter $T \leq \mathrm{poly}(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive error. The algorithm applies only unitary operators, without intermediate measurements. We show various implications and applications of this result: First, we use this algorithm to show that the class of quantum logspace algorithms with only quantum memory and with intermediate measurements is equivalent to the class of quantum logspace algorithms with only quantum memory without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms (without classical memory). More generally, we give a quantum algorithm with space $O(S + \log T)$ that takes as an input the description of a quantum algorithm with quantum space $S$ and time $T$, with intermediate measurements (without classical memory), and simulates it unitarily with polynomially small error, without intermediate measurements. Since unitary transformations are reversible (while measurements are irreversible) an interesting aspect of this result is that it shows that any quantum logspace algorithm (without classical memory) can be simulated by a reversible quantum logspace algorithm. This proves a quantum analogue of the result of Lange, McKenzie and Tapp that deterministic logspace is equal to reversible logspace [LMT00]. Finally, we use our results to show non-trivial classical simulations of quantum logspace learning algorithms.
