Bounds on the power of proofs and advice in general physical theories.
Bounds on the power of proofs and advice in general physical theories.
复制标题
DOI：
10.1098/rspa.2016.0076
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Hoban MJ
中科院分区：
文献类型：
--
作者：
Lee CM;Hoban MJ
量子理论为我们提供了超越经典理论的计算和通信工具。揭示这些优势来源的一种方法是确定当量子理论被其他可操作定义的理论所取代时，计算和通信能力是如何变化的。这样的研究可能会揭示强大的计算和通信所需的一些关键物理特征。在本文中，我们研究了简单的物理原理如何约束两种不同的计算范式的能力，这两种范式以一种非平凡的方式结合了计算和通信：带通知的计算和交互式证明系统。我们证明了一个理论中非平凡动力学的存在意味着计算能力的一个界。此外，我们还提供了一个明确的例子，说明一个没有非平凡动力学的理论，其中具有通知的计算能力是无界的。最后，我们证明了简单交互证明系统在局部测量足以进行断层扫描的理论中的能力是非平凡有界的。这个结果提供了一个包含在的证明，它不使用任何独特的量子结构——比如可观测值对应于自伴随算子的事实——因此可能是独立的兴趣。
Quantum theory presents us with the tools for computational and communication advantages over classical theory. One approach to uncovering the source of these advantages is to determine how computation and communication power vary as quantum theory is replaced by other operationally defined theories from a broad framework of such theories. Such investigations may reveal some of the key physical features required for powerful computation and communication. In this paper, we investigate how simple physical principles bound the power of two different computational paradigms which combine computation and communication in a non-trivial fashion: computation with advice and interactive proof systems. We show that the existence of non-trivial dynamics in a theory implies a bound on the power of computation with advice. Moreover, we provide an explicit example of a theory with no non-trivial dynamics in which the power of computation with advice is unbounded. Finally, we show that the power of simple interactive proof systems in theories where local measurements suffice for tomography is non-trivially bounded. This result provides a proof that is contained in , which does not make use of any uniquely quantum structure—such as the fact that observables correspond to self-adjoint operators—and thus may be of independent interest.