Time-Space Efficient Simulations of Quantum Computations
Time-Space Efficient Simulations of Quantum Computations
复制标题
量子计算的时空高效模拟
作者：
D. Melkebeek;T. Watson
我们给出了两种具有中间测量的时间和空间效率的量子计算模拟，一种是具有无界误差的经典随机计算，另一种是使用任意固定通用门集的量子计算。具体来说，我们的模拟表明，在时间t和空间s中运行的有界误差量子算法可解的每种语言，也可以在时间O（t logt）和空间O（s+ logt）中运行的无界误差随机算法可解，以及限制使用任意泛集并在时间O（t polylogt）和空间O（s+ logt）中运行的有界误差量子算法，只要该泛集在伴随下闭合。我们还开发了一个量子模型，特别适合研究具有同步时间和空间界限的一般计算。作为随机模拟的一个应用，我们得到了求解可满足性问题的一般量子算法的第一个非平凡下界。我们的界限适用于MAJSAT和MAJMAJSAT，这是确定真理的问题
We give two time- and space-efficient simulations of quantum computations with intermediate measurements, one by classical randomized computations with unbounded error and the other by quantum computations that use an arbitrary fixed universal set of gates. Specifically, our simulations show that every language solvable by a bounded-error quantum algorithm running in time t and space s is also solvable by an unbounded-error randomized algorithm running in time O(t logt) and space O(s+ logt), as well as by a bounded-error quantum algorithm restricted to use an arbitrary universal set and running in time O(t polylogt) and space O(s+ logt), provided the universal set is closed under adjoint. We also develop a quantum model that is particularly suitable for the study of general computations with simultaneous time and space bounds. As an application of our randomized simulation, we obtain the first nontrivial lower bound for general quantum algorithms solving problems related to satisfiability. Our bound applies to MAJSAT and MAJMAJSAT, which are the problems of determining the truth