Eliminating intermediate measurements in space-bounded Quantum computation
Eliminating intermediate measurements in space-bounded Quantum computation
复制标题
消除空间有限量子计算中的中间测量
DOI：
10.1145/3406325.3451051
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Remscrim, Zachary
中科院分区：
文献类型：
--
作者：
Fefferman, Bill;Remscrim, Zachary
量子计算理论中的一个基本结果，也就是众所周知的“安全存储原理”表明，总是有可能利用量子电路，产生一个等效电路，在计算结束时进行所有测量。虽然这个过程是时间高效的，这意味着它不会在门的数量上引入很大的开销，但它使用了额外的辅助量子比特，因此通常不是空间高效的。人们很自然地会问，是否有可能在不增加辅助量子比特的情况下消除中间测量。我们给出了一个肯定的答案，通过展示一个过程，消除所有中间测量，同时是空间效率和时间效率。特别是，这表明空间受限量子复杂性类的定义对于允许或禁止中间测量是稳健的。我们方法的一个关键部分，可能是独立感兴趣的，涉及到证明许多标准线性代数问题的良好条件版本可以用比经典计算机看起来可能的更小的空间由量子计算机解决。
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 eliminate intermediate measurements 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. In particular, this shows that the definition of a space-bounded quantum complexity class is robust to allowing or forbidding intermediate measurements. 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.
登录
查看更多内容
算术复杂度、克林闭包和形式幂级数
影响因子：
0.5
作者：
Eric Allender;V. Arvind;M. Mahajan
通讯作者：
M. Mahajan
DOI：
10.1090/conm/536/10552
发表时间：
2006-02
期刊：
arXiv: Quantum Physics
影响因子：
--
作者：
S. Bravyi
通讯作者：
S. Bravyi
关于概率对数空间中随机矩阵特征值的逼近
影响因子：
1.4
作者：
Dean Doron;Amir Sarid;A. Ta
通讯作者：
A. Ta
DOI：
10.4230/lipics.itcs.2021.39
发表时间：
2020-03
期刊：
--
影响因子：
--
作者：
Zachary Remscrim
通讯作者：
Zachary Remscrim
可逆空间等于确定性空间
DOI：
10.1109/ccc.1997.612299
发表时间：
1997
期刊：
Proceedings of Computational Complexity. Twelfth Annual IEEE Conference
影响因子：
--
作者：
Klaus;P. McKenzie;Alain Tapp
通讯作者：
Alain Tapp