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]

Preview

Text 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:	Article
Identification Number (DOI):	https://doi.org/10.1038/s41534-019-0156-9
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.
Keywords:	quantum computers, quantum theory, AWPP
Departments, Centres and Research Units:	Computing
Dates:	Date Event 23 April 2019 Accepted 20 May 2019 Published
Item ID:	27000
Date Deposited:	24 Sep 2019 08:07
Last Modified:	11 Jun 2021 01:22
Peer Reviewed:	Yes, this version has been peer-reviewed.
URI:	https://research.gold.ac.uk/id/eprint/27000

View statistics for this item...

Edit Record (login required)