The computational landscape of general physical theories

Barrett, Jonathan; de Beaudrap, Niel; Hoban, Matty J. and Lee, Ciarán M.. 2019. The computational landscape of general physical theories. npj Quantum Information, 5(41), [Article]

s41534-019-0156-9.pdf - Published Version
Available under License Creative Commons Attribution.

Download (891kB) | Preview

Abstract or Description

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.

Item Type:


Identification Number (DOI):

Additional Information:

We acknowledge support from the EPSRC National Quantum Technology Hub in Networked Quantum Information Technologies, an FQXi Large Grant and the Wiener-Anspach Foundation. This project and publication were made possible through the support of a grant from the John Templeton Foundation.


quantum computers, quantum theory, AWPP

Departments, Centres and Research Units:



23 April 2019Accepted
20 May 2019Published

Item ID:


Date Deposited:

24 Sep 2019 08:07

Last Modified:

11 Jun 2021 01:22

Peer Reviewed:

Yes, this version has been peer-reviewed.


View statistics for this item...

Edit Record Edit Record (login required)