论文标题
消除空间结合的量子计算中的中间测量
Eliminating Intermediate Measurements in Space-Bounded Quantum Computation
论文作者
论文摘要
量子计算理论中的基本结果称为“安全存储原理”表明，始终有可能采用量子电路并产生等效电路，该电路在计算结束时进行所有测量。尽管此过程是有效的，但这意味着它不会在大门数量中引入大开销，但它使用了额外的辅助量子台，因此通常不会有效。询问是否可以将测量值推迟到量子计算的末端而不增加辅助量子数的数量是很自然的。 我们通过展示一项程序来消除所有同时空间效率和时间效率的程序来对这个问题提供肯定的答案。我们方法的一个关键组成部分可能具有独立的兴趣，涉及表明，在许多标准线性敏捷问题的条件版本中，可以通过量子计算机在空间中求解许多标准线性 - 偏用问题，而不是像经典计算机所能更少的空间。
A foundational result in the theory of quantum computation known as the "principle of safe storage" shows that it is always possible to take a quantum circuit and produce an equivalent circuit that makes all measurements at the end of the computation. While this procedure is time efficient, meaning that it does not introduce a large overhead in the number of gates, it uses extra ancillary qubits and so is not generally space efficient. It is quite natural to ask whether it is possible to defer measurements to the end of a quantum computation without increasing the number of ancillary qubits. We give an affirmative answer to this question by exhibiting a procedure to eliminate all intermediate measurements that is simultaneously space-efficient and time-efficient. A key component of our approach, which may be of independent interest, involves showing that the well-conditioned versions of many standard linear-algebraic problems may be solved by a quantum computer in less space than seems possible by a classical computer.
