What is Quantum Computing?

1 1 Quantum ComputingLecture 1 Anuj DawarBits and Qubits2 What is Quantum Computing? Aim to use Quantum mechanical phenomena that have no classicalcounterpart for computational research tasks include: Building devices with a specified behaviour. Designing algorithms to use the these two are models of s eye viewA computer scientist looks at Quantum Computing:Algorithmic LanguagesTheory/complexitySystem ArchitectureSpecified BehaviourPhysicsDragons4 Why look at Quantum Computing? The world is Quantum classical models of computation provide a level ofabstraction discrete state systems Devices are getting smaller Moore s law the only descriptions that work on the very small scale arequantum Exploit Quantum phenomena using Quantum phenomena may allow us to performcomputational tasks that are not otherwise possible/efficient understand capabilities/resources5 Course OutlineA total of eight and Qubits(this lecture).

2 Of InformationSome useful books: Nielsen, and Chuang, (2000). Quantum Computationand Quantum Information. Cambridge University Press. Mermin, (2007). Quantum Computer Science. CUP. Kitaev, , Shen, and Vyalyi, (2002).Classicaland Quantum Computation. AMS. Hirvensalo, M. (2004). Quantum Computing. website: building block of classical computational devices is a 1 Indeed, any system with a finite set ofdiscrete, stablestates, withcontrolled transitions between them will mechanics tells us that any such system can exist in asuperpositionof general, the state of aquantum bit(orqubitfor short) isdescribed by: |0i+ |1iwhere, and are complex numbers, satisfying| |2+| |2= 19 Qubits|0i|1i |0i+ |1iA qubit may be visu-alised as a unit vectoron the general, however, and attempt to measure the state |0i+ |1iresults in|0iwith probability| |2, and|1iwith probability| | the measurement, the system is in the measured state!

3 That is, further measurements will always yield the same can only extract one bit of information from the state of |0i+ |1iand |0i |1ihavethe same probabilities for theirmeasurementHowever, they aredistinctstateswhich behave differently in termsof how they evolve.|0i|1i |0i+ |1i |0i |1i12 VectorsFormally, the state of a qubit is a unit vector inC2 the2-dimensional complexvector vector can be written as |0i+ |1iwhere,|0i= 10 and|1i= 01 .| i aket, Dirac notation for pair of vectors| i,| i C2that are linearly independentcould serve as a basis. |0i+ |1i= | i+ | iThe basis is determined by the measurement process or of the time, we assume a standard (orthonormal) basis|0iand|1iis will be called thecomputational basis14 ExampleThe vector"1 21 2#measured in the computational basis giveseither outcome with probability1 in the basis 1 21 2 , 1 2 1 2 it gives the first outcome with probability system can exist in any superposition of the2nbasisstates.

4 0|000000i+ 1|000001i+ + 2n 1|111111iwithP2n 1i=0| i|2= 1 Sometimes such a state can be decomposed into the states ofindividual bits12(|00i+|01i+|10i+|11i) =1 2(|0i+|1i) 1 2(|0i+|1i)16 EntanglementCompare the two (2-qubit) states:1 2(|00i+|01i) and1 2(|00i+|11i)If we measure the first qubit in the first case, we see|0iwithprobability 1 and the state remains the second case (an EPR pair), measuring the first bit gives|0ior|1iwith equal probability. After this, the second qubit is ComputingLecture 2 Anuj DawarReview of Linear Algebra2 Linear AlgebraThe state space of a Quantum system is described in terms of avector spaces are the object of study inLinear this lecture we review definitions from linear algebra that weneed in the rest of the are mainly interested in vector spaces over thecomplex numberfield use theDirac notation |vi,| i(read asket) for SpacesA vector space overCis a setVwith a commutative, associative addition operation+that has an identity0:|vi+0=|vi inverses:|vi+ ( |vi) =0 an operation of multiplication by a scalar Csuch that.

5 ( |vi) = ( )|vi ( + )|vi= |vi+ |viand (|ui+|vi) = |ui+ |vi 1|vi=| the vector space ofn-tuples of complex numbers: n .with addition n + n = 1+ n+ n and scalar multiplicationz n = z n 5 BasisAbasisof a vector spaceVis aminimalcollection of vectors|v1i, .. ,|vnisuch that every vector|vi Vcan be expressed as alinear combination of these:|vi= 1|v1i+ + n| the size of the basis is uniquely determined byVand is a basis, every vector|vican be represented as ann-tuple forCnThe standard basis forCnis , , .. , (written|0i, .. ,|n 1i).But other bases are possible:"32#,"4 i#is a basis ll be interested inorthonormalbases. That is bases of vectorsof unit length that are mutually orthogonal. Examples are|0i,|1iand1 2(|0i+|1i),1 2(|0i |1i).

