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.
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.
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.
Phase lies at the heart of quantum physics and quantum information theory. A quantum bit is qualitatively different from a classical bit as it allows for the coherent superposition of possibilities, which demonstrate different behaviours depending on the phase between them. These behaviours constitute as interference phenomena, and lie behind the existence of algorithms in quantum computing which are arguably faster than the best classical alternatives. The concept of phase is deeply steeped in the structure of Hilbert spaces: the mathematical framework that underlies quantum theory. What if quantum theory did not hold in all scenarios, or was only a limiting case of some broader theory? In this case, would we still be able to meaningfully talk about phase and interference? In this thesis, we will adopt an operational generalisation of quantum theory known as the framework of generalised probabilistic theories. We will provide a reasonable definition of phase in this framework. Using this, we shall explore single-particle interferometry set-ups (particularly Mach-Zehnder interferometers): experiments whose output is highly dependent on the phase between the spatially disjoint branches through which a particle might be traversing. By applying physically-motivated locality considerations, we identify the crucial role that the uncertainty principle and its generalisations play in quantum theory as an enabler of non-trivial interference. By taking into account relativity of simultaneity, we will also provide a physical motivation for why standard quantum theory provides the best description of the location of a particle traversing such a system. Finally, we apply our generalised definition of phase in the related context of particle exchange behaviour, and identify a method for classifying post-quantum particles. All of this will demonstrate that phase between possibilities and its consequences are not uniquely quantum phenomena. Much of the behaviour we might ascribe to phase in quantum theory in fact holds generally true for phase in probabilistic theories.
In our previous work, we defined a quantum algorithmic technique known as the Generalised Phase Kick-Back, or GPK, and analysed its applications in generalising some classical quantum problems, such as the Deutsch-Jozsa problem or the Bernstein-Vazirani problem. We also proved that using this technique we can solve Simon's problem in a more efficient manner. In this paper we continue analysing the potential of this technique, defining the concept of y-balanced functions and solving a new problem, which further generalises the generalised Deutsch-Jozsa problem (the fully balanced image problem). This problem also underlines the relation between quantum computation and Boolean function theory, and, in particular, the Walsh and Fourier-Hadamard transforms. We finish our discussion by solving the generalised version of Simon's problem using the GPK algorithm, while analysing the efficiency of this new solution.
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 .
Abstract In this paper, we present a generalisation of the Phase Kick-Back technique, which is central to some of the classical algorithms in quantum computing. We will begin by recalling the Phase Kick-Back technique to then introduce the new generalised version for f:{0,1}n→{0,1}m f : { 0 , 1 } n → { 0 , 1 } m functions using the eigenvalues of the oracle function Uf U f . After that, we will present a new generalised version of the Deutsch–Jozsa problem and how it can be solved using the previously defined technique. We will also deal with a generalised version of the Bernstein–Vazirani problem and solve it using the generalised Phase Kick-Back. Finally, we show how we can use this technique to obtain an algorithm for Simon’s problem that improves the classical one.
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.