Computation in generalised probabilistic theories

Understand

From 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 is in AWPP.
• This work investigates limits on computational power that are imposed by physical 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 inclusion still holds? We show that given only an assumption of tomographic locality (roughly, that multipartite states can be characterised by local measurements), efficient computations are contained in AWPP.