6 7 Linear OperatorsA linear operatorAfrom one vector spaceVto anotherWis afunction such that:A( |ui+ |vi) = (A|ui) + (A|vi)IfVis of dimensionnandWis of dimensionm, then the operatorAcan be represented as anm matrix representation depends on the choice of bases a choice of bases|v1i, .. ,|vniand|w1i, .. ,|wmi, letA|vji=mXi=1 ij|wiiThen, the matrix representation ofAis given by the entries this matrix by the representation of a vector|viin thebasis|v1i, .. ,|vnigives the representation ofA|viin the basis|w1i, .. ,| 45 rotation of the real plane that takes"10#to"1 21 2#and"01#to" 1 21 2#is represented, in the standard basis by thematrix 1 2 1 21 21 2 The operator 0 ii0 does not correspond to a transformationof the real ProductsAn inner product onVis an operation that associates to each pair|ui,|viof vectors acomplex numberhu| operation satisfies hu| v+ wi= hu|vi+ hu|wi hu|vi=hv|ui where the denotes the complex conjugate.

7 Hv|vi 0(note:hv|viis a real number) andhv|vi= 0iff|vi= Product onCnThe standard inner product onCnis obtained by taking, for|ui=Xiui|iiand|vi=Xivi|iihu|vi=Xiu iviNote:hu|is abra, which together with|viforms thebra-kethu| a vector|vi(written|| |vi||) is thenon-negative, realnumber:|| |vi||=phv| vectoris a vector with norm vectors|uiand|viareorthogonalifhu|vi= for an inner product spaceVis a basis madeup ofpairwise orthogonal, unit termHilbert spaceis also used for an inner product space13 Outer ProductWith a pair of vectors|ui U,|vi Vwe associate a linearoperator|uihv|:V U, known as theouter productof|uiand|vi.(|uihv|)|v i=hv|v i|ui|vihv|is theprojectionon the one-dimensional space generated by| linear operator can be expressed as a linear combinationofouter products:A=XijAij|iihj|.

8 14 EigenvaluesAneigenvectorof a linear operatorA:V Vis a non-zero vector|visuch thatA|vi= |vifor some complex number is theeigenvaluecorresponding to the eigenvalues ofAare obtained as solutions of the characteristicequation:det(A I) = 0 Each operator has at least one RepresentationA linear operatorAisdiagonalisableifA=Xi i|viihvi|where the|viiare an orthonormal set of eigenvectors ofAwithcorresponding eigenvalues ,Acan be written as a matrix n in the basis|v1i, .. ,|vniof its with any linear operatorAis itsadjointA whichsatisfieshv|Awi=hA v|wiIn terms of matrices,A = (A )Twhere denotes complex conjugation andTdenotes transposition. 1 +i1 i 11 = 1 i 11 +i1 17 Normal and Hermitian OperatorsAn operatorAis said to benormalifAA =A AFact:An operator is diagonalisable if, and only if, it is said to beHermitianifA=A A normal operator is Hermitian if, and only if, it has OperatorsA linear operatorAisunitaryifAA =A A=IUnitary operators are normal and therefore operators are norm-preserving and |Avi=hu|viAll eigenvalues of a unitary operator have modulus ProductsIfUis a vector space of dimensionmandVone of dimensionnthenU Vis a space of |uvifor the vectors inU V: |(u+u )vi=|uvi+|u vi |u(v+v )i=|uvi+|uv i z|uvi=|(zu)vi=|u(zv)iGiven linear operatorsA:U UandB.

9 V V, we can definean operatorA BonU Vby(A B)|uvi=|(Au),(Bv)i20 Tensor ProductsIn matrix terms,A B= A11B A12B A1mBA21B A22B Am2B AmmB 1 Quantum ComputingLecture 3 Anuj DawarPrinciples of Quantum Mechanics2 What is Quantum MechanicsQuantum Mechanicsis a framework for the development of is not itself a physical statesfour mathematical postulatesthat a physical theory physical theories, such asQuantum Electrodynamicsarebuilt upon a foundation of Quantum are the Postulates AboutThe four postulates specify a general framework for describing thebehaviour of a physical How to describe the state of a closed system. Staticsorstatespace2. How to describe the evolution of a closed system. Dynamics3. How to describe the interactions of a system with externalsystems.

10 Measurement4. How to describe the state of a composite system in terms of itscomponent PostulateAssociated to any physical system is acomplex inner product space(orHilbert space) known as thestate spaceof the system is completely described at any given point in timebyitsstate vector, which is aunit vectorin its state : Quantum mechanics does not prescribe what the statespace is for any given physical system. That is specified byindividual physical : A QubitAny system whose state space can be described byC2 thetwo-dimensional complex vector space can serve as animplementation of a :An electron systems may require an infinite-dimensional state always assume, for the purposes of this course, that our systemshave afinite dimensionalstate PostulateThe time evolution ofclosedquantum system is described by theSchr odinger equation:i~d| idt=H| iwhere ~is Planck s constant; and His a fixed Hermitian operator known as theHamiltonianofthe Postulate Simpler FormThe state| iof a closed Quantum system at timet1is related tothe state| iat timet2by a unitary operatorUthat depends onlyont1andt2.