Quantum Computing (fall2013) Instructor:Shengyu Zhang. Lecture 1 Basic concepts Anybody who is not shocked by quantum theory has not understood it.---Niels Bohr I think I can safely say that nobody understands quantum mechanics.---Richard Feynman On quantum theory I use up more brain grease than on relativity.---Albert Einstein 0.About the course Hard math(for CS students).CSE Undergrads:If you don't find the Algorithm course "too easy",then you probably should consider to just sit in this course instead of taking it for credit. More from computer science perspectives,namely algorithms and complexity issues. Less from physics.Almost none about physical implementation of quantum computers. 4 homework assignments +1 final:reading project 1.Starting from qubits One qubit:)=al0)+B1),where a,B are complex numbers satisfying l1a2+lB12=1. Some examples::10),I1),1+〉=2(I0)+1),1-）=2(I0)-I1): Dirac notation:I)for column vector,(I for raw vector,for inner product. Measurement in computational basis:If one measures )a0)+B1)in {10),|1), she observes 0 with probability lal2,and observes 1 with probability IB12.If0 is observed, then the state becomes 10),and if 1 is observed,then the state becomes |1).Note that in general,measurements/observations change the system
Quantum Computing (Fall 2013) Instructor: Shengyu Zhang. Lecture 1 Basic concepts Anybody who is not shocked by quantum theory has not understood it. --- Niels Bohr I think I can safely say that nobody understands quantum mechanics. --- Richard Feynman On quantum theory I use up more brain grease than on relativity. --- Albert Einstein 0. About the course ⚫ Hard math (for CS students). CSE Undergrads: If you don’t find the Algorithm course “too easy”, then you probably should consider to just sit in this course instead of taking it for credit. ⚫ More from computer science perspectives, namely algorithms and complexity issues. Less from physics. Almost none about physical implementation of quantum computers. ⚫ 4 homework assignments + 1 final: reading project. 1. Starting from qubits One qubit: |𝜓〉 = 𝛼|0〉 + 𝛽|1〉, where α, β are complex numbers satisfying |α| 2 + |𝛽| 2 = 1. Some examples: |0〉, |1〉, |+〉 = 1 √2 (|0〉 + |1〉), |−〉 = 1 √2 (|0〉 − |1〉). Dirac notation: | 〉 for column vector, 〈 | for raw vector, ⟨ | ⟩ for inner product. Measurement in computational basis: If one measures |𝜓〉 = 𝛼|0〉 + 𝛽|1〉 in {|0〉, |1〉}, she observes 0 with probability |𝛼| 2 , and observes 1 with probability |𝛽| 2 . If 0 is observed, then the state becomes |0〉, and if 1 is observed, then the state becomes |1〉. Note that in general, measurements/observations change the system
Note some distinctive properties:1.Outcome ofa measurement is not deterministic.2. Measurement changes the system. Operation on one qubit:One can operate on a single qubit in different ways.Some examples:the Pauli-X (NOT)gate X,the Pauli-X gate Y,the Pauli-Z gate Z and the Hadamard gate H are defined as follows x=91,y=[901z=6l, Operating on a single qubit,these operators have the following effects X(al0〉+B11)=Bl0〉+a1,Y(alo〉+B11)=-i邛l0〉+ial1), Z(al0)+11)=l0)-B11), Ha10y+B1》=+e1oy+-911. 2 Multiple qubits:If we have two qubits,then a state in the 2-qubit system is lp）=aool00〉+ao1l01）+a10l10〉+a11l11, where aoo,ao1,a1o,a11 are complex numbers satisfying laool2+la0112+la1012+la1112 =1. For example,the following is an"EPR state": 1妙=100)+111) √Z And it is an example of non-product state,in the sense that it cannot be written as (a10)+ B1))(a210)+B21))for any coefficients ai,Bi. Measurement in computational basis:For any aja2E (00,01,10,11)Observe aaz with probabilityand the state becomes) Operation on two qubits:One can also operate on a two-qubit system.An important example is Controlled-NOT(CNOT),defined as follows. 00 01 CNOT 0 100 001 0 01 0
Note some distinctive properties: 1. Outcome of a measurement is not deterministic. 2. Measurement changes the system. Operation on one qubit: One can operate on a single qubit in different ways. Some examples: the Pauli-X (NOT) gate 𝑋, the Pauli-X gate 𝑌, the Pauli-Z gate Z and the Hadamard gate 𝐻 are defined as follows. 𝑋 = [ 0 1 1 0 ] , 𝑌 = [ 0 −𝑖 𝑖 0 ], 𝑍 = [ 1 0 0 −1 ] , 𝐻 = 1 √2 [ 1 1 1 −1 ]. Operating on a single qubit, these operators have the following effects. 𝑋(𝛼|0〉 + 𝛽|1〉) = 𝛽|0〉 + 𝛼|1〉, 𝑌(𝛼|0〉 + 𝛽|1〉) = −𝑖𝛽|0〉 + 𝑖𝛼|1〉, 𝑍(𝛼|0〉 + 𝛽|1〉) = 𝛼|0〉 − 𝛽|1〉, 𝐻(𝛼|0〉 + 𝛽|1〉) = 𝛼 + 𝛽 √2 |0〉 + 𝛼 − 𝛽 √2 |1〉. Multiple qubits: If we have two qubits, then a state in the 2-qubit system is |𝜓〉 = 𝛼00|00〉 + 𝛼01|01〉 + 𝛼10|10〉 + 𝛼11|11〉, where α00 , 𝛼01, 𝛼10, 𝛼11 are complex numbers satisfying |𝛼00| 2 + |𝛼01| 2 + |𝛼10| 2 + |𝛼11| 2 = 1. For example, the following is an “EPR state”: |𝜓〉 = |00〉 + |11〉 √2 And it is an example of non-product state, in the sense that it cannot be written as (𝛼1 |0〉 + 𝛽1 |1〉)⊗ (𝛼2 |0〉 + 𝛽2 |1〉) for any coefficients 𝛼𝑖 ,𝛽𝑖 . Measurement in computational basis: For any 𝑎1𝑎2 ∈ {00,01,10,11}Observe 𝑎1𝑎2 with probability |𝛼𝑎1𝑎2 | 2 , and the state becomes |𝑎1𝑎2 〉. Operation on two qubits: One can also operate on a two-qubit system. An important example is Controlled-NOT (CNOT), defined as follows. CNOT = [ 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 ]
which has the effect CNOT(@ool00)+@o1101)+@10l10)+a111)) =aoo100〉+ao1l01）+a11l10)+a1ol11) About the name"Controlled-NOT:the first bit is the control bit,and conditioned on the control bit is 1,apply NOT gate to the second qubit. General pure states:In general,a pure quantum state of a k-qubit system corresponds to a unit vector in Cthe 2k-dimensional vector space over complex numbers.Here a unit vector is a vector l)with 2-norm being 1. General (orthogonal)measurements:Suppose that M={v),...,lv)}is a set of orthonormal basis in a K-dimensional system.If we make an orthogonal measurement in basis M on a pure state l),then outcome i occurs with probability v)2,and if outcome i occurs,the state collapses to vi). Ifone prepares a state chosen from {),...v)],and give it to you,then you can tell which state it is by the above measurement.An interesting(and sometimes annoying)fact is that if the set of states are not orthogonal,then there is no way to distinguish them perfectly. States with different global phases cannot be distinguished.Namely,if)=ei),then no measurement can distinguish them. 2.Mathematical model for quantum mechanics The postulates of quantum mechanics. Postulate 1:Associated to any isolated physical system is a complex vector space with inner product known as the state space of the system.The system is completely described by its state vector,which is a unit vector in the system's state space. Postulate 2:The evolution of a closed quantum system is described by a unitary transformation.That is,the state l)of the system at time t is related to the state)of the system at time tz by a unitary operator U which depends only on the times t and tz, lψ)=Ul小)
which has the effect CNOT(𝛼00|00〉 + 𝛼01 |01〉 + 𝛼10|10〉 + 𝛼11|11〉) = 𝛼00 |00〉 + 𝛼01 |01〉 + 𝛼11|10〉 + 𝛼10|11〉. About the name “Controlled-NOT”: the first bit is the control bit, and conditioned on the control bit is 1, apply NOT gate to the second qubit. General pure states: In general, a pure quantum state of a 𝑘-qubit system corresponds to a unit vector in 𝐶 2 𝑘 , the 2 𝑘 -dimensional vector space over complex numbers. Here a unit vector is a vector |𝜓〉 with ℓ2 -norm being 1. General (orthogonal) measurements: Suppose that 𝑀 = {|𝑣1 〉 ,… , |𝑣𝐾 〉} is a set of orthonormal basis in a 𝐾-dimensional system. If we make an orthogonal measurement in basis 𝑀 on a pure state |𝜓〉, then outcome 𝑖 occurs with probability |⟨𝑣𝑖 |𝜓⟩| 2 , and if outcome 𝑖 occurs, the state collapses to |𝑣𝑖 〉. If one prepares a state chosen from {|𝑣1 〉 ,…, |𝑣𝐾 〉}, and give it to you, then you can tell which state it is by the above measurement. An interesting (and sometimes annoying) fact is that if the set of states are not orthogonal, then there is no way to distinguish them perfectly. States with different global phases cannot be distinguished. Namely, if |𝜓1 〉 = 𝑒 𝑖𝜃|𝜓2 〉, then no measurement can distinguish them. 2. Mathematical model for quantum mechanics The postulates of quantum mechanics. Postulate 1: Associated to any isolated physical system is a complex vector space with inner product known as the state space of the system. The system is completely described by its state vector, which is a unit vector in the system's state space. Postulate 2: The evolution of a closed quantum system is described by a unitary transformation. That is, the state |𝜓〉 of the system at time 𝑡1 is related to the state |𝜓′〉 of the system at time 𝑡2 by a unitary operator 𝑈 which depends only on the times 𝑡1 and 𝑡2 , |𝜓′〉 = 𝑈|𝜓〉
Postulate 3:Quantum measurements are described by a collection {Mm}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.If the state of the quantum system is)immediately before the measurement then the probability that result m occurs is given by Pr[m]=(Mm Mm) and the state of the system after the measurement is MPr [m].The measurement operators satisfy the completeness equationmMM=1,which expresses the fact that probabilities sum to one. Postulate 4:The state space of a composite physical system is the tensor product of the state spaces of the component physical systems.Moreover,if we have systems numbered 1 through n,and system number i is prepared in the state),then the joint state of the total system is1）☒l2〉☒…☒lpn）〉 3.Basic facts,protocols No-cloning theorem---One cannot make a copy of a quantum state. Theorem There isn't a unitary operator U operating on 2 qubits and mapping0)to for all single-qubit state). Proof.Consider )=10),11),1+). Teleportation---How to send quantum states using only classical channel (with the help of shared entanglement). Alice holdsa qubit=0)+B1).Alice and Bob share an EPR pair= Here we use subscripts to indicate the registers holding the state. Protocol:Alice applies CNOTon A1A2(A being the control bit),followed by a Hadamard gate on A.Alice then measures her part AA2,which makes Bob's qubit to collapse to one of the four orthogonal states〉=al0)+Bl1),lo1〉=al1)+β1lo),lp1o〉=al0)- Bl1),l4:）=al1）-βlo.Alice also observes a corresponding outcome a∈ {00,01,10,11).Alice sends a,the 2-bit classical information to Bob,who then knows how to revert his state back to l)=al0)+B1)
Postulate 3: Quantum measurements are described by a collection {𝑀𝑚} 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. If the state of the quantum system is |𝜓〉 immediately before the measurement then the probability that result 𝑚 occurs is given by Pr[𝑚] = ⟨𝜓|𝑀𝑚 † 𝑀𝑚|𝜓⟩ and the state of the system after the measurement is 𝑀𝑚|𝜓〉/√Pr [𝑚]. The measurement operators satisfy the completeness equation ∑ 𝑀𝑚 † m 𝑀𝑚 = 𝐼, which expresses the fact that probabilities sum to one. Postulate 4: The state space of a composite physical system is the tensor product of the state spaces of the component physical systems. Moreover, if we have systems numbered 1 through 𝑛, and system number 𝑖 is prepared in the state |𝜓𝑖 〉, then the joint state of the total system is |𝜓1 〉 ⊗ |𝜓2 〉 ⊗ ⋯ ⊗ |𝜓𝑛 〉. 3. Basic facts, protocols No-cloning theorem---One cannot make a copy of a quantum state. Theorem There isn’t a unitary operator 𝑈 operating on 2 qubits and mapping |𝜓〉|0〉 to |𝜓〉|𝜓〉 for all single-qubit state |𝜓〉. Proof. Consider |𝜓〉 = |0〉, |1〉, |+〉. Teleportation---How to send quantum states using only classical channel (with the help of shared entanglement). Alice holds a qubit |𝜓〉𝐴1 = 𝛼|0〉 + 𝛽|1〉. Alice and Bob share an EPR pair |𝜙〉𝐴2𝐵 = |00〉+|11〉 √2 . Here we use subscripts to indicate the registers holding the state. Protocol: Alice applies CNOT on 𝐴1𝐴2 (𝐴1 being the control bit), followed by a Hadamard gate on 𝐴1 . Alice then measures her part 𝐴1𝐴2 , which makes Bob’s qubit to collapse to one of the four orthogonal states |𝜓00 〉 = 𝛼|0〉 + 𝛽|1〉, |𝜓01 〉 = 𝛼|1〉 + 𝛽|0〉, |𝜓10 〉 = 𝛼|0〉 − 𝛽|1〉, |𝜓11 〉 = 𝛼|1〉 − 𝛽|0〉. Alice also observes a corresponding outcome 𝑎 ∈ {00, 01, 10,11}. Alice sends 𝑎, the 2-bit classical information to Bob, who then knows how to revert his state back to |𝜓〉 = 𝛼|0〉 + 𝛽|1〉
For more details,see [NC0O]Chapter 1.3.7.(If you don't have the book,see the wiki page for a nice explanation.) Superdense coding---Using one qubit to encode two classical bits. Superdense coding is something converse to teleportation.Alice and Bob share an EPR pair lo）=eoΨ，and lie wantstofrwit∈o0,0L,10,11 to Bob. Protocol:Alice applies I,Z,X,ir if a=00,01,10,11,respectively.Then the shared state becomes l00)+11l0o)-11I10)+l01101)-102 respectively.Alice sends her qubit to Bob, who then measures the state and gets the encoded information about a. 4.Entanglement and nonlocality Recall that an EPR stateis an entangled state,and it cannot be writtenas o2)for any single-qubit states lo)and 1o2).Entanglement is a key difference between classical and quantum mechanics. CHSH game.Consider the following game.Alice and Bob each receive a bit,s and t, respectively,and they each want to output a bit,a and b,respectively,such that a b= s A t.Note that no communication between Alice and Bob is allowed. With classical local operations and shared randomness,they can succeed with probability 3/4=75%,and that is optimal.With quantum local operations on a shared EPR pair,they can succeed with probability cos2(/8)=0.853...,higher than classical.See [BCMdW10] (Section II.B)for details. Reference [NC0O]Michael Nielsen and Isaac Chuang,Quantum Computation and Quantum Information, Cambridge University Press,2000. [BCMdW10]Harry Buhrman,Richard Cleve,Serge Massar,Ronald de Wolf,Nonlocality and communication complexity,Reviews of Modem Physics,volume 82,2010
For more details, see [NC00] Chapter 1.3.7. (If you don’t have the book, see the wiki page for a nice explanation.) Superdense coding---Using one qubit to encode two classical bits. Superdense coding is something converse to teleportation. Alice and Bob share an EPR pair |𝜙〉 = |00〉+|11〉 √2 , and Alice wants to transfer two classical bits 𝑎 ∈ {00,01, 10, 11} to Bob. Protocol: Alice applies 𝐼, 𝑍, 𝑋, 𝑖𝑌 if 𝑎 = 00,01, 10, 11, respectively. Then the shared state becomes |00〉+|11〉 √2 , |00〉−|11〉 √2 , |10〉+|01〉 √2 , |01〉−|10〉 √2 , respectively. Alice sends her qubit to Bob, who then measures the state and getsthe encoded information about 𝑎. 4. Entanglement and nonlocality Recall that an EPR state |𝜙〉 = |00〉+|11〉 √2 is an entangled state, and it cannot be written as |𝜙1 〉|𝜙2 〉 for any single-qubit states |𝜙1 〉 and |𝜙2 〉. Entanglement is a key difference between classical and quantum mechanics. CHSH game. Consider the following game. Alice and Bob each receive a bit, 𝑠 and 𝑡, respectively, and they each want to output a bit, 𝑎 and 𝑏, respectively, such that 𝑎 ⊕ 𝑏 = 𝑠 ∧ 𝑡. Note that no communication between Alice and Bob is allowed. With classical local operations and shared randomness, they can succeed with probability 3/4=75%, and that is optimal. With quantum local operations on a shared EPR pair, they can succeed with probability cos2 (𝜋/8) = 0.853…, higher than classical. See [BCMdW10] (Section II.B) for details. Reference [NC00] Michael Nielsen and Isaac Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000. [BCMdW10] Harry Buhrman, Richard Cleve, Serge Massar, Ronald de Wolf, Nonlocality and communication complexity, Reviews of Modern Physics, volume 82, 2010
Exercise 1.We said that non-orthogonal states cannot be perfectly distinguished.Consider this ona simple example:One preparesa state l)chosen from {10),11),1+),I-)},and let you guess which one it is.Show that you cannot use any measurement to identify)with certainty Pove that theed theenityatriare hoonal toach other with the inner product defined by (A,B)=ijA Bij.Here the superscript *is the complex conjugate
Exercise 1. We said that non-orthogonal states cannot be perfectly distinguished. Consider this on a simple example: One prepares a state |𝜓〉 chosen from {|0〉,|1〉,|+〉, |−〉}, and let you guess which one it is. Show that you cannot use any measurement to identify |𝜓〉 with certainty. 2. Prove that the three Pauli matrices and the Identity matrix 𝐼 = [ 1 0 0 1 ] are orthogonal to each other with the inner product defined by 〈𝐴, 𝐵〉 = ∑ 𝐴𝑖𝑗 ∗ 𝑖𝑗 𝐵𝑖𝑗 . Here the superscript * is the complex conjugate