Example: confidence

Quantum Computing - Lecture Notes - University of …

Quantum Computing - Lecture NotesMark Oskin Department of Computer Science and EngineeringUniversity of WashingtonAbstractThe following Lecture Notes are based on the bookQuantum Computation and Quantum In-formationby Michael A. Nielsen and Isaac L. Chuang. They are for a math-based quantumcomputing course that I teach here at the University of Washington to computer science grad-uate students (with advanced undergraduates admitted upon request). These Notes start with abrief linear algebra review and proceed quickly to cover everything from Quantum algorithmsto error correction techniques.

The following lecture notes are based on the book Quantum Computation and Quantum In-formation by Michael A. Nielsen and Isaac L. Chuang. They are for a math-based quantum ... Quantum mechanics is a mathematical language, much like calculus. Just as classical physics uses calculus to explain nature, quantum physics uses quantum mechanics to ...

Tags:

  Lecture, Notes, Computing, Lecture notes, Quantum, Calculus, Quantum computing

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Quantum Computing - Lecture Notes - University of …

1 Quantum Computing - Lecture NotesMark Oskin Department of Computer Science and EngineeringUniversity of WashingtonAbstractThe following Lecture Notes are based on the bookQuantum Computation and Quantum In-formationby Michael A. Nielsen and Isaac L. Chuang. They are for a math-based quantumcomputing course that I teach here at the University of Washington to computer science grad-uate students (with advanced undergraduates admitted upon request). These Notes start with abrief linear algebra review and proceed quickly to cover everything from Quantum algorithmsto error correction techniques.

2 The material takes approximately 16 hours of Lecture time topresent. As a service to educators, the LATEXandXfigsource to these Notes is available onlinefrom my home page: In addition, underthe section course material from my web page, in the spring quarter/2002 590mo class youwill find a sequence of homework assignments geared to computer scientists. Please feel free toadapt these Notes and assignments to whatever classes your may be teaching. Corrections andexpanded material are welcome; please send them by email The following work is supported in part by NSF CAREER Award Linear Algebra (short review)42 Postulates of Quantum 1: A Quantum bit.

3 2: Evolution of Quantum systems .. 3: Measurement .. 4: Multi-qubit 83 Entanglement94 Teleportation115 Super-dense Coding156 Deutsch s Algorithm .. 207 Bloch traveling backwards through control versus bitflips .. 288 Universal Quantum than two qubit controlled operations .. interesting gates .. Swap .. 3229 Shor s and order-finding .. Fourier Transform (QFT) .. s Algorithm the easy estimation .. s Algorithm Phase estimation fraction expansion .. Exponentiation.

4 4210 Grover s Algorithm4311 Error Shor s 3 qubit bit-flip code .. Protecting phase .. 7 Qubit Steane Recursive error correction and the threshold 5331 Linear Algebra (short review)The following linear algebra terms will be used throughout these - complex conjugateifZ=a+b ithenZ =a b ij i- vector, ket :::cn3775j i- vector, bra [c 1;c 2;:::;c n]h j i- inner product between vectorsj iandj for QC this is onCnspace notRn!Noteh j i=h j i Example:j i= 26i ,j i= 34 h j i=[2; 6i] 34 =6 24ij i j i- tensor product ofj iandj written asj ij iExample.

5 J ij i= 26i 34 =26642 32 46i 36i 43775=26646818i24i3775A - complex conjugate of 16i3i2+4i thenA = 1 6i 3i2 4i AT- transpose of 16i3i2+4i thenAT= 13i6i2+4i A - Hermitian conjugate (adjoint) of = AT ifA= 16i3i2+4i thenA = 1 3i 6i2 4i 4kj ik- norm of vectorj ikj ik=ph j iImportant for normalization ofj i=kj ikh jAj i- inner product ofj iandAj inner product ofA j iandj i2 Postulates of Quantum MechanicsAn important distinction needs to be made between Quantum mechanics, Quantum physics andquantum Computing . Quantum mechanics is a mathematical language, much like calculus .

