2 0 0 Foundations of quantum theory and 2 c e quantum information applications D 2 2 1 v 4 2 1 2 1 2 0 / h p - t n a Ernesto Fagundes Galv˜ao u q Wolfson College : v University of Oxford i X r a A thesis submitted for the degree of Doctor of Philosophy, University of Oxford Trinity Term 2002 Abstract Foundations of quantum theory and quantum information applications Thesis submitted for the Degree of Doctor of Philosophy. Ernesto Fagundes Galv˜ao Wolfson College, University of Oxford Trinity Term 2002 This thesis establishes a numberof connections between foundational issues in quan- tum theory, and some quantum information applications. It starts with a review of quantum contextuality and non-locality, multipartite entanglement characterisation, and of a few quantum information protocols. Quantum non-locality and contextuality are shown to be essential for different im- plementations of quantum information protocols known as quantum random access codes and quantum communication complexity protocols. The simplest versions of these protocols are shown to be equivalent to tests of two- and multi-party contex- tuality and non-locality. From them I derive sufficient experimental conditions for tests of these quantum properties. I also discusshow the distributionof quantum information throughquantum cloning processes can be useful in quantum computing. Regarding entanglement character- isation, some results are obtained relating two problems, that of additivity of the relative entropy of entanglement, and that of identifying different types of tripartite entanglement in the asymptotic regime of manipulations of many copies of a given state. The thesis ends with a description of an information processing task in which a single qubit substitutes for an arbitrarily large amount of classical communication. This result is interpreted in different ways: as a gap between quantum and classical computationspacecomplexity; asaboundontheamountofclassical communication necessary to simulate entanglement; andas abasic resulton hidden-variabletheories for quantum mechanics. In this case, the resource behind the quantum advantage is simply the real nature of the set of quantum pure states. I also show that the advantage of quantum over classical communication can be established in a feasible experiment. Acknowledgements My warmest thanks go to my supervisor Lucien Hardy, who managed to provide intellectual stimulation and guidance while giving me freedom to find my own way in research. His sharp insights and enthusiasm for quantum theory were a constant source of inspiration for my work. IamalsothankfultoArturEkertforhissupport,andforcreatingagreatresearchat- mosphereat the Centrefor QuantumComputation. Over fouryears at CQCI ended up meeting most people in the research community, and learned much in enjoyable conversations with many of them. A partial list includes Sougato Bose, Dagmar Bruß, Mark Bowdrey, Garry Bowen, Holly Cummins, Hilary Greaves, Patrick Hay- den, Leah Henderson, John Howell, Hitoshi Inamori, Daniel Jonathan, Antia Lamas Linares, Jan-˚AkeLarsson, P´erola Milman, Daniel Oi, Tony Short, Vlatko Vedraland Jon Walgate. Ihadthechancetodoresearchandpublishwithtwootherco-authors: MartinPlenio and Shashank Virmani. I am very thankful for their warm hospitality during many lunch times and afternoon discussions at Imperial College. I thank all of my friends, and specially Joana and Z´e for their love and support. A big ‘thank you’ to my family, whose love, support and encouragement made it possible for me to choose an academic career. I was supported financially by a scholarship from the Brazilian agency Coordenac¸˜ao de Aperfeic¸oamento de Pessoal de N´ıvel Superior (CAPES); by Universities UK through an Overseas Research Students Awards Scheme (ORS) award; and by Wolf- son College, which provided some funding for academic travel. Contents Abstract i Acknowledgements ii 1 Introduction 1 2 On the foundations of quantum theory 4 2.1 Why hidden-variable theories? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 A deterministic hidden-variable theory is possible . . . . . . . . . . . . . 5 2.2 Quantum contextuality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.1 Two simple contextuality proofs . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1.1 Peres’ contextuality proof . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1.2 Mermin’s contextuality proof . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Other results on contextuality . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.3 Making sense of contextuality . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Quantum non-locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.1 The Clauser-Horne-Shimony-Holt inequality . . . . . . . . . . . . . . . . 10 2.3.2 Non-locality without inequalities . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.2.1 A strange duel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.2.2 Hardy’s quantum non-locality proof . . . . . . . . . . . . . . . . 13 2.4 Hardy’s axioms for quantum theory . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5 The invariant information of Brukner and Zeilinger . . . . . . . . . . . . . . . . 16 2.5.1 Shannon and von Neumann entropies . . . . . . . . . . . . . . . . . . . . 17 2.5.2 Defining invariant quantum information . . . . . . . . . . . . . . . . . . . 18 3 Quantifying entanglement 21 3.1 Entangled versus separable states . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1.1 The Peres-Horodecki separability criterion . . . . . . . . . . . . . . . . . 22 3.2 Different approaches to quantifying entanglement . . . . . . . . . . . . . . . . . . 23 3.3 Single-copy approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.1 Multipartite entanglement . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 Asymptotic limit approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4.1 Asymptotic equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4.1.1 Mixed state entanglement . . . . . . . . . . . . . . . . . . . . . . 26 3.4.2 Minimal Reversible Entanglement Generating Sets (MREGS) . . . . . . . 26 3.5 Quantum relative entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.5.1 Classical relative entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.5.2 Relative entropy of entanglement . . . . . . . . . . . . . . . . . . . . . . 28 iii CONTENTS iv 4 Quantum information applications 29 4.1 Communication complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.1.1 Quantum communication complexity . . . . . . . . . . . . . . . . . . . . 30 4.2 Quantum random access codes (QRAC’s) . . . . . . . . . . . . . . . . . . . . . . 30 4.2.1 A simple 2 1 QRAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 → 4.2.1.1 Optimal classical protocol . . . . . . . . . . . . . . . . . . . . . . 31 4.2.1.2 Quantum protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 Quantum cloning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3.1 The no-cloning theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3.2 Quantum cloning machines . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.3.3 Universal quantum cloning machines . . . . . . . . . . . . . . . . . . . . 34 4.3.4 A curious fidelity balance result . . . . . . . . . . . . . . . . . . . . . . . 36 4.3.5 Probabilistic cloning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5 Tripartite entanglement and relative entropy 39 5.1 MREGS for multipartite entanglement . . . . . . . . . . . . . . . . . . . . . . . 40 5.2 Tripartite entanglement and relative entropy . . . . . . . . . . . . . . . . . . . . 41 5.2.1 Sub-additivity of E and tripartite MREGS . . . . . . . . . . . . . . . . . 42 5.3 Calculating the relative entropy of entanglement . . . . . . . . . . . . . . . . . . 43 5.4 Suspicious states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.4.1 Λ states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.4.2 W-type states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.4.3 Purifications of bound-entangled states . . . . . . . . . . . . . . . . . . . 46 5.5 Entanglement of W versus GHZ . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.6 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6 Cloning and quantum computation 49 6.1 Example with universal cloning . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.1.1 Score with cloning step . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.1.2 Score without cloning step . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.1.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.2 Example with probabilistic cloning . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.2.1 Score without cloning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2.2 Score using cloning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.3 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 7 On quantum random access codes 57 7.1 QRAC’s and contextuality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.2 QRAC’s and non-locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.3 Relations with other applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.4 QRAC’s and quantum communication complexity . . . . . . . . . . . . . . . . . 60 7.4.1 A simple two-party communication complexity task . . . . . . . . . . . . 60 7.4.2 Quantum protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 7.5 Invariant information and QRAC’s . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.5.1 Bounding the efficiency of simple QRAC’s . . . . . . . . . . . . . . . . . . 61 7.5.2 More general bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7.6 Experimental feasibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.6.1 Detection efficiency and noise rate . . . . . . . . . . . . . . . . . . . . . . 65 7.6.2 Feasibility of qubit communication protocol . . . . . . . . . . . . . . . . . 65 7.6.3 Feasibility of entanglement-based protocol . . . . . . . . . . . . . . . . . . 66 7.7 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 CONTENTS v 8 On multi-party quantum communication complexity 69 8.1 A multi-party communication complexity task . . . . . . . . . . . . . . . . . . . 70 8.1.1 Restraining the amount of communication . . . . . . . . . . . . . . . . . . 70 8.2 Determining the optimal classical protocols . . . . . . . . . . . . . . . . . . . . . 71 8.2.1 Sequential communication . . . . . . . . . . . . . . . . . . . . . . . . . . 71 8.2.2 Non-sequential communication . . . . . . . . . . . . . . . . . . . . . . . . 72 8.3 Quantum protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8.3.1 Entanglement-based quantum protocol . . . . . . . . . . . . . . . . . . . 73 8.3.1.1 Relation with multi-party non-locality and contextuality . . . . 74 8.3.2 Sequential qubit communication protocol . . . . . . . . . . . . . . . . . . 74 8.4 Experimental feasibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.4.1 Feasibility of entanglement-based protocol . . . . . . . . . . . . . . . . . . 75 8.4.2 Feasibility of qubit communication protocol . . . . . . . . . . . . . . . . 77 8.5 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 9 Encoding information in a single qubit 79 9.1 The task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 9.2 Two simple solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 9.2.1 A quantum protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 9.2.2 A classical protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 9.3 Necessity of unlimited amount of classical communication . . . . . . . . . . . . . 82 9.3.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 9.3.2 Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 9.4 Why is quantum better? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 9.5 A computational perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 9.5.1 Time- versus space-complexity . . . . . . . . . . . . . . . . . . . . . . . . 85 9.5.1.1 ROM-based computation . . . . . . . . . . . . . . . . . . . . . . 85 9.5.1.2 Task as a ROM-based computation . . . . . . . . . . . . . . . . 86 9.5.2 On the accuracy needed . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 9.5.3 Achieving the accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 9.5.4 Quantum versus analog computation . . . . . . . . . . . . . . . . . . . . . 88 9.6 Simulating entanglement with classical communication . . . . . . . . . . . . . . 89 9.6.1 Some results on entanglement simulation . . . . . . . . . . . . . . . . . . 90 9.6.2 Simulating our task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 9.7 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 10 Conclusion 92 Bibliography 95 List of Figures 4.1 Qubit states used in a 2 1 QRAC. . . . . . . . . . . . . . . . . . . . . . . . . . 32 → 6.1 Cloning and no-cloning approaches. . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.2 Quantum circuit to distinguish functions f . . . . . . . . . . . . . . . . . . . . . . 53 i 6.3 Probabilistic cloning in quantum computation. . . . . . . . . . . . . . . . . . . . 54 7.1 Encoding states for the qubit 3 1 QRAC. . . . . . . . . . . . . . . . . . . . . 62 → 7.2 Experimental conditions for a better-than-classical entanglement-based 2 1 → QRAC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8.1 Experimental conditions for a better-than-classical entanglement-based N-party quantum communication complexity protocol. . . . . . . . . . . . . . . . . . . . . 76 9.1 An information processing task. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 9.2 Solution to the task based on teleportation. . . . . . . . . . . . . . . . . . . . . . 89 vi Chapter 1 Introduction The conceptual revolution brought to science by quantum theory is now almost a century old. Despite this grand old age, it still seems that the theory’s full significance has not yet been appreciated outside a limited circle of physicists and philosophers of science. It is true that terms like ‘quantum leap’ and ‘uncertainty principle’ have been incorporated by everyday language. They are often used to convey concepts which are only remotely related to their physical meaning, but at least this shows that a wider public has taken note of some aspects of the interpretation of quantum mechanics. This timid acknowledgement, however, is completely overshadowed by the penetration of general relativity into mainstream culture, a theory of comparable age and importance. This acceptance of relativity’s ideas by the general public shows up in popular science mag- azines and newspapers. Terms like black holes and space-time are presented as the theoretical constructs they are, and not just as misinformed analogies, as usually happens with quantum theory. I think this can be attributed at least to two factors. First, quantum theory’s rupture with the previous theoretical paradigm was more radical than relativity’s. A non-scientist may not have a good understanding of what space-time and black holes are, but at least he or she can be comforted in the knowledge that professional physicists apparently do. This is definitely not the case with quantum theory, whose interpreta- tion has always been a motive for argument even among experts. This seems to arise from the overturning of concepts preserved even by relativity, such as locality and perhaps determinism. This is whyit seems quiteappropriateto groupthe other great physical theories and namethem ‘classical’ (relativity included), while quantum theory remains in a class of its own. Another factor which keeps the discussion of the foundations of quantum theory away from a wider audience is the lack of practical applications. Relativity also has few widespread appli- cations, butthis gap in publicperception seems to have been filled by astronomical observations and thought experiments involving spaceships and black holes, for example. In comparison, quantum theory’s applications seem much less convincing: the stability of matter and quantum tunnelling are two examples that come to my mind. Working applications of quantum theory’s most baffling characteristics are not yet part of day-to-day life. Inthelastfewyears, thenewfieldofquantuminformationhasbeenchangingthat. Practical quantum information applications are justaround the corner, with prototypes of quantum cryp- tographic setups and small-scale quantum computers already working in laboratories. These applications illustrate some of the counter-intuitive features of quantum theory in a particularly compellingway. Asignofthisistheincreasinguseoftheseapplicationsinintroductoryquantum mechanics courses. In a broader context, we see the public being engaged by the excitement of research in quantum physics, through television, general lectures and numerous popular science articles that have been appearing in the general press. By bringing the information-theoretic structure of quantum mechanics to the fore, these applications are very helpful to the researcher as well. Quantum information applications offer simple examples and proceduresthat illustrate important characteristics of quantum mechanics. As we will see in this thesis, these applications often suggest what is essential and what is accessory in quantumtheory, highlighting features which may beof practical useandtheoretical importance. 1 CHAPTER 1. INTRODUCTION 2 My research has been directed at examining these applications, and working out what they can tell us about foundational issues in quantum theory, such as contextuality and non-locality. Itappearsthattakingintoaccounttheroleofinformationinquantumtheorywillbeunavoidable for major further developments. This is hinted at by the existence of information-based results (such as black hole entropy) which will need to be accounted for by some future unification of gravity and quantum mechanics. Of course, a deeper theoretical understanding of the information-theoretic aspects of the theory should also lead to new or improved applications. Another research goal of mine is to turn the insights coming from the foundations of quantum theory into useful quantum informa- tion applications that can hopefully be implemented in the near future. Given the theoretical promises and thecurrentrate of experimental progress, quantum computingand other quantum technologies may assume a great economic importance in the next decades. Having stated two of my main research motivations, let me now give a preview of the work I have been doing along these lines in the last years, and which constitute this thesis. Chapters 2, 3 and 4 present introductory material respectively on the foundations of quantum theory, quantum entanglement, and a few quantum information applications. Most of theresultsherearedrawnfromtherecentliterature,butthechoiceoftopicsandthepresentation is made so as to prepare terrain for chapters 5 to 9. The original material in the introductory chapters includes an analogy used to present Hardy’s non-locality proof in section 2.3.2.1, and a curious fidelity balance result for cloning machines in section 4.3.4. In chapter 5 I investigate the characterisation of tripartite entanglement, which is a much harder mathematical problem than the bipartite case. This problem is important as multi- particle entanglement shows up in natural systems, as well as in quantum information protocols such as the one I discuss in chapter 8. This chapter results from collaboration with Martin Plenio and Shashank Virmani from Imperial College (London). The work I report is mostly my own, while in the publishedversion of these results [84] there are also analytical results obtained mostly thanks to my collaborators’ considerable mathematical skills. Section 5.5 results from numerical calculations performed in joint work with Leah Henderson from the University of Bristol. I also published a second paper on multipartite entanglement in joint work with Lucien Hardy [81], but as its results did not fit in naturally with the rest of this thesis, I decided not to include them here. Encoding information in quantum systems involves some counter-intuitive constraints. One of these is the no-cloning theorem, which states that it is impossible to make perfect copies of an arbitrary unknown quantum state. Non-perfect but good-quality copying is feasible, but the question is: what are these quantum cloning machines good for? In chapter 6 I show that quantum cloning can be used to distribute quantum information in an efficient manner during quantum computations. This chapter resulted from collaboration with my supervisor Lucien Hardy, having been published in [82]. In chapter 7 I turn to a quantum information application known as quantum random access codes. We will see that some simple versions of these codes had already cropped upunder different guises previously, without being noticed. I recognise the equivalence between these different protocols and show that their higher-than-classical performance derives from either quantum contextuality or non-locality. I also analyse the feasibility of implementing these codes experimentally, showingthatasuccessfulimplementation wouldbeequivalent toacontextuality or non-locality test. The quantum random access code using a qutrit in section 7.5.2 was found in joint work with Daniel Oi. In theory, quantum communication is better than classical communication for many tasks. However, given the difficulty of implementing quantum protocols experimentally, usually it is theclassical protocols thatoutperformthequantum versions inpractical setups. Inchapter 8I present solutions to a communication complexity problem which rely either on entanglement or on quantum communication. The analysis of this problem leads to sufficient conditions for test- ing multipartite non-locality and contextuality. Moreover, I show it is possible to demonstrate experimentally the advantage of quantumover classical communication in a feasibleexperiment. Some of these results appeared in preprint format [79], while others were published [80]. In chapter 9 I present a generalisation of the communication complexity problem discussed in chapter 8. I rigorously prove that a single qubit of quantum communication can be better CHAPTER 1. INTRODUCTION 3 than any finite number of classical bits for a particular task. The result lends itself to different interpretations. First, I show it means that entanglement is very hard to simulate with classical communication. I also demonstrate that quantum computers can have an unboundedadvantage in memory size with respect to classical computers. Interestingly, all these results can be shown to stem froma singleaxiom that distinguishes quantumtheory from classical probability theory. This chapter represents joint work with my supervisor, and some of it has appeared in preprint format [83]. Finally, in chapter 10 I offer some concluding remarks, and point at some open problems for further research. I hope the reader can recognise my two main research motivations in the treatment I give to the topics addressed in this thesis. In working on them I have acquired a more intuitive grasp of what quantum theory can offer for information processing, and why. Fortunately, the source of surprises seems to be endless.