Quantum Computing - Lecture Notes
Quantum Computing - Lecture NotesMark Oskin Department of Computer Science and EngineeringUniversity of WashingtonAbstractThe following lecture notes are based on the book Quantum Computation and Quantum Information by 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 graduate 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 material takes approximately 16 hours of lecture time topresent. As a service to educators, the LATEXand Xfig source to these notes is available onlinefrom my home page: http://www.cs.washington.edu/homes/oskin. 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 to oskin@cs.washington.edu. Thefollowing work is supported in part by NSF CAREER Award ACR-0133188.1
Contents1 Linear Algebra (short review)42 Postulates of Quantum Mechanics52.1Postulate 1: A quantum bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52.2Postulate 2: Evolution of quantum systems . . . . . . . . . . . . . . . . . . . . . .62.3Postulate 3: Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.4Postulate 4: Multi-qubit systems . . . . . . . . . . . . . . . . . . . . . . . . . . .83 Entanglement94 Teleportation115 Super-dense Coding156 Deutsch’s Algorithm166.1Deutsch-Jozsa Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 Bloch Sphere227.1Phase traveling backwards through control operations . . . . . . . . . . . . . . . . 277.2Phaseflips versus bitflips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 Universal Quantum Gates298.1More than two qubit controlled operations . . . . . . . . . . . . . . . . . . . . . . 318.2Other interesting gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318.3Swap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
9 Shor’s Algorithm339.1Factoring and order-finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339.2Quantum Fourier Transform (QFT) . . . . . . . . . . . . . . . . . . . . . . . . . . 349.3Shor’s Algorithm – the easy way . . . . . . . . . . . . . . . . . . . . . . . . . . . 389.4Phase estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399.5Shor’s Algorithm – Phase estimation method . . . . . . . . . . . . . . . . . . . . 409.6Continuous fraction expansion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429.7Modular Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4210 Grover’s Algorithm4311 Error Correction4611.1 Shor’s 3 qubit bit-flip code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4711.2 Protecting phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5011.3 7 Qubit Steane code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5111.4 Recursive error correction and the threshold theorem . . . . . . . . . . . . . . . . 533
1 Linear Algebra (short review)The following linear algebra terms will be used throughout these notes.Z - complex conjugateif Z a b i then Z ab ijψi - vector,“ket”i.e.23c16 c2 7674 ::: 5cnjψi - vector, “bra” i.e.[c 1 ; c 2 ; :::; c n ]hϕjψi - inner product between vectors jϕi and jψi.Note for QC this is on C n space not R n !Note hϕjψi hψ jϕi 23Example: jϕi , jψi 6i4 hϕjψi [2; 6i] 34 6 24ijϕi jψi - tensor product of jϕi and jψi.Also written as jϕijψiExample: jϕijψi 26i 342 A - complex conjugateof matrixA. 16i then A if A 3i 2 4iAT - transpose of matrix A. 16ithen ATif A 3i 2 4i 322 36 2 4 7 67 6 64 6i 3 5 46i 413i 26i4i13i6i 2 4iA† - Hermitian conjugate (adjoint) of matrix A.†TNote A A 16i1†if A then A 6i 23i 2 4i4 3i4i 368 7718i 524i
k jψi k - norm ofpvector jψik jψi k hψjψiImportant for normalization of jψi i.e. jψi k jψi khϕjAjψi - inner product of jϕi and Ajψi.or inner product of A† jϕi and jψ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. 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, or qubit.Postulate 2: How qubit(s) transform (evolve).Postulate 3: The effect of measurement.Postulate 4: How qubits combine together into systems of qubits.2.1 Postulate 1: A quantum bitPostulate 1 (Nielsen and Chuang, page 80):“Associated to any isolated physical system is a complex vector space with inner product (i.e. a Hilbert space) known as the state space of the system. The system iscompletely described by its state vector, which is a unit vector in the system’s statespace.”Consider a single qubit - a two-dimensional state space. Let jφ 0 i and jφ1 i be orthonormal basisfor the space. Then a qubit jψi ajφ0i bjφ1 i. In quantum computing we usually label the basiswith some boolean name but note carefully that this is only a name. For example, jφ 0 i j0i andjφ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. This same detachment occursclassically where we traditionally call a high positive voltage “1” and a low ground potential “0”.Note that jψi aj0i bj1i must be a unit vector. In other words, hψjψi 1 or jaj 2 jbj2 1. Forquantum computing fa; bg 2 CThis formalism for a quantum bit is a direct extension of one way to describe a classical computer.That is, way may write that a classical bit jωi is in the state jωi xj0i yj1i. The only differenceis x and y are defined not over the complex numbers but rather from the set f0; 1g. That is fx; yg 2f0; 1g. The same normalization condition applies jxj2 jyj2 1. This normalization condition isnot a property of quantum mechanics but rather of probability theory.2.2 Postulate 2: Evolution of quantum systemsPostulate 2 (Nielsen and Chuang, page 81):“The evolution of a closed quantum system is described by a unitary transformation.That is, the state ψ of the system at time t 1 is related to the state of ψ0 of the systemat time t2 by a unitary operator U which depends only on times t 1 and t2 .”j ij iI.e. jψ0 i U jψi.The fact that U cannot depend on jψi and only on t 1 and t2 is a subtle and disappointing fact.We will see later that if U could depend on jψi then quantum computers could easily solve NPcomplete problems! Conceptually think of U as something you can apply to a quantum bit but youcannot conditionally apply it. The transform occurs without any regard to the current state of jψi.Example:jψi aj0i bj1iU 0 11 0jψ0i U jψi 0 11 0 ab ba bj0i aj1iExample:Let jψi 1j0i 0 j1i j0i11U p1211 111110ppjψ i U jψi 2 1 1 0 2 11 p12 j0i p12 j1i6
Important: U must be unitary, that is U †U IExample:U p12 11U †U p12 p1211 then U † p121111 11 11 11 11 122 00 2 I2.3 Postulate 3: MeasurementPostulate 3 (Nielsen and Chuang, page 84):f g“Quantum measurements are described by a collection M m of measurement operators. These are operators acting on the state space of the system being measured.The index m refers to the measurement outcomes that may occur in the experiment. Ifthe state of the quantum system is ψ immediately before the measurement then theprobability that result m occurs is given by:j i† M jψip(m) hψjMmmand the state of the system after measurement is:Mm jψiqhψjMm† Mm jψiThe measurement operators satisfy the completeness equation:† M jψi I m hψjMmmThe completeness equation expresses the fact that probabilities sum to one:†M ψ ”1 m p(m) m ψ Mmmh jj iSome important measurement operators are M0 j0ih0j and M1 j1ih1j M0 M1 1001 [1; 0] [0; 1] 1 00 00 00 1 Observe that M0† M0 M1† M1 I and are thus complete.Example:jψi aj0i bj1ip(0) hψjM0† M0 jψi7
Note that M0† M0 M0 , hence 1 0p(0) hψjM0 jψi [a ; b ] [a ; b ] a0 0 0 ab jaj2Hence the probability of measuring j0i is related to its probability amplitude a by way of jaj 2 .It important to note that the state after measurement is related to the outcome of the measurement.For example, suppose j0i was measured, then the state of the system after this measurement isre-normalized as:M0 jψiajaj jaj j0iAs a side note we are forced to wonder if Postulate 3 can be derived from Postulate 2. It seemsnatural given that measurement in the physical world is just interacting a qubit with other qubits.Thus it seems strange to have measurement be its own postulate. At this point though physicistsdon’t know how derive the measurement postulate from the other three, so we shall just have to bepragmatic and accept it.2.4 Postulate 4: Multi-qubit systemsPostulate 4 (Nielsen and Chuang, page 94):“The state space of a composite physical system is the tensor product of the statespaces of the component physical systems. [sic] e.g. suppose systems 1 through nand system i is in state ψi , then the joint state of the total system is ψ 1ψ2:::ψn .”j ij ij i j iExample:Suppose jψ1 i aj0i bj1i and jψ2 i cj0i d j1i, then:jψ1i jψ2 i jψ1ψ2 i a cj0ij0i a d j0ij1i b cj1ij0i b d j1ij1i acj00i ad j01i bcj10i bd j11iWhy the tensor product? This is not a proof, but one would expect some way to describe a composite system. Tensor product works for classical systems (except the restricted definition of theprobability amplitudes makes it so that the result is a simple concatenation). For quantum systemstensor product captures the essence of superposition, that is if system A is in state jAi and B in statejBi then there should be some way to have a little of A and a little of B. Tensor product exposesthis.8
3 EntanglementEntanglement is a uniquely quantum phenomenon. Entanglement is a property of a multi-qubitstate space (multi-qubit system) and can be thought of as a resource. To explain entanglement we’llexamine the creation and destruction of an EPR pair of qubits named after Einstein, Podolsky, andRosen.Suppose you begin with a qubit jψ 1 i in a zero j0i state.Let U H1 p2 1111 Then let jψ01 i H jψ1 i p1 j0i p1 j1i p1222j0i j1i)(Now take another qubit jψ2 i also in the zero j0i state. The joint state-space probability vector isthe tensor product of these two:jψ01i jψ2 i jψ01ψ2 i p12 j00i 0j01i p12 j10i 0j11iNow define a new unitary transform:216 0CNot 64 0001000001300 771 50(As an exercise show that CNot is unitary), but for now lets just apply CNot to our two qubits:216j (ψ01 ψ2 )00i CNot jψ01ψ2i 64 000010000013 2 1 3 2 p1 37 6 2 77 6 0 7 p17 67 2 ( 00 11 )5 4 0 5p02600 76761 5 4 p1200j i j ip12The key to entanglement is the property that the state space cannot be decomposed into componentspaces. That is, for our example, there does not exists any jϕ 1 i and jϕ2 i such that jϕ1 i jϕ2 i p1 (j00i j11i).2To illustrate why entanglement is so strange, lets consider performing a measurement just prior toapplying the CNot gate. The two measurement operators (for obtaining a j0i or a j1i) are:9
216 0M02 64 0000000010300 77 and M120 50206 0 64 0001000000300 770 51Recall that just prior to the CNot the system is in the state jψ 01 ψ2 i p1 j00i 0j01i 2p1 j10i 0j11i, hence the result of measuring the second qubit will clearly be j0i. Note that2M0†2 M02 M02 .Therefore:p(0) hψ01 ψ2 jM0†2 M02 jψ01 ψ2 i hψ01 ψ2 jM02 jψ01 ψ2 i 21i6h0p1 ; 0; p1 ; 0 642200After measurement: q00000010Mm jψihψj†MmMmjψi3232 1 3p17 hi6 2 776 0 7117 p2 ; 0; p2 ; 0 6 1 7 154 p 5p0260 706760 5 4 p1200 2 1 3p66 2 7766 0 7766 p1 774 2 50120 jψ01ψ2 iWe can see that measurement had no effect on the first qubit. It remains in a superposition of j0iand j1i. Now lets consider the same measurement but just after the CNot gate is applied. Here:jψi j (ψ01ψ2 )00i p12 (j00i j11i)Now it is not clear whether the second qubit will return a j0i or a j1i, both outcomes are equallylikely. To see this, lets calculate the probability of obtaining j0i:p(0) hψjM0†2 M02 jψi hψjM02 jψi 21i6h011 p ; 0; 0; p 6422000000001032 1 32 1 3p7 hi6 2 770 7 17 p12 ; 0; 0; p12 64 0 5 25p02600 76760 54 0p1020Hence, after the CNot gate is applied we have only a 1 2 chance of obtaining j0i. Of particularinterest to our discussion, however, is what happens to the state vector of the system:10
3 2 p11 0 0 026 0 0 0 0 7606674 0 0 1 0 564 02After measurement: qMm jψihψjMm† Mm jψi2 1 3pp11 2 66422100 p11 2 0 0 0 03p13777 526 70 77 6 0 7 000 5 4 0 5j iThis is the remarkable thing about entanglement. By measuring one qubit we can affect the probability amplitudes of the other qubits in a system! How to think about this process in an abstractway is an open challenge in quantum computing. The difficulty is the lack of any classical analog.One useful, but imprecise way to think about entanglement, superposition and measurement is thatsuperposition “is” quantum information. Entanglement links that information across quantum bits,but does not create any more of it. Measurement “destroys” quantum information turning it intoclassical. Thus think of an EPR pair as having as much “superposition” as an unentangled set ofqubits, one in a superposition between zero and one, and another in a pure state. The superpositionin the EPR pair is simply linked across qubits instead of being isolated in one.This, admittedly fuzzy way of thinking about these concepts is useful when we examine teleportation. There we insert an unknown quantum state (carrying a fixed amount of “quantum information”) into a system of qubits. We mix them about with additional superposition and entanglementand then measure out the superposition we just added. The net effect is the unknown quantumstate remains in the joint system of qubits, albeit migrated through entanglement to another physical qubit.4 TeleportationContrary to its sci-fi counterpart, quantum teleportation is rather mundane. Quantum teleportationis a means to replace the state of one qubit with that of another. It gets its out-of-this-world namefrom the fact that the state is “transmitted” by setting up an entangled state-space of three qubitsand then removing two qubits from the entanglement (via measurement). Since the informationof the source qubit is preserved by these measurements that “information” (i.e. state) ends up inthe final third, destination qubit. This occurs, however, without the source (first) and destination(third) qubit ever directly interacting. The interaction occurs via entanglement.Suppose jψi aj0i bj1i and given an EPR pair p12 (j00i j11i) the state of the entire system is:11
Generate EPR pair and distribute to each endDestinationin state AFixupresultSourcein state A(destroyed in process)Transmit classical informationFigure 1: Teleportation works by pre-transmitting an EPR pair to the source and destination. Thequbit containing the state to be “teleported” interacts with onehalf of this EPR pair creating a jointstate space. It is then measured and only classical information is transmitted to the destination.This classical information is used to “fixup” the destination qubit26666611p [a 0 ( 00 11 ) b 1 ( 00 11 )] p 62266664jij i j ijij i j ia00ab00b377777777775Perform the CNot operation and you obtain266666p1 [a 0 ( 00 11 ) b 1 ( 10 01 )] p1 62266664jij i j ijij i j ia00a0bb0377777777775Next we apply the H gate. However, as an aside, lets examine what happens when we apply the Hgate to j0i and to j1i. Recall that:11H p1211H j0i1 p2 1111 10 1 p2 11 12
H y 0 0 HXZ y Figure 2: Quantum circuit depicting teleportation. Note that in this diagram single lines representquantum data while double lines represent classical information.H j1i1 p2 1111 01 p12 11 Thus, applying H to our system we have:2abbaabba6666i61 ) ( 10 01 ) 12 666664hjϕi p12 p12 a (j0i j1i) (j00i j11i) p12 b (j0iji j i j i377777777775We can rewrite this expression as:2 666 66666 66666 4ab 377 7b 77a 77 1 7 2 [ 00 (a 0 b 1 ) 01 (a 1 b 0 ) 10 (a 0a 77b 77 7b 5j i jiji j i jiji j i jibj1i) j11i (aj1ibj0i)]aWhich we can shorten to: 12j00i 1 00 1 jψi j01i 0 11 0 jψi j10i 1001 jψi j11ii 0iThese gates are the famous “Pauli” (I,X,Z,Y) operators and this is also written as:13i0 jψi
j00iI jψi j01iX jψi j10iZ jψi j11iiY jψi]12[And of interest to us with teleportation:jϕi 12 [j00iI jψi j01iX jψi j10iZ jψi j11iX Z jψi]This implies that we can measure the first and second qubit and obtain two classical bits. Thesetwo classical bits tell us what transform was applied to the third qubit. Thereby we can “fixup”the third qubit by knowing the classical outcome of the measurement of the first two qubits. Thisfixup is fairly straightforward, either applying nothing, X , Z or both X and Z. Lets work throughan example:266666M10 01000000000000000000377777777775††P(10) hϕjM10M10 jϕi hϕjM10 jϕi, since here M10M10 . Thus:26666616M10 ϕ 2 66664ji0000ab003777777777752Therefor: hϕjM10 jϕi 12 [a; b; b; a; a;b;6666616b; a] 2 666640000ab00377777 17 [a a b b ]7 47775 Recall that by definition of a qubit we know that a a b b 1, hence the probability of measuring 01 is 1 4. The same is true for the other outcomes.14
5 Super-dense CodingSuper dense coding is the less popular sibling of teleportation. It can actually be viewed as theprocess in reverse. The idea is to send two classical bits of information by only sending onequantum bit. The process starts out with an EPR pair that is shared between the receiver andsender (the sender has one half and the receiver has the other).Pre communicated EPR pairb0b1InterpretTransmitFigure 3: Super-dense coding works by first pre-communicating an EPR pair. To send two bitsof classical information one half of this EPR pair (a single qubit) is manipulated and sent to theother side. The two qubits (the one pre-communicated and the one sent) are then interacted andthe resulting two bits of classical information is obtained.jψi p12 (j00i j11i)To send information apply particular quantum gates: 00: apply I (i.e. do nothing)01: apply Z10: apply X11: apply iY (i.e. both X and Z) 00:1 00 1 2p12j00i j11i) ! p12 (j00i j11i) (3160 77p1 624 0 512 01:1001 p126j00i j11i) ! p12 (j00i j11i) p12 64(2 10:0 11 0 p12j00i j11i) ! p12 (j10i j01i) (15310 770 513061 77p1 624 1 50
11: i0ii0 2p126j00i j11i) ! p12 (j01i j10i) p12 64(301 771 50These states are known as bell basis states. They key to super-dense coding is that they are orthonormal from eachother and are hence distinguishable by a quantum measurement.Hbit 0bit 1Figure 4: To obtain the two bits of classical information a bell-basis measurement is performed.Examining this process in more detail:jψ00i p12 (j00i j11i) p12 (j0ij0i j1ij1i)apply CNot gives us: p1 (j0ij0i j1ij0i)2apply H gives us: p1 p1 ((j0i j1i) j0i (j0i j1i) j0i) 2 212 (j00i j10i j00i j10i) j00ijψ01i p12 (j00i j11i) p12 (j0ij0
Quantum mechanics is a mathematical language, much like calculus. Just as classical physics uses calculus to explain nature, quantum physics uses quantum mechanics to explain nature. Just as classical computers can be thought of in boolean algebra terms, quantum computers are reasoned about with quantum mechanics. There are four postulates to .
Introduction of Chemical Reaction Engineering Introduction about Chemical Engineering 0:31:15 0:31:09. Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Lecture 21 Lecture 22 Lecture 23 Lecture 24 Lecture 25 Lecture 26 Lecture 27 Lecture 28 Lecture
1. Quantum bits In quantum computing, a qubit or quantum bit is the basic unit of quantum information—the quantum version of the classical binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics.
Quantum computing is a subfield of quantum information science— including quantum networking, quantum sensing, and quantum simulation—which harnesses the ability to generate and use quantum bits, or qubits. Quantum computers have the potential to solve certain problems much more quickly t
Topics History of Computing What are classical computers made of? Moore's Law (Is it ending?) High Performance computing Quantum Computing Quantum Computers Quantum Advantage The Qubit (Information in superposition) Information storage Different kinds of quantum computers Superconducting vs Ion Traps Annealing vs Universal/Gate quantum computers
Quantum computing with photons: introduction to the circuit model, the one-way quantum computer, and the fundamental principles of photonic experiments . quantum computing are presented and the quantum circuit model as well as measurement-based models of quantum computing are introduced. Furthermore, it is shown how these concepts can
Keywords—machine learning, quantum computing, deep learning, quantum machine intelligence I. INTRODUCTION There is currently considerable interest in quantum computing. In the U.S. in January 2019, the National Quantum Initiative Act authorized 1.2 billion investment over the next 5-10 years (Rep Smith, 2019). A quantum computing race is ongoing
According to the quantum model, an electron can be given a name with the use of quantum numbers. Four types of quantum numbers are used in this; Principle quantum number, n Angular momentum quantum number, I Magnetic quantum number, m l Spin quantum number, m s The principle quantum
GEOMETRY NOTES Lecture 1 Notes GEO001-01 GEO001-02 . 2 Lecture 2 Notes GEO002-01 GEO002-02 GEO002-03 GEO002-04 . 3 Lecture 3 Notes GEO003-01 GEO003-02 GEO003-03 GEO003-04 . 4 Lecture 4 Notes GEO004-01 GEO004-02 GEO004-03 GEO004-04 . 5 Lecture 4 Notes, Continued GEO004-05 . 6