6 Justas classical physics uses calculus to explain nature, Quantum physics uses Quantum mechanics toexplain nature. Just as classical computers can be thought of in boolean algebra terms, quantumcomputers are reasoned about with Quantum mechanics. There are four postulates to quantummechanics, which will form the basis of Quantum computers: Postulate 1:Definition of a Quantum bit, orqubit. Postulate 2:How qubit(s) transform (evolve). Postulate 3:The effect of measurement. Postulate 4:How qubits combine together into systems of Postulate 1: A Quantum bitPostulate 1 (Nielsen and Chuang, page 80): Associated to anyisolatedphysical system is a complex vector space with inner prod-uct ( a Hilbert space) known as the state space of the system.

7 The system iscompletely described by its state vector, which is aunit vectorin the system s statespace. Consider a single qubit - a two-dimensional state space. Letj 0iandj 1ibe orthonormal basisfor the space. Then a qubitj i=aj 0i+bj 1i. In Quantum Computing we usually label the basiswith some boolean name but note carefully that this isonlya name. For example,j 0i=j0iandj 1i=j1i. Making this more concrete one might imagine that j0i is being represented by anup-spin while j1i by a down-spin. The key is there is an abstraction between the technology5(spin state or other Quantum phenomena) and the logical meaning.

8 This same detachment occursclassically where we traditionally call a high positive voltage 1 and a low ground potential 0 .Note thatj i=aj0i+bj1imust be a unit vector. In other words,h j i=1orjaj2+jbj2=1. Forquantum computingfa;bg2 CThis formalism for a Quantum bit is a direct extension of one way to describe a classical is, way may write that a classical bitj iis in the statej i=xj0i+yj1i. The only differenceisxandyare defined not over the complex numbers but rather from the setf0;1g. That isfx;yg2f0;1g. The same normalization condition appliesjxj2+jyj2=1. This normalization condition isnot a property of Quantum mechanics but rather of probability Postulate 2: Evolution of Quantum systemsPostulate 2 (Nielsen and Chuang, page 81): The evolution of aclosedquantum system is described by aunitary is, the statej iof the system at timet1is related to the state ofj 0iof the systemat timet2by a unitary operatorUwhich depends only on timest1andt2.

9 0i=Uj fact thatUcannot depend onj iand only ont1andt2is a subtle and disappointing will see later that ifUcould depend onj ithen Quantum computers could easily solve NPcomplete problems! Conceptually think ofUas something you can apply to a Quantum bit but youcannot conditionally apply it. The transform occurs without any regard to the current state ofj :j i=aj0i+bj1iU= 0110 j 0i=Uj i= 0110 ab = ba =bj0i+aj1iExample:Letj i=1j0i+0j1i=j0iU=1p2 111 1 j 0i=Uj i=1p2 111 1 10 =1p2 11 =1p2j0i+1p2j1i6 Important:Umust be unitary, that isU U=IExample:U=1p2 111 1 thenU =1p2 111 1 U U=1p2 1p2 111 1 111 1 =12 2002 = Postulate 3: MeasurementPostulate 3 (Nielsen and Chuang, page 84): Quantum measurements are described by a collectionfMmgof measurement oper-ators.

10 These are operators acting on the state space of the system being indexmrefers to the measurement outcomes that may occur in the experiment. Ifthe state of the Quantum system isj iimmediately before the measurement then theprobability that resultmoccurs is given by:p(m)=h jM mMmj iand the state of the system after measurement is:Mmj iqh jM mMmj iThe measurement operators satisfy thecompleteness equation: mh jM mMmj i=IThe completeness equation expresses the fact that probabilities sum to one:1= mp(m)= mh jM mMmj i Some important measurement operators areM0=j0ih0jandM1=j1ih1jM0= 10 [1;0]= 1000 M1= 01 [0.]


Related search queries