Lee Ciarán M, Hoban Matty J
Department of Computer Science , University of Oxford , Wolfson Building, Parks Road, Oxford OX1 3QD, UK.
Proc Math Phys Eng Sci. 2016 Jun;472(2190):20160076. doi: 10.1098/rspa.2016.0076.
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 [Formula: see text] is contained in [Formula: see text], 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.
量子理论为我们提供了相较于经典理论在计算和通信方面具有优势的工具。揭示这些优势来源的一种方法是，从这样一个广泛的理论框架中，确定当量子理论被其他通过操作定义的理论取代时，计算和通信能力是如何变化的。此类研究可能会揭示强大的计算和通信所需的一些关键物理特征。在本文中，我们研究了简单的物理原理如何限制两种不同计算范式的能力，这两种范式以一种不平凡的方式将计算和通信结合起来：带建议的计算和交互式证明系统。我们表明，理论中存在非平凡动力学意味着对带建议的计算能力存在限制。此外，我们给出了一个不存在非平凡动力学的理论的明确示例，其中带建议的计算能力是无界的。最后，我们表明，在局部测量足以进行层析成像的理论中，简单交互式证明系统的能力受到非平凡的限制。这一结果证明了[公式：见原文]包含于[公式：见原文]，且未利用任何独特的量子结构，比如可观测量对应自伴算子这一事实，因此可能具有独立的研究价值。
