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.
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.
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.
Grover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all possible classical search algorithms. Quantum interference between computational paths has been posited as a key resource behind this computational speed-up. However there is a limit to this interference, at most pairs of paths can ever interact in a fundamental way. Could more interference imply more computational power? Sorkin has defined a hierarchy of possible interference behaviours—currently under experimental investigation—where classical theory is at the first level of the hierarchy and quantum theory belongs to the second. Informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In this work, we consider how Grover's speed-up depends on the order of interference in a theory. Surprisingly, we show that the quadratic lower bound holds regardless of the order of interference. Thus, at least from the point of view of the search problem, post-quantum interference does not imply a computational speed-up over quantum theory.
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 .
Grover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all possible classical search algorithms. Quantum interference between computational paths has been posited as a key resource behind this computational speed-up. However there is a limit to this interference, at most pairs of paths can ever interact in a fundamental way. Could more interference imply more computational power? Sorkin has defined a hierarchy of possible interference behaviours---currently under experimental investigation---where classical theory is at the first level of the hierarchy and quantum theory belongs to the second. Informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In this work, we consider how Grover's speed-up depends on the order of interference in a theory. Surprisingly, we show that the quadratic lower bound holds regardless of the order of interference. Thus, at least from the point of view of the search problem, post-quantum interference does not imply a computational speed-up over quantum theory.
The advent of quantum computing has challenged classical conceptions of which problems are efficiently solvable in our physical world. This motivates the general study of how physical principles bound computational power. In this paper we show that some of the essential machinery of quantum computation—namely reversible controlled transformations and the phase kick-back mechanism—exist in any operational-defined theory with a consistent notion of information. These results provide the tools for an exploration of the physics underpinning the structure of computational algorithms. We investigate the relationship between interference behaviour and computational power, demonstrating that non-trivial interference behaviour is a general resource for post-classical computation. In proving the above, we connect higher-order interference to the existence of post-quantum particle types, potentially providing a novel experimental test for higher-order interference. Finally, we conjecture that theories with post-quantum interference—the higher-order interference of Sorkin—can solve problems intractable even on a quantum computer.
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.