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 , where is a classical complexity class (known to be included in , hence ). 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 . 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, , is equal to . Given only the assumption of tomographic locality, the inclusion in 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 .
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 , where is a classical complexity class (known to be included in , hence ). 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 . 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, , is equal to . Given only the assumption of tomographic locality, the inclusion in 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 .
From the general difficulty of simulating quantum systems using classical systems, and in particular \nthe existence of an efficient quantum algorithm for factoring, it is likely that quantum computation is \nintrinsically more powerful than classical computation. At present, the best upper bound known for \nthe power of quantum computation is that BQP AWPP ⊆ , where AWPP is a classical complexity \nclass (known to be included in PP, hence PSPACE). This work investigates limits on computational \npower that are imposed by simple physical, or information theoretic, principles. To this end, we define \na circuit-based model of computation in a class of operationally-defined theories more general than \nquantum theory, and ask: what is the minimal set of physical assumptions under which the above \ninclusions still hold? We show that given only an assumption of tomographic locality (roughly, that \nmultipartite states and transformations can be characterized by local measurements), efficient \ncomputations are contained in AWPP. This inclusion still holds even without assuming a basic notion \nof causality (where the notion is, roughly, that probabilities for outcomes cannot depend on future \nmeasurement choices). Following Aaronson, we extend the computational model by allowing postselection \non measurement outcomes. Aaronson showed that the corresponding quantum complexity \nclass, PostBQP, is equal to PP. Given only the assumption of tomographic locality, the inclusion in \nPP still holds for post-selected computation in general theories. Hence in a world with post-selection, \nquantum theory is optimal for computation in the space of all operational theories. We then consider \nwhether one can obtain relativized complexity results for general theories. It is not obvious how to \ndefine a sensible notion of a computational oracle in the general framework that reduces to the \nstandard notion in the quantum case. Nevertheless, it is possible to define computation relative to a \n‘classical oracle’. Then, we show there exists a classical oracle relative to which efficient computation in \nany theory satisfying the causality assumption does not include NP.
The advent of quantum computing has challenged classical conceptions of which problems are efficiently solvable in our physical world. This raises the general question of what broad relationships exist between physical principles and computation. The current thesis explores this question within the operationally-defined framework of generalised probabilistic theories. In particular, we investigate the limits on computational power imposed by simple physical principles. At present, the best known upper bound on the power of quantum computers is that BQP is contained in AWPP, where AWPP is a classical complexity class contained in PP. We define a circuit-based model of computation in the above mentioned operational framework and show that in theories where local measurements suffice for tomography, efficient computations are also contained in AWPP. Moreover, we explicitly construct a theory in which the class of efficiently solvable problems exactly equals AWPP, showing this containment to be tight. We also investigate how simple physical principles bound the power of computational paradigms which combine computation and communication in a non-trivial fashion, such as interactive proof systems. Additionally, we show how some of the essential components of computational algorithms arise from certain natural physical principles. We use these results to investigate the relationship between interference behaviour and computational power, demonstrating that non-trivial interference behaviour is a general resource for post-classical computation. We then investigate whether post-quantum interference is a resource for post-quantum computation. Sorkin has defined a hierarchy of possible post-quantum interference behaviours where, informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In quantum theory, at most pairs of paths can ever interact in a fundamental way. We consider how Grover's speed-up depends on the order of interference in a theory, and show that, surprisingly, the quadratic lower bound holds regardless of the order of interference.
Abstract 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.
We investigate the connection between interference and computational power within the operationally defined framework of generalised probabilistic theories. To compare the computational abilities of different theories within this framework we show that any theory satisfying four natural physical principles possess a well-defined oracle model. Indeed, we prove a subroutine theorem for oracles in such theories which is a necessary condition for the oracle model to be well-defined. The four principles are: causality (roughly, no signalling from the future), purification (each mixed state arises as the marginal of a pure state of a larger system), strong symmetry (existence of a rich set of nontrivial reversible transformations), and informationally consistent composition (roughly: the information capacity of a composite system is the sum of the capacities of its constituent subsystems). Sorkin has defined a hierarchy of conceivable interference behaviours, where the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. Given our oracle model, we show that if a classical computer requires at least n queries to solve a learning problem, because fewer queries provide no information about the solution, then the corresponding “no-information” lower bound in theories lying at the kth level of Sorkin’s hierarchy is ⌈n/k⌉ . This lower bound leaves open the possibility that quantum oracles are less powerful than general probabilistic oracles, although it is not known whether the lower bound is achievable in general. Hence searches for higher-order interference are not only foundationally motivated, but constitute a search for a computational resource that might have power beyond that offered by quantum computation.
Abstract The computational abilities of theories within the generalised probabilistic theory framework has been the subject of much recent study. Such investigations aim to gain an understanding of the possible connections between physical principles and computation. Moreover, comparing and contrasting the computational properties of quantum theory with other operationally-sensible theories could shed light on the strengths and limitations of quantum computation. This paper reviews and extends some of these results, deriving new bounds on the computational ability of theories satisfying n-local tomography, and theories in which states are represented as generalised superpositions. It moreover provides a refined version of the conjecture that a quantum computer can simulate the computation in any theory within a certain sub-class of generalised probabilistic theories with at most polynomial overhead. The paper ends by describing an important relation between this conjecture and delegated computation, similar to the relation between quantum non-locality and device-independent cryptography.
We consider restricted versions of postBQP where postselection probabilities can be efficiently calculated by classical or quantum computers. We show that such restricted postBQP classes are in AWPP(⊆PP=postBQP). This result suggests that postselecting an event with an exponentially small probability does not necessarily boost BQP to PP. The best upperbound of BQP is AWPP, and therefore restricted postBQP classes are other examples of complexity classes slightly above BQP. In [C. M. Lee and J. Barrett, arXiv:1412.8671], it was shown that the computational capacity of a general probabilistic theory which satisfies the tomographic locality is in AWPP. Our result therefore implies that quantum physics with restricted postselections is an example of a super quantum theory which seems to be outside of their general probabilistic theory but its computational capacity is also in AWPP. Although it is physically natural to expect that such restricted postBQP classes are not equivalent to BQP, we show that UP∩coUP, which is unlikely to be in BQP, is contained in the restricted postBQP classes. Finally, we also consider another restricted class of postBQP, where the postselected probability depends only on the size of inputs. We show that this restricted version is contained in APP, where AWPP⊆APP⊆PP=postBQP.