Applications of coherent classical communication and the Schur transform to quantum information theory by Aram Wettroth Harrow 5 B.S., Massachusetts Institute of Technology (2001) 0 0 Submitted to the Department of Physics 2 in partial fulfillment of the requirements for the degree of c e D Doctor of Philosophy in Physics 0 at the 3 MASSACHUSETTS INSTITUTE OF TECHNOLOGY 1 v September 2005 5 5 c Aram Wettroth Harrow, MMV. All rights reserved. 2 (cid:13) 2 1 The author hereby grants to MIT permission to reproduce and distribute publicly 5 paper and electronic copies of this thesis document in whole or in part. 0 / h p - t n a Author............................................................................. u Department of Physics q : August 4, 2005 v i X r a Certified by......................................................................... Isaac L. Chuang Associate Professor of Electrical Engineering and Computer Science, and Physics Thesis Supervisor Accepted by........................................................................ Thomas J. Greytak Professor of Physics 2 Applications of coherent classical communication and the Schur transform to quantum information theory by Aram Wettroth Harrow Submitted to the Department of Physics on August 4, 2005, in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Physics Abstract Quantum mechanics has led not only to new physical theories, but also a new understanding of information and computation. Quantum information not only yields new methods for achieving classicaltaskssuchasfactoringandkeydistributionbutalsosuggestsacompletelynewsetofquantum problems, such as sending quantum information over quantum channels or efficiently performing particular basis changes on a quantum computer. This thesis contributes two new, purely quantum, tools to quantum information theory—coherent classical communication in the first half and an efficient quantum circuit for the Schur transform in the second half. The first partofthis thesis (Chapters 1-4)is in fact built aroundtwo looselyoverlappingthemes. One is quantum Shannon theory, a broad class of coding theorems that includes Shannon and Schu- macher data compression, channel coding, entanglement distillation and many others. The second, more specific, theme is the concept of using unitary quantum interactions to communicate between two parties. We begin by presenting new formalism: a general framework for Shannon theory that describes communication tasks in terms of fundamental information processing resources, such as entanglement and classical communication. Then we discuss communication with unitary gates and introduce the concept of coherent classical communication, in which classical messages are sent via some nearly unitary process. We find that coherent classical communication can be used to derive several new quantum protocols and unify them both conceptually and operationally with old ones. Finally,weusethesenewprotocolstoproveoptimaltrade-offcurvesforawidevarietyofcodingprob- lems in which a noisy channel or state is consumed and two noiseless resources are either consumed or generated at some rate. Thesecondhalfofthethesis(Chapters5-8)isbasedontheSchurtransform,whichmapsbetween the computational basis of (Cd) n and a basis (known as the Schur basis) which simultaneously ⊗ diagonalizesthe commuting actionsofthe symmetric group andthe unitarygroup . The Schur n d S U transform is used as a subroutine in many quantum communication protocols (which we review and further develop), but previously no polynomial-time quantum circuit for the Schur transform was known. Wegivesuchapolynomial-timequantumcircuitbasedontheClebsch-Gordantransformand then give algorithmic connections between the Schur transform and the quantum Fourier transform on . n S Thesis Supervisor: Isaac L. Chuang Title: Associate Professor of Electrical Engineering and Computer Science, and Physics 3 4 5 Acknowledgments Very little of the work in this thesis, or indeed that I have done throughout my time in grad school, would have been possible without the support of countless colleagues, collaborators, advisors and friends. IfirstwanttothankIkeChuangforguidingmeinquantuminformationfromevenbeforeIentered grad school and for doing such a good job of alternatingly pushing me, supporting me and turning me loose, always with an eye towardmy growthas a scientist. I am also indebted to Eddie Farhi for his encouragement and for innumerable discussions, as well as for teaching me quantum mechanics in the first place. Thanks to Peter Shor for, among other things, sharing so many of his unpublished ideas with me, including a crucial improvement to remote state preparation in the summer of 2001 that led to my first researchresult in grad school. I am deeply grateful to Charlie Bennett and Debbie Leung for being wonderful collaborators, mentors and friends throughout my time in grad school. In fact, I’m indebted to the group at IBM Yorktown for most of my research direction, and I would to thank Nabil Amer, Guido Burkard, Igor Devetak, David DiVincenzo, Roberto Oliveira, Barbara Terhal and especially John Smolin for everything I learned from working with them. I am have been fortunate to have so many productive travel opportunities. Thanks to Michael NielsenforinvitingmetotheU.ofQueensland,whereIenjoyedgreatdiscussionswithMickBremner, ChrisDawson,JenDodd,HenryHaselgroveandmanyotherresearchers. ThanksalsotoJohnPreskill at Caltech, Keiji Matsumoto at ERATO and Noah Linden at the Newton Institute for making these trips possible for me. MostofmyworkingradschoolhasbeencollaborativeandIamgratefultomymanycollaborators for teaching me, sharing their ideas with me and helping me improve my own ideas. In particular, theworkinthisthesiswasdoneincollaborationwithDaveBacon,CharlieBennett,IkeChuang,Igor Devetak, Debbie Leung, John Smolin and Andreas Winter. I have also had valuable collaborations with Ken Brown, Patrick Hayden, Seth Lloyd, Hoi-Kwong Lo, Michael Nielsen (and many others at UQ), Roberto Oliveira, Ben Recht and Barbara Terhal. Besides the colleagues I have mentioned so far, I want to thank Herb Bernstein, Carl Caves, AndrewChilds,MatthiasChristandl,AndrewCross,ChrisFuchs,MasahitoHayashi,DenesPetzand Krysta Svore for many valuable discussions. Thanks to Nolan Wallach for crucial discussions on the Schur transform and in particular for the idea behind Section 8.2. MostofmyworkingradschoolwasfundedbyaQuaCGRgrant(AROcontractDAAD19-01-1-06) for which I am grateful to Henry Everitt, Mark Heiligman, the NSA and ARDA. Thisthesisisdedicatedtomyparentsandtomyteachers: inparticular,toMikeMasterson,Mrs. Thomas, Mr. Steidle, Will Repko, Susan Schuur and Gian-Carlo Rota. 6 Contents 0 Introduction 11 0.1 Motivation and context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 0.2 Summary of results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1 Quantum Shannon theory 19 1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.1.1 Variations on formalism of quantum mechanics . . . . . . . . . . . . . . . . . . 21 1.1.2 Quantities, norms, inequalities, and miscellaneous notation . . . . . . . . . . . 24 1.2 Information processing resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.2.1 The distant labs paradigm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.2.2 Finite resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.2.3 Asymptotic resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1.3 General resource inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 1.4 Known coding theorems expressed as resource inequalities . . . . . . . . . . . . . . . . 44 1.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2 Communication using unitary interactions 53 2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.1.1 Survey of related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.1.2 Schmidt decompositions of states and operators . . . . . . . . . . . . . . . . . . 54 2.2 Entanglement capacity of unitary gates . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.3 Classical communication capacity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.3.1 General facts about the achievable classical communication rate region . . . . . 62 2.3.2 Capacity theorem for entanglement-assisted one-way classical communication . 63 2.3.3 Relations between entanglement and classical communication capacities . . . . 65 2.3.4 Challenges for bidirectional communication . . . . . . . . . . . . . . . . . . . . 67 2.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.4.1 SWAP, CNOT and double CNOT . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.4.2 A gate for which C (U) may be less than C (U) . . . . . . . . . . . . . . . . 70 ← → 2.4.3 A gate for which C (U) may be less than E(U). . . . . . . . . . . . . . . . . . 74 + 2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3 Coherent classical communication 77 3.1 Introduction and definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.2 Sources of coherent classical communication . . . . . . . . . . . . . . . . . . . . . . . . 78 3.3 Rules for using coherent classical communication . . . . . . . . . . . . . . . . . . . . . 80 3.4 Applications to remote state preparation and unitary gate capacities . . . . . . . . . . 82 3.4.1 Remote state preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.4.2 One-way classical capacities of unitary gates. . . . . . . . . . . . . . . . . . . . 83 3.4.3 Two-way cbit, cobit, qubit and ebit capacities of unitary gates . . . . . . . . . 85 3.5 Collected proofs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7 8 CONTENTS 3.5.1 Proof of Rule I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 3.5.2 Proof of Rule O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.5.3 Proof of Coherent RSP (Eq. 3.14) . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.5.4 Proof of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 4 Optimal trade-offs in quantum Shannon theory 101 4.1 A family of quantum protocols. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.2 Two dimensional trade-offs for the family . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.2.1 Grandmother protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.2.2 Trade-off for noisy super-dense coding . . . . . . . . . . . . . . . . . . . . . . . 105 4.2.3 Trade-off for quantum communication assisted entanglement distillation . . . . 106 4.2.4 Trade-off for noisy teleportation . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.2.5 Trade-off for classical communication assisted entanglement distillation . . . . 109 4.2.6 Trade-off for entanglement assisted quantum communication . . . . . . . . . . 110 4.2.7 Trade-off for entanglement assisted classical communication . . . . . . . . . . . 112 4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5 The Schur transform 115 5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.2 Representation theory and quantum computing . . . . . . . . . . . . . . . . . . . . . . 116 5.2.1 Basics of representation theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.2.2 The Clebsch-Gordan transform . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.2.3 The quantum Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.3 Schur duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.3.1 Constructing d and using Schur duality . . . . . . . . . . . . . . . . . . . 122 Qλ Pλ 5.4 Dual reductive pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6 Applications of the Schur transform to quantum information theory 125 6.1 The classical method of types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 6.2 Schur duality as a quantum method of types . . . . . . . . . . . . . . . . . . . . . . . 128 6.3 Applications of Schur duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6.4 Normal form of memoryless channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 6.4.1 The Clebsch-Gordan transformation . . . . . . . . . . . . . . . . . . . . . . 132 n S 6.4.2 Decomposition of memoryless quantum channels . . . . . . . . . . . . . . . . . 133 6.4.3 Jointly typical projectors in the Schur basis . . . . . . . . . . . . . . . . . . . . 134 6.4.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 7 Efficient circuits for the Schur transform 139 7.1 Subgroup-adapted bases for d and . . . . . . . . . . . . . . . . . . . . . . . . . . 140 Qλ Pλ 7.1.1 Subgroup Adapted Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 7.1.2 Explicit orthonormalbases for d and . . . . . . . . . . . . . . . . . . . . . 141 Qλ Pλ 7.2 Constructing the Schur transform from a series of Clebsch-Gordan transforms . . . . . 144 7.2.1 Branching rules and Clebsch-Gordanseries for . . . . . . . . . . . . . . . . . 144 d U 7.2.2 Constructing the Schur Transform from Clebsch-Gordan Transforms . . . . . . 146 7.3 Efficient circuits for the Clebsch-Gordan transform . . . . . . . . . . . . . . . . . . . . 148 7.3.1 The Wigner-EckartTheorem and Clebsch-Gordan transform . . . . . . . . . . 148 7.3.2 A recursive construction of the Clebsch-Gordan transform . . . . . . . . . . . . 150 7.3.3 Efficient Circuit for the Reduced Wigner Operator . . . . . . . . . . . . . . . . 153 CONTENTS 9 8 Relations between the Schur transform and the QFT 157 n S 8.1 Generalized phase estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 8.1.1 Using GPE to measure λ and . . . . . . . . . . . . . . . . . . . . . . . . . . 157 λ P 8.1.2 Using GPE to measure d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 Qλ 8.1.3 Connection to the Clebsch-Gordan transform . . . . . . . . . . . . . . . . . . . 162 8.2 Deriving the QFT from the Schur transform . . . . . . . . . . . . . . . . . . . . . . 166 n S 10 CONTENTS