Principal Quantum Computer Science: An Introduction
Due to the technical work on the site downloading books (as well as file conversion and sending books to email/kindle) may be unstable from May, 27 to May, 28 Also, for users who have an active donation now, we will extend the donation period.
You may be interested in Powered by Rec2Me
Most frequently terms
Quantum Computer Science An Introduction In the 1990s it was realized that quantum physics has some spectacular applications in computer science. This book is a concise introduction to quantum computation, developing the basic elements of this new branch of computational theory without assuming any background in physics. It begins with a novel introduction to the quantum theory from a computer-science perspective. It illustrates the quantum-computational approach with several elementary examples of quantum speed-up, before moving to the major applications: Shor’s factoring algorithm, Grover’s search algorithm, and quantum error correction. The book is intended primarily for computer scientists who know nothing about quantum theory but would like to learn the elements of quantum computation either out of curiosity about this new paradigm, or as a basis for further work in the subject. It will also be of interest to physicists who want to learn the theory of quantum computation, and to physicists and philosophers of science interested in quantum foundational issues. It evolved during six years of teaching the subject to undergraduates and graduate students in computer science, mathematics, engineering, and physics, at Cornell University. N. DAVID MERMIN is Horace White Professor of Physics Emeritus at Cornell University. He has received the Lilienfeld Prize of the American Physical Society and the Klopsteg award of the American Association of Physics Teachers. He is a member of the U.S. National Academy of Sciences and the American Academy of Arts and Sciences. Professor Mermin has written on quantum foundational issues for several decades, and is known for the clarity and wit of his scientiﬁc writings. Among his other books are Solid State Physics (with N. W. Ashcroft, Thomson Learning 1976), Boojums all the Way Through (Cambridge University Press 1990), and It’s about Time: Understanding Einstein’s Relativity (Princeton University Press 2005). “This is one of the ﬁnest books in the rapidly growing ﬁeld o; f quantum information. Almost every page contains a unique insight or a novel interpretation. David Mermin has once again demonstrated his legendary pedagogical skills to produce a classic.” Lov Grover, Bell Labs “Mermin’s book will be a standard for instruction and reference for years to come. He has carefully selected, from the mountain of knowledge accumulated in the last 20 years of research in quantum information theory, a manageable, coherent subset that constitutes a complete undergraduate course. While selective, it is in no sense “watered down”; Mermin moves unﬂinchingly through difﬁcult arguments in the Shor algorithm, and in quantum error correction theory, providing invaluable diagrams, clear arguments, and, when necessary, extensive appendices to get the students successfully through to the end. The book is suffused with Mermin’s unique knowledge of the history of modern physics, and has some of the most captivating writing to be found in a college textbook.” David DiVincenzo, IBM T. J. Watson Research Center “Mermin’s book is a gentle introduction to quantum computation especially aimed at an audience of computer scientists and mathematicians. It covers the basics of the ﬁeld, explaining the material clearly and containing lots of examples. Mermin has always been an entertaining and comprehensible writer, and continues to be in this book. I expect it to become the deﬁnitive introduction to this material for non-physicists.” Peter Shor, Massachusetts Institute of Technology “Textbook writers usually strive for a streamlined exposition, smoothing out the infelicities of thought and notation that plague any ﬁeld’s early development. Fortunately, David Mermin is too passionate and acute an observer of the cultural side of science to fall into this blandness. Instead of omitting infelicities, he explains and condemns them, at the same time using his experience of having taught the course many times to nip nascent misunderstandings in the bud. He celebrates the ﬁeld’s mongrel origin in a shotgun wedding between classical computer scientists, who thought they knew the laws of information, and quantum physicists, who thought information was not their job. Differences remain: we hear, for example, why physicists love the Dirac notation and mathematicians hate it. Worked-out examples and exercises familiarize students with the necessary algebraic manipulations, while Mermin’s lucid prose and gentle humor cajole them toward a sound intuition for what it all means, not an easy task for a subject superﬁcially so counterintuitive.” Charles Bennett, IBM T. J. Watson Research Center Quantum Computer Science An Introduction N. David Mermin Cornell University In memory of my brother, Joel Mermin You would have enjoyed it. CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9780521876582 © N. D. Mermin 2007 This publication is in copyright. Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published in print format 2007 eBook (NetLibrary) ISBN-13 978-0-511-34258-5 ISBN-10 0-511-34258-6 eBook (NetLibrary) ISBN-13 ISBN-10 hardback 978-0-521-87658-2 hardback 0-521-87658-3 Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. Contents Preface A note on references page xi xv 1 Cbits and Qbits 1.1 What is a quantum computer? 1.2 Cbits and their states 1.3 Reversible operations on Cbits 1.4 Manipulating operations on Cbits 1.5 Qbits and their states 1.6 Reversible operations on Qbits 1.7 Circuit diagrams 1.8 Measurement gates and the Born rule 1.9 The generalized Born rule 1.10 Measurement gates and state preparation 1.11 Constructing arbitrary 1- and 2-Qbit states 1.12 Summary: Qbits versus Cbits 1 1 3 8 11 17 19 21 23 28 30 32 34 2 General features and some simple examples 2.1 The general computational process 2.2 Deutsch’s problem 2.3 Why additional Qbits needn’t mess things up 2.4 The Bernstein–Vazirani problem 2.5 Simon’s problem 2.6 Constructing Toffoli gates 36 36 41 46 50 54 58 3 Breaking RSA encryption 3.1 Period ﬁnding, factoring, and cryptography 3.2 Number-theoretic preliminaries 3.3 RSA encryption 3.4 Quantum period ﬁnding: preliminary remarks 3.5 The quantum Fourier transform 3.6 Eliminating the 2-Qbit gates 3.7 Finding the period 63 63 64 66 68 71 76 79 viii CONTENTS 3.8 Calculating the periodic function 3.9 The unimportance of small phase errors 3.10 Period ﬁnding and factoring 83 84 86 4 Searching with a quantum computer 4.1 The nature of the search 4.2 The Grover iteration 4.3 How to construct W 4.4 Generalization to several special numbers 4.5 Searching for one out of four items 88 88 89 94 96 98 5 Quantum error correction 5.1 The miracle of quantum error correction 5.2 A simpliﬁed example 5.3 The physics of error generation 5.4 Diagnosing error syndromes 5.5 The 5-Qbit error-correcting code 5.6 The 7-Qbit error-correcting code 5.7 Operations on 7-Qbit codewords 5.8 A 7-Qbit encoding circuit 5.9 A 5-Qbit encoding circuit 99 99 100 109 113 117 121 124 127 128 6 Protocols that use just a few Qbits 6.1 Bell states 6.2 Quantum cryptography 6.3 Bit commitment 6.4 Quantum dense coding 6.5 Teleportation 6.6 The GHZ puzzle 136 136 137 143 146 149 154 Appendices A. Vector spaces: basic properties and Dirac notation B. Structure of the general 1-Qbit unitary transformation C. Structure of the general 1-Qbit state D. Spooky action at a distance E. Consistency of the generalized Born rule F. Other aspects of Deutsch’s problem G. The probability of success in Simon’s problem H. One way to make a cNOT gate I. A little elementary group theory J. Some simple number theory K. Period ﬁnding and continued fractions L. Better estimates of success in period ﬁnding 159 159 168 173 175 181 183 187 189 193 195 197 201 CONTENTS M. N. O. P. Index Factoring and period ﬁnding Shor’s 9-Qbit error-correcting code A circuit-diagrammatic treatment of the 7-Qbit code On bit commitment 203 207 210 216 218 ix Preface It was almost three quarters of a century after the discovery of quantum mechanics, and half a century after the birth of information theory and the arrival of large-scale digital computation, that people ﬁnally realized that quantum physics profoundly alters the character of information processing and digital computation. For physicists this development offers an exquisitely different way of using and thinking about the quantum theory. For computer scientists it presents a surprising demonstration that the abstract structure of computation cannot be divorced from the physics governing the instrument that performs the computation. Quantum mechanics provides new computational paradigms that had not been imagined prior to the 1980s and whose power was not fully appreciated until the mid 1990s. In writing this introduction to quantum computer science I have kept in mind readers from several disciplines. Primarily I am addressing computer scientists, electrical engineers, or mathematicians who may know little or nothing about quantum physics (or any other kind of physics) but who wish to acquire enough facility in the subject to be able to follow the new developments in quantum computation, judge for themselves how revolutionary they may be, and perhaps choose to participate in the further development of quantum computer science. Not the least of the surprising things about quantum computation is that remarkably little background in quantum mechanics has to be acquired to understand and work with its applications to information processing. Familiarity with a few fundamental facts about ﬁnite-dimensional vector spaces over the complex numbers (summarized and reviewed in Appendix A) is the only real prerequisite. One of the secondary readerships I have in mind consists of physicists who, like myself – I am a theorist who has worked in statistical physics, solid-state physics, low-temperature physics, and mathematical physics – know very little about computer science, but would like to learn about this extraordinary new application of their discipline. I stress, however, that my subject is quantum computer science, not quantum computer design. This is a book about quantum computational software – not hardware. The difﬁcult question of how one might actually build a quantum computer is beyond its scope. xii PREFACE Another secondary readership is made up of those philosophers and physicists who – again like myself – are puzzled by so-called foundational issues: what the strange quantum formalism implies about the nature of the world that it so accurately describes. By applying quantum mechanics in an entirely new way – and especially by applying it to the processing of knowledge – quantum computation gives a new perspective on interpretational questions. While I rarely address such matters explicitly, for purely pedagogical reasons my presentation is suffused with a perspective on the quantum theory that is very close to the venerable but recently much reviled Copenhagen interpretation. Those with a taste for such things may be startled to see how well quantum computation resonates with the Copenhagen point of view. Indeed, it had been my plan to call this book Copenhagen Computation until the excellent people at Cambridge University Press and my computer-scientist friends persuaded me that virtually no members of my primary readership would then have had any idea what it was about. Several years ago I mentioned to a very distinguished theoretical physicist that I spent the ﬁrst four lectures of a course in quantum computation giving an introduction to quantum mechanics for mathematically literate people who knew nothing about quantum mechanics, and quite possibly little if anything about physics. His immediate response was that any application of quantum mechanics that can be taught after only a four-hour introduction to the subject cannot have serious intellectual content. After all, he remarked, it takes any physicist many years to develop a feeling for quantum mechanics. It’s a good point. Nevertheless computer scientists and mathematicians with no background in physics have been able quickly to learn enough quantum mechanics to understand and make major contributions to the theory of quantum computation. There are two main reasons for this. First of all, a quantum computer – or, more accurately, the abstract quantum computer that one hopes someday to be able to embody in actual hardware – is an extremely simple example of a physical system. It is discrete, not continuous. It is made up out of a ﬁnite number of units, each of which is the simplest possible kind of quantum-mechanical system, a so-called two-state system, whose behavior, as we shall see, is highly constrained and easily speciﬁed. Much of the analytical complexity of learning quantum mechanics is connected with mastering the description of continuous (inﬁnite-state) systems. By restricting attention to collections of two-state systems (or even d -state systems for ﬁnite d ) one can avoid much suffering. Of course one also loses much wisdom, but hardly any of it – at least at this stage of the art – is relevant to the basic theory of quantum computation. Second, and just as important, the most difﬁcult part of learning quantum mechanics is to get a good feeling for how the formalism PREFACE can be applied to actual phenomena. This almost invariably involves formulating oversimpliﬁed abstract models of real physical systems, to which the quantum formalism can then be applied. The best physicists have an extraordinary intuition for what features of the phenomena are essential and must be represented in a model, and what features are inessential and can be ignored. It takes years to develop such intuition. Some never do. The theory of quantum computation, however, is entirely concerned with an abstract model – the easy part of the problem. To understand how to build a quantum computer, or even to study what physical systems are promising candidates for realizing such a device, you must indeed have many years of experience in quantum mechanics and its applications under your belt. But if you only want to know what such a device is capable in principle of doing once you have it, then there is no reason to get involved in the really difﬁcult physics of the subject. Exactly the same thing holds for ordinary classical computers. One can be a masterful practitioner of computer science without having the foggiest notion of what a transistor is, not to mention how it works. So while you should be warned that the subset of quantum mechanics you will acquire from this book is extremely focused and quite limited in its scope, you can also rest assured that it is neither oversimpliﬁed nor incomplete, when applied to the special task for which it is intended. I might note that a third impediment to developing a good intuition for quantum physics is that in some ways the behavior implied by quantum mechanics is highly counterintuitive, if not downright weird. Glimpses of such strange behavior sometimes show up at the level of quantum computation. Indeed, for me one of the major appeals of quantum computation is that it affords a new conceptual arena for trying to come to a better understanding of quantum weirdness. When opportunities arise I will call attention to some of this strange behavior, rather than (as I easily could) letting it pass by unremarked upon and unnoticed. The book evolved as notes for a course of 28 one-hour lectures on quantum computation that I gave six times between 2000 and 2006 to a diverse group of Cornell University undergraduates, graduate students, and faculty, in computer science, electrical engineering, mathematics, physics, and applied physics. With so broad an audience, little common knowledge could be assumed. My lecture notes, as well as my own understanding of the subject, repeatedly beneﬁted from comments and questions in and after class, coming from a number of different perspectives. What made sense to one of my constituencies was often puzzling, absurd, or irritatingly simple-minded to others. This ﬁnal form of my notes bears little resemblance to my earliest versions, having been improved by insightful remarks, suggestions, and complaints about everything from notation to number theory. xiii xiv PREFACE In addition to the 200 or so students who passed through P481-P681CS483, I owe thanks to many others. Albert J. Sievers, then Director of Cornell’s Laboratory of Atomic and Solid State Physics, started me thinking hard about quantum computation by asking me to put together a two-week set of introductory lectures for members of our laboratory, in the Fall of 1999. So many people showed up from all over the university that I decided it might be worth expanding this survey into a full course. I’m grateful to two Physics Department chairs, Peter Lepage and Saul Teukolsky, for letting me continue teaching that course for six straight years, and to the Computer Science Department chair, Charlie van Loan, for support, encouragement, and a steady stream of wonderful students. John Preskill, though he may not know it, taught me much of the subject from his superb online Caltech lecture notes. Charles Bennett ﬁrst told me about quantum information processing, back when the term might not even have been coined, and he has always been available as a source of wisdom and clariﬁcation. Gilles Brassard has on many occasions supplied me with help from the computer-science side. Chris Fuchs has been an indispensable quantum-foundational critic and consultant. Bob Constable made me, initially against my will, a certiﬁed Cornell Information Scientist and introduced me to many members of that excellent community. But most of all, I owe thanks to David DiVincenzo, who collaborated with me on the 1999 two-week LASSP Autumn School and has acted repeatedly over the following years as a sanity check on my ideas, an indispensable source of references and historical information, a patient teacher, and an encouraging friend. A note on references Quantum Computer Science is a pedagogical introduction to the basic structure and procedures of the subject – a quantum-computational primer. It is not a historical survey of the development of the ﬁeld. Many of these procedures are named after the people who ﬁrst put them forth, but although I use their names, I do not cite the original papers unless they add something to my own exposition. This is because, not surprisingly, work done since the earliest papers has led to clearer expositions of those ideas. I learned the subject myself almost exclusively from secondary, tertiary, or even higher-order sources, and then reformulated it repeatedly in the course of teaching it for six years. On the few occasions when I do cite a paper it is either because it completes an exposition that I have only sketched, or because the work has not yet become identiﬁed in the ﬁeld with the name(s) of the author(s) and I wanted to make clear that it was not original with me. Readers interested in hunting down earlier work in the ﬁeld can begin (and in most cases conclude) their search at the quantum-physics subdivision of the Cornell (formerly Los Alamos) E-print Archive, http://arxiv.org/archive/quant-ph, where most of the important papers in the ﬁeld have been and are still being posted. Chapter 1 Cbits and Qbits 1.1 What is a quantum computer? It is tempting to say that a quantum computer is one whose operation is governed by the laws of quantum mechanics. But since the laws of quantum mechanics govern the behavior of all physical phenomena, this temptation must be resisted. Your laptop operates under the laws of quantum mechanics, but it is not a quantum computer. A quantum computer is one whose operation exploits certain very special transformations of its internal state, whose description is the primary subject of this book. The laws of quantum mechanics allow these peculiar transformations to take place under very carefully controlled conditions. In a quantum computer the physical systems that encode the individual logical bits must have no physical interactions whatever that are not under the complete control of the program. All other interactions, however irrelevant they might be in an ordinary computer – which we shall call classical – introduce potentially catastrophic disruptions into the operation of a quantum computer. Such damaging encounters can include interactions with the external environment, such as air molecules bouncing off the physical systems that represent bits, or the absorption of minute amounts of ambient radiant thermal energy. There can even be disruptive interactions between the computationally relevant features of the physical systems that represent bits and other features of those same systems that are associated with computationally irrelevant aspects of their internal structure. Such destructive interactions, between what matters for the computation and what does not, result in decoherence, which is fatal to a quantum computation. To avoid decoherence individual bits cannot in general be encoded in physical systems of macroscopic size, because such systems (except under very special circumstances) cannot be isolated from their own irrelevant internal properties. Such isolation can be achieved if the bits are encoded in a small number of states of a system of atomic size, where extra internal features do not matter, either because they do not exist, or because they require unavailably high energies to come into play. Such atomic-scale systems must also be decoupled from their surroundings except for the completely controlled interactions that are associated with the computational process itself. 1 2 CBITS AND QBITS Two things keep the situation from being hopeless. First, because the separation between the discrete energy levels of a system on the atomic scale can be enormously larger than the separation between the levels of a large system, the dynamical isolation of an atomic system is easier to achieve. It can take a substantial kick to knock an atom out of its state of lowest energy. The second reason for hope is the discovery that errors induced by extraneous interactions can actually be corrected if they occur at a sufﬁciently low rate. While error correction is routine for bits represented by classical systems, quantum error correction is constrained by the formidable requirement that it be done without knowing either the original or the corrupted state of the physical systems that represent the bits. Remarkably, this turns out to be possible. Although the situation is therefore not hopeless, the practical difﬁculties in the way of achieving useful quantum computation are enormous. Only a rash person would declare that there will be no useful quantum computers by the year 2050, but only a rash person would predict that there will be. Never mind. Whether or not it will ever become a practical technology, there is a beauty to the theory of quantum computation that gives it a powerful appeal as a lovely branch of mathematics, and as a strange generalization of the paradigm of classical computer science, which had completely escaped the attention of computer scientists until the 1980s. The new paradigm demonstrates that the theory of computation can depend profoundly on the physics of the devices that carry it out. Quantum computation is also a valuable source of examples that illustrate and illuminate, in novel ways, the mysterious phenomena that quantum behavior can give rise to. For computer scientists the most striking thing about quantum computation is that a quantum computer can be vastly more efﬁcient than anything ever imagined in the classical theory of computational complexity, for certain computational tasks of considerable practical interest. The time it takes the quantum computer to accomplish such tasks scales up much more slowly with the size of the input than it does in any classical computer. Much of this book is devoted to examining the most celebrated examples of this speed-up. This exposition of quantum computation begins with an introduction to quantum mechanics, specially tailored for this particular application. The quantum-mechanics lessons are designed to give you, as efﬁciently as possible, the conceptual tools needed to delve into quantum computation. This is done by restating the rules of quantum mechanics, not as the remarkable revision of classical Newtonian mechanics required to account for the behavior of matter at the atomic and subatomic levels, but as a curious generalization of rules describing an ordinary classical digital computer. By focusing exclusively on how quantum mechanics enlarges the possibilities for the physical manipulation of digital information, it is possible to characterize how 1.2 CBITS AND THEIR STATES the quantum theory works in an elementary and quite concise way, which is nevertheless rigorous and complete for this special area of application. While I assume no prior familiarity with quantum physics (or any other kind of physics), I do assume familiarity with elementary linear algebra and, in particular, with the theory of ﬁnite-dimensional vector spaces over the complex numbers. Appendix A summarizes the relevant linear algebra. It is worth examining even if you are well acquainted with the mathematics of such vector spaces, since it also provides a compact summary of the mathematically unconventional language – Dirac notation – in which linear algebra is couched in all treatments of quantum computation. Dirac notation is also developed, more informally, throughout the rest of this chapter. 1.2 Cbits and their states We begin with an offbeat formulation of what an ordinary classical computer does. I frame the elementary remarks that follow in a language which may look artiﬁcial and cumbersome, but is designed to accommodate the richer variety of things that a computer can do if it takes full advantage of the possibilities made available by the quantummechanical behavior of its constituent parts. By introducing and applying the unfamiliar nomenclature and notation of quantum mechanics in a familiar classical context, I hope to make a little less strange its subsequent extension to the broader quantum setting. A classical computer operates on strings of zeros and ones, such as 110010111011000, converting them into other such strings. Each position in such a string is called a bit, and it contains either a 0 or a 1. To represent such collections of bits the computer must contain a corresponding collection of physical systems, each of which can exist in two unambiguously distinguishable physical states, associated with the value (0 or 1) of the abstract bit that the physical system represents. Such a physical system could be, for example, a switch that could be open (0) or shut (1), or a magnet whose magnetization could be oriented in two different directions, “up” (0) or “down” (1). It is a common practice in quantum computer science to use the same term “bit” to describe the two-state classical system that represents the value of the abstract bit. But this use of a single term to characterize both the abstract bit (0 or 1) and the physical system whose two states represent the two values is a potential source of confusion. To avoid such confusion, I shall use the term Cbit (“C” for “classical”) to describe the two-state classical physical system and Qbit to describe its quantum generalization. This terminology is inspired by Paul Dirac’s early use of c-number and q-number to describe classical quantities and their quantum-mechanical generalizations. “Cbit” and 3 4 CBITS AND QBITS “Qbit” are preferable to “c-bit” and “q-bit” because the terms themselves often appear in hyphenated constructions. Unfortunately the preposterous spelling qubit currently holds sway for the quantum system. The term qubit was invented and ﬁrst used in print by the otherwise admirable Benjamin Schumacher.1 A brief history of the term can be found in the acknowledgments at the end of his paper. Although “qubit” honors the English (German, Italian, . . .) rule that q should be followed by u, it ignores the equally powerful requirement that qu should be followed by a vowel. My guess is that “qubit” has gained acceptance because it visually resembles an obsolete English unit of distance, the homonymic cubit. To see its ungainliness with fresh eyes, it sufﬁces to imagine that Dirac had written qunumber instead of q-number, or that one erased transparencies and cleaned one’s ears with Qutips. Because clear distinctions among bits, Cbits, and Qbits are crucial in the introduction to quantum computation that follows, I shall use this currently unfashionable terminology. If you are already addicted to the term qubit, please regard Qbit as a convenient abbreviation. To prepare for the extension from Cbits to Qbits, I introduce what may well strike you as a degree of notational overkill in the discussion of Cbits that follows. We shall represent the state of each Cbit as a kind of box, depicted by the symbol | , into which we place the value, 0 or 1, represented by that state. Thus the two distinguishable states of a Cbit are represented by the symbols |0 and |1. It is the common practice to call the symbol |0 or |1 itself the state of the Cbit, thereby using the same term to refer to both the physical condition of the Cbit and the abstract symbol that represents that physical condition. There is nothing unusual in this. For example one commonly uses the term “position” to refer to the symbol x that represents the physical position of an object. I call this common, if little noted, practice to your attention only because in the quantum case “state” refers only to the symbol, there being no internal property of the Qbit that the symbol represents. The subtle relation between Qbits and their state symbol will emerge later in this chapter. Along the same lines, we shall characterize the states of the ﬁve Cbits representing 11001, for example, by the symbol |1|1|0|0|1, (1.1) and refer to this object as the state of all ﬁve Cbits. Thus a pair of Cbits can have (or “be in”) any of the four possible states |0|0, |0|1, |1|0, |1|1, 1 Benjamin Schumacher, “Quantum coding,” Physical Review A 51, 2738–2747 (1995). (1.2) 1.2 CBITS AND THEIR STATES three Cbits can be in any of the eight possible states |0|0|0, |0|0|1, |0|1|0, |0|1|1, |1|0|0, |1|0|1, |1|1|0, |1|1|1, (1.3) and so on. As (1.4) already makes evident, when there are many Cbits such products are often much easier to read if one encloses the whole string of zeros and ones in a single bigger box of the form | rather than having a separate box for each Cbit: |000, |001, |010, |011, |100, |101, |110, |111. (1.4) We shall freely move between these two equivalent ways of expressing the state of several Cbits that represent a string of bits, boxing the whole string or boxing each individual bit. Whether the form (1.3) or (1.4) is to be preferred depends on the context. There is also a third form, which is useful when we regard the zeros and ones as constituting the binary expansion of an integer. We can then replace the representations of the 3-Cbit states in (1.4) by the even shorter forms |0, |1, |2, |3, |4, |5, |6, |7. (1.5) Note that, unlike the forms (1.3) and (1.4), the form (1.5) is ambiguous, unless we are told that these symbols express states of three Cbits. If we are not told, then there is no way of telling, for example, whether |3 represents the 2-Cbit state|11, the 3-Cbit state|011, or the 4-Cbit state |0011, etc. This ambiguity can be removed, when necessary, by adding a subscript making the number of Cbits explicit: |03 , |13 , |23 , |33 , |43 , |53 , |63 , |73 . (1.6) Be warned, however, that, when there is no need to emphasize how many Cbits |x represents, it can be useful to use such subscripts for other purposes. If, for example, Alice and Bob each possess a single Cbit it can be convenient to describe the state of Alice’s Cbit (if it has the value 1) by |1a , Bob’s (if it has the value 0) by |0b , and the joint state of the two by |1a |0b or |10ab . Dirac introduced the | notation (known as Dirac notation) in the early days of the quantum theory, as a useful way to write and manipulate vectors. For silly reasons he called such vectors kets, a terminology that has survived to this day. In Dirac notation you can put into the box | anything that serves to specify what the vector is. If, for example, we were talking about displacement vectors in ordinary three-dimensional space, we could have a vector |5 horizontal centimeters northeast. (1.7) 5 6 CBITS AND QBITS In using Dirac notation to express the state of a Cbit, or a collection of Cbits, I’m suggesting that there might be some utility in thinking of the states as vectors. Is there? Well, in the case of Cbits, not very much, but maybe a little. We now explore this way of thinking about Cbit states, because when we come to the generalization to Qbits, it becomes absolutely essential to consider them to be vectors – so much so that the term state is often taken to be synonymous with vector (or, more precisely, “vector that represents the state”). We shall brieﬂy explore what one can do with Cbits when one takes the two states |0 and |1 of a single Cbit to be represented by two orthogonal unit vectors in a two-dimensional space. While this is little more than a curious and unnecessarily elaborate way of describing Cbits, it is fundamental and unavoidable in dealing with Qbits. Playing unfamiliar and somewhat silly games with Cbits will enable you to become acquainted with much of the quantum-mechanical formalism in a familiar setting. If you prefer your vectors to be expressed in terms of components, note that we can represent the two orthogonal states of a single Cbit, |0 and |1, as column vectors 1 0 |0 = , |1 = . (1.8) 0 1 In the case of two Cbits the vector space is four-dimensional, with an orthonormal basis |00, |01, |10, |11. (1.9) The alternative notation for this basis, |0|0, |0|1, |1|0, |1|1, (1.10) is deliberately designed to suggest multiplication, since it is, in fact, a short-hand notation for the tensor product of the two single-Cbit 2-vectors, written in more formal mathematical notation as |0 ⊗ |0, |0 ⊗ |1, |1 ⊗ |0, |1 ⊗ |1. (1.11) In terms of components, the tensor product a ⊗ b of an M-component vector a with components a µ and an N-component vector b with components b ν is the (MN)-component vector with components indexed by all the MN possible pairs of indices (µ, ν), whose (µ, ν)th component is just the product a µ b ν . A broader view can be found in the extended review of vector-space concepts in Appendix A. I shall freely move back and forth between the various ways (1.9)–(1.11) of writing the tensor product and their generalizations to multi-Cbit states, using in each case a form that makes the content clearest. Once one agrees to regard the two 1-Cbit states as orthogonal unit vectors, the tensor product is indeed the natural way to represent 1.2 CBITS AND THEIR STATES multi-Cbit states, since it leads to the obvious multi-Cbit generalization of the representation (1.8) of 1-Cbit states as column vectors. If we express the states |0 and |1 of each single Cbit as column vectors, then we can get the column vector describing a multi-Cbit state by repeatedly applying the rule for the components of the tensor product of two vectors. The result is illustrated here for a three-fold tensor product: ⎛x y z ⎞ 0 0 0 ⎜ x0 y0 z1 ⎟ ⎟ ⎜ x0 y1 z0 ⎟ ⎜ ⎟ ⎜ y0 z0 x0 ⎜x y z ⎟ ⊗ ⊗ = ⎜ 0 1 1 ⎟. x1 y1 z1 ⎜ x1 y0 z0 ⎟ ⎟ ⎜ ⎜ x1 y0 z1 ⎟ ⎠ ⎝ x1 y1 z0 x1 y1 z1 On applying this, for example, to the case |53 , we have (1.12) ⎛0⎞ ⎜0⎟ ⎜ ⎟ 0⎟ ⎜ ⎜ ⎟ 0 1 0 ⎜0⎟ |53 = |101 = |1|0|1 = ⊗ ⊗ = ⎜ ⎟. (1.13) 1 0 1 ⎜0⎟ ⎜ ⎟ ⎜1⎟ ⎝ ⎠ 0 0 If we label the vertical components of the 8-vector on the right 0, 1, . . ., 7, from the top down, then the single nonzero component is the 1 in position 5 – precisely the position speciﬁed by the state vector in its form on the left of (1.13). This is indeed the obvious multi-Cbit generalization of the column-vector form (1.8) for 1-Cbit states. This is quite general: the tensor-product structure of multi-Cbit states is just what one needs in order for the 2n -dimensional column vector representing the state |m n to have all its entries zero except for a single 1 in the m th position down from the top. One can turn this development upside down, taking as one’s starting point the simple rule that an integer x in the range 0 ≤ x < N is represented by one of N orthonormal vectors in an N-dimensional space. One can then pick a basis so that 0 is represented by an Ncomponent column vector |0 that has 0 in every position except for a 1 in the top position, and x is to be represented by an N-component column vector |x that has 0 in every position except for a 1 in the position x down from the top. It then follows from the nature of the tensor product that if N = 2n and x has the binary expansion x = n−1 j j =0 x j 2 , then the column vector |xn is the tensor product of the n 2-component column vectors |x j : |xn = |xn−1 ⊗ |xn−2 ⊗ · · · ⊗ |x1 ⊗ |x0 . (1.14) 7 8 CBITS AND QBITS In dealing with n-Cbit states of the form (1.14) we shall identify each of the n 1-Cbit states, out of which they are composed, by giving the power of 2 associated with the individual bit that the Cbit represents. Thus the 1-Cbit state on the extreme right of (1.14) represents Cbit 0, the state immediately to its left represents Cbit 1, and so on. This relation between tensor products of vectors and positional notation for integers is not conﬁned to the binary system. Suppose, for example, one represents a decimal digit x = 0, 1, . . ., 9 as a 10component column vector v(x) with all components 0 except for a 1, x positions down from the top. If the n-digit decimal number j (xn−1 ) ⊗ X = n−1 j =0 x j 10 is represented by the tensor product V = v (xn−2 ) (1) (0) n v ⊗ · · · ⊗ v ⊗ v , then V will be a 10 -component column vector with all components 0 except for a 1, x positions down from the top. Although the representation of Cbit states by column vectors clearly shows why tensor products give a natural description of multi-Cbit states, for almost all other purposes it is better and much simpler to forget about column vectors and components, and deal directly with the state vectors in their abstract forms (1.3)–(1.6). 1.3 Reversible operations on Cbits Quantum computers do an important part of their magic through reversible operations, which transform the initial state of the Qbits into its ﬁnal form using only processes whose action can be inverted. There is only a single irreversible component to the operation of a quantum computer, called measurement, which is the only way to extract useful information from the Qbits after their state has acquired its ﬁnal form. Although measurement is a nontrivial and crucial part of any quantum computation, in a classical computer the extraction of information from the state of the Cbits is so conceptually straightforward that it is not viewed as an inherent part of the computational process, though it is, of course, a nontrivial concern for those who design digital displays or printers. Because the only computationally relevant operations on a classical computer that can be extended to operations on a quantum computer are reversible, only operations on Cbits that are reversible will be of interest to us here. In a reversible operation every ﬁnal state arises from a unique initial state. An example of an irreversible operation is ERASE, which forces a Cbit into the state |0 regardless of whether its initial state is |0 or |1. ERASE is irreversible in the sense that, given only the ﬁnal state and the fact that it was the output of the operation ERASE, there is no way to recover the initial state. The only nontrivial reversible operation we can apply to a single Cbit is the NOT operation, denoted by the symbol X, which interchanges 1.3 REVERSIBLE OPERATIONS ON CBITS the two states |0 and |1: X : |x → |x̃; 1̃ = 0, 0̃ = 1. (1.15) This is sometimes referred to as ﬂipping the Cbit. NOT is reversible because it has an inverse: applying X a second time brings the state of the Cbit back to its original form: X 2 = 1, (1.16) where 1 is the unit (identity) operator. If we represent the two orthogonal states of the Cbit by the column vectors (1.8), then we can express NOT by a linear operator X on the two-dimensional vector space, whose action on the column vectors is given by the matrix 0 1 X= . (1.17) 1 0 So the two reversible things you can do to a single Cbit – leaving it alone and ﬂipping it – correspond to the two linear operators X and 1, 1 0 1= , (1.18) 0 1 on its two-dimensional vector space. A pedantic digression: since multiplication by the scalar 1 and action by the unit operator 1 achieve the same result, I shall sometimes follow the possibly irritating practice of physicists and not distinguish notationally between them. I shall take similar liberties with the scalar 0, the zero vector 0, and the zero operator 0. Possibilities for reversible operations get richer when we go from a single Cbit to a pair of Cbits. The most general reversible operation on two Cbits is any permutation of their four possible states. There are 4! = 24 such operations. Perhaps the simplest nontrivial example is the swap (or exchange) operator Si j , which simply interchanges the states of Cbits i and j : S10 |xy = |yx. (1.19) Since the swap operator S10 interchanges |01 = |12 and |10 = |22 , while leaving |00 = |02 and |11 = |32 ﬁxed, its matrix in the basis |02 , |12 , |22 , |32 is ⎛ ⎞ 1 0 0 0 ⎜0 0 1 0⎟ ⎟ (1.20) S10 = S01 = ⎜ ⎝ 0 1 0 0 ⎠. 0 0 0 1 The 2-Cbit operator whose extension to Qbits plays by far the most important role in quantum computation is the controlled-NOT or cNOT operator Ci j . If the state of the i th Cbit (the control Cbit) is |0, Ci j leaves the state of the j th Cbit (the target Cbit) unchanged, but, 9 10 CBITS AND QBITS if the state of the control Cbit is |1, Ci j applies the NOT operator X to the state of the target Cbit. In either case the state of the control Cbit is left unchanged. We can summarize this compactly by writing C10 |x|y = |x|y ⊕ x, C01 |x|y = |x ⊕ y|y, (1.21) where ⊕ denotes addition modulo 2: y ⊕ 0 = y, y ⊕ 1 = ỹ = 1 − y. (1.22) The modulo-2 sum x ⊕ y is also called the “exclusive OR” (or XOR) of x and y. You can construct SWAP out of three cNOT operations: Si j = Ci j C j i Ci j . (1.23) This can easily be veriﬁed by repeated applications of (1.21), noting that x ⊕ x = 0. We note some other ways of showing it below. To construct the matrix for the cNOT operation in the fourdimensional 2-Cbit space, note that if the control Cbit is on the left then cNOT leaves |00 = |02 and |01 = |12 ﬁxed and exchanges |10 = |22 and |11 = |32 . Therefore the 4 ⊗ 4 matrix representing C10 is just ⎛ ⎞ 1 0 0 0 ⎜0 1 0 0⎟ ⎟ C10 = ⎜ (1.24) ⎝ 0 0 0 1 ⎠. 0 0 1 0 If the control Cbit is on the right, then the states |01 = |12 and |11 = |32 are interchanged, and |00 = |02 and |10 = |22 are ﬁxed, so the matrix representing C01 is ⎞ ⎛ 1 0 0 0 ⎜0 0 0 1⎟ ⎟ (1.25) C01 = ⎜ ⎝ 0 0 1 0 ⎠. 0 1 0 0 The construction (1.23) of S out of cNOT operators also follows from (1.20), (1.24), and (1.25), using matrix multiplication. As a practical matter, it is almost always more efﬁcient to establish operator identities by dealing with them directly as operators, avoiding matrix representations. A very common kind of 2-Cbit operator consists of the tensor product ⊗ of two 1-Cbit operators: (a ⊗ b)|xy = (a ⊗ b)|x ⊗ |y = a|x ⊗ b|y, (1.26) from which it follows that (a ⊗ b)(c ⊗ d) = (ac) ⊗ (bd). (1.27) 1.4 MANIPULATING OPERATIONS ON CBITS This tensor-product notation for operators can become quite ungainly when one is dealing with a large number of Cbits and wants to write a 2-Cbit operator that affects only a particular pair of Cbits. If, for example, the 2-Cbit operator in (1.26) acts only on the second and fourth Cbits from the right in a 6-Cbit state, then the operator on the 6-Cbit state has to be written as 1 ⊗ 1 ⊗ a ⊗ 1 ⊗ b ⊗ 1. (1.28) To avoid such typographical monstrosities, we simplify (1.28) to 1 ⊗ 1 ⊗ a ⊗ 1 ⊗ b ⊗ 1 = a3 b1 = b1 a3 , (1.29) where the subscript indicates which Cbit the 1-Cbit operator acts on, and it is understood that those Cbit states whose subscripts do not appear remain unmodiﬁed – i.e. they are acted on by the unit operator. As noted above, we label each 1-Cbit state by the power of 2 it would represent if the n Cbits were representing an integer: the state on the extreme right is labeled 0, the one to its left, 1, etc. Since the order in which a and b are written is clearly immaterial if their subscripts specify different 1-Cbit states, the order in which one writes them in (1.29) doesn’t matter: 1-Cbit operators that act on different 1-Cbit states commute. Sometimes we deal with 1-Cbit operators that already have subscripts in their names; under such conditions it is more convenient to indicate which Cbit state the operator acts on by a superscript, enclosed in parentheses to avoid confusion with an exponent: thus X(2) represents the 1-Cbit operator that ﬂips the third Cbit state from the right, but X2 represents the square of the ﬂip operator (i.e. the unit operator) without reference to which Cbit state it acts on. To prepare for some of the manipulations we will be doing with operations on Qbits, we now examine a few examples of working with operators on Cbits. 1.4 Manipulating operations on Cbits It is useful to introduce a 1-Cbit operator n that is simply the projection operator onto the state |1: n|x = x|x, x = 0 or 1. (1.30) Because |0 and |1 are eigenvectors of n with eigenvalues 0 and 1, n is called the 1-Cbit number operator. We also deﬁne the complementary operator, ñ = 1 − n, (1.31) 11 12 CBITS AND QBITS which projects onto the state |0, so |0 and |1 are eigenvectors of ñ with eigenvalues 1 and 0. These operators have the matrix representations 0 0 1 0 n= , ñ = . (1.32) 0 1 0 0 It follows directly from their deﬁnitions that n 2 = n, ñ2 = ñ, nñ = ñn = 0, n + ñ = 1. (1.33) We also have nX = Xñ, ñX = Xn, (1.34) since ﬂipping the state of a Cbit and then acting on it with n (ñ) is the same as acting on the state with ñ (n) and then ﬂipping it. All the simple relations in (1.33) and (1.34) also follow, as they must, from the matrix representations (1.17) and (1.32) for X, n, and ñ. Although n has no interpretation as a physical operation on Cbits – replacing the state of a Cbit by the zero vector corresponds to no physical operation – it can be useful in deriving relations between operations that do have physical meaning. Since, for example, the SWAP operator Si j acts as the identity if the states of the Cbits i and j are the same, and ﬂips the numbers represented by both Cbits if their states are different, it can be written as Si j = ni n j + ñi ñ j + (Xi X j )(ni ñ j + ñi n j ). (1.35) At the risk of belaboring the obvious, I note that (1.35) acts as the swap operator because if both Cbits are in the state |1 (so swapping their states does nothing) then only the ﬁrst term in the sum acts (i.e. each of the other three terms gives 0) and multiplies the state by 1; if both Cbits are in the state |0, only the second term acts and again multiplies the state by 1; if Cbit i is in the state |1 and Cbit j is in the state |0, only the third term acts and the effect of ﬂipping both Cbits is to swap their states; and if Cbit i is in the state |0 and Cbit j is in the state |1, only the fourth term acts and the effect of the two Xs is again to swap their states. To help you become more at home with this notation, you are urged to prove from (1.35) that Si2j = 1, using only the relations in (1.33) and (1.34), the fact that X2 = 1, and the fact that 1-Cbit operators acting on different Cbits commute. The construction (1.23) of SWAP out of cNOT operators can also be demonstrated using a more algebraic approach. Note ﬁrst that Ci j can be expressed in terms of ns and Xs by Ci j = ñi + X j ni , (1.36) since if the state of Cbit i is |0 only the ﬁrst term acts, which leaves the states of both Cbits unchanged, but if the state of Cbit i is |1 only the second term acts, which leaves the state of Cbit i unchanged, while X j 1.4 MANIPULATING OPERATIONS ON CBITS ﬂips Cbit j . If you substitute expressions of the form (1.36) for each of the three terms in (1.23), then you can show by purely algebraic manipulations that four of the eight terms into which the products expand vanish and the remaining four can be rearranged to give the swap operator (1.35). An operator that has no direct role to play in classical computation, but which is as important as the NOT operator X in quantum computation, is the operator Z deﬁned by 1 0 Z = ñ − n = . (1.37) 0 −1 It follows from (1.34) (or from the matrix representations (1.17) and (1.37)) that X anticommutes with Z: ZX = −XZ. (1.38) Since ñ + n = 1, we can use (1.37) to express the 1-Cbit projection operators ñ and n in terms of 1 and Z: n = 12 (1 − Z), ñ = 12 (1 + Z). (1.39) Using this we can rewrite the cNOT operator (1.36) in terms of X and Z operators: Ci j = = 1 2 1 2 1 + Zi + 12 X j 1 − Zi 1 + X j + 12 Zi 1 − X j . (1.40) The second form follows from the ﬁrst because X j and Zi commute when i = j . Note that, if we were to interchange X and Z in the second line of (1.40), we would get back the expression directly above it except for the interchange of i and j . So interchanging the X and Z operators has the effect of switching which Cbit is the control and which is the target, changing Ci j into C j i . An operator that can produce just this effect is the Hadamard transformation (also sometimes called the Walsh–Hadamard transformation), 1 1 1 1 H = √ (X + Z ) = √ . (1.41) 2 2 1 −1 This is another operator of fundamental importance in quantum computation.2 2 Physicists should note here an unfortunate clash between the notations of quantum computer science and physics. Quantum physicists invariably use H to denote the Hamiltonian function (in classical mechanics) or Hamiltonian operator (in quantum mechanics). Fortunately Hamiltonian operators, although of crucial importance in the design of quantum computers, play a very limited role in the general theory of quantum computation, being completely overshadowed by the unitary transformations that they generate. So physicists can go along with the computer-science notation without getting into serious trouble. 13 14 CBITS AND QBITS Since X2 = Z2 = 1 and XZ = −ZX, one easily shows from the deﬁnition (1.41) of H in terms of X and Z that H2 = 1 (1.42) and that HXH = Z, HZH = X. (1.43) This shows how H can be used to interchange the X and Z operators in C j i : it follows from (1.43), together with (1.40) and (1.42), that C j i = Hi H j Ci j Hi H j . (1.44) We shall see that this simple relation can be put to some quite remarkable uses in a quantum computer. While one can achieve this interchange on a classical computer using the SWAP operation, C j i = Si j Ci j Si j , the crucial difference between Si j and Hi H j is that the latter is a product of two 1-Cbit operators, while the former is not. Of course, the action of H on the state of a Cbit that follows from (1.41), H|0 = √1 (|0 2 + |1), H|1 = √1 (|0 2 − |1), (1.45) describes no meaningful transformation of Cbits. Nevertheless, when combined with other operations, as on the right side of (1.44), the Hadamard operations result in the perfectly sensible operation given on the left side. In a quantum computer the action of H on 1-Qbit states turns out to be not only meaningful but also easily implemented, and the possibility of interchanging control and target Qbits using only 1-Qbit operators in the manner shown in (1.44) turns out to have some striking consequences. The use of Hadamards to interchange the control and target Qbits of a cNOT operation is sufﬁciently important in quantum computation to merit a second derivation of (1.44), which further illustrates the way in which one uses the operator formalism. In strict analogy to the deﬁnition of cNOT (see (1.21) and the preceding paragraph) we can deﬁne a controlled-Z operation, CiZj , which leaves the state of the target Cbit j unchanged if the state of the control Cbit i is |0, and operates on the target Cbit with Z if the state of the control Cbit is |1. As a Z |xy acts as the identity on |xy unless both x and y are 1, in result C10 which case it simply takes |11 into −|11. This behavior is completely symmetric in the two Cbits, so CiZj = C Zji . (1.46) It is a straightforward consequence of (1.42) and (1.43) that sandwiching the target Cbit of a cNOT between Hadamards converts 1.4 MANIPULATING OPERATIONS ON CBITS it to a C Z : H j Ci j H j = CiZj , Hi C j i Hi = C Zji . (1.47) In view of (1.46), we then have H j Ci j H j = Hi C j i Hi , (1.48) which is equivalent to (1.44), since H2 = 1. As a ﬁnal exercise in treating operations on Cbits as linear operations on vectors, we construct an alternative form for the swap operator. If we use (1.39) to reexpress each n and ñ appearing in the swap operator (1.35) in terms of Z, we ﬁnd that Si j = 12 (1 + Zi Z j ) + 12 (Xi X j )(1 − Zi Z j ). If we deﬁne Y = i XZ = −i 0 0 i (i = √ −1), (1.49) (1.50) we get the more compact form Si j = 12 (1 + Xi X j + Yi Y j + Zi Z j ). (1.51) For three quarters of a century physicists have enjoyed grouping the matrix representations of the three operators X, Y, and Z into a “3→ vector” − σ whose “components” are 2 ⊗ 2 matrices: 0 1 0 −i 1 0 σx = , σy = , σz = . 1 0 i 0 0 −1 (1.52) The swap operator then becomes3 Si j = 1 2 → 1+− σ (i ) → ·− σ ( j) , (1.53) where “·” represents the ordinary three-dimensional scalar product: → − → σ (i ) · − σ ( j ) = σ (ix ) σ (xj ) + σ (iy ) σ (yj ) + σ (iz ) σ (zj ) . (1.54) → The three components of − σ have many properties that are unchanged under cyclic permutations of x, y, and z. All three are Hermitian.4 All square to unity, σ 2x = σ 2y = σ 2z = 1. (1.55) 3 Physicists might enjoy the simplicity of this “computational” derivation of the form of the exchange operator, compared with the conventional quantum-mechanical derivation, which invokes the full apparatus of angular-momentum theory. 4 The elements of a Hermitian matrix A satisfy A j i = Ai∗j , where ∗ denotes complex conjugation. A fuller statement in a broader context can be found in Appendix A. 15 16 CBITS AND QBITS They all anticommute in pairs and the product of any two of them is simply related to the third: σ x σ y = −σ y σ x = i σ z, σ y σ z = −σ zσ y = i σ x , σ zσ x = −σ x σ z = i σ y . (1.56) The three relations (1.56) differ only by cyclic permutations of x, y, and z. All the relations in (1.55) and (1.56) can be summarized in a single − → → compact and useful identity. Let − a and b be two 3-vectors with components a x , a y , a z and b x , b y , b z that are ordinary real numbers. (They can also be complex numbers, but in most useful applications they are real.) Then one easily conﬁrms that all the relations in (1.55) and (1.56) imply and are implied by the single identity − → → − → → − → → → → → a × b )·− σ, (1.57) (− a ·− σ )( b · − σ ) = (− a · b )1 + i (− − → → → where − a × b denotes the vector product (or “cross product”) of − a − → and b , − → → (− a × b )x = a y b z − a zb y , − → → (1.58) (− a × b ) y = a zb x − a x b z, − → − → ( a × b )z = a x b y − a y b x . Together with the unit matrix 1, the matrices σ x , σ y , and σ z form a basis for the four-dimensional algebra of two-dimensional matrices of complex numbers: any such matrix is a unique linear combination of these four with complex coefﬁcients. Because the four are all Hermitian, any two-dimensional Hermitian matrix A of complex numbers must be a real linear combination of the four, and therefore of the form → → A = a0 1 + − a ·− σ, (1.59) → where a 0 and the components of the 3-vector − a are all real numbers. The matrices σ x , σ y , and σ z were introduced in the early days of quantum mechanics by Wolfgang Pauli, to describe the angular momentum associated with the spin of an electron. They have many other useful purposes, being simply related to the quaternions invented by Hamilton to deal efﬁciently with the composition of three-dimensional rotations.5 It is pleasing to ﬁnd them here, buried in the interior of the operator that simply swaps two classical bits. We shall have extensive occasion to use Pauli’s 1-Qbit operators when we come to the subject of 5 Hamilton’s quaternions i, j, k are represented by i σ x , i σ y , i σ z . The beautiful and useful connection between Pauli matrices and three-dimensional rotations discovered by Hamilton is developed in Appendix B. 1.5 QBITS AND THEIR STATES quantum error correction. Some of their properties, developed further in Appendix B, prove to be quite useful in treating Qbits, to which we now turn. 1.5 Qbits and their states The state of a Cbit is a pretty miserable specimen of a two-dimensional vector. The only vectors with any classical meaning in the whole twodimensional vector space are the two orthonormal vectors |0 and |1, since those are the only two states a Cbit can have. Happily, nature has provided us with physical systems, Qbits, described by states that do not suffer from this limitation. The state |ψ associated with a Qbit can be any unit vector in the two-dimensional vector space spanned by |0 and |1 over the complex numbers. The general state of a Qbit is α0 , (1.60) |ψ = α0 |0 + α1 |1 = α1 where α0 and α1 are two complex numbers constrained only by the requirement that |ψ, like |0 and |1, should be a unit vector in the complex vector space – i.e. only by the normalization condition |α0 |2 + |α1 |2 = 1. (1.61) The state |ψ is said to be a superposition of the states |0 and |1 with amplitudes α0 and α1 . If one of α0 and α1 is 0 and the other is 1 – i.e. the special case in which the state of the Qbit is one of the two classical states |0 or |1 – it can be convenient to retain the language appropriate to Cbits, speaking of the Qbit “having the value” 0 or 1. More correctly, however, one is entitled to say only that the state of the Qbit is |0 or |1. Qbits, in contrast to Cbits, cannot be said to “have values.” They have – or, more correctly, are described by, or, better still, are associated with – states. We shall often sacriﬁce correctness for ease of expression. Some reasons for this apparently pedantic terminological hair splitting will emerge below. Just as the general state of a single Qbit is any normalized superposition (1.60) of the two possible classical states, the general state | that nature allows us to associate with two Qbits is any normalized superposition of the four orthogonal classical states, ⎛α ⎞ 00 ⎜α ⎟ | = α00 |00 + α01 |01 + α10 |10 + α11 |11 = ⎝ 01 ⎠, α (1.62) 10 α11 with the complex amplitudes being constrained only by the normalization condition |α00 |2 + |α01 |2 + |α10 |2 + |α11 |2 = 1. (1.63) 17 18 CBITS AND QBITS This generalizes in the obvious way to n Qbits, whose general state can be any superposition of the 2n different classical states, with amplitudes whose squared magnitudes sum to unity: αx |xn , | = (1.64) 0≤x<2n |αx |2 = 1. (1.65) 0≤x<2n In the context of quantum computation, the set of 2n classical states – all the possible tensor products of n individual Qbit states |0 and |1 – is called the computational basis. For most purposes classical basis is a more appropriate term. I shall use the two interchangeably. The states that characterize n Cbits – the classical-basis states – are an extremely limited subset of the states of n Qbits, which can be any (normalized) superposition with complex coefﬁcients of these classical-basis states. If we have two Qbits, one in the state |ψ = α0 |0 + α1 |1 and the other in the state |φ = β0 |0 + β1 |1, then the state | of the pair, in a straightforward generalization of the rule for multi-Cbit states, is taken to be the tensor product of the individual states, | = |ψ ⊗ |φ = α0 |0 + α1 |1 ⊗ β0 |0 + β1 |1 = α0 β0 |00 + α0 β1 |01 + α1 β0 |10 + α1 β1 |11 ⎛α β ⎞ 0 0 ⎜ α0 β1 ⎟ . (1.66) =⎝ α1 β0 ⎠ α1 β1 Note that a general 2-Qbit state (1.62) is of the special form (1.66) if and only if α00 α11 = α01 α10 . Since the four amplitudes in (1.62) are constrained only by the normalization condition (1.63), this relation need not hold, and the general 2-Qbit state, unlike the general state of two Cbits, is not a product (1.66) of two 1-Qbit states. The same is true for states of n Qbits. Unlike Cbits, whose general state can only be one of the 2n products of |0s and |1s, a general state of n Qbits is a superposition of these 2n product states and cannot, in general, be expressed as a product of any set of 1-Qbit states. Individual Qbits making up a multi-Qbit system, in contrast to individual Cbits, cannot always be characterized as having individual states of their own.6 Such nonproduct states of two or more Qbits are called entangled states. The term is a translation of Schrödinger’s verschränkt, which I 6 More precisely, they do not always have what are called pure states of their own. It is often convenient to give a statistical description of an individual Qbit (or a group of Qbits) in terms of what is called a density matrix or mixed state. If one wishes to emphasize that one is not talking about a mixed state, one uses the term “pure state.” In this book the term “state” always means “pure state.” 1.6 REVERSIBLE OPERATIONS ON QBITS am told is rendered more accurately as “entwined” or “enfolded.” But Schrödinger himself used the English word “entangled,” and may even have used it before coining the German term. When the state of several Qbits is entangled, they can sometimes behave in some very strange ways. An example of such peculiar behavior is discussed in Appendix D. Aside from its intrinsic interest, the appendix provides some further exercise in the analytical manipulation of Qbits. 1.6 Reversible operations on Qbits The only nontrivial reversible operation a classical computer can perform on a single Cbit is the NOT operation X. Nature has been far more versatile in what it allows us to do to a Qbit. The reversible operations that a quantum computer can perform upon a single Qbit are represented by the action on the state of the Qbit of any linear transformation that takes unit vectors into unit vectors. Such transformations u are called unitary and satisfy the condition7 uu† = u† u = 1. (1.67) Since any unitary transformation has a unitary inverse, such actions of a quantum computer on a Qbit are reversible. The reason why reversibility is crucial for the effective functioning of a quantum computer will emerge in Chapter 2. The most general reversible n-Cbit operation in a classical computer is a permutation of the (2n )! different classical-basis states. The most general reversible operation that a quantum computer can perform upon n Qbits is represented by the action on their state of any linear transformation that takes unit vectors into unit vectors – i.e. any 2n -dimensional unitary transformation U, satisfying UU† = U† U = 1. (1.68) Any reversible operation on n Cbits – i.e. any permutation P of the 2n Cbit states – can be associated with a unitary operation U on n Qbits. One deﬁnes the action of U on the classical-basis states of the Qbit to be identical to the operation of P on the corresponding classical states of the Cbit. Since the classical basis is a basis, U can be extended to arbitrary n-Qbit states by requiring it to be linear. Since the action of U on the classical-basis states is to permute them, its effect on any superposition of such states αx |xn is to permute the amplitudes |αx |2 , so U takes αx . Such a permutation preserves the value of unit vectors into unit vectors. Being norm-preserving and linear, U is indeed unitary. 7 These and other facts about linear operators on vector spaces over the complex numbers are also reviewed and summarized in Appendix A. 19 20 CBITS AND QBITS Many important unitary operations on Qbits that we shall be examining below are deﬁned in this way, as permutations of the classical-basis states, which are implicitly understood to be extended by linearity to all Qbit states. In particular, the transformations NOT, SWAP, and cNOT on Cbits are immediately deﬁned in this way for Qbits as well. But the available unitary transformations on Qbits are, of course, much more general than straightforward extensions of classical operations. We have already encountered two such examples, the operator Z and the Hadamard transformation H. Both of these take the classical-basis states of a Qbit into another orthonormal basis, so their linear extensions to all Qbit states are necessarily unitary. In designing quantum algorithms, the class of allowed unitary transformations is almost always restricted to ones that can be built entirely out of products of unitary transformations that act on only one Qbit at a time, called 1-Qbit gates, or that act on just a pair of Qbits, called 2-Qbit gates. This restriction is imposed because the technical problems of making higher-order quantum gates are even more formidable than the (already difﬁcult) problems of constructing reliable 1- and 2-Qbit gates. It turns out that this is not a fundamental limitation, since arbitrary unitary transformations can be approximated to an arbitrary degree of precision by sufﬁciently many 1- and 2-Qbit gates. We shall not prove this general result,8 because all of the quantum algorithms to be developed here will be explicitly built up entirely out of 1- and 2-Qbit gates. One very important illustration of the sufﬁciency of 1and 2-Qbit gates will emerge in Chapter 2. For a reversible classical computer, it can be shown that at least one 3-Cbit gate is needed to build up general logical operations. But, in a quantum computer, we shall ﬁnd, remarkably – and importantly for the feasibility of practical quantum computation – that the quantum extension of this 3-Cbit gate can be constructed out of a small number of 1- and 2-Qbit gates. While unitarity is generally taken to be the hallmark of the transformations nature allows us to perform on quantum states, what is really remarkable about the transformations of Qbit states is their linearity (which is, of course, one aspect of their unitarity). It is easy to dream up simple classical models for a Qbit, particularly if one restricts its states to real linear combinations of the two computational basis states. It is not hard to invent classical models for NOT and Hadamard 1Qbit gates that act linearly on all the 1-Qbit states of the model Qbit. But I know of no classical model that can extend a cNOT on the four computational basis states of two Cbits to an operation that acts 8 The argument is given by David P. DiVincenzo, “Two-bit gates are universal for quantum computation,” Physical Review A 51, 1015–1022 (1995), http://arxiv.org/abs/quant-ph/9407022. 1.7 CIRCUIT DIAGRAMS y u u y Fig 1.1 A circuit diagram representing the action on a single Qbit of the 1-Qbit gate u. Initially the Qbit is described by the input state |ψ on the left. The thin line (wire) represents the subsequent history of the Qbit. After emerging from the box representing u, the Qbit is described on the right by the ﬁnal state u|ψ. Ψ U UΨ Fig 1.2 A circuit diagram representing the action on n Qbits of the n-Qbit gate U. Initially the Qbits ares described by the input state | on the left. The thick line (bar) represents the subsequent history of the Qbits. After emerging from the box representing U, the Qbits are described on the right by the ﬁnal state U|. linearly on all the states of two model Qbits. It is a remarkable and highly nontrivial fact about the physical world that nature does allow us, with much ingenuity and hard work, to fabricate unitary cNOT gates for a pair of genuine quantum Qbits. 1.7 Circuit diagrams It is the practice in quantum computer science to represent the action of a sequence of gates acting on n Qbits by a circuit diagram. The initial state of the Qbits appears on the left, the ﬁnal state on the right, and the gates themselves in the central part of the ﬁgure. Figure 1.1 shows the simplest possible such diagram: a Qbit initially in the state |ψ is acted on by a 1-Qbit gate u, with the result that the Qbit is assigned the new state u|ψ. Figure 1.2 shows the analogous diagram for an n-Qbit gate U and an n-Qbit initial state |. The line that goes into and out of the box representing the unitary transformation – which becomes useful when one starts chaining together a sequence of gates – is sometimes called a wire in the case of a single Qbit, and the thicker line (which represents n wires) associated with an n-Qbit gate is sometimes called a bar. Figure 1.3 reveals a peculiar feature of these circuit diagrams that it is important to be aware of. The diagrams are read from left to right (as one reads ordinary prose in European languages). Part (a) portrays a circuit that acts ﬁrst with V and then with U on the initial state |. The result is the state UV|, because it is the convention, in writing equations for linear operators on vector spaces, that the operation appears to the 21 22 Fig 1.3 (a) A circuit diagram representing the action on n Qbits of two n-Qbit gates. Initially the Qbits are described by the input state | on the left. They are acted upon ﬁrst by the gate V and then by the gate U, emerging on the right in the ﬁnal state UV|. Note that the order in which the Qbits encounter unitary gates in the ﬁgure is opposite to the order in which the corresponding symbols are written in the symbol for the ﬁnal state on the right. (b) This emphasizes the unfortunate convention that, because gates on the left act before gates on the right in a circuit diagram, a circuit showing V on the left and U on the right represents the operation conventionally denoted by UV. CBITS AND QBITS Ψ V UV Ψ U (a) V = U UV (b) left of the state on which it acts. Thus the sequence of symbols |, V, and U on the left of the circuit diagram in (a) is reversed from the sequence in which they appear in the mathematical representation of the state that is produced on the right. Part (b) shows the consequences of this for the part of the circuit diagram containing just the gates: a diagram in which a gate V (on the left) is followed by a gate U on the right describes the unitary transformation UV. One should be wary of the possibility for confusion arising from the fact that operators (and states) in circuit diagrams always appear in the diagrams in the opposite sequence from the order in which they appear on the page in the corresponding equations. While several of the most important diagrams we shall encounter are left–right symmetric, many are not, so one should be on guard against getting things backwards when translating equations into circuit diagrams and vice versa. In lecturing on quantum computation I tried for several years to reverse the computer-science convention, putting the initial state on the right of the circuit diagram and letting the gates on the right act ﬁrst. This has the great advantage of making the diagram look like the equation it represents. It has, however, a major disadvantage, even setting aside the fact that it ﬂies in the face of well established convention. It requires one to write on the blackboard in the wrong direction, from right to left, whenever one wishes to produce a circuit diagram. Guessing how far to the right one should start is hard to do if the diagram is a lengthy one, and for this reason I gave up after a few years and reverted to the conventional form. A better alternative would be for physicists to start writing their equations with the states on the left (represented by bra vectors rather than ket vectors9 ) and with linear operators appearing to the right of the states on which they act. But this would require abandoning a tradition that goes back three quarters of a century. So we are stuck with a clash of cultures, and must simply keep in mind that confusion can arise if one forgets the elementary fact represented in Figure 1.3(b). There is little utility to circuit diagrams of the simple form in Figures 1.1–1.3, but they are important as building blocks out of which 9 See Appendix A for the distinction between bras and kets. 1.8 MEASUREMENT GATES AND THE BOR N RULE larger circuit diagrams are constructed. As the number of operations increases, the diagrams enable one to see at a glance the action of a sequence of 1- and 2-Qbit unitary gates on a collection of many Qbits in a way that is far more transparent and much more easily remembered than the corresponding formulae. Indeed, many calculations that involve rather lengthy equations can be simply accomplished by manipulating circuit diagrams, as we shall see. When the state vectors entering or leaving a wire or bar in a circuit diagram are computational-basis states like |x, one sometimes omits the symbol | and simply writes x. 1.8 Measurement gates and the Born rule To give the state of a single Cbit you need only one bit of information: whether the state of the Cbit is |0 or |1. But to specify the state (1.60) of a single Qbit to an arbitrarily high degree of precision, you need arbitrarily many bits of information, since you must specify two complex numbers α and β subject only to the normalization constraint (1.61). Because Qbits not only have a much richer set of states than Cbits, but also can be acted on by a correspondingly richer set of transformations, it might appear obvious that a quantum computer would be vastly more powerful than a classical computer. But there is a major catch! The catch is this: if you have n Cbits, each representing either 0 or 1, you can ﬁnd out the state of each just by looking. There is nothing problematic about learning the state of a Cbit, and hence learning the result of any calculation you may have built up out of operations on those Cbits. Furthermore – and this is taken for granted in any discussion of a classical computer – the state of Cbits is not altered by the process of reading them. The act of acquiring the information from Cbits is not disruptive. You can read the Cbits at any stage of a computation without messing up subsequent stages. In stark contrast, if you have n Qbits in a superposition (1.64) of computational basis states, there is nothing whatever you can do to them to extract from those Qbits the vast amount of information contained in the amplitudes αx . You cannot read out the values of those amplitudes, and therefore you cannot ﬁnd out what the state is. The state of n Qbits is not associated with any ascertainable property of those Qbits, as it is for Cbits. There is only one way to extract information from n Qbits in a given state. It is called making a measurement.10 Making a measurement 10 Physicists will note – others need pay no attention to this remark – that what follows is more accurately characterized as “making a (von Neumann) measurement in the computational (classical) basis.” There are other ways 23 24 CBITS AND QBITS consists of performing a certain test on each Qbit, the outcome of which is either 0 or 1. The particular collection of zeros and ones produced by the test is not in general determined by the state | of the Qbits; the state determines only the probability of the possible outcomes, according to the following rule: the probability of getting a particular result – say 01100, if you have ﬁve Qbits – is given by the squared magnitude of the amplitude of the state |01100 in the expansion of the state | of the Qbits in the 25 computational basis states. More generally, if the state of n Qbits is |n = αx |xn , (1.69) 0≤x<2n then the probability that the zeros and ones resulting from measurements of all the Qbits will give the binary expansion of the integer x is p(x) = |αx |2 . (1.70) This basic rule for how information can be extracted from a quantum state was ﬁrst enunciated by Max Born, and is known as the Born rule. It provides the link between amplitudes and the numbers you can actually read out when you test – i.e. measure – the Qbits. The squared magnitudes of the amplitudes give the probabilities of outcomes of measurements. Normalization conditions like (1.65) are just the requirements that the probabilities for all of the 2n mutually exclusive outcomes add up to 1. The process of measurement is carried out by a piece of hardware with a digital display, known as an n-Qbit measurement gate. Such an n-Qbit measurement gate is depicted schematically in Figure 1.4. In contrast to unitary gates, which have a unique output state for each input state, the state of the Qbits emerging from a measurement gate is only statistically determined by the state of the input Qbits. In further contrast to unitary gates, the action of a measurement gate cannot be undone: given the ﬁnal state |x, there is no way of reconstructing the initial state |. Measurement is irreversible. Nor is the action of a measurement gate in any sense linear. To the extent that it suggests that some preexisting property is being revealed, “measurement” is a dangerously misleading term, but it is to make such a measurement, but they can all be reduced to measurements in the computational basis if an appropriate unitary transformation is applied to the n-Qbit state of the computer just before carrying out the measurement. In this book the term “measurement” always means measurement in the computational basis. Measurements in other bases will always be treated as measurements in the computational basis preceded by suitable unitary transformations. There are also more general forms of measurement than von Neumann measurements, going under the unpleasant acronym POVM (for “positive operator-valued measure”). We shall make no explicit use of POVMs. 1.8 MEASUREMENT GATES AND THE BOR N RULE x Ψ n = Σ ax x n Mn x n p = ax 2 Fig 1.4 A circuit diagram representing an n-Qbit measurement gate. The Qbits are initially described by the n-Qbit state |n = αx |xn , 0≤x<2n on the left. After the measurement gate Mn has acted, with probability p = |αx |2 it indicates an integer x, 0 ≤ x < 2n , and the Qbits are subsequently described by the state |xn on the right. hallowed by three quarters of a century of use by quantum physicists, and impossible to avoid in treatments of quantum computation. One should avoid being misled by such spurious connotations of “measurement,” though it confused many physicists in the early days of quantum mechanics and may well continue to confuse some to this day. In quantum computation “measurement” means nothing more or less than applying and reading the display of an appropriate measurement gate, whose action is fully speciﬁed by the Born rule, as described above, and expanded upon below. While measurement in quantum mechanics is not at all like measuring somebody’s weight, it does have some resemblance to measuring Alice’s IQ , which, one can argue, reveals no preexisting numerical property of Alice, but only what happens when she is subjected to an IQ test. The simplest statement of the Born rule is for a single Qbit. If the state of the Qbit is the superposition (1.60) of the states |0 and |1 with amplitudes α0 and α1 then the result of the measurement is 0 with probability |α0 |2 and 1 with probability |α1 |2 . This measurement is carried out by a 1-Qbit measurement gate, as illustrated in Figure 1.5. We shall see below that n-Qbit measurement gates can be realized by applying 1-Qbit measurement gates to each of the n Qbits. The process of measurement can thus be reduced to applying multiple copies of a single elementary piece of hardware: the 1-Qbit measurement gate. In addition to displaying an n-bit integer with probabilities determined by the amplitudes, there is a second very important aspect of the action of measurement gates: if n Qbits, initially described by a state |, are sent through an n-Qbit measurement gate, and the display of the measurement gate indicates the integer x, then one must associate with the Qbits emerging from that measurement gate the classical-basis state |xn , as shown in Figures 1.4 and 1.5. This means that all traces of the amplitudes αx characterizing the input state have vanished from the output state. The only role they have played in the measurement is to determine the probability of a particular output. 25 26 CBITS AND QBITS Fig 1.5 A special case of Figure 1.4: a 1-Qbit measurement gate. The reading x of the gate is either 0 or 1. y = a0 0 + a1 1 x M x p = ax 2 If the state of the input Qbits is one of the classical-basis states |xn , then according to the Born rule the probability that the measurement gate will read x and the output state will remain |xn is 1. But for superpositions (1.69) with more than a single nonzero amplitude αx , the output state is not determined. Being a single one of the classical basis states |xn , the output state no longer carries any information about the amplitudes characterizing the initial state, other than certifying that the particular amplitude αx was not zero, and, in all likelihood, was not exceedingly small. So once you send n Qbits through an n-Qbit measurement gate, you remove the possibility of extracting any further information about their original state |. After such a measurement of ﬁve Qbits, if the result is 01100, then the post-measurement state associated with the Qbits is no longer |, but |01100. The original state |, with all the rich information potentially available in its amplitudes, is irretrievably lost. Qbits emerging from a measurement gate that indicates the outcome x are characterized by the state |x, regardless of what their pre-measurement state may have been. This change of state attendant upon a measurement is often referred to as a reduction or collapse of the state. One says that the premeasurement state reduces or collapses to the post-measurement state, as a consequence of the measurement. This should not be taken to imply (though, alas, it often is) that the Qbits themselves suffer a catastrophic “reduction” or “collapse.” It is important to keep in mind, in this context, that the state of n Qbits is nothing more than an abstract symbol, used, via the Born rule, to calculate probabilities of measurement outcomes. As has already been noted, there is no internal property of the Qbits that corresponds to their state. You might well wonder how one can learn anything at all of computational interest under these wretched conditions. The artistry of quantum computation consists of producing, through a cunningly constructed unitary transformation, a superposition in which most of the amplitudes αx are zero or extremely close to zero, with useful information being carried by any of the values of x that have an appreciable probability of being indicated by the measurement. It is thus important to be seeking information that, once possessed, can easily be conﬁrmed, perhaps with an ordinary (classical) computer (e.g. the factors of a large number), so that one is not misled by rare and irrelevant low-probability outcomes. How this is actually accomplished in various cases of interest will be one of our major preoccupations. It is important to note and immediately reject a possible misunderstanding of the Born rule. One might be tempted to infer from 1.8 MEASUREMENT GATES AND THE BOR N RULE the rule that for a Qbit to be in a superposition, such as the state |ψ = α0 |0 + α1 |1, means nothing more than that the “actual state” of the Qbit is either |0 with probability |α0 |2 or |1 with probability |α1 |2 . Such an assertion goes beyond the rule, of course, which merely asserts that if one subjects a Qbit in the state |ψ to an appropriate test – a measurement – then the outcome of the test will be 0 or 1 with those probabilities and the post-measurement state of the Qbit can correspondingly be taken to be |0 or |1. This does not imply that prior to the test the Qbit already carried the value revealed by the test and was already described by the corresponding classical-basis state, since, among other possibilities, the action of the test itself might well play a role in bringing forth the outcome. In fact, it is easy to produce examples that demonstrate that the Qbit, prior to the test, could not have been in either of the states |0 and |1. We can see this with the help of the Hadamard transformation (1.41). We have deﬁned the action of the 1-Qbit operators H, X, and Z only on the computational-basis states |0 and |1, but, as noted above, we can extend their action to arbitrary linear combinations of these states by requiring the extensions to be linear operators. Since the states |0 and |1 form a basis, this determines the action of H, X, and Z on any 1-Qbit state. Because it is linear and norm-preserving, H is unitary, and is therefore the kind of operation a quantum computer can apply to the state of a Qbit: a 1-Qbit gate. The result of the operation of a Hadamard gate is to change the state |φ of a Qbit to H|φ. Suppose, now, that we apply H to a Qbit that is initially in the state |φ = √1 (|0 2 + |1). (1.71) It follows from (1.45) that the result is just H|φ = |0. (1.72) So according to the Born rule, if we measure a Qbit described by the state H|φ, the result will be 0 with probability 1. But suppose that a Qbit in the state |φ were indeed either in the state |0 with probability 12 or in the state |1 with probability 12 . In either case, according to (1.45), the subsequent√action of H would produce √ a state – either (1/ 2)(|0 + |1) or (1/ 2)(|0 − |1) – that under measurement yielded 0 or 1 with equal probability. This contradicts the fact just extracted directly from (1.72) that the result of making a measurement on a Qbit in the state H|φ is invariably 0. So a Qbit in a quantum superposition of |0 and |1 cannot be viewed as being either in the state |0 or in the state |1 with certain probabilities. Such a state represents something quite different. Although the Qbit reveals only a 0 or a 1 when you query it with a measurement gate, 27 28 CBITS AND QBITS prior to the query its state is not in general either |0 or |1, but a superposition of the form (1.60). Such a superposition is as natural and irreducible a description of a Qbit as |0 and |1 are. This point is expanded on in Appendix C. If the states of n Qbits are restricted to computational-basis states then the process of measurement is just like the classical process of “learning the value” of x without altering the state. Thus a quantum computer can be made to simulate a reversible classical computer by allowing only computational-basis states as input, and using only unitary gates that take computational-basis states into computational-basis states. The Born rule, relating the amplitudes αx in the expansion (1.64) of a general n-Qbit state | to the probabilities of measuring x, is often stated in terms of inner products or projection operators.11 The probability of a measurement giving the result x (0 ≤ x < 2n ) is p (x) = | αx |2 = | x||2 . (1.73) It can also be usefully expressed in terms of projection operators: p (x) = x| |x = x|P |x (1.74) p (x) = |x x| = |Px |, (1.75) or where P = | | is the projection operator on the state |, and Px = |x x| is the projection operator on the state |x. 1.9 The generalized Born rule There is a stronger version of the Born rule, which plays an important role in quantum computation, even though, surprisingly, it is rarely explicitly mentioned in most standard quantum-mechanics texts. We shall call it the generalized Born rule. This stronger form applies when one measures only a single one of n + 1 Qbits, by sending it through a standard 1-Qbit measurement gate. To formulate the generalized Born rule, note that any state of all n + 1 Qbits can be represented in the form |n+1 = α0 |0|0 n + α1 |1|1 n , |α0 |2 + |α1 |2 = 1, (1.76) 11 The Dirac notation for inner products and projection operators is described in Appendix A. 1.9 THE GENERALIZED BORN RULE x Ψ = a 0 0 Φ0 x M + a 1 1 Φ1 p = ax 2 Φx where |0 n and |1 n are normalized (but not necessarily orthogonal). This follows directly from the general form, |n+1 = 2n+1 −1 2n+1 −1 γ (x)|xn+1 , x=0 |γ (x)|2 = 1. (1.77) x=0 The states |0 n and |1 n are given by |0 n = (1/α0 ) 2n −1 γ (x)|xn , |1 n = (1/α1 ) x=0 2n −1 γ (2n + x)|xn , x=0 (1.78) where α02 = 2n −1 | γ (x)| , 2 x=0 α12 = 2n −1 |γ (2n + x)|2 . (1.79) x=0 (The α0 and α1 in (1.78) and (1.79) are real numbers, but can be multiplied by arbitrary phase factors if |0 n and |1 n are multiplied by the inverse phase factors.) The generalized Born rule asserts that if one measures only the single Qbit whose state symbol is explicitly separated out from the others in the (n + 1)-Qbit state (1.76), then the 1-Qbit measurement gate will indicate x (0 or 1) with probability |αx |2 , after which the (n + 1)-Qbit state can be taken to be the product state |x|x n . (The rule holds for the measurement of any single Qbit – there is nothing special about the Qbit whose state symbol appears on the left in the (n + 1)-Qbit state symbol.) This action of a 1-Qbit measurement gate on an (n + 1)-Qbit state is depicted schematically in Figure 1.6. If the Qbit on which the 1-Qbit gate acts is initially unentangled with the remaining n Qbits, then the action of the gate on the measured Qbit is just that speciﬁed by the ordinary Born rule, and the unmeasured Qbits play no role at all, remaining in their original state throughout the process. This is evident from the above statement of the generalized Born rule, specialized to the case in which the two states |0 n and |1 n are identical. It is illustrated in Figure 1.7. If one applies the generalized Born rule n times to successive 1-Qbit measurements of each of n Qbits, initially in the general n-Qbit state (1.69), one can show by a straightforward argument, given in Appendix E, that the ﬁnal state of the n Qbits is x with probability |αx |2 , where x is the n-bit integer whose bits are given by the readings 29 Fig 1.6 The action of a 1-Qbit measurement gate on a single one of n + 1 Qbits, according to the generalized Born rule. The initial state (on the left) is a general (n + 1)-Qbit state, expressed in the form |n+1 = a 0 |0|0 n + a 1 |1|1 n . Only the single Qbit on the left of this expression is subjected to a measurement gate. 30 CBITS AND QBITS Fig 1.7 A simpliﬁcation of Figure 1.6 when |0 = |1 = |. In this case the initial state on the left is just the product state |n = |ψ| = a 0 |0 + a 1 |1 |, and the ﬁnal state of the unmeasured Qbits continues to be | regardless of the value of x indicated by the 1-Qbit measurement gate. The unmeasured Qbits are unentangled with the measured Qbit and described by the state | throughout the process. The 1-Qbit measurement gate acts on the measured Qbit exactly as it does in Figure 1.5 when no other Qbits are present, and the generalized Born rule of Figure 1.6 reduces to the ordinary Born rule. x y = a 0 +a 1 0 1 M Φ x p = ax 2 Φ on the n 1-Qbit measurement gates. This is nothing but the ordinary Born rule, with the n 1-Qbit measurement gates playing the role of the single n-Qbit measurement gate. There is thus, as remarked upon above, only a single primitive piece of measurement hardware: the 1Qbit measurement gate. The construction of an n-Qbit measurement gate out of n 1-Qbit measurement gates is depicted in Figure 1.8. An even more general version of the Born rule follows from the generalized Born rule itself. The general state of m + n Qbits can be written as 2m |m +n = αx |xm |x n , (1.80) x=0 where x |αx |2 = 1 and the states |x n are normalized, but not necessarily orthogonal. By applying the generalized Born rule m times to m Qbits in an (m + n)-Qbit state, one establishes the rule that if just the m Qbits on the left of (1.80) are measured, then with probability |αx |2 the result will be x, and after the measurement the state of all m + n Qbits will be the product state |xm |x n (1.81) in which the m measured Qbits are in the state |xm and the n unmeasured ones are in the state |x n . 1.10 Measurement gates and state preparation In addition to providing an output at the end of a computation, measurement gates also play a crucial role (which is not often emphasized) at the beginning. Since there is no way to determine the state of a given collection of Qbits – indeed, in general such a collection might be entangled with other Qbits and therefore not even have a state of its own – how can one produce a set of Qbits in a deﬁnite state for the gates of a quantum computer to transform into another computationally useful state? The answer is by measurement. If one takes n Qbits off the shelf, and subjects them to an n-Qbit measurement gate that registers x, then the Qbits emerging from that gate are assigned the classical-basis state |xn . If one then applies the 1-Qbit operation X to each Qbit that registered a 1 in the measurement, doing nothing to the Qbits that 1.10 MEASUREMENT GATES AND STATE PREPARATION x3 M x2 M x M = x1 M x0 M registered 0, the resulting set of Qbits will be described by the state |0n . It is this state that most quantum-computational algorithms take as their input. Such a use of a measurement gate to produce a Qbit described by the state |0 is shown in Figure 1.9. Measurement gates therefore play two roles in a quantum computation. They get the Qbits ready for the subsequent action of the computer, and they extract from the Qbits a digital output after the computer has acted. The initial action of the measurement gates is called state preparation, since the Qbits emerging from the process can be characterized by a deﬁnite state. The association of unitary operators with the gates that subsequently act on the Qbits permits one to update that initial state assignment into the corresponding unitary transformation of the initial state, thereby making it possible to calculate, using the Born rule, the probabilities of the outcomes of the ﬁnal measurement gates. This role of measurement gates in state preparation follows from the Born rule if the Qbits that are to be prepared already have a state of their own, even though that state might not be known to the user of the quantum computer. It also follows from the generalized Born rule if the Qbits already share an entangled state – again, not necessarily known to the user – with additional (unmeasured) Qbits. But one cannot deduce from the Born rules that measurement gates serve to prepare states for Qbits “off the shelf,” whose past history nobody knows anything about. In such cases the use of measurement gates to assign a state to the Qbits is a reasonable and plausible extension of the Born rules. It is consistent with them, but goes beyond them. For particular physical realizations of Qbits, there may be other ways to produce the standard initial state |0n . Suppose, for example, that each Qbit is an atom, the state |0 is the lowest-energy state (the ground state) of the atom, and the state |1 is the atomic state of next-lowest 31 Fig 1.8 Constructing a 4-Qbit measurement gate out of four 1-Qbit measurement gates. The integer x has the binary expansion x3 x2 x1 x0 . 32 CBITS AND QBITS Fig 1.9 Using a 1-Qbit measurement gate to prepare an off-the-shelf Qbit so that its associated state is |0. The input on the left is a Qbit in an unknown condition – i.e. nothing is known of its past history. After the measurement gate is applied, the NOT gate X is or is not applied, depending on whether the measurement gate indicates 1 or 0. The Qbit that emerges (on the right) is described by the state |0. x ? M X x 0 energy (the ﬁrst excited state). Then one can produce the state |0n by cooling n such atoms to an appropriately low temperature (determined by the energy difference between the two states – the smaller that energy, the lower the temperature must be). From the conceptual point of view, state preparation by the use of measurement gates is the simplest way. An acceptable physical candidate for a Qbit must be a system for which measurement gates are readily available. Otherwise there would be no way of extracting information from the computation, however well the unitary gates did their job. So the hardware for state preparation by measurement is already there. Whether one chooses to use it or other (e.g. cryogenic) methods to initialize the Qbits to the state |0n is a practical matter that need not concern us here. It is enough to know that it can always be done with measurement gates. 1.11 Constructing arbitrary 1- and 2-Qbit states The art of quantum computation is to construct circuits out of 1and 2-Qbit gates that produce ﬁnal states capable of revealing useful information, when measured. The expectation is that 1-Qbit gates will be comparatively easy to construct. Two-Qbit gates that are not mere tensor products of 1-Qbit gates are likely to be substantially more difﬁcult to make. Attention has focused strongly on the cNOT gate, and gates that can be constructed from it in combination with 1-Qbit unitaries. All of the circuits we shall be examining can, in fact, be reduced to combinations of 1-Qbit gates and 2-Qbit cNOT gates. Given the difﬁculty in making cNOT gates, it is generally considered desirable to keep their number as small as possible. As an illustration of such constructions, we now examine how to assign arbitrary states to one or two Qbits, starting with the standard 1-Qbit state |0 or the standard 2-Qbit state |00. (Both of these standard states can be produced with the help of measurement gates, as described in Section 1.10.) The situation for 1-Qbit states is quite simple. Let |ψ be any 1-Qbit state, and let |φ be the orthogonal state (unique to within an overall phase), satisfying φ|ψ = 0. Since |0 and |1 are linearly independent, there is a unique linear transformation taking them into |ψ and |φ. But, since |ψ and |φ are an orthonormal pair (as are |0 and |1), this linear transformation is easily veriﬁed to preserve the norm 1.11 CONSTRUCTING ARBITRARY 1- AND 2-QBIT STATES of arbitrary states, so it is a unitary transformation u. Thus, for any |ψ there is a 1-Qbit unitary gate u that takes |0 into |ψ: |ψ = u|0. (1.82) Things are more complicated for 2-Qbit states. An unentangled 2Qbit state, being the product of two 1-Qbit states, can be constructed out of |00 by the application of 1-Qbit unitaries to each of the two Qbits. But a general 2-Qbit state is entangled, and its production requires a 2-Qbit gate that is not just a tensor product of 1-Qbit unitaries. Interestingly, a single cNOT gate, combined with 1-Qbit unitaries, is enough to do the trick. To see this, note that the general 2-Qbit state, | = α00 |00 + α01 |01 + α10 |10 + α11 |11, (1.83) is of the form | = |0 ⊗ |ψ + |1 ⊗ |φ, (1.84) where |ψ = α00 |0 + α01 |1 and |φ = α10 |0 + α11 |1. Apply u ⊗ 1 to |, where u is a linear transformation, whose action on the computational basis is of the form u|0 = a|0 + b |1, u|1 = −b ∗ |0 + a ∗ |1; |a|2 + |b |2 = 1. (1.85) The transformation u is unitary because it preserves the orthogonality and normalization of the basis |0, |1. We have u ⊗ 1 | = a|0 + b |1 ⊗ |ψ + − b ∗ |0 + a ∗ |1 ⊗ |φ = |0 ⊗ |ψ + |1 ⊗ |φ , (1.86) where |ψ = a|ψ − b ∗ |φ, |φ = b |ψ + a ∗ |φ. (1.87) We would like to choose the complex numbers a and b to make |φ and |ψ orthogonal. The inner product φ |ψ is φ |ψ = a 2 φ|ψ − b ∗2 ψ|φ + ab ∗ ψ|ψ − φ|φ . (1.88) If φ|ψ = 0, then setting φ |ψ to 0 gives a quadratic equation for a/b ∗ , which has two complex solutions. If a in (1.85) is any nonzero complex number then either solution determines b , which, with a, gives a 1-Qbit unitary u for which u ⊗ 1 | = |0 ⊗ |ψ + |1 ⊗ |φ (1.89) where |ψ and |φ are orthogonal. If φ|ψ = 0 then (1.84) is already of this form with u = 1. 33 34 CBITS AND QBITS We can pick positive real numbers λ and µ so that |ψ = |ψ /λ and |φ = |φ /µ are unit vectors, making |ψ and |φ an orthonormal pair. They are therefore related to |0 and |1 by a unitary transformation v: |ψ = v|0, |φ = v|1. (1.90) Equation (1.89) then gives12 | = u† ⊗ v λ|0 ⊗ |0 + µ|1 ⊗ |1 . (1.91) We can write this as | = u† ⊗ v C10 λ|0 + µ|1 ⊗ |0. (1.92) Since | is a unit vector and unitary transformations preserve unit vectors, it follows f