5 0 0 2 v o N 0 3 Quantum Computation: 1 v A Computer Science Perspective 1 4 7 2 1 1 Anders K.H. Bengtsson 2 5 0 / February 22, 2005 h p - t n a u q : v i X r a 1Work supported by theSwedish KK-foundation underthePromoteIT program. 2e-mail: [email protected] Abstract Thetheoryofquantumcomputationispresentedinaselfcontainedwayfroma computerscienceperspective. Thebasicsofclassicalcomputationandquantum mechanicsis reviewed. The circuitmodel ofquantumcomputationis presented indetail. Throughoutthereisanemphasisonthephysicalaswellastheabstract aspects of computation and the interplay between them. ThisreportispresentedasaMaster’sthesisatthedepartmentofComputer Science and Engineering at G¨oteborg University, G¨oteborg, Sweden. Thetextispartofalargerworkthatisplannedtoincludechaptersonquan- tum algorithms, the quantum Turing machine model and abstract approaches to quantum computation. Contents 1 Introduction 7 1.1 The theory of computation . . . . . . . . . . . . . . . . . . . . . 8 1.2 The input/output model of physics and computation . . . . . . . 9 1.3 Classical physics and the computer . . . . . . . . . . . . . . . . . 10 1.4 Quantum computation . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Classical computation 13 2.1 Some definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.2 Computation . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1.3 Program. . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.4 Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.5 Alphabets, Strings and Numbers . . . . . . . . . . . . . . 16 2.1.6 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.1.7 Decision procedures and Computation procedures . . . . 19 2.2 A note on the connection to everyday computing . . . . . . . . . 20 2.3 The classical Turing machine model of computation . . . . . . . 20 2.3.1 Informal description of Turing machines . . . . . . . . . . 21 2.3.2 Formal definition of a Turing Machine Model . . . . . . . 22 2.3.3 Syntax and semantics . . . . . . . . . . . . . . . . . . . . 30 2.3.4 Decision procedures and Computation procedures revisited 30 2.3.5 The Church-Turing Thesis . . . . . . . . . . . . . . . . . . 31 2.3.6 Computability . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.7 Universal Turing machines. . . . . . . . . . . . . . . . . . 34 2.3.8 The halting problem is undecidable . . . . . . . . . . . . . 35 2.4 The classical circuit model of computation . . . . . . . . . . . . . 37 2.4.1 The circuit model and non-computable functions . . . . . 40 2.4.2 Reversible gates . . . . . . . . . . . . . . . . . . . . . . . 42 2.4.3 Reversible circuits and un-computation . . . . . . . . . . 45 2.4.4 Reversible computation and physics . . . . . . . . . . . . 46 2.5 Comparison to real computers . . . . . . . . . . . . . . . . . . . . 47 2.6 Non-deterministic Turing Machines . . . . . . . . . . . . . . . . . 48 2.6.1 A note on classical parallelism . . . . . . . . . . . . . . . 49 2.7 Probabilistic Turing machines . . . . . . . . . . . . . . . . . . . . 49 1 2.8 Some Complexity Theory . . . . . . . . . . . . . . . . . . . . . . 51 2.8.1 Measures of complexity . . . . . . . . . . . . . . . . . . . 52 2.8.2 Complexity classes . . . . . . . . . . . . . . . . . . . . . . 54 3 Algebra of quantum bits 57 3.1 Classical and quantum physical systems . . . . . . . . . . . . . . 57 3.2 Two-state quantum systems and the quantum bit . . . . . . . . . 58 3.3 Multiple qubit states . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.4 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4 Introduction to quantum mechanics 67 4.1 Quantum mechanics in one space dimension . . . . . . . . . . . . 69 4.1.1 Separation of space and time . . . . . . . . . . . . . . . . 71 4.1.2 Particle in a potential well. . . . . . . . . . . . . . . . . . 72 4.2 Linear harmonic oscillator . . . . . . . . . . . . . . . . . . . . . . 75 4.2.1 Quantization of the oscillator . . . . . . . . . . . . . . . . 76 4.2.2 Operators for momentum and position . . . . . . . . . . . 77 4.2.3 Commutators . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2.4 A note on classical dynamics . . . . . . . . . . . . . . . . 78 4.2.5 Quantization . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.2.6 Dirac notation, a case of abstraction . . . . . . . . . . . . 81 4.2.7 Summary of the classical harmonic oscillator . . . . . . . 82 4.2.8 Creation and annihilation operators . . . . . . . . . . . . 82 4.3 Angular momentum and spin . . . . . . . . . . . . . . . . . . . . 89 4.3.1 Spin 1/2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5 General quantum theory 97 5.1 State spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.1.1 Vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.1.2 Hilbert spaces. . . . . . . . . . . . . . . . . . . . . . . . . 100 5.1.3 Dirac notation . . . . . . . . . . . . . . . . . . . . . . . . 101 5.1.4 Tensor products . . . . . . . . . . . . . . . . . . . . . . . 102 5.2 Operators and dynamical variables . . . . . . . . . . . . . . . . . 103 5.2.1 Linear operators . . . . . . . . . . . . . . . . . . . . . . . 103 5.2.2 Outer products . . . . . . . . . . . . . . . . . . . . . . . . 105 5.2.3 Projectors . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 5.2.4 Adjoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.2.5 Composition of operators . . . . . . . . . . . . . . . . . . 109 5.3 Transformations and symmetries . . . . . . . . . . . . . . . . . . 109 5.4 Eigenvectors and eigenvalues . . . . . . . . . . . . . . . . . . . . 111 5.4.1 Spectral decomposition . . . . . . . . . . . . . . . . . . . 112 5.5 Quantum dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.5.1 Schr¨odinger picture. . . . . . . . . . . . . . . . . . . . . . 116 5.5.2 Heisenberg picture . . . . . . . . . . . . . . . . . . . . . . 116 5.6 Quantum measurement . . . . . . . . . . . . . . . . . . . . . . . 118 5.6.1 Projective measurement . . . . . . . . . . . . . . . . . . . 118 2 5.6.2 General measurement . . . . . . . . . . . . . . . . . . . . 119 5.6.3 POVM measurement . . . . . . . . . . . . . . . . . . . . . 120 6 Abstract quantum computation: The circuit model 121 6.1 Quantum alphabets, strings and languages. . . . . . . . . . . . . 121 6.2 The circuit model of quantum computation . . . . . . . . . . . . 124 6.2.1 Gates and wires . . . . . . . . . . . . . . . . . . . . . . . 126 6.2.2 General notation . . . . . . . . . . . . . . . . . . . . . . . 126 6.2.3 Special discrete one-qubit gates . . . . . . . . . . . . . . . 128 6.2.4 One-qubit rotation operators . . . . . . . . . . . . . . . . 128 6.2.5 The rotation operators and the Bloch sphere . . . . . . . 129 6.2.6 Single qubit phase-shift operators. . . . . . . . . . . . . . 130 6.2.7 Some special controlled operations . . . . . . . . . . . . . 130 6.2.8 Some practical ”machinery” . . . . . . . . . . . . . . . . . 132 6.2.9 Entanglement . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.2.10 Some important gate constructions . . . . . . . . . . . . . 137 6.2.11 Decomposing general two-level unitary operation on n- qubit states . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.2.12 Universal sets of quantum gates. . . . . . . . . . . . . . . 143 6.2.13 Exact and approximate universality . . . . . . . . . . . . 144 6.2.14 Exact universality of two-level unitaries . . . . . . . . . . 145 6.2.15 Summary of universality results . . . . . . . . . . . . . . . 146 6.2.16 Discrete sets of gates . . . . . . . . . . . . . . . . . . . . . 147 6.2.17 General results . . . . . . . . . . . . . . . . . . . . . . . . 148 3 Foreword Theintendedreadershipforthismaster’sthesisinComputerScienceisprimarily the computer scientist wishing to get an idea of what quantum computing is about. But I also have physicists in mind. Therefore, the physicist will find material on physics that will appear to be obvious and the computer scientist willfindmaterialoncomputersthatwilllikewiseappeartobetrivial. Soperhaps the reader who will benefit the most from the text is the one who is unfamiliar with both subjects. The point is that I’m actually not writing for the lucky fewwhohaveexpertiseinbothfields butratherforthosewhocomefromeither field, or from none of them. The text is thus basically introductory, but not elementary. There is also a further point. Since quantum computation straddles the borderline between physics and computing science, it is interesting to spell out the basic assumptions and facts of both fields in some detail. Obviously, this text can be seen as a review article. But I have no intention to treat every aspect of the subject which is simply to vast. The depth of the treatment will also vary considerably. Some basic definitions and some, in my opinion fundamental, results, will be spelt out in detail, whereas many topics thatacomprehensivetextwouldtreat,willbepassedoverrapidly. Theprinciple behind these choices is that I will attempt to be detailed on issues that has a bearing on the connections between physics and computation. What has been left out can be found in the textbook literature and original articles on the subject as well as in other review articles. The text is mostly written in theoretical physics style, introducing no more formalism than needed to make the arguments clear. The degree of formal- ization will vary. A high level of formalization throughout tends to make the text unreadable, whereas a low level of formalization might leave the reader unnecessarily confused. Definitions, derivations and results are presented and proved in the running text, but occasionally, due to the nature of subject, a more formal style will be adopted. I’ve chosen a level of formalization that I found appropriate and in the end it reflects my own taste. There are of course lots of review article on quantum computation. I have thereforedecidednottorepeattomuchofthestandardcalculationsandderiva- tions,insteadfocusingonwhatIfindinteresting,tryingtoputforwardaslightly differentperspective,andinsteadbeingdetailedonpointsthatareoftenglossed over. InthisrespectIhopethistextcanbeacomplementtothemanyexcellent 4 books and reviews already in circulation, a few of which are [1, 2, 3, 4, 39]. One seldom learns a subject by reading just one book or just one review article. In writing chapter 4 on introduction to quantum mechanics, I realized howmuchisleftimplicit,eventhoughyoutrytomakethetextselfcontained. If youhaven’talreadymastereda subject, perhapsyoucannotgainsomuchfrom just one review - you must read several articles and books to see the subject treated in different ways. Outline of contents Chapter 1 is an introduction to text and a motivation for studying quantum computation. Some fundamental questions on the connection between physics andcomputationwillbe mentioned. Theywillbereturnedtoinaplannedpart II of this work. Chapter2isanoverviewofthecentralconceptsofclassicalcomputationsuch as the notions of computational models, computability and complexity theory. TogetherwithChapter5ongeneralquantumtheoryitservesasthe foundation for a treatment of quantum computational models and quantum algorithms. Chapter 3 is a brief introductionto quantum computation. It servesmainly as motivating the subsequent two chapters on quantum mechanics. Chapter 4 contains a quite extensive introduction to quantum mechanics written in a physics style. Three important models are treated in some detail; a particle trapped in a potential well, the harmonic oscillator and the theory of angular momentum. Apart from being important in quantum physics, these models are the standard ones employed when teaching introductory quantum mechanics. Allconceptsofquantummechanicscanbeintroducedwhilestudying these simple models. Chapter 5 then sets up the formal theory of quantum mechanics in terms of linear operators on Hilbert spaces. After that, the stage is set for treating quantum computation. Chapter 6 describes in an abstract way the quantum circuit model. As this text is mainly on the abstract and theoretical aspects of classical and quantum computational models, not very much will be said on practical realizations of quantum computing devices, or quantum computers for short. Presumably, the theoretical aspects of the subject matter will remain relevant, whilethepractical,implementationaldetailsarelikelytoundergomoredramatic change. Onelastremark. MyinitialintentionswastotreatalsotheQuantumTuring machine model and quantum algorithms. However, the scope of the project would then have gone beyond the boundaries of a masters project. For this reason, these topics will be left for a part II. Acknowledgment This work was done with support from the Swedish Knowledge Foundation under the Promote IT program. 5 I wouldlike to thank professorBengtNordstro¨mfor supervising the project and for valuable discussions on computing science in general and the theory of computability in particular. IalsothankIngemarBengtssonforreadingandcommentingonthemanuscript. 6 Chapter 1 Introduction Computer science, and in particular the theory of computation, can be studied without explicit regard to physics. The whole area of research into classical computabilityisphrasedwithoutanyreferencetophysicsorevenrealcomputing machines. Therelatedareasofsyntaxandsemanticsofprogramminglanguages make no reference to anything more real than symbol shuffling by abstract machines. Classical computation is a discrete process. Whether viewed in terms of Turingmachines,RAM-machinesoroperationalsemanticsofprogramminglan- guages in terms of abstract stack machines1, it really just amounts to string processing or symbol manipulation. The number of symbols is finite and the number of basic operations is finite. A program is a finite set of instructions in terms of the operations acting on the set of strings built out of the symbols. Seen in this way, computation seems to be detached from physical reality, and any ’system’ that ’understands’ the rules can perform the computation. From a practical point of view, the software/hardwaredivision also stresses this apparent independence of physics. The software in the form of computer programs written in any of the many hundreds of invented programming lan- guagesareagainjuststringsofsymbols. Theyseemtohavenomoreconnection to physics than the ink with which they are recordedon paper. When they are compiledandstoredelectronically,the link with physicsis somewhatmorepro- nounced but still weak. It is upon actually running the program,which always entails the motion of some physical system, that the physical nature of compu- tation comes into focus. This is obvious if the algorithmis carriedout by hand or using some mechanical computing device. So there is a link, howeverweak, to some physical substratum, and it is not possible to severe this link completely. On the other hand, it is a fundamental propertyofrealitythatitis possibleworkandsolvecomputationalproblemsat abstractlevelswithouthavingtocheckphysicalrealizabilityateverystep. This isanalogoustothe processofabstractionwhichissocharacteristicofcomputer 1Anabstractstack machineisanotational system forgivingstep-by-stepmeaningtothe primitivesofaprogramminglanguage. 7 science. By abstraction, ever more powerful and complicated computational tools can be invented, which, once it has been ascertained that they can be implemented in terms of more primitive structures, can be used to solve more difficult computationalproblemswithout checking the implementation atevery step. Butifweworktheotherway,fromabstractlevelsofprogrammingstructures tomoreconcreteprimitives,theneventuallywewillarriveatsomephysicalsys- tem, a computing machine, that actually performs the physical motion needed in order to carry out the computations. In digital computers this is switching voltage levels in transistors, which in its turn involves the collective motion of large numbers of electrons. Thus,aswaspointedoutandstudiedbyLandauer[5],informationisalways carriedbysomephysicalmedium,andlikewisecomputationisaphysicalprocess constituted by some well defined motion of a physical system. 1.1 The theory of computation The theory of computation arosein the nineteen thirties as a response to prob- lemsinthefoundationsofmathematicsandlogic[6],inparticularinconnection toDavidHilbert’sEntscheidungsproblem. TheEntscheidungsproblemisaprob- lemwithintheformaloraxiomaticapproachtomathematics. Hilbert’sprogram was to formalize mathematical theories into a set of axioms defining relations between the undefined primitive notions of the theory, and a set of rules of de- duction. In this way one should be able secure the foundations of mathematics aswellasmechanizethe processoftheoremproving. Goodproperties,likecon- sistencyandcompleteness,shouldbe possibleto ascertainwithin the axiomatic system. The axiomatic approach itself has a long history dating back to antiquity. AftertheinventionofthecalculusbyNewtonandLeibnizinthemidseventeenth century,therewasaveryrapidprogressinthefieldsofappliedmathematicsand physics. The new mathematics was phrased in an axiomatic language but the underlyingconceptswereintuitiveandoftenvague. Inthebackgroundhistoryof Hilbert’s approachwe find attempts to secure the foundations of such concepts as infinitesimals, limits, real numbers, functions and derivatives to name a few. Asanasideitisinterestingtonotetheverycloseinterplaybetweenmathematics and physics during this period. Apart from being a theoretical subject of its own,mathematicsisalsothelanguageofthephysicalsciencesandoftechnology. Hilbert’s formalistic approach to mathematics made a distinction between thesyntacticaspectsofmathematics,i.e. theaxiomsandtherulesofdeduction, and the semantic aspects, i.e. what the mathematical concepts and theorems actually mean. Physicist, engineers and applied mathematicians are normally interested in the meaning of mathematics. Phenomena in the real world, and whole areas of science,aremodeledusingmathematics. Onthe otherhand,oncethemodeling isdone, the actualcalculationscanbe performedwithoutconsideringthe inter- 8