Lectures on Quantum Computation

Quantum Error Correcting Codes and Information Theory, lecture notes for physics quantum information and computation, what are quantum computing systems
Dr.FlynnHanks Profile Pic
Dr.FlynnHanks,United States,Teacher
Published Date:26-07-2017
Your Website URL(Optional)
Comment
Lectures on Quantum Computation, Quantum Error Correcting Codes and Information Theory by K. R. Parthasarathy Indian Statistical Institute (Delhi Centre) Notes by Amitava Bhattacharya Tata Institute of Fundamental Research, MumbaiPreface These notes were prepared by Amitava Bhattacharya on a course of lecturesIgaveattheTataInstituteofFundamentalResearch(Mumbai) in the months of April 2001 and February 2002. I am grateful to my colleagues at the TIFR, in general, and Professor Parimala Raman in particular, for providing me a receptive and enthusiastic audience and showering on me their warm hospitality. I thank Professor Jaikumar for his valuable criticism and insight and several fruitful conversations in enhancing my understanding of the subject. Finally, I express my warm appreciation of the tremendous effort put in by Amitava Bhattacharya A for the preparation of these notes and their LT X files. E Financial support from the Indian National Science Academy (in the form of C. V. Raman Professorship), TIFR (Mumbai) and Indian Statistical Institute (Delhi Centre) is gratefully acknowledged. K. R. Parthasarathy Delhi June 2001Contents 1 Quantum Probability 1 1.1 Classical Versus Quantum Probability Theory . . . . . . . 1 1.2 Three Distinguishing Features . . . . . . . . . . . . . . . . 7 1.3 Measurements: von Neumann’s Collapse Postulate . . . . 9 1.4 Dirac Notation . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4.1 Qubits . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Quantum Gates and Circuits 11 2.1 Gates in n-qubit Hilbert Spaces . . . . . . . . . . . . . . . 11 2.2 Quantum Gates . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1 One qubit gates. . . . . . . . . . . . . . . . . . . . 13 2.2.2 Two qubit gates . . . . . . . . . . . . . . . . . . . 14 2.2.3 Three qubit gates. . . . . . . . . . . . . . . . . . . 16 2.2.4 Basic rotations . . . . . . . . . . . . . . . . . . . . 17 2.3 Some Simple Circuits. . . . . . . . . . . . . . . . . . . . . 19 2.3.1 Quantum teleportation . . . . . . . . . . . . . . . 19 2.3.2 Superdense coding: quantum communication through EPR pairs . . . . . . . . . . . . . . . . . . 21 2.3.3 Ageneralizationof“communicationthroughEPR states” . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3.4 Deutsche algorithm . . . . . . . . . . . . . . . . . . 24 2.3.5 Arithmetical operations on a quantum computer . 25 3 Universal Quantum Gates 29 3.1 CNOT and Single Qubit Gates are Universal . . . . . . . 29 3.2 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4 The Fourier Transform and an Application 41 4.1 Quantum Fourier Transform . . . . . . . . . . . . . . . . . 41 4.2 Phase Estimation . . . . . . . . . . . . . . . . . . . . . . . 44 4.3 Analysis of the Phase Estimation Circuit. . . . . . . . . . 45 iii Contents 5 Order Finding 49 5.1 The Order Finding Algorithm . . . . . . . . . . . . . . . . 49 Appendix 1: Classical reversible computation . . . . . . . 52 j 2 Appendix 2: Efficient implementation of controlled U operation . . . . . . . . . . . . . . . . . . . . . . . 54 Appendix 3: Continued fraction algorithm . . . . . . . . . 55 ϕ(r) Appendix 4: Estimating . . . . . . . . . . . . . . . . 58 r 6 Shor’s Algorithm 61 6.1 Factoring to Order Finding . . . . . . . . . . . . . . . . . 61 7 Quantum Error Correcting Codes 67 7.1 Knill Laflamme Theorem . . . . . . . . . . . . . . . . . . 67 7.2 Some Definitions . . . . . . . . . . . . . . . . . . . . . . . 75 7.2.1 Invariants . . . . . . . . . . . . . . . . . . . . . . . 75 7.2.2 What is a t–error correcting quantum code? . . . . 76 7.2.3 A good basis forE . . . . . . . . . . . . . . . . . . 77 t 7.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 7.3.1 A generalized Shor code . . . . . . . . . . . . . . . 78 7.3.2 Specialization to A=0,1,m=3,n=3 . . . . . 79 7.3.3 Laflamme code . . . . . . . . . . . . . . . . . . . . 80 7.3.4 Hadamard-Steane quantum code . . . . . . . . . . 81 7.3.5 Codes based on Bush matrices . . . . . . . . . . . 83 7.3.6 Quantum codes from BCH codes . . . . . . . . . . 85 8 Classical Information Theory 87 8.1 Entropy as information. . . . . . . . . . . . . . . . . . . . 87 8.1.1 What is information? . . . . . . . . . . . . . . . . 87 8.2 A Theorem of Shannon . . . . . . . . . . . . . . . . . . . 90 8.3 Stationary Source . . . . . . . . . . . . . . . . . . . . . . . 93 9 Quantum Information Theory 97 9.1 von Neumann Entropy . . . . . . . . . . . . . . . . . . . . 97 9.2 Properties of von Neumann Entropy . . . . . . . . . . . . 97 Bibliography 127Lecture 1 Quantum Probability In the Mathematical Congress held at Berlin, Peter Shor presented a new algorithm for factoring numbers on a quantum computer. In this series of lectures, we shall study the areas of quantum computation (in- cludingShor’salgorithm), quantumerrorcorrectingcodesandquantum information theory. 1.1 Classical Versus Quantum Probability Theory We begin by comparing classical probability and quantum probabil- ity. In classical probability theory (since Kolmogorov’s 1933 mono- graph 11), we have a sample space, a set of events, a set of random variables, and distributions. In quantum probability (as formulated in vonNeumann’s1932book14),wehaveastatespace(whichisaHilbert space) instead of a sample space; events, random variables and distribu- tions are then represented as operators on this space. We now recall the definitions of these notions in classical probability and formally define the analogous concepts in quantum probability. In our discussion we will be concerned only with finite classical probability spaces, and their quantum analogues—finite dimensional Hilbert spaces. 12 Lecture 1. Quantum Probability Spaces 1.1 The sample space 1.2 The state space H: It Ω: This is a finite set, say is a complex Hilbert space of di- 1,2,...,n. mension n. Events 1.3 The set of events F : 1.4 The set of events P(H): Ω This is the set of all subsets of Ω. This is the set of all orthogo- F is a Boolean algebra with the nal projections in H. An ele- Ω union (∪) operation for ‘or’ and ment E ∈ P(H) is called an theintersection (∩)operationfor event. Here, instead of ‘∪’ we ‘and’. In particular, we have have the max (∨) operation, and instead of ‘∩’ the min (∧) oper- E∩(F ∪F )=(E∩F )∪(E∩F ). 1 2 1 2 ation. Note, however, that E ∧ (F ∨F ) is not always equal to 1 2 (E∧F )∨(E∧F ). (They are 1 2 equal if E,F ,F commute with 1 2 each other). Random variables and observables 1.5 The set of random vari- 1.6 The set of observ- ables B : This is the set of ables B(H): This is the Ω ∗ all complex valued functions on (non-Abelian) C -algebra of all Ω. The elements of B are operators on H, with ‘+’ and ‘·’ Ω ∗ calledrandom variables. B isan defined as usual, and X defined Ω ∗ AbelianC -algebraundertheop- to be the adjoint of X. We † ∗ erations will use X instead of X . The identity projection I is the unit (αf)(ω) = αf(ω); in this algebra. (f +g)(ω) = f(ω)+g(ω); Wesaythatanobservableisreal- † valued if X =X, that is, if X is (f·g)(ω) = f(ω)g(ω); Hermitian. For such an observ- Δ ∗ † f (ω)=f (ω) = f(ω¯). able, we define Sp(X) to be the set of eigen values of X. Since Here, α ∈ C, f,g ∈ B , and the Ω X is Hermitian, Sp(X)⊆R, and ‘bar’standsforcomplexconjuga- by the spectral theorem, we can tion. The random variable1 (de- write X as Δ fined by 1(ω)=1), is the unit in X this algebra. X = λE , λ λ∈Sp(X)1.1. Classical Versus Quantum Probability Theory 3 WitheacheventE∈F weasso- whereE istheprojectiononthe Ω λ ciate the indicator random vari- subspaceu:Xu=λu and able 1 defined by E 0 0 E E 0=0,λ,λ ∈Sp(X),λ6=λ; λ λ ( X 1 if ω∈E; E =I. λ 1 (ω)= E 0 otherwise. λ∈Sp(X) Similarly, we have For a random variable f, let Δ X Sp(f) = f(Ω). Then, f can r r X = λ E , λ be written as the following linear λ∈Sp(X) combination of indicator random variables: and in general, for a function ϕ : X R→R, we have f = λ1 −1 , f (λ) X λ∈Sp(f) ϕ(X)= ϕ(λ)E . λ λ∈Sp(X) so that 0 1 −1 ·1 −1 0 =0 for λ6=λ; f (λ) f (λ ) X 1 −1 = 1. f (λ) λ∈Sp(f) Similarly, we have X r r f = λ 1 −1 , f (λ) λ∈Sp(f) and, in general, for a function ϕ : C → C, we have the random variable X ϕ(f)= ϕ(λ)1 −1 . f (λ) λ∈Sp(f) Later, we will be mainly inter- ested in real-valued random vari- ables, that is random variables f † with Sp(f)⊆R (or f =f).4 Lecture 1. Quantum Probability Distributions and states 1.7 A distribution p: This 1.8 A state ρ: In quantum is a function from F to R, probability, we have a state ρ in- Ω determined by n real numbers stead of the distribution p. A p ,p ,...,p , satisfying: state is a non-negative definite 1 2 n operator on H with Trρ = 1. p ≥ 0; i The probability of the event E ∈ n X P(H) in the state ρ is defined p = 1. i to be TrρE, and the probability i=1 thatthereal-valuedobservableX takes the value λ is The probability of the event E∈ ( F (under the distributionp) is Ω TrρE if λ∈Sp(X); λ Pr(X=λ)= X Δ 0 otherwise. Pr(E;p)= p . i i∈E Thus, a real-valued observableX When there is no confusion we hasadistributionontherealline write Pr(E) instead of Pr(E;p). with mass TrρE at λ∈R. λ We will identify p with the sequence (p ,p ,...,p ). The 1 2 n probability that a random vari- able f takes the value λ∈R is Δ −1 Pr(f =λ)=Pr(f (λ)); thus, a real-valued random vari- able f has a distribution on the −1 real line with mass Pr(f (λ)) at λ∈R. Expectation, moments, variance The expectation of a random The expectation of an observable variable f is X in the state ρ is X Δ Δ f = f(ω)p . X =TrρX. E E ω p ρ ω∈Ω The map X 7→ X has the fol- Eρ The r-th moment of f is the ex- lowing properties: r pectation of f , that is1.1. Classical Versus Quantum Probability Theory 5 X (1) It is linear; r r f = (f(ω)) p E ω p ω∈Ω † (2) X X ≥ 0, for all X ∈ E X ρ r −1 = λ Pr(f (λ)), B(H). λ∈Sp(f) (3) I =1. E ρ and the characteristic function of f is the expectation of the The r-th moment of X is the ex- r pectation of X ; if X is real- complex-valued random variable itf e , that is, valued, then using the spectral decomposition, we can write X itf itλ −1 e = e Pr(f (λ)). E X p r r X = λ TrρE . λ∈Sp(f) E λ ρ λ∈Sp(X) Thevarianceofareal-valuedran- The characteristic function of dom variable f is the real-valued observable X is Δ 2 the expectation of the observable var(f)= (f− f) ≥0. E E p p itX e . The variance of a (real- valued) observable X is Note that Δ 2 2 2 var(f)= f −( f) ; var(X) = Trρ(X−TrρX) E E p p 2 2 = TrρX −(TrρX) also, var(f)=0 if and only if all ≥ 0. the mass in the distribution of f is concentrated at f. ThevarianceofX vanishesifand E p only if the distribution of X is concentrated at the point TrρX. Thisisequivalenttotheproperty that the operator range of ρ is containedintheeigensubspaceof X with eigenvalue TrρX. Extreme points 1.9 The set of distribu- 1.10 Thesetofstates: The tions: The set of all probabil- set of all states in H is a convex ity distributions on Ω is a com- set. Let ρ be a state. Since ρ pact convex set (Choquet sim- is non-negative definite, its eigen plex) with exactly n extreme valuesarenon-negativereals,and points, δ (j =1,2,...,n), where we can write j δ is determined by j6 Lecture 1. Quantum Probability X ½ ρ= λE ; λ Δ 1 if ω =j; λ∈Sp(ρ) δ (ω)= j 0 otherwise. since Trρ=1, we have If P = δ , then every random j X λ×dim(E )=1. variable has a degenerate distri- λ λ∈Sp(ρ) bution under P: the distribution of the random variable f is con- The projection E can, in turn, λ centrated on the point f(j). be written as a sum of one- dimensional projections: dim(E ) λ X E = E . λ λ,i i=1 Then, dim(E ) λ X X ρ= λE . λ,i i=1 λ∈Sp(ρ) Proposition 1.1.1 A one-dim- ensional projection cannot be written as a non-trivial convex combination of states. Thus, the extreme points of the convex set of states are precisely the one-dimensional projections. Let ρ be the extreme state corre- sponding to the one-dimensional projection on the ray Cu (where kuk = 1). Then, the expectation m of the observable X is † † m=Truu X=Tru Xu=hu,Xui, and † 2 var(X) = Truu (X−m) 2 = Trk(X−m)uk .1.2. Three Distinguishing Features 7 Thus,var(X)=0ifandonlyifu is an eigenvector of X. So, even for this extreme state, not all ob- servables have degenerate distri- butions: degeneracy of the state does not kill the uncertainty of the observables The product 1.11 Product spaces: If 1.12 Product spaces: If there are two statistical systems (H ,ρ ) and (H ,ρ ) are two 1 1 2 2 described by classical probability quantum systems, then the spaces (Ω ,p ) and (Ω ,p ) quantum system with state 1 2 1 2 respectively, then the proba- space H ⊗H and state ρ ⊗ρ 1 2 1 2 bility space (Ω × Ω ,p × p ) (which is a non-negative defi- 1 2 1 2 determined by nite operator of unit trace on H ⊗ H ) describes the two 1 2 Δ independent quantum systems Pr((i,j);p ×p )= 1 2 as a single system. Pr(i;p )Pr(j;p ), 1 2 describes the two independent systems as a single system. Dynamics 1.13 Reversible dynam- 1.14 Reversible dynamics ics in Ω: This is determined in H: This is determined by by a bijective transformation a unitary operator U : H → H. T :Ω→Ω. Then, Then, we have the dynamics of † Heisenberg: XÃU XU forX ∈ fÃf◦T (for random variables) B(H); −1 PÃP ◦T (for distributions) † Schr¨odinger ρ à UρU for the state ρ. 1.2 Three Distinguishing Features We now state the first distinguishing feature. Proposition 1.2.1 LetE andF beprojectionsinHsuchthatEF= 6 FE. Then, E∨F ≤E+F is false.8 Lecture 1. Quantum Probability Proof Suppose E∨F ≤E+F. Then, E∨F −E≤F. So, F(E∨F −E)=(E∨F −E)F. That is, FE =EF, a contradiction. ¤ Corollary 1.2.2 SupposeE andF are projectionssuch thatEF = 6 FE. Then, for some state ρ, the inequality Trρ(E∨F) ≤ TrρE +TrρF is false. Proof By the above proposition, E∨F ≤E+F is false; that is, there exists a unit vector u such that hu,(E∨F)ui 6≤hu,Eui+hu,Fui. Choose ρ to be the one dimensional projection on the ray Cu. Then, Tr(E∨F)ρ=hu,(E∨F)ui, TrEρ=hu,Eui, TrFρ=hu,Fui. ¤ The second distinguishing feature is: Proposition 1.2.3 (Heisenberg’s inequality) Let X and Y be ob- servables and let ρ be a state in H. Assume TrρX =TrρY =0. Then, µ ¶ µ ¶ 2 2 1 1 var(X)var(Y)≥ Trρ X,Y + Trρ iX,Y ρ ρ 2 2 1 2 ≥ (TrρiX,Y) , 4 where Δ X,Y=XY +YX; and Δ X,Y=XY −YX.1.3. Measurements: von Neumann’s Collapse Postulate 9 Proof For z∈C, we have † Trρ(X +zY) (X +zY)≥0. iθ If z =re , 2 2 −iθ 2 r TrρY +2re TrρYX +TrρX ≥0. The left hand side is a degree-two polynomial in the variable r. Since, it is always non-negative, it can have at most one root. Thus, for all θ, 2 2 −iθ 2 (TrρX )(TrρY )≥(e TrρYX) µ ¶ 2 XY+YX XY−YX ≥ cosθTrρ +sinθTrρi 2 2 2 =(xcosθ+ysinθ) , Δ Δ 1 i where x = Trρ X,Y and y = Trρ X,Y. Note that the right 2 2 y x √ √ hand side is maximum when cosθ = and sinθ = and 2 2 2 2 x +y x +y the proposition follows. ¤ Now we state the third distinguishing feature: Extremalstates (one-dimensionalprojections) arecalled pure states. The set of all pure states in an n-dimensional complex Hilbert space is a manifold of dimension 2n− 2. (The set of all extremal probability distributions on a sample space of n points has cardinality n). 1.3 Measurements: von Neumann’s Collapse Postulate Suppose X is an observable (i.e. a Hermitian operator) with spectral decomposition X X = λE . λ λ∈Sp(X) Then, the measurement of X in the quantum state ρ yields the value λ with probability TrρE . If the observed value is λ, then the state col- λ lapses to E ρE λ λ ρ˜ = . λ TrρE λ The collapsed state ρ˜ has its support in the subspace E (H). λ λ10 Lecture 1. Quantum Probability 1.4 Dirac Notation ElementsoftheHilbertspaceHarecalledketvectorsanddenotedbyui. ∗ ElementsofthedualspaceH arecalled bra vectorsanddenotedbyhu. The bra hu evaluated on the ket vi is the bracket huvi, the scalar product between u,v as elements ofH. The operatoruihv is defined by Δ uihv(wi)=hvwiui. It is a rank one operator when u and v are non-zero. Truihv=hvui † (uihv) =vihu u ihv u ihv ···u ihv =(hv u ihv u i···hv u i)u ihv . 1 1 2 2 n n 1 2 2 3 n−1 n 1 n The scalar product huvi is anti-linear (conjugate-linear) in the first variable and linear in the second variable. 1.4.1 Qubits ­£ ¤ £ ¤® Δ a c 2 ¯ The Hilbert space h =C , with scalar product , =a¯c+bd, is b d called a 1-qubit Hilbert space. Let · ¸ · ¸ 1 0 0i= and 1i= . 0 1 Then, · ¸ a =a0i+b1i, b and the ket vectors0i and1i form an orthonormal basis for h. ⊗n 2 ⊗n The Hilbert spaceh =(C ) is called the n-qubit Hilbert space. Ifx x ···x isann-lengthwordfromthebinaryalphabet0,1, welet 1 2 n Δ x x ···x i=x ix i···x i 1 2 n 1 2 n Δ =x i⊗x i⊗···⊗x i 1 2 n Δ =xi, n−1 n−2 where x = x × 2 + x × 2 +··· + x × 2 + x (that is, as 1 2 n−1 n x x ...x varies over all n-length words, the integer x varies in the 1 2 n n range0,1,...,2 −1).Lecture 2 Quantum Gates and Circuits 2.1 Gates in n-qubit Hilbert Spaces In ordinary (classical) computers, information is passed through a clas- sical channel. Logic gates (like AND, OR, NOT) operate on these chan- nels. Likewise, in a quantum computer, information is passed through a quantumchannelanditisoperateduponbyquantumgates. Aquantum gate is a unitary operator U in a (finite dimensional) Hilbert SpaceH. Notalltheclassicalgatesarereversible(forexampleifaANDb=0, there are three possible values for the ordered pair (a,b)). On the con- trary, all quantum gates are reversible. If a gate U acts on an n-qubit Hilbert space H we depict it as in Figure 2.1. If U acts on a single qubit it is represented pictorially as shown in Figure 2.2. ui Uui n U Figure 2.1: A quantum circuit. ui Uui U Figure 2.2: A gate U acting on a single qubit. If the input isui and it passes through the gate U, then the output is written as Uui. 1112 Lecture 2. Quantum Gates and Circuits Any unitary operator U which acts on a single qubit can be written as · ¸ a b iα U =e , −b a 2 2 wherea +b =1 in the computational basis consisting of0i and1i. The action of the unitary operator U on the basis states can be computed as shown below. · ¸· ¸ a b 1 iα iα U0i=e =e a0i−b1i. −b a 0 iα Similarly, U1i=e b0i+a1i. By measurement on the n-qubit reg- ister of a quantum computer we usually mean measuring the observable n 2 −1 X X = jjihj, j=0 and it is indicated in circuits by the ammeter symbol, as in Figure 2.1. Since by measuring we get two quantities, namely a classical value and a (collapsed) quantum state, pictorially it is indicated by a dou- ble line, as in Figure 2.1. The output consists of a value of X in the n range 0,1,...,2 −1, where the probability of the event X = j is 2 hjUui , and a collapsed basis stateji, where j is the observed value. As an example, let us simulate a Markov chain using a quantum circuit. Consider the circuit in Figure 2.3. j j vi 1 2 n U U 1 2 Figure 2.3: A quantum circuit to simulate a Markov Chain. After each measurement, the observed classical parts j ,j ,... take 1 22.2. Quantum Gates 13 n values in the space0,1,2,...,2 −1 with the following properties: 2 n Pr(j )=hj U vi 0≤j ≤2 −1 1 1 1 1 2 n Pr(j j )=hj U j i 0≤j ≤2 −1 2 1 2 2 1 2 . . . . . . 2 n Pr(j j j ,...,j )=hj U j i 0≤j ≤2 −1 k k−1 k−2 1 k k k−1 k . . . . . . Thus, we have simulated a classical Markov chain with state space n 0,1,2,...,2 − 1. The drawback here is that we need a separate n unitary operator for each of the 2 possible outcomes of the measure- ment. Problem Given a doubly stochastic matrix M of size n × n, does 2 there exist a unitary matrix U such that, u = p for all i,j ∈ ij ij 0,1,2,...,n? Existenceofsuchamatrixwillresultinsimplificationofthequantum circuit for simulating a Markov chain. 2.2 Quantum Gates 2.2.1 One qubit gates Inclassicalcomputing,theonlyinterestingone-bitgateistheNOTgate. In the quantum world, we have many 1-qubit gates. Some of them are given below. 1. Pauli gates: There are three such gates and they are denoted by X, Y, Z. The unitary matrices of X,Y,Z in the computational basis are given by · ¸ · ¸ · ¸ 0 1 0 −i 1 0 X = ,Y = ,Z = . 1 0 i 0 0 −1 TheunitarymatrixX isalsocalledthenotgate becauseX0i=1i and X1i=0i. These gates are called Pauli gates because the unitary matrices corresponding to these operators are the Pauli matrices σ ,σ , σ 1 2 314 Lecture 2. Quantum Gates and Circuits of quantum mechanics. Pauli matrices are the basic spin observ- 2 2 2 ables taking values±1. X,Y,Z are hermitian, X =Y =Z =1 and X,Y,Z anticommute with each other i.e. XY +YX =0. 2. Hadamardgate: TheunitarymatrixcorrespondingtotheHadamard £ ¤ 0i+1i 1 1 1 √ √ gate is H = . In this case, H0i = and H1i = 1 −1 2 2 n 0i−1i ⊗ √ . Its n-fold tensor product H is the Hadamard gate on 2 n-qubits satisfying X 1 n ⊗ H 00...0i= xi n 2 2 n x∈0,1 and more generally X n 1 ⊗ x·y H xi= (−1) yi, n 2 2 n y∈0,1 where x·y =x y +x y +···+x y . 1 1 2 2 n n £ ¤ 1 0 3. Phase gate: The unitary matrix for this gate is S = . This 0 i gate changes the phase of the ket vector 1i by i so that 1i be- comes i1i, and leaves the ket vector0i fixed. π 4. gate: The unitary matrix for this gate is 8 " " −iπ 8 1 0 π e 0 i 8 T = =e . iπ iπ 4 0 e 8 0 e π i 4 This gate changes the phase of1i by e . 2.2.2 Two qubit gates 1. Controlled NOT:This gate(Figure 2.4) actsasa NOTgateon the second qubit (target qubit) if the first qubit (control qubit) is in the computational basis state1i. So the vectors01i and00i are unaltered, while the vector 10i gets modified into 11i and vice versa. The unitary matrix for this gate is   1 0 0 0   0 1 0 0   T = .   0 0 0 1 0 0 1 02.2. Quantum Gates 15 Figure 2.4: Two qubit gates. A CNOT gate and a SWAP gate. Thegatecouldalsonegatethecontentofthefirstqubitdepending on the second qubit. Such a gate will have a different unitary ma- trix. Theessentialpointisthataqubitcangetnegateddepending on a control qubit. The control qubit will always be denoted by a solid dot in pictures. 2. Swap gate: This gate (Figure 2.4) swaps the contents of the two qubits. Be- cause the vectors00i and11i are symmetric, they are unaltered, while the vector01i gets mapped to10i and vice versa. The unitary matrix for this gate is   1 0 0 0   0 0 1 0   P = .   0 1 0 0 0 0 0 1 Exercise 2.2.1 Prove that the two circuits given in Figure 2.5 are equivalent. Figure 2.5: Swap gate as a composition of three CNOT gates. Solution To check the equivalence of the circuits on the left hand side and right hand side we compute how the circuit on the right hand side acts on the basis statea,bi. a,bi→a,a⊕bi→a⊕(a⊕b),a⊕bi=b,a⊕bi→b,(a⊕b)⊕bi=b,ai.16 Lecture 2. Quantum Gates and Circuits 3. Controlled unitary: This is just like the controlled NOT, but in- stead of negating the target qubit, we perform the unitary trans- form prescribed by the matrix U (only if the control qubit is in state 1i). It is represented schematically as shown in the first diagram of Figure 2.6. 2.2.3 Three qubit gates U Figure 2.6: A controlled unitary gate, Toffoli gate and a Fredkin gate. 1. Toffoli gate: This (as in second diagram of Figure 2.6) is a double controlled NOT gate. The only computational basis vectors which getchangedare110iand111i. Thecorrespondingunitarymatrix is   1 0 0 0 0 0 0 0   0 1 0 0 0 0 0 0     0 0 1 0 0 0 0 0     0 0 0 1 0 0 0 0   U = .   0 0 0 0 1 0 0 0     0 0 0 0 0 1 0 0     0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 2. Fredkin gate: This is a controlled swap gate (last diagram of Fig- ure 2.6). The corresponding unitary matrix is   1 0 0 0 0 0 0 0   0 1 0 0 0 0 0 0     0 0 1 0 0 0 0 0     0 0 0 1 0 0 0 0   U = .   0 0 0 0 1 0 0 0     0 0 0 0 0 0 1 0     0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.