This dissertation explores some diferences between quantum mechanics and other theories from a computational perspective, in particular with respect to the kind of correlations they allow, and their computational consequences. It starts with an operational characterization of locality, no-signaling and noncontextuality. Then it proceeds to an introduction to measurement-based quantum computation, a model in which quantum correlations are used to perform computation. Such a model is then generalized in a framework, proposed by Anders and Browne [1] and studied by Raussendorf [2], that aims to make the computational power of correlations more evident. We proceed to see that noncontextual resources do not provide a computational enhancement and that quantum resources do provide it even without adaptivity. We continue by reviewing a scheme for reliable computation using faulty components, rst proposed by von Neumann and later studied by Hajek and Weller [3] and Evans and Schulman [4]. This scheme is then used to show how a range of bipartite quantum correlations su ce for reliable computation. We conclude by showing that quantum correlations that violate non-contextuality bounds by an arbitrarily small amount can be used to enable reliable computation
This dissertation explores some diferences between quantum mechanics and other theories from a computational perspective, in particular with respect to the kind of correlations they allow, and their computational consequences. It starts with an operational characterization of locality, no-signaling and noncontextuality. Then it proceeds to an introduction to measurement-based quantum computation, a model in which quantum correlations are used to perform computation. Such a model is then generalized in a framework, proposed by Anders and Browne [1] and studied by Raussendorf [2], that aims to make the computational power of correlations more evident. We proceed to see that noncontextual resources do not provide a computational enhancement and that quantum resources do provide it even without adaptivity. We continue by reviewing a scheme for reliable computation using faulty components, rst proposed by von Neumann and later studied by Hajek and Weller [3] and Evans and Schulman [4]. This scheme is then used to show how a range of bipartite quantum correlations su ce for reliable computation. We conclude by showing that quantum correlations that violate non-contextuality bounds by an arbitrarily small amount can be used to enable reliable computation
Measurement-based quantum computation (or the one-way quantum computation) is a model in which a series of adaptive single qubit measurements upon an entangled resource state can produce classical output data equivalent to an arbitrary quantum logic circuit. Loosely speaking, the correlations in these measurements can be considered the resource which allows the computation to be performed. Bell inequalities demonstrate that quantum mechanics permits the outcomes of sets of measurements to be correlated in ways incompatible with the predictions of any local hidden variable theory, including classical physics. In the Bell inequality, and multi-party generalisations, a set of single-qubit measurements are performed, on spatially separated systems. Correlations in these measurements can act as a signature that no local hidden variable description of the experiment is possible. At first sight, we see superficial similarities between these settings. In both cases, non-classical correlations play a central role. However, there are also some key differences. Most importantly, measurement-based quantum computing requires adaptive measurements, at odds with the spatial-separated nature of Bell inequality experiments. Nevertheless some striking connections have been reported [1], [2] particularly between GHZ-type paradoxes and deterministic MBQC computations, and between CHSH-type Bell inequalities and non-deterministic MBQC correlations [1], [3]. In my talk I will survey these works and some recent results [3], [4] from my group at UCL, in which a number of connections between multi-party Bell inequalities and MBQC are explored. [1] J. Anders and D.E. Browne, "The Computational Power of Correlations", Physical Review Letters 102, 050502 (2009) [2] R. Raussendorf, "Quantum computation, discreteness, and contextuality", arxiv:0907.5449 [3] M. J. Hoban, E.T. Campbell, K. Loukopolous, D.E. Browne, "Non-adaptive measurement-based quantum computation and multi-party Bell inequalties", in preparation. [4] M. J. Hoban and D.E. Browne, in preparation.
Physics has two main ambitions: to predict and to understand. Indeed, physics aims for the prediction of all natural phenomena. Prediction entails modeling the correlation between an action, the input, and what is subsequently observed, the output.Understanding, on the other hand, involves developing insightful principles and models that can explain the widest possible varietyof correlations present in nature. Remarkably, advances in both prediction and understanding foster our physical intuition and, as a consequence, novel and powerful applications are discovered. Quantum mechanics is a very successful physical theory both in terms of its predictive power as well as in its wide applicability. Nonetheless and despite many decades of development, we do not yet have a proper physical intuition of quantum phenomena. I believe that improvements in our understanding of quantum theory will yield better, and more innovative, protocols and vice versa.This dissertation aims at advancing our understanding and developing novel protocols. This is done through four approaches. The first one is to study quantum theory within a broad family of theories. In particular, we study quantum theory within the family of locally quantum theories. We found out that the principle that singles out quantum theory out of this family, thus connecting quantum local and nonlocal structure, is dynamical reversibility. This implies that the viability of large scale quantum computing can be based on concrete physical principles that can be experimentally tested at a local level without needing to test millions of qubits simultaneously. The second approach is to study quantum correlations from a black box perspective thus making as few assumptions as possible. The strategy is to study the completeness of quantum predictions by benchmarking them against alternative models. Three main results and applications come out of our study. Firstly, we prove that performing complete amplification of randomness starting from a source of arbitrarily weak randomness - a task that is impossible with classical resources - is indeed possible via nonlocality. This establishes in our opinion the strongest evidence for a truly random event in nature so far. Secondly, we prove that there exist finite events where quantum theory gives predictions as complete as any no-signaling theory can give, showing that the completeness of quantum theory is not an asymptotic property. Finally, we prove that maximally nonlocal theories can never be maximally random while quantum theory can, showing a trade-off between the nonlocality of a theory and its randomness capabilities. We also prove that quantum theory is not unique in this respect. The third approach we follow is to study quantum correlations in scenarios where some parties have a restriction on the available quantum degrees of freedom. The future progress of semi-device-independent quantum information depends crucially on our ability to bound the strength of these correlations. Here we provide a full characterization via a complete hierarchy of sets that approximate the target set from the outside. Each set can be in turn characterized using standard numerical techniques. One application of our work is certifying multidimensional entanglement device-independently.The fourth approach is to confront quantum theory with computer science principles. In particular, we establish two interesting implications for quantum theory results of raising the Church-Turing thesis to the level of postulate. Firstly, we show how different preparations of the same mixed state, indistinguishable according to the quantum postulates, become distinguishable when prepared computably. Secondly, we identify a new loophole for Bell-like experiments: if some parties in a Bell-like experiment use private pseudorandomness to choose their measurement inputs, the computational resources of an eavesdropper have to be limited to observe a proper violation of non locality.
Quantum mechanics is nonlocal, meaning it cannot be described by any classical local hidden variable model. In this thesis we study two aspects of quantum nonlocality. Part I addresses the question of what classical resources are required to simulate nonlocal quantum correlations. We start by constructing new local models for noisy entangled quantum states. These constructions exploit the connection between nonlocality and Grothendieck's inequality, first noticed by Tsirelson. Next, we consider local models augmented by a limited amount of classical communication. After generalizing Bell inequalities to this setting, we show that (i) one bit of communication is sufficient to simulate the correlations of projective measurements on a maximally entangled state of two qubits, and (ii) five bits of communication are sufficient to simulate the joint correlation of two-outcome measurements on any bipartite quantum state. The latter result can be interpreted as a stronger (constrained) version of Grothendieck's inequality. In part II, we investigate the monogamy of nonlocal correlations. In a setting where three parties, A, B, and C, share an entangled quantum state of arbitrary dimension, we: (i) bound the trade-off between AB's and AC's violation of the CHSH inequality, obtaining an intriguing generalization of Tsirelson's bound, and (ii) demonstrate that forcing B and C to be classically correlated prevents A and B from violating certain Bell inequalities. We study not only correlations that arise within quantum theory, but also arbitrary correlations that do not allow signaling between separate groups of parties. These results are based on new techniques for obtaining Tsirelson bounds, or bounds on the quantum value of a Bell inequality, and have applications to interactive proof systems and cryptography.
It is well known that measurements performed on spatially separated entangled quantum systems can give rise to correlations that are nonlocal, in the sense that a Bell inequality is violated. They cannot, however, be used for superluminal signaling. It is also known that it is possible to write down sets of ``superquantum'' correlations that are more nonlocal than is allowed by quantum mechanics, yet are still nonsignaling. Viewed as an information-theoretic resource, superquantum correlations are very powerful at reducing the amount of communication needed for distributed computational tasks. An intriguing question is why quantum mechanics does not allow these more powerful correlations. We aim to shed light on the range of quantum possibilities by placing them within a wider context. With this in mind, we investigate the set of correlations that are constrained only by the no-signaling principle. These correlations form a polytope, which contains the quantum correlations as a (proper) subset. We determine the vertices of the no-signaling polytope in the case that two observers each choose from two possible measurements with d outcomes. We then consider how interconversions between different sorts of correlations may be achieved. Finally, we consider some multipartite examples.
** The primary topic of this dissertation is the study of the relationships between parts and wholes as described by particular physical theories, namely generalized probability theories in a quasi-classical physics framework and non-relativistic quantum theory. ** A large part of this dissertation is devoted to understanding different aspects of four different kinds of correlations: local, partially-local, no-signaling and quantum mechanical correlations. Novel characteristics of these correlations have been used to study how they are related and how they can be discerned via Bell-type inequalities that give non-trivial bounds on the strength of the correlations. ** The study of quantum correlations has also prompted us to study a) the multi-partite qubit state space with respect to its entanglement and separability characteristics, and b) the differing strength of the correlations in separable and entangled qubit states. Results include a novel classification of multipartite (partial) separability and entanglement, strong constraints on the monogamy of entanglement and of non-local correlations, and many new entanglement detection criteria that are directly experimentally accessible. ** Because of the generality of the investigation these results also have strong foundational as well as philosophical repercussions for the different sorts of physical theories as a whole; notably for the viability of hidden variable theories for quantum mechanics, for the possibility of doing experimental metaphysics, for the question of holism in physical theories, and for the classical vs. quantum dichotomy.
Since Bell, Kochen and Specker formulated the first notions of contextuality, a number of frameworks have been created to help make philosophical and mathematical sense of the concept. Two of the most common are the Equivalence-based approach due to Spekkens, and the Sheaf-theoretic framework of Abramsky and Brandenburger. Each of these can support a hierarchy of strengths of contextuality, which can include possibilistic concepts. This thesis will explore the differences between the two approaches, and explore what can be demonstrated by using weaker notions of noncontextuality. Notions of noncontextuality are important for proving no-go theorems which highlight that many properties that are true of classical mechanics fail to be compatible with quantum predictions. Often, the notions of noncontextuality used are very strong assumptions, and even weaker flavours of noncontextuality can be used to draw the same, or similar conclusions. An important class of such notions are, possibilistic assumptions that only care about whether or not events are possible or impossible, rather than the exact Born rule probabilities that are applied to events. Even these weaker notions are often impossible to resolve with the logical structure and predictions of quantum theory. Contextuality has been demonstrated to be a resource for many quantum computational operations, and the contextual fraction has been shown to be an important resource. We introduce a metric that can differentiate between different quantum mechanical scenarios with contextual fraction 1, and demonstrate analogues of CHSH and Tsirelson bounds for this quantity. We also investigate the computational complexity of calculating the values of some metrics for nonlocality and contextuality, completing the classification of possibilistic nonlocality scenarios, as well as other metrics of nonlocality analogous to our metric of maximal contextuality.