The computational landscape of general physical theories
The computational landscape of general physical theories
复制标题
一般物理理论的计算景观
DOI：
--
复制
发表时间：
2017
影响因子：
7.6
通讯作者：
Ciarán M. Lee
中科院分区：
文献类型：
--
作者：
J. Barrett;N. de Beaudrap;M. Hoban;Ciarán M. Lee
有很好的证据表明，量子计算机比经典计算机更强大，而且对量子理论的各种简单修改产生的计算能力更大。然而，这些修改也违反了基本的物理原理。这就提出了一个问题，即是否存在一种物理理论，允许计算比量子更强大，但仍然尊重这些基本的物理原理。我们以前的工作在一个合适的理论框架内引入了这个问题，这些理论具有良好的操作意义，并表明在任何满足层析局部性的理论中，能够有效解决的问题类包含在复杂性类AWPP中。这里，我们证明了这个界是紧的，因为存在一个满足层析局部性的理论，以及一个基本的因果关系原理，它可以有效地决定AWPP中的一切。因此，该理论可以有效地模拟包括量子计算在内的任何计算。
There is good evidence that quantum computers are more powerful than classical computers, and that various simple modifications of quantum theory yield computational power that is dramatically greater still. However, these modifications also violate fundamental physical principles. This raises the question of whether there exists a physical theory, allowing computation more powerful than quantum, but which still respects those fundamental physical principles. Prior work by two of us introduced this question within a suitable framework for theories that make good operational sense, and showed that in any theory satisfying tomographic locality, the class of problems that can be solved efficiently is contained in the complexity class AWPP. Here, we show that this bound is tight, in the sense that there exists a theory, satisfying tomographic locality, as well as a basic principle of causality, which can efficiently decide everything in AWPP. Hence this theory can efficiently simulate any computation in this framework, including quantum computation.
一般物理理论中证明和建议的力量的界限
DOI：
10.48550/arxiv.1510.04702
发表时间：
2015
期刊：
--
影响因子：
--
作者：
Lee C
通讯作者：
Lee C
影响因子：
3.3
作者：
Lee, Ciaran M.;Barrett, Jonathan
通讯作者：
Barrett, Jonathan