Computation in generalised probabilisitic theories
Computation in generalised probabilisitic theories
复制标题
DOI：
10.1088/1367-2630/17/8/083001
复制
发表时间：
2015-08-03
影响因子：
3.3
通讯作者：
Barrett, Jonathan
中科院分区：
文献类型：
--
作者：
Lee, Ciaran M.;Barrett, Jonathan
从使用经典系统模拟量子系统的一般困难，特别是存在一个有效的量子算法的因式分解，很可能量子计算本质上比经典计算更强大。目前，已知量子计算能力的最佳上限是AWPP的BQP子集，其中AWPP是经典复杂度类（已知包含在PP中，因此是PSPACE）。这项工作调查的计算能力，是由简单的物理，或信息理论，原则的限制。为此，我们在一类比量子理论更一般的操作定义的理论中定义了一个基于电路的计算模型，并问：上述包含仍然成立的最小物理假设集是什么？我们表明，只给出一个假设的层析局部性（粗略地说，多体状态和变换的特点是当地的测量），有效的计算包含在AWPP。即使没有假设因果关系的基本概念，这种包容性仍然成立（其中的概念大致是，结果的概率不能取决于未来的测量选择）。在Aaronson之后，我们通过允许测量结果的后选择来扩展计算模型。Aaronson证明了相应的量子复杂性类PostBQP等于PP。仅假设层析局部性，PP中的包含仍然适用于一般理论中的后选择计算。因此，在一个具有后选择的世界中，量子理论是所有运算理论空间中计算的最佳选择。然后，我们考虑是否可以获得一般理论的相对复杂性结果。如何在简化为量子情形下的标准概念的一般框架中定义计算预言机的合理概念并不明显。然而，相对于“经典预言机”来定义计算是可能的。然后，我们证明存在一个经典的预言，相对于任何理论的有效计算满足因果关系假设不包括NP。
From the general difficulty of simulating quantum systems using classical systems, and in particular the existence of an efficient quantum algorithm for factoring, it is likely that quantum computation is intrinsically more powerful than classical computation. At present, the best upper bound known for the power of quantum computation is that BQP subset of AWPP, where AWPP is a classical complexity class (known to be included in PP, hence PSPACE). This work investigates limits on computational power that are imposed by simple physical, or information theoretic, principles. To this end, we define a circuit-based model of computation in a class of operationally-defined theories more general than quantum theory, and ask: what is the minimal set of physical assumptions under which the above inclusions still hold? We show that given only an assumption of tomographic locality (roughly, that multipartite states and transformations can be characterized by local measurements), efficient computations are contained in AWPP. This inclusion still holds even without assuming a basic notion of causality (where the notion is, roughly, that probabilities for outcomes cannot depend on future measurement choices). Following Aaronson, we extend the computational model by allowing post-selection on measurement outcomes. Aaronson showed that the corresponding quantum complexity class, PostBQP, is equal to PP. Given only the assumption of tomographic locality, the inclusion in PP still holds for post-selected computation in general theories. Hence in a world with post-selection, quantum theory is optimal for computation in the space of all operational theories. We then consider whether one can obtain relativized complexity results for general theories. It is not obvious how to define a sensible notion of a computational oracle in the general framework that reduces to the standard notion in the quantum case. Nevertheless, it is possible to define computation relative to a 'classical oracle'. Then, we show there exists a classical oracle relative to which efficient computation in any theory satisfying the causality assumption does not include NP.