论文标题
通过后选择的空间结合的统一量子计算
Space-Bounded Unitary Quantum Computation with Postselection
论文作者
论文摘要
由太空结合的计算一直是经典和量子复杂性理论中的一个核心主题。在量子情况下，每个基本门必须统一。这种限制使得尚不清楚通过允许中间测量来改变空间绑定的计算的能力。在有限的误差案例中，Fefferman和Remscrim [Stoc 2021，pp.1343---1356]和Girish，Raz和Zhan〜 [ICALP 2021，pp.73：1--73：20]最近提供了电源不变的突破性结果。本文表明，相似的结果适用于与空间结合的量子计算。也就是说，可以证明可以在有界校园设置的空间结合的量子计算中消除中间选择和测量。我们的结果加强了Le Gall，Nishimura和Yakaryilmaz〜 [TQC 2021，第10：1--10：17]，与中等的后选择性和测量值相机相对于空间限制的量子计算和测量在计算势力上是相等的计算能力，可与无限型 - 无限制计算计算。作为一种应用，可以表明，有界面空间的单量子量子量子计算（DQC1）在计算能力中等同于无界越界空间遇到的概率计算，并且在复杂的范围内遇到的界面空间隔离式DQC1的计算至上是复杂的。
Space-bounded computation has been a central topic in classical and quantum complexity theory. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343--1356] and Girish, Raz and Zhan~[ICALP 2021, pp.73:1--73:20] recently provided the break-through results that the power does not change. This paper shows that a similar result holds for space-bounded quantum computation with postselection. Namely, it is proved possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall, Nishimura and Yakaryilmaz~[TQC 2021, pp.10:1--10:17] that logarithmic-space bounded-error quantum computation with intermediate postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. As an application, it is shown that bounded-error space-bounded one-clean qubit computation (DQC1) with postselection is equivalent in computational power to unbounded-error space-bounded probabilistic computation, and the computational supremacy of the bounded-error space-bounded DQC1 is interpreted in complexity-theoretic terms.
