positivitymkxk.com

AppendixAElementaryProbabilityTheoryThemathematicalconceptofprobabilitybuildsonsomebasicmeasure-theoreticnotions,whichweexhibitrst.
DenitionA.
1LetΩbeanon-emptysetandA{B|BΩ}asetofsub-setsofΩ.
ThesetofsubsetsAiscalledσ-AlgebraonΩifΩ∈AB∈AΩB∈An∈NAn∈Aforeverysequence(An)n∈NwithAn∈Aholds.
Thepair(Ω,A)iscalledameasurablespace.
Ameasureon(Ω,A)isamapμwiththepropertiesμ:A→[0,∞]μ(/0)=0μn∈NAn=∑n∈Nμ(An)foreverysequence(An)n∈NwithAn∈AandAn∩Am=/0foralln=m.
Thetriple(Ω,A,μ)iscalledmeasurespace.
Fori∈{1,2}let(Ωi,Ai)betwomeasurablespaces.
Afunctionf:Ω1→Ω2iscalledmeasurableifforeveryA∈A2itspre-imagef1(A):={ω∈Ω1|f(ω)∈A}satisesf1(A)∈A1.
Bydenitioneverymeasuretakesonlynon-negativevalues.
IfameasureissuchthatonthecompletesetΩittakesthevalue1(and,consequently,takesonlyvaluesin[0,1])itbecomesaprobabilitymeasure.
SpringerNatureSwitzerlandAG2019W.
Scherer,MathematicsofQuantumComputing,https://doi.
org/10.
1007/978-3-030-12358-1501502AppendixA:ElementaryProbabilityTheoryDenitionA.
2AmeasurePonameasurablespace(Ω,A)iscalledproba-bilitymeasureifP(Ω)=1.
(A.
1)Thetriple(Ω,A,P)iscalledprobabilityspace.
Aprobabilityspaceenablesustodenewhatiscalledarandomvariable.
DenitionA.
3Let(Ω,A,P)beaprobabilityspaceand(M,M)ameasurablespace.
AnM-valuedrandomvariableZisameasurablemapZ:Ω→M.
TheprobabilitymeasurePZ:=PZ1:M→[0,1]on(M,M)iscalledprobabilitydistribution(orsimplydistribution)ofZ.
IftheimageofZiscountable,thatis,ifthereexistsanindexsetINsuchthatZ{Ω}={mi|i∈I},thenZiscalledadiscreterandomvariable.
InthiscasePZbecomesadiscreteprobabilitydistribution,whichassignsaprobabilityPZ({m})=PZ1({m})toeverym∈Z{Ω}.
ForeverysubsetSMsatisfyingS∈MtherealnumberPZ(S)=P{ω|Z(ω)∈S}iscalledtheprobabilityofthe'event'Z(ω)∈Stakingplace.
Toemphasizethis,wewilloftenwriteP{Z∈S}forPZ(S)or,inthecaseofadiscreterandomvariable,P{Z=m}forPZ({m}).
ExampleA.
4Let(Ω,A,P)beaprobabilityspaceandlet(Rn,B)bethemeasurespace,whereBdenotestheBORELsetsofRn.
ThenanymeasurablefunctionZ:Ω→Rnconstitutesann-dimensionalreal-valuedrandomvariable.
ThismeansthattoanyBORELsetB∈BwecanassignaprobabilityP{ω|Z(ω)∈B}.
AppendixA:ElementaryProbabilityTheory503DenitionA.
5LetZbeann-dimensionalreal-valuedrandomvariableonaprobabilityspace(Ω,A,P).
TheexpectationvalueofZisdenedasE[Z]:=ΩZ(ω)dP(ω)=RnxdPZ(x),(A.
2)wheredPZ(x)isoften(inparticularwhenn=1)writtenasP{Z∈[x,x+dx]}.
IncaseZisaninteger-valueddiscreterandomvariablewithZ{Ω}={xi|i∈I}Z,theexpectationvalueisgivenbyE[Z]:=∑i∈IxiP{Z=xi}.
(A.
3)Ascanbeseenfromtherightsideof(A.
2)and(A.
3),theknowledgeofΩ,PandZ(ω)isnotrequiredtocalculatetheexpectationvalueaslongasoneknowstherespectiveprobabilitiesP{Z∈[x,x+dx]}or,incaseofadiscreterandomvariable,P{Z=xi}.
LemmaA.
6LetZbeaninteger-valuedrandomvariableonaprobabilityspace(Ω,A,P)satisfying|Z(ω)|≤c(A.
4)forallω∈Ωandsomenon-negativec∈R.
Thenwehave|E[Z]|≤c.
Proof|E[Z]|=(A.
3)∑i∈IxiP{Z=xi}≤∑i∈I|xiP{Z=xi}|=∑i∈I|xi|P{Z=xi}≤(A.
4)∑i∈IcP{Z=xi}=c∑i∈IP{Z=xi}=(A.
1)cIfZisann-dimensionalreal-valuedrandomvariable,thenforeveryBORELmea-surablefunctionf:Rn→RmthefunctionfZ:Ω→Rmisalsoanm-dimensionalreal-valuedrandomvariable.
ItsexpectationvalueisgivenbyE[f(Z)]=Ωf(Z(ω))dP(ω)=Rnf(x)dPZ(x).
(A.
5)504AppendixA:ElementaryProbabilityTheoryFordiscreterandomvariablesonehasanalogouslyE[f(Z)]=∑i∈If(xi)P{Z=xi}.
(A.
6)DenitionA.
7LetZ1andZ2beone-dimensionalreal-orinteger-valuedrandomvariables.
Theirvariancevar[Zi],covariancecov[Z1,Z2]andcorrelationcor[Z1,Z2]aredenedasvar[Zi]:=E(ZiE[Zi])2cov[Z1,Z2]:=E[(Z1E[Z1])(Z2E[Z2])]cor[Z1,Z2]:=cov[Z1,Z2]var[Z1]var[Z2].
Ascanbeseenfrom(A.
5)and(A.
6),thecalculationoftheexpectationvalueofafunctionofseveralrandomvariablesZ1,Z2,.
.
.
requirestheirjointdistributionP{Z1∈[x1,x1+dx],Z2∈[x2,x2+dx],.
.
.
}orP{Z1=x1,Z2=x2,.
.
.
}fordiscreterandomvariables.
Thisholds,inparticular,forcovarianceandcorrelationoftworandomvariables.
AppendixBElementaryArithmeticOperationsThefollowinglemmaformalizesthealgorithmforthebinaryrepresentationoftheadditionoftwonumbers.
Itisabinaryversionoftheelementarytextbookaddi-tionofnumbersindecimalrepresentationandisimplementedwiththequantumadderdenedinSect.
5.
5.
1.
ThefunctionsabandamodbusedherearedenedinDenitionD.
1.
Thebinarysuma2b=(a+b)mod2wasintroducedinDeni-tion5.
2.
LemmaB.
1Letn∈Nanda,b∈N0witha,bM|f(N)|≤ε|g(N)|,andthebigLandausymbolO(·)isdenedasf(N)∈O(g(N))forN→∞:C∈RandM∈N:N>M|f(N)|≤C|g(N)|.
Wesayfisofpolynomialorder(oroforderpoly(N))andwritethisasf(N)∈poly(N)iff(N)∈Ok∑j=0ajNjforanitek∈N0andsomeaj∈R.
SpringerNatureSwitzerlandAG2019W.
Scherer,MathematicsofQuantumComputing,https://doi.
org/10.
1007/978-3-030-12358-1513514AppendixC:LANDAUSymbolsApartfromthosegivenabove,slightlymodiedorgeneralizeddenitionsofthesesymbolscanbefoundintheliterature,buttheaboveissuitableandsufcientforourpurposes.
ExampleC.
2ByapplicationoftheL'HOSPITALruleonecaneasilyshowthatlimN→∞lnNN1m=0=limN→∞Nmexp(N)m∈N.
Thisimpliesforallm∈N:lnN=oN1mandNm=o(exp(N)).
ExerciseC.
117Letfi(N)∈O(gi(N))fori∈{1,2}andN→∞.
ShowthatthenforN→∞(i)f1(N)+f2(N)∈O(|g1(N)|+|g2(N)|).
(C.
1)(ii)f1(N)f2(N)∈O(g1(N)g2(N)).
(C.
2)(iii)IfthereexistsanM∈NsuchthatforallN>Mwehave|g1(N)|N.
ShowthatthenamodN0rj:=rj2modrj1(D.
6)sj:=sj2rj2rj1sj1(D.
7)tj:=tj2rj2rj1tj1.
(D.
8)Thenrj0andrn+1=0.
Thisproves(D.
9).
Inordertoshow(D.
10),werstprovebydescendinginductionthatforallj∈{0,.
.
.
,n+1}aznj∈Nexistssuchthatrnj=znjrn.
(D.
13)Fortheinduction-startletn∈Nbesuchthatrn>0butrn+1=0.
Itfollowsthat0=rn+1=(D.
6)rn1modrn=rn1rn1rnrn.
Consequently,thereexistsazn1:=rn1rn∈Nthatsatisesrn1=zn1rn.
Furthermore,onehasperdenition(D.
6)thatrn=rn2modrn1andthusrn2=rn+rn2rn1rn1=1=:zn+rn2rn1zn1rn=zn2rnforazn2∈N.
Thisproves(D.
13)forj∈{1,2},andthestartofthedescendinginductionisestablished.
Next,weturntotheinductivestep.
Wewillshowthatifthereexistzn(j1),znj∈N,suchthatrn(j1)=zn(j1)rn(D.
14)rnj=znjrn,(D.
15)AppendixD:ModularArithmetic519thenthereexistsazn(j+1)∈Nsatisfyingrn(j+1)=zn(j+1)rn.
Fromthedenition(D.
6)ofrn(j1)andtheassumptions(D.
14)and(D.
15)itfol-lowsthatrn(j+1)=rn(j1)+rn(j+1)rnjrnj=zn(j1)+rn(j+1)rnjznj:=zn(j+1)∈Nrn=zn(j+1)rn1.
Thiscompletestheinductiveproofof(D.
13).
Hence,thereexistz0,z1∈N,suchthatmin{a,b}=r0=z0rnmax{a,b}=r1=z1rn,andrnisacommondivisorofaandb.
Toshowthatrnisthegreatestsuchdivisor,supposegisalsoacommondivisorofaandb.
Thendenea:=ag∈Nandb:=bg∈N.
Applyingthealgorithmtoa,bgeneratesrj:=rjgandthusrn=rng∈N,inotherwords,anycommondivisorofaandbalsodividesrn.
Consequently,rnisthegreatestcommondivisorofaandb.
Thiscompletestheproofof(D.
10).
Toprove(D.
11),weusethat,becauseofrj0,itfollowsthatn21satisfyabmodN=0gcd(a,N)gcd(b,N)>1.
Inparticular,ifNisprime,thenabmodN=0amodN=0orbmodN=0(D.
28)holds.
ProofLetabmodN=0.
Thenthereexistsaq∈Nsuchthatab=qN.
Fromtheprimedecompositionofthisequation=apα11···pαss=bpβ11···pβrr==qpκ11···pκvv=Npν11···pνuuoneseesthattheprimefactorsofNhavetobecontainedinthoseofaorbandthusthataorbmusthavecommondivisorswithN,thatis,gcd(a,N)>1orgcd(b,N)>1.
AppendixD:ModularArithmetic525IfNisprimeandN|abholds,thenNmustbecontainedinaorbasaprimefactor.
Conversely,amodN=0impliesN|aandbmodN=0impliesN|b.
EithercasehasN|abasaconsequence.
DenitionD.
12TheEULERfunctionφisdenedasφ:N→Nn→φ(n):=r∈{1,.
.
.
,n1}|gcd(r,n)=1,(D.
29)thatis,φ(n)isthenumberofallr∈Nwith1≤r1andthusφ(10)=4.
Generally,itisquitedifculttocomputetheEULERfunction.
Forprimepowers,however,itisveryeasyasshowninthefollowinglemma.
LemmaD.
14Forpprimeandk∈Nonehasφ(pk)=pk1(p1).
(D.
30)ProofInthesetofthepk1numbers1,.
.
.
,pk1thepk11multiples1p,2p,.
.
.
,(pk11)pofparetheonlynumbersthathaveanon-trivialcommondivisorwithpk.
Consequently,thenumberφ(pk)ofthosewhichdonothaveacom-mondivisorwithpkisgivenbyφ(pk)=pk1(pk11)=pk1(p1).
FornumbersN=pqthathaveonlytwosimpleprimefactorsp,q∈Pri,thatis,so-calledhalf-primes,theknowledgeofφ(N)isequivalenttotheknowledgeoftheprimefactorspandqasthefollowinglemmashows.
526AppendixD:ModularArithmeticLemmaD.
15Letpandqbeprimessuchthatp>qandletN=pq.
Thenwehaveφ(N)=(p1)(q1)andwithS:=N+1φ(N)(D.
31)D:=S24N>0,(D.
32)furthermore,p=S+D2(D.
33)q=SD2.
(D.
34)ProofSincepandqaredifferentprimes,wendthatamongtheN1naturalnumberssmallerthanN=pqonlythenumbers1*q,2*q,.
.
.
,(p1)*qand1*p,2*p,.
.
.
,(q1)*phaveacommondivisorwithN.
Hence,wehaveφ(N)=N1(p1)(q1)=pq(p+q)+1=(p1)(q1).
Togetherwith(D.
31)and(D.
32),thisimpliesS=p+qD=pq,and(D.
33)aswellas(D.
34)followimmediately.
ExampleD.
16InExampleD.
13wefoundforN=10thatφ(10)=4.
Usingthisin(D.
31)and(D.
32)yieldsS=7andD=3,whichinturngivesp=5andq=2.
ThefollowingtheorembyEULERisusefulforthedecryptionintheRSApub-lickeyencryptionmethodaswellasinconnectionwiththeprimefactorizationinSect.
6.
5.
2.
TheoremD.
17(EULER)Anycoprimeb,N∈Nsatisfybφ(N)modN=1.
(D.
35)AppendixD:ModularArithmetic527ProofFirst,wedeneaj:=rjbmodNforallrj∈Nwith1≤rj1withNsuchthataj=usandN=vs.
Thenthereexistsak∈Zsuchthatus=rjb+kvs,whichisequivalenttorjb=(ukv)s.
This,however,wouldimplythatrjbandNhaveacommondivisors>1,whichcontradicts(D.
37).
Consequently,allajarecoprimewithNandthereexistφ(N)distinctajwith1≤ajm,wehaveforallx∈Zthatg(x)modp=(D.
57)m∑l=0glxlmodp=k1∑l=0glxlmodp=(D.
55)g(x)modp,(D.
58)andthesetofzerosmodulopofgandgcoincide.
Becauseofthisand(D.
56),ghasatleastkzerosmodulop.
Atthesametimegisapolynomialofdegreenotexceedingk1andthussatisestheinductiveassumption,whichthenimpliesthatgand,becauseof(D.
58),alsogcanonlybethezero-polynomialmodulop:g(x)modp=0x∈Z.
With(D.
55)itthusfollowsthatforallx∈ZAppendixD:ModularArithmetic535f(x)modp=fkk∏j=1(xnj)modp,andforanarbitraryzerozoffmodulopwehave0=f(z)modp=fkk∏j=1(znj)modp.
Sincebyassumptionp|fk,oneofthefactorsin∏kj=1(znj)hastosatisfy(znj)modp=0.
Aswechosethenjformtheset{1,.
.
.
,p1},itfollowsthatzmodp=nj,andziseitheroneofthekzerosselectedfrom{1,.
.
.
,p1}oritdiffersfromoneofthesebyamultipleofpandisthusnotanelementoftheset{1,.
.
.
,p1}.
LemmaD.
24Letpbeprime,danaturalnumbersatisfyingd|p1andlethbethepolynomialh:Z→Zx→h(x):=xd1.
Thentherearedzerosofhmodulopin{1,.
.
.
,p1}N,thatis,in{1,.
.
.
,p1}thereexistdnaturalnumbersnjsatisfyingh(nj)modp=0.
ProofLetk∈Nbesuchthatp1=dkandsetf(x):=k1∑l=0xdl.
Thenwehaveg(x):=h(x)f(x)=xd1k1∑l=0xdl=xp11.
Sincep1=φ(p)and,accordingtotheEULERTheoremD.
17,aφ(p)modp=1foralla∈{1,.
.
.
,p1},itfollowsthatforallz∈{1,.
.
.
,p1}zp1modp=1.
536AppendixD:ModularArithmeticHence,allp1=dkintegersin{1,.
.
.
,p1}arezerosmodulopofthepolynomialg.
Sincepisaprimeandg=hf,eachofthedkzerosnj∈{1,.
.
.
,p1}ofgmodulophastosatisfyh(nj)modp=0orf(nj)modp=0.
AccordingtoLemmaD.
23thepolynomialhhasatmostdandthepolynomialfhasatmostd(k1)zerosmodulopin{1,.
.
.
,p1}.
Denotingthenumberofzerosmodulopin{1,.
.
.
,p1}ofthepolynomialsg,handfbyNg,NhandNf,wehavethusdk=Ng≤Nh+Nf≤d+d(k1)=dk.
Thiscanonlybetrueiffhasexactlyd(k1)andhhasexactlydzeros,whichwastobeshown.
TheoremD.
25Foreveryoddprimepthereexistsatleastoneprimitiverootamodulop,thatis,anaturalnumberasuchthatordp(a)=φ(p).
ProofLetqbeaprimefactorofp1,thatis,thereexistsakq∈Nsuchthatqkq|p1.
FromLemmaD.
24weknowthatthepolynomialh(x):=xqkq1hasexactlyqkqzerosmodulopin{1,.
.
.
,p1}.
Letaqbeoneofthesezerossuchthatitsatisesaqkqq1modp=0andthusaqkqqmodp=1.
Sinceaq∈{1,.
.
.
,p1}andgcd(aq,p)=1,itfollowsfrom(D.
40)inTheo-remD.
22thatordp(aq)|qkq.
Ifthiszeroaqofhhastheadditionalpropertyordp(aq)|qjforaj∈Nwithj0holds,weinferfrom(D.
17)thatn1andwith(E.
17)thatpj=ajpj1+pj2≥pj1+pj2.
CorollaryE.
8LetI={0,.
.
.
,n}N0orI=N0,andlet(aj)j∈Ibeasequenceofnumbers,wherea0∈Zandaj∈Nforj≥1.
Moreover,forallj∈Iletpjqj=[a0;a1,.
.
.
,aj].
Thenthefollowingholds:(i)Forallj∈I{0}pjqj1qjpj1=(1)j1(E.
22)andgcd(pj,qj)=1.
(E.
23)(ii)Forj,k∈Isuchthatj>k≥0pkqkpjqj=(1)jjk1∑l=0(1)lqjlqjl1.
(E.
24)(iii)Forallk∈Ip2kq2kkpkqkpjqj=pkqkpk+1qk+1+pk+1qk+1pk+2qk+2+···+pj1qj1pjqj=(E.
28)(1)k+1qkqk+1+(1)k+2qk+1qk+2+···+(1)jqj1qj=(1)jjk1∑l=0(1)lqjlqjl1,proving(E.
24).
Toprove(iii),weobservethat554AppendixE:ContinuedFractionsp2kq2kp2k+2q2k+2=(E.
24)(1)2k+21q2k+2q2k+11q2k+1q2k=1q2k+11q2k+21q2k0forarbitraryk∈I.
Withthisweobtainthedesiredinequalityasfollowsp2k+1q2k+1p2kq2k=p2k+1q2kp2kq2k+1q2kq2k+1=(E.
22)1q2kq2k+1>0.
WiththeseauxiliaryresultswecannowshowtheclaimrequiredfortheSHORalgorithm,whichstatesthat,ifapositiverationalnumberissufcientlyclosetoasecondpositiverationalnumber,therstrationalnumberhastobeacontinuedfractionofthesecond.
TheoremE.
9LetP,Q∈Nbegivenandlet[a0;.
.
.
,an]bethecontinuedfrac-tionoftheirquotient,thatis[a0;a1,.
.
.
,an]=PQ.
(E.
29)Ifp,q∈NaresuchthatPQpqpandthuspj+1qj+1=pqwithpj+1>pandqj+1>q,whichisimpossiblebecauseof(E.
36).
Hence,duetoa∈Zitmustbethat|a|≥1andweobtainqpnqnp=(aqj+bqj+1)pnqn(apj+bpj+1)=aqjpnqnpj=:cj+bqj+1pnqnpj+1=:cj+1.
(E.
37)Accordingto(E.
27)inCorollaryE.
8onehasforevenj∈{0,.
.
.
,n1}thatpjqj0.
(E.
39)AppendixE:ContinuedFractions557Similarly,itfollowsfrom(E.
35)thata=qqj+1bqjandwithb∈Zaswellasq0q1,itisnon-abelian.
AparticularcaseisV=Cnforn∈NandF=C,whichgivesthegroupofallinvertiblecomplexn*nmatricesGL(n,C):=M∈Mat(n*n,C)detM=0.
Togetherwiththeusualmatrixmultiplication,thissetformsagroupwhichisabelianforn=1butnon-abelianforn>1.
ThisgroupisdenotedbyGL(n,C).
Itisalsoacontinuous,inotherwords,anon-discretegroup,andsincetheunderlyingsetisadifferentiablemanifold,itisalsoaLIEgroup.
Likewise,GL(n,R):=M∈Mat(n*n,R)detM=0formsagroup.
LemmaF.
5LetN∈N.
ThenthesetG={0,1,.
.
.
,N1}withthegroupmultiplicationgivenbyadditionmoduloN,thatis,a+ZNb:=(a+b)modN(F.
11)isaniteabeliangroup(G,+ZN)denotedbyZN.
Moreover,foraprimepthesetG{0}={1,.
.
.
,p1}withgroupmul-tiplicationgivenbya·Zpb:=(ab)modp(F.
12)alsoconstitutesaniteabeliangroup(G{0},·Zp),whichisdenotedbyZ*p.
AppendixF:SomeGroupTheory563ProofFirst,considertheadditivegroupZN.
Since(a+b)modN∈{0,.
.
.
,N1},thegroupmultiplicationgivenin(F.
11)isamapG*G→Gand,dueto(D.
23),itisassociative.
Theneutralelementise+=0andtheinverseofana∈G{0}isgivenbya1=Na∈Gsincea+ZNa1=(F.
11)(a+Na)modN=0=e+.
(F.
13)Clearly,Gisniteanda+ZNb=b+ZNa.
NowconsiderZ*p,wherepisaprime,andleta,b∈{1,.
.
.
,p1}suchthatamodp=0=bmodp.
From(D.
28)inLemmaD.
11itthenfollowsthat(ab)modp=0.
Consequently,(ab)modp∈{1,.
.
.
,N1},andthegroupmultiplicationgivenin(F.
12)isamapG{0}*G{0}→G{0}.
Becauseof(D.
20),itisassociative.
Theneutralelementofthisgroupise·=1sinceforanya∈{1,.
.
.
,p1}wehavea·Zpe·=amodp=a.
Moreover,sinceforanysuchawehavegcd(a,p)=1,weknowfrom(D.
12)intheextendedEUCLIDalgorithmgiveninTheoremD.
4thatwecanalwaysndx,y∈Zsuchthatax+py=1.
LemmaD.
9thenimpliesthatxmodp=a1modp∈G{0}suchthata·Zp(xmodp)=(F.
12)a(xmodp)modp=(D.
27)1.
Hence,everya∈G{0}hasaninverseunder·ZpinG{0}.
Obviously,a·Zpb=(ab)modp=b·Zpa,andtheproofthatZ*pisaniteabeliangroupiscomplete.
DenitionF.
6Let(G,·)beagroupwithneutralelemente.
AsubsetHGwhichsatisese∈H(F.
14)h∈Hh1∈H(F.
15)h1,h2∈Hh1·h2∈H(F.
16)iscalledasubgroupofG,andthisisexpressedbywritingH≤G.
AsubgroupHiscalledapropersubgroupofGifHG,andthisisexpressedbywritingH1wehavethatNZisapropersubgroupofZ,thatis,NZ1.
Foranyelementg∈Zwehavethecoset570AppendixF:SomeGroupTheory[g]NZ=g+Nkk∈Z={g,g±N,g±2N,g±3N,.
.
.
}={gmodN,gmodN±N,gmodN±2N,gmodN±3N,.
.
.
}=[gmodN]NZ,(F.
24)thatis,anycoset[g]NZ∈NZisequalto[m]NZ,wherem=gmodN∈{0,1,.
.
.
,N1}.
IfHisasubgroupofthegroupG,thenwehaveforanyk∈Handanyg∈GkH=(F.
22)khh∈H=hh∈H=HgkH=(F.
22)gkhh∈H=ghh∈H=gH.
(F.
25)LemmaF.
20LetHbeasubgroupofthegroupG.
Foranytwog1,g2∈Gtheirleftcosetsg1Handg2Hareeitherdisjointortheyareidentical.
Thesameholdsforanytworightcosets.
ProofIfg1H∩g2H=/0theyaredisjoint,andthereisnothingtoprove.
Supposethenthatthereisag∈g1H∩g2H,namelythatthereexisth1,h2∈Hsuchthatg1h1=g=g2h2.
(F.
26)Sinceh1,h2∈HandHisasubgroup,wehaveh1h12∈H.
Consequently,foranyh∈Hg2h=(F.
26)g1h1h12h∈H∈(F.
22)g1Handthusg2Hg1H.
(F.
27)Similarly,wehaveh2h11∈Hg1=(F.
26)g2h2h11∈H∈(F.
22)g2H,whichimpliesg1Hg2H,(F.
28)AppendixF:SomeGroupTheory571anditfollowsfrom(F.
27)and(F.
28)thatg1H∩g2H=/0impliesg1H=g2H.
ThepreviouslemmaallowsustoprovewhatingrouptheoryisknownasLAGRANGE'sTheorem,whichstatesthatforanitegroupthenumberofitsele-mentsisdivisiblebythenumberofelementsofanysubgroup.
TheoremF.
21LetHbeasubgroupofthenitegroupG.
ThenthenumberofelementsineachleftcosetgHisequaltotheorder|H|ofH,namelythenumberofelementsinH.
Moreover,theorderofHdividestheorderofGandGisthedisjointunionofJ=|G||H|∈NleftcosetsofH,thatis,therearegj∈Gwithj∈{1,.
.
.
,J}suchthatgiH∩gjH=/0ifi=jandG=Jj=1gjH.
(F.
29)Thesamestatementholdsfortherightcosets.
ProofWeonlyprovethestatementsforleftcosetshere.
Theprooffortherightcosetsis,ofcourse,similar.
First,weprove(F.
29).
Forthiswepickanyg∈Gandsetg1=g.
Then,succes-sivelyforj∈Nandaslongasji=1giH=G,wepickanyg∈Gji=1giHandsetgj+1=g.
Byconstruction,wehaveforanyk∈{1,.
.
.
,j}thatgj+1/∈gkHanditfollowsfromLemmaF.
20thatgj+1HisdisjointfromallsuchgkH.
Moreover,sinceGisassumednite,thisprocessterminatesforaJthatsatises(F.
29).
Next,weprovethestatementaboutthenumberofelementsincosetsgHforagiveng∈G.
Foranytwoelementsh1,h2∈Hwithh1=h2itfollowsthatgh1=gh2.
Consequently,thenumberofelementsingH={gh|h∈H}isequaltothenumberofelementsinH.
Hence,(F.
29)impliesthatGistheunionofJdisjointsetseachofwhichhas|H|elements.
Therefore,thenumberofelementsinGisgivenby|G|=J|H|.
Weknowalreadythatforabeliangroupsleftandrightcosetsofanysubgroupcoincide.
Thisisactuallyageneralpropertyofnormalsubgroupsofany(notneces-sarilyabelian)group.
ExerciseF.
129LetHbeasubgroupofthegroupG.
ShowthatthenHisnormalgH=Hgg∈G.
572AppendixF:SomeGroupTheoryForasolutionseeSolutionF.
129Foranormalsubgroupwethusdonotneedtodistinguishbetweenleftandrightcosets.
Moreover,thesetofcosetsofanormalsubgroupcanbeendowedwithamultiplicationandmadeintoagroupitselfasthefollowingpropositionshows.
PropositionF.
22LetGbeagroupwithneutralelementeandletHG.
Thentheset[g]Hg∈Gofcosetsformsagroupwithmultiplication:forallg1,g2∈G[g1]H·[g2]H:=[g1g2]H,(F.
30)neutralelement:[e]H=H,(F.
31)inverse:foreachg∈G([g]H)1:=g1H.
(F.
32)Moreover,foranyg1,g2∈Gwehave[g1]H=[g2]Hh∈H:g1=g2h.
(F.
33)ProofSinceforanyg1,g2∈Gwehaveg1g2∈G,themultiplicationdenedin(F.
30)isabinarymap·:[g]Hg∈G*[g]Hg∈G→[g]Hg∈G[g1]H,[g2]H→[g1g2]H,andassociativityof·followsfromassociativityinG:([g1]H·[g2]H)·[g3]H=(F.
30)[g1g2]H·[g3]H=(F.
30)([g1g2)g3]H=(F.
1)[g1g2g3]H.
Toshowthattheproductasdenedin(F.
30)doesnotdependontheparticularg1andg2chosentorepresentthecosets[g1]Hand[g2]H,requirestheinvariancepropertyofH.
Forthisleti∈{1,2}andgi∈Gbesuchthatgi=gi,but[gi]H=[gi]H.
Thenthereexisthi∈Hfori∈{1,2}suchthatgi=gihiandthus[g1g2]H=[g1h1g2h2]H=(F.
25)[g1h1g2]H.
(F.
34)AppendixF:SomeGroupTheory573SinceHisassumednormal,DenitionF.
15impliesthatforanyh∈Handg∈Gthereexistsanh∈Hsuchthatghg1=handthusgh=hg.
Usingthisforh=h1andg=g2in(F.
34)gives[g1g2]H=[g1h1g2]H=g1g2h1H=(F.
25)[g1g2]H,whichshowsthattheproductoftwocosets[g1]H·[g2]Hasdenedin(F.
30)doesnotdependonthechoiceofthegitorepresentthecosets.
Foranyg∈Gwehave[g]H·[e]H=(F.
30)[ge]H=(F.
2)[g]H,whichprovesthat[e]Hisindeedtheneutralelement.
Finally,[g]H·([g]H)1=(F.
32)[g]H·g1H=(F.
30)gg1H=(F.
3)[e]H,whichveriesthatevery[g]Hhasaninversein[g]Hg∈G.
Toprove(F.
33),letg1,g2∈G.
Thenwehave[g1]H=[g2]H(F.
22){g1h1|h1∈H}={g2h2|h2∈H}h1∈Hh2∈Handh2∈Hh1∈H:g1h1=g2h2h1∈Hh2∈Handh2∈Hh1∈H:g1=g2h2h11=h∈Hh∈H:g1=g2h.
Foranormalsubgroup,thestatementsinPropositionF.
22allowustodeneagroupthatconsistsofcosets.
Thisgroupformedbycosetsiscalledisthequotientgroup.
DenitionF.
23LetHbeanormalsubgroupofthegroupG.
Thegroup[g]Hg∈G,·givenbythecosetsofHinGwiththemultiplication,neutralelementandinversesasgivenin(F.
30)–(F.
32)iscalledthequotientgroupofHinGanddenotedbyG/H.
574AppendixF:SomeGroupTheoryExampleF.
24Consideragainthegroup(Z,+)ofExampleF.
3anditssubgroup(NZ,+)ofExampleF.
7forsomeN>1.
Thegroupmultiplicationoftwocosets[g1]NZ,[g2]NZ∈Z/NZ,whichwewriteas+Z/NZsincewearedealingwithanabeliangroup,isthengivenby[g1]NZ+Z/NZ[g2]NZ=(F.
24)[g1modN]NZ+Z/NZ[g2modN]NZ=(F.
30)[g1modN+g2modN]NZ=(F.
24)[(g1modN+g2modN)modN]NZ=(D.
23)[(g1+g2)modN]NZ=(F.
11)(g1+ZNg2)NZ,(F.
35)where+ZNisthegroupmultiplicationinZNofLemmaF.
5.
Foranitegroup,thenumberofelementsinaquotientgroupofanyofitssub-groupsisindeedthequotientgivenbythenumberofelementsinthegroupdividedbythenumberofelementsinthesubgroupasthefollowingcorollaryshows.
CorollaryF.
25LetHbeanormalsubgroupofthenitegroupG.
ThentheorderofthequotientgroupG/HisgivenbythequotientoftheordersofGandH,namely|G/H|=|G||H|.
(F.
36)ProofFromTheoremF.
21weknowthatthereareexactly|G||H|distinctcosetsin[g]Hg∈G,whichisthesetofelementsofthegroupG/H.
Hence,anynormalsubgroupofagroupgivesrisetoanewgroupformedbytheirquotientgroup.
Thisisonewaytoconstructnewgroupsfromexistingones.
Anotherwaytodothisisbyformingthedirectproductgroupoftwogroups(G1,·1)and(G2,·2).
Theunderlyingsetofthisgroupisthecartesianproduct,andmultiplicationisdenedcomponent-wiseineachofthegroups.
ExerciseF.
130Let(G1,·G1)and(G2,·G2)betwogroups.
ShowthatthesetG1*G2togetherwiththemultiplicationAppendixF:SomeGroupTheory575(g1,g2)·*(g1,g2):=g1·G1g1,g2·G2g2(F.
37)formsagroup,andthatifG1andG2arebothnite,thisgroupisalsoniteandsatises|G1*G2|=|G1||G2|.
(F.
38)ForasolutionseeSolutionF.
130AsaconsequenceofthestatementinExerciseF.
130,wecangivethefollowingdenition.
DenitionF.
26Let(G1,·G1)and(G2,·G2)begroups.
Theirdirectprod-uctgroupG1*G2,·*isdenedasthesetofpairs(g,k)∈G1*G2withcomponent-wisemultiplication·*:G1*G2*G1*G2→G1*G2(g1,g2),(g1,g2)→(g1·G1g1,g2·G2g2).
(F.
39)Beforeweturntomapsbetweengroupsandrelatedconcepts,weintroducethenotionofa(left)actionofagrouponasetandthatofastabilizeronaset.
DenitionF.
27LetGbeagroupwithneutralelementeandletMbeaset.
AleftactionofGonMisdenedasamapΛ:G*M→M(g,m)→g.
mthatsatisesforallh,g∈Gandm∈Me.
m=m(F.
40)hg.
m=h.
(g.
m).
(F.
41)ThestabilizerofasubsetQMundertheleftactionisdenedasStaG(Q):=g∈Gg.
m=mm∈Q.
(F.
42)ExerciseF.
131LetGbeagroupwhichactsbyleftactiononasetM.
ShowthatforanysubsetQMitsstabilizerisasubgroupofG,thatis,StaG(Q)≤G.
576AppendixF:SomeGroupTheoryForasolutionseeSolutionF.
131F.
2Homomorphisms,CharactersandDualGroupsAnotherwaytoconnecttwogroupsisbymapsfromonegroupintotheothersuchthatthegroupmultiplicationineachofthegroupsispreservedbythemap.
Suchmapsarecalledhomomorphisms.
If,inaddition,theyarebijective,theyarecalledisomorphisms.
DenitionF.
28Ahomomorphismbetweentwogroups(G1,·G1)and(G2,·G2)isamap:G1→G2thatmaintainsthegroupmultiplication,thatis,whichsatisesforallg,h∈G1(g)·G2(h)=(g·G1h).
(F.
43)ThesetofallhomomorphismsfromagroupG1toagroupG2isdenotedbyHom(G1,G2).
Thepre-imageinG1oftheneutralelemente2∈G2underahomomorphism,namelythesetKer():=g∈G1(g)=e2,(F.
44)iscalledthekernelof.
Amap:G→Giscalledanisomorphismifitisahomomorphismandabijection.
TwogroupsG1andG2aresaidtobeisomorphicifthereexistsanisomorphismbetweenthem,andthisisexpressedbythenotationG1=G2.
ExampleF.
29Consideragainthegroup(Z,+)ofExampleF.
3anditssubgroup(NZ,+)ofExampleF.
7forsomeN>1.
WewillshowthatthequotientgroupZ/NZisisomorphictothegroupZN,whichwasdenedinLemmaF.
5andwhichconsistsoftheintegers{0,1,.
.
.
,N1}withmultiplicationgivenbyadditionmod-uloN.
Moreprecisely,wewillshowthatthemap:Z/NZ→ZN[g]NZ→gmodN(F.
45)constitutesanisomorphismbetweenthetwogroupsZ/NZandZN.
Tobeginwith,weshowthatiswelldened,inotherwords,thattheimage[g]NZdoesnotdependontheg∈Zchosentorepresentthecoset[g]NZ.
ToseeAppendixF:SomeGroupTheory577this,letg1,g2∈Zbesuchthat[g1]NZ=[g2]NZ.
Thenitfollowsfrom(F.
24)that[g1modN]NZ=[g2modN]NZ.
SincegimodN∈{0,1,.
.
.
,N1}fori∈{1,2},thisimpliesg1modN=g2modN,hence,[g1]NZ=[g2]NZ.
Now,supposeg1,g2∈Zaresuchthat[g1]NZ=[g2]NZ.
Thenitfollowsagainfrom(F.
24)thatg1modN=g2modN,sinceotherwisetheircosetswouldbeequal.
Consequently,[g1]NZ=[g2]NZ,whichmeansthatisinjective.
Itisalsosur-jective,since,againusing(F.
24),everym∈{0,1,.
.
.
,N1}uniquelydenesacoset[m]NZ,whichalsosatises[m]NZ=m.
Therefore,isabijection.
Itremainstoshowthatisalsoahomomorphism.
Forthisweapplytobothsidesof(F.
35)toobtain[g1]NZ+Z/NZ[g2]NZ=(F.
35)[(g1+g2)modN]NZ=(F.
45)(g1+g2)modN=(F.
11)g1modN+ZNg2modN=(F.
45)[g1]NZ+ZN[g2]NZ,whichshowsthatsatises(F.
43),henceisalsoahomomorphism.
Altogether,wehavethusshownthatZ/NZ=ZN.
(F.
46)Asaresultof(F.
46)weshallnolongerdistinguishbetweenZ/NZandZNandalsousethenotation[m]NZtodenoteanelementm∈ZN.
LemmaF.
30Let∈Hom(G1,G2)beahomomorphismbetweenthetwogroupsG1andG2.
ThenKer()isanormalsubgroupofG1,thatis,Ker()G1.
ProofWerstshowthatKer()isasubgroupofG1.
Fori∈{1,2}leteidenotetheneutralelementinGi.
Foranyg∈G1wehave(e1)=(F.
3),(F.
2)(e1)(g)(g)1=(F.
43)(e1g)(g)1=(F.
9)(g)(g)1=(F.
3)e2,(F.
47)578AppendixF:SomeGroupTheorywhichshowsthate1∈Ker()andveries(F.
14).
Next,foranyh∈Ker()itfollowsthat(h1)=(F.
9)e2(h1)=(F.
44)(h)(h1)=(F.
43)(hh1)=(F.
3)(e1)=(F.
47)e2,whichshowsthath1∈Ker()andveries(F.
15).
Finally,foranyh1,h2∈Ker()(h1h2)=(F.
43)(h1)(h2)=(F.
44)e2e2=e2,whichshowsthath1h2∈Ker()andveries(F.
16).
NowthatwehaveshownthatKer()isasubgroup,itremainstoshowthatitisnormal.
Forthisletg∈G1bearbitraryandleth∈Ker()g,thatis,thereisanh∈Ker()suchthath=ghg1.
Thenwehave(h)=(ghg1)=(F.
43)(g)(h)(g1)=(F.
44)(g)e2(g1)=(g)(g1)=(F.
43)(gg1)=(e1)=e2,whichshowsthatforanyg∈G1wehavethath∈Ker()gimpliesh∈Ker().
Hence,wehaveshownthatKer()gKer()g∈G1.
(F.
48)Tonallyshowthereverseinclusion,leth∈Ker()andg∈G1bearbitrary.
Thenk=g1hg(F.
49)satises(k)=(g1hg)=(F.
43)(g1)(h)(g)=(F.
44)(g1)e2(g)=(g1)(g)=(F.
43)(g1g)=(e1)=(F.
47)e2suchthatk∈Ker().
Butthenitfollowsforthearbitraryh∈Ker()thath=(F.
49)gkg1∈Ker()g.
AppendixF:SomeGroupTheory579Consequently,wehaveKer()Ker()gg∈G1,which,togetherwith(F.
48),nallyprovesthatKer()=Ker()gforallg∈G1,thatis,Ker()isanormalsubgroupofG1.
ExerciseF.
132Showthatanyhomomorphism:G1→G2betweentwogroupsG1andG2satises(g1)=(g)1g∈G1.
(F.
50)ForasolutionseeSolutionF.
132ThefollowingtheoremiscalledFirstGroupIsomorphismTheoremandisalsoknownasthefundamentalhomomorphismtheorem.
Itstatesthattheforahomo-morphismthequotientgroupoveritskernelcanbeidentiedwithitsimage.
TheoremF.
31(FirstGroupIsomorphism)LetG1andG2begroupsandlet∈Hom(G1,G2).
ThenwehaveG1/Ker()={G1},wheretheisomorphismisprovidedbythemap:G1/Ker()→{G1}[g]Ker()→(g).
(F.
51)ProofFromLemmaF.
30weknowthatKer()isanormalsubgroupofG1,andwecandenethequotientgroupG1/Ker().
Toshowthatisanisomorphism,werstshowthatitiswelldened.
Forthislet,ga,gb∈G1and[ga]Ker()=[gb]Ker().
Thenweknowfrom(F.
33)thatthereexistsanh∈Ker()suchthatga=gbh.
(F.
52)Consequently[ga]Ker()=(F.
51)(ga)=(F.
52)(gbh)=(F.
43)(gb)(h)=h∈Ker()(gb)e2=(F.
3)(gb)=(F.
51)[gb]Ker(),580AppendixF:SomeGroupTheoryprovingthatiswelldened.
Here,asusual,e2denotestheneutralelementinG2.
Injectivityofisprovenbythefollowingchainofimplicationsforgc,gd∈G1:[gc]Ker()=[gd]Ker()(F.
51)(gc)=(gd)(gd)1(gc)=e2(F.
43)(g1dgc)=e2(F.
44)g1dgc∈Ker()h∈Ker():gc=gdh(F.
22)[gc]Ker()=[gd]Ker().
Toshowsurjectivity,notethat{G1}={(g)|g∈G1}.
Therefore,foranyh∈{G1}thereexistsag∈G1suchthath=(g)=(F.
51)[g]Ker(),provingthatissurjectiveaswell.
Itremainstoshowthatisahomomorphism.
Forthisconsider[g1]Ker()[g2]Ker()=(F.
30)[g1g2]Ker()=(F.
51)(g1g2)=(F.
43)(g1)(g2)=(F.
51)[g1]Ker()[g2]Ker(),whichshowsthatindeed∈HomG1/Ker(),{G1}.
Averyusefulclassofhomomorphismsforthestudyofgroupsaretheso-calledcharactersofagroup.
Theycanbedenedforanygroup,butforusthespecialcaseofabeliangroupssufces.
DenitionF.
32AcharacterofanabeliangroupGisdenedasanelementχ∈HomG,U(1),whereU(1)=z∈Czz=1=eiαα∈R(F.
53)isthespecialunitarygroupinonedimension.
ForanycharacterχofanabeliangroupGwedenetheconjugatechar-acterχasχ:G→U(1)g→χ(g).
(F.
54)AppendixF:SomeGroupTheory581AspecialcharacterforanyabeliangroupGisthetrivialcharacter1G:G→U(1)g→1,(F.
55)whichmapsanygroupelementto1∈U(1).
NotethatbydenitionanycharacterχofanabeliangroupGbeingahomomor-phismfromGtoU(1),itsatisesforanyg1,g2∈Gχ(g1+Gg2)=(F.
43)χ(g1)χ(g2),(F.
56)where+GdenotesthegroupmultiplicationintheabeliangroupG,whereasontherightsidetheproductisinU(1),whichisjustamultiplicationoftwocomplexnumbersofunitmodulus.
Asaconsequenceof(F.
56),anycharacterofanabeliangrouphastomaptheneutralelementeofthegroupGto1,thatis,wehaveχ(e)=(F.
56)χ(g+Ge)χ(g)=1(F.
57)sinceg+Ge=g.
Actually,thisstatementalreadyfollowsfromLemmaF.
30sinceasasubgroupKer(χ)={g∈G|χ(g)=1}hastocontaine.
Moreover,sinceχ(g)∈U(1)1=(F.
53)χ(g)χ(g)=(F.
54)χ(g)χ(g),wehaveχ(g)=χ(g)1=(F.
50)χ(g1).
(F.
58)ExampleF.
33ForthegroupZNdenedinLemmaF.
5andconsideredinExam-pleF.
29,wehavethecharactersχn:ZN→U(1)[g]NZ→e2πingN,(F.
59)wheren∈{0,1,.
.
.
,N1}.
Toverify(F.
56),wenotethatforany[g1]NZ,[g2]NZ∈ZN582AppendixF:SomeGroupTheoryχn[g1]NZ+ZN[g2]NZ=(F.
35)χn[(g1+g2)modN]NZ=(F.
59)e2πin(g1+g2)modNN=e2πin(g1+g2)N=(F.
59)χn[g1]NZχn[g2]NZ.
Thekernelofaχnconsistsofallcosets[g]NZsuchthatngN∈Z,thatis,forwhichngmodN=0.
Thecharactersofanabeliangroupagainformagroup.
TheoremF.
34ThecharactersG=HomG,U(1)ofanabeliangroupGformanabeliangroupwiththethetrivialcharacter1Gastheneutralele-mentandwiththegroupmultiplication·:G*G→G(χ1,χ2)→χ1χ2,(F.
60)whereχ1χ2isthecharacterχ1χ2:G→U(1)g→χ1(g)χ2(g).
(F.
61)ProofToshowthatGisagroup,weneedtoshowthatthemultiplicationoftwoofitselementsasdenedin(F.
60)givesagainanelementofG,thatthereisaneutralelementforthismultiplication,andthateveryelementhasaninverseinG.
Letχ1,χ2∈Gandg1,g2∈G.
Thenwendχ1χ2(g1)χ1χ2(g2)=(F.
61)χ1(g1)χ2(g1)χ1(g2)χ2(g2)=(F.
43)χ1(g1g2)χ2(g1g2)=(F.
61)χ1χ2(g1g2)andχ1χ2asdenedin(F.
60)and(F.
61)isindeedanelementofHomG,U(1).
Foranyχ∈Gandg∈Gwehaveχ1G(g)=(F.
61)χ(g)1G(g)=(F.
55)χ(g)AppendixF:SomeGroupTheory583suchthatthemultiplication(F.
60)givesindeedχ1G=χforanyχ∈Gand1Gistheneutralelement.
Finally,foranyχ∈Gitsinverseisgivenbyitsconjugatecharacterχ∈G,sinceforanyg∈Gχχ(g)=(F.
61)χ(g)χ(g)=(F.
55)χ(g)χ(g)=(F.
53)1.
(F.
62)DenitionF.
35LetGbeanabeliangroup.
ThegroupG:=HomG,U(1)formedbyitscharacterswiththegroupmultiplicationgivenin(F.
60)and(F.
61)iscalledthedualorcharactergroupofG.
TheoremF.
36LetHbeasubgroupoftheniteabeliangroupG.
ThenanycharacterofHcanbeextendedtoacharacterofG,andthenumberofsuchextensionsis|G||H|.
ProofTobeginwith,werecallthatsubgroupsofabeliangroupsarealwaysnormal,sowecanalwaysformquotientgroupswiththem.
IfH=Gwearedone.
Otherwise,wehaveH1andgn=e.
Withthisnwedeneμg:g→U(1)gm→e2πimn.
Sinceanyelementg∈gcanbewrittenintheformg=gmforsomem∈Z,wehavethatμgisindeeddenedonallofgandforanygi=gmi∈gwithi∈{1,2},obviously,μg(g1g2)=μg(gm1+m2)=e2πim1+m2n=μg(g1)μg(g2).
AppendixF:SomeGroupTheory587Hence,μgisacharacterofthesubgroupg≤G,anditsatisesμg(g)=e2πin=1.
WethenapplyTheoremF.
36tothesubgroupgtoextendthecharacterμgtoacharacterχ∈Gsuchthatχg=μgandthusχ(g)=1.
LemmaF.
39LetHbeasubgroupoftheabeliangroupG.
ThenH⊥:=χ∈GHKer(χ)(F.
72)isasubgroupofG.
ProofLeteGdenotetheneutralelementofthedualgroupG.
SinceeG=1GandKer(1G)=G,wehaveHKer(eG)andthuseG∈H⊥,proving(F.
14).
Next,weshowthatH⊥isclosedundermultiplication.
Forthisletχ1,χ2∈H⊥andh∈Hbearbitrary.
Thenwehaveχ1χ2(h)=(F.
61)χ1(h)χ2(h)=h∈HKer(χi)1.
Hence,χ1χ2∈H⊥,and(F.
16)holds.
Itremainstoshowthatforanyχ∈H⊥itsinverseliesinH⊥.
From(F.
62)weknowalreadythattheconjugatecharacterχistheinverseofχ,soweonlyneedtoshowthatitisanelementofH⊥.
Forthisleth∈Hbearbitrary.
Thenχ∈H⊥impliesthath∈Ker(χ)andthusχ(h)=1fromwhichitfollowsthat1=χ(h)=(F.
54)χ(h).
Consequently,χ1=χ∈H⊥,andwehaveveried(F.
15),whichcompletestheproofthatH⊥isasubgroup.
ExampleF.
40LeteGdenotetheneutralelementofthegroupGandeGthatofthedualgroupG.
ForthetrivialsubgroupeG0thereisaδ(ε)=ε||ψ||suchthatfor0,∈Hthatsatisfy||0||≤δ(ε)itfollowsthat|ψ|0|≤(2.
17)||ψ||||0||≤||ψ||δ(ε)=ε.
(G.
55)Hence,ψ|:→ψ|iscontinuousat0.
Solution2.
6(i)Firstweshowthat(A)=A.
Forarbitrary|ψ,|∈Honehasψ|(A)=(2.
1)(A)|ψ=(2.
30)|Aψ=(2.
1)Aψ|=(2.
30)ψ|A.
Itfollowsthatψ|(A)A=0forarbitrary|ψ.
With(2.
8)thisimplies(A)|=A|forall|.
(ii)Letc∈CandA∈L(H)bearbitrary.
Thenwehaveforany|ψ,|∈H(cA)ψ|=(2.
30)ψ|cA=(2.
4)cψ|A=(2.
30)cAψ|=(2.
6)cAψ|andthus(cA)cAψ|=0(2.
8)(cA)cA|ψ=0|ψ∈H.
(iii)InthelinearmapsAψ|:H→C→Aψ|,ψ|A:H→C→ψ|ASolutionstoExercises645onethenhasAψ|=(2.
31)(A)ψ|=(2.
30)ψ|AandthusAψ|=ψ|A.
(iv)Let{|ej}beanONBinH.
Theclaim(2.
35)thenfollowsfromAjk=(2.
22)ej|Aek=(2.
30)(A)ej|ek=(2.
31)Aej|ek=(2.
1)ek|Aej=(2.
22)Akj.
(v)PerDenition2.
8oftheadjointoperatorwehaveforany|ξ,|η∈H|ψ|ξ|η=(2.
30)ξ||ψ|η=ξ|ψ|η=(2.
6)ψξ||η=(2.
1)ψ|ξ|η=|ψ|ξ|η(G.
56)andtheclaim(2.
36)followsfromthefactthat(G.
56)holdsforany|ξ,|η∈H.
Solution2.
7WeshowrstthatfromtheunitarityofUitfollowsthatUU=1.
Thenthatthisimplies||Uψ||=||ψ||andnallythatthisinturnimpliestheunitarityofU.
LetUbeunitary.
ThenonehasUψ|U=ψ||ψ,|∈H(2.
30)ψ|UU=ψ||ψ,|∈Hψ|UU=0|ψ,|∈H(2.
8)UU||=0|∈HUU=1.
NowsupposeUU=1.
Forany|ψ∈Hitfollowsthenthat||ψ||=(2.
5)ψ|ψ=ψ|UUψ=(2.
30)(U)ψ|Uψ=(2.
31)Uψ|Uψ=(2.
5)||Uψ||.
Finally,supposethat||Uψ||=||ψ||forall|ψ∈H.
Using(2.
9)twiceitfollowsthatforany|ψ,|∈Honehas646SolutionstoExercisesUψ|U=(2.
9)14||Uψ+U||2||UψU||2+i||UψiU||2i||Uψ+iU||2=14Uψ+2Uψ2+iUψi2iUψ+i2=14||ψ+||2||ψ||2+i||ψi||2i||ψ+i||2=(2.
9)ψ|andUisperDenition2.
9unitary.
Solution2.
8LetA|ψ=λ|ψfora|ψ=0inH.
(i)Becauseofψ|A=(2.
30)(A)ψ|=(2.
31)Aψ|=λψ|=(2.
6)λψ|thelinearmapsψ|A:H→C→ψ|A,λψ|:H→C→λψ|areidentical.
(ii)With|ψ=0onehasλψ|ψ=(2.
4)ψ|λψ=ψ|Aψ=Aψ|ψ=A=AAψ|ψ=λψ|ψ=(2.
6)λψ|ψandthusA=Aimpliesλ=λ.
(iii)LetU|ψ=λ|ψfora|ψ=0inHandletbeUunitary,suchthat||ψ||=(2.
37)||Uψ||=||λψ||=(2.
7)|λ|||ψ||andthus|λ|=1.
Solution2.
9Let|ej,αj∈{1,.
.
.
,d},α∈{1,.
.
.
,dj}betheONBofeigenstatesofA,thatis,letA|ej,α=λj|ej,α,(G.
57)SolutionstoExercises647wherewealloweacheigenspacetohavedimensiondj≥1.
ItfollowsfromDe-nition2.
3ofanONBthatany|ψ∈Hwith||ψ||=1canbewrittenintheform|ψ=d∑j=1dj∑α=1ψj,α|ej,α(G.
58)withd∑j=1dj∑α=1ψj,α2=(2.
14)||ψ||2=1.
(G.
59)Thenwehaveψ|Aψ=(G.
58)d∑j=1dj∑α=1ψj,α|ej,α|Ad∑k=1dk∑β=1ψk,β|ek,β=d∑j,kdj,dk∑α,β=1ψj,αψk,βej,α|Aek,β=(G.
57),(2.
4)d∑j,kdj,dk∑α,β=1ψj,αψk,βλkej,α|ek,β=δj,kδα,β=(2.
10)d∑jdj∑αψj,α2λj.
(G.
60)Consequently,λ1=(G.
59)d∑j=1dj∑α=1ψj,α2λ1≤(2.
39)d∑jdj∑αψj,α2λj=(G.
60)ψ|Aψ≤(2.
39)d∑j=1dj∑α=1ψj,α2λd=(G.
59)λd.
Solution2.
10With(2.
41)wehavePj=(2.
41)dj∑α=1|ej,αej,α|=dj∑α=1|ej,αej,α|=(2.
36)dj∑α=1|ej,αej,α|=(2.
41)Pj648SolutionstoExercisesandPjPk=dj∑α=1|ej,αej,α|dk∑β=1|ek,βek,β|=dj∑α=1dk∑β=1|ej,αej,α|ek,βek,β|=(2.
10)dj∑α=1dk∑β=1|ej,αδjkδαβek,β|=δjkdj∑α=1|ej,αej,α|=δjkPj,suchthatPjsatisesthedeningpropertiesofanorthogonalprojectiongiveninDenition2.
11.
Asthe{|ej,αj∈I,α∈{1,.
.
.
,dj}}areassumedtobeanONBofeigenvectorsofAanyeigenvector|ψ∈Eig(A,λj)canbewrittenintheform|ψ=(2.
20)dj∑α=1|ej,αej,α|ψ=(2.
41)Pj|ψshowingthatPjisindeedaprojectionontoEig(A,λj).
Solution2.
11LetPbeaprojectionandP|ψj=λj|ψjwithψj=1.
SinceP=Palleigenvaluesλjarereal.
FromP2=Pitalsofollowsthatλ2j=λ2jψj2=(2.
5)λ2jψj|ψj=(2.
4)ψj|λ2jψj=ψj|P2ψj=ψj|Pψ=ψj|λjψj=(2.
4)λjψj|ψj=(2.
5)λjψj2=λj.
Hence,wehaveλj=0or1andthusP=(2.
42)∑jλj|ψjψj|=∑j:λj=1|ψjψj|.
Solution2.
12Let|,|ψ∈Hbearbitrary.
Then(AB)ψ|=(2.
30)ψ|AB=(2.
30)Aψ|B=(2.
30)BAψ|.
Consequently,(AB)BAψ|=0|ψ,|∈H(2.
8)(AB)BA|ψ=0|ψ∈H,SolutionstoExercises649whichproves(AB)=BAandthus(2.
47).
Next,supposethatalsoA=AandB=B.
(G.
61)Thenwehave[A,B]=0(2.
46)AB=BA=(G.
61)BA=(2.
47)(AB),whichproves(2.
48).
Toshow(2.
49)notethatAA≤cBBDef.
2.
120≤ψ|cBBAAψ|ψ∈H(2.
4)0≤cψ|BBψψ|AAψ|ψ∈H(2.
30),(2.
31)0≤cBψ|BψAψ|Aψ|ψ∈H(2.
5)0≤c||Bψ||2||Aψ||2|ψ∈H||Aψ||≤√c||Bψ|||ψ∈H(2.
57)||A||≤√c||B||.
ThelastclaimofExercise2.
12thenfollowsfrom||1||=1.
Solution2.
13IfAisself-adjoint,thensoisA2andithastherealeigenvaluesλ2jj∈{1,.
.
.
,d}andthesameeigenvectorsasA.
Applying(2.
40)toA2,weobtainλ2d≥(2.
40)ψ|A2ψ=(2.
30)Aψ|Aψ=(2.
5)||Aψ||2,suchthat||Aψ||≤|λd|forany|ψ∈Hwith||ψ||=1.
Itthenfollowsfromthedenition(2.
45)oftheoperatornormthat||A||≤|λd|.
(G.
62)Ontheotherhand,anyeigenvector|edfortheeigenvalueλdwith||ed||=1satises||A|ed||=||λd|ed||=(2.
7)|λd|||ed||=|λd|.
650SolutionstoExercisesThedenitionoftheoperatornormgivenin(2.
45)thenimplies||A||≥|λd|.
(G.
63)Together(G.
62)and(G.
63)yield||A||=|λd|,whichistheclaim(2.
50).
Solution2.
14SinceA0=0thestatementistriviallytrueforthezerovector0∈H.
Supposethenthat|ψ=0.
Thus,wehave||ψ||=0andψ||ψ||=1.
Consequently,1||ψ||||Aψ||=(2.
7)1||ψ||Aψ=Aψ||ψ||≤sup||A|||∈H,||||=1=(2.
45)||A||.
Hence,||Aψ||≤||A||||ψ||(G.
64)asclaimed.
AccordingtoDenition2.
12||AB||=(2.
45)sup||ABψ|||ψ∈H,||ψ||=1≤(G.
64)sup||A||||Bψ|||ψ∈H,||ψ||=1≤||A||sup||Bψ|||ψ∈H,||ψ||=1=(2.
45)||A||||B||,whichproves(2.
52).
Again,accordingtoDenition2.
12||A+B||=(2.
45)sup||(A+B)ψ|||ψ∈H,||ψ||=1≤(2.
18)sup||Aψ||+||Bψ|||ψ∈H,||ψ||=1≤sup||Aψ|||ψ∈H,||ψ||=1+sup||Bψ|||ψ∈H,||ψ||=1=(2.
45)||A||+||B||.
Oncemore,accordingtoDenition2.
12SolutionstoExercises651||aA||=(2.
45)sup||aAψ|||ψ∈H,||ψ||=1=(2.
7)sup|a|||Aψ|||ψ∈H,||ψ||=1=|a|sup||Aψ|||ψ∈H,||ψ||=1=(2.
45)|a|||A||,proving(2.
54).
Next,consideranorthogonalprojectionPwhichsatises||Pψ||2=(2.
5)Pψ|Pψ=(2.
30)ψ|PPψ=Def.
2.
11ψ|P2ψ=Def.
2.
11ψ|Pψ≤(2.
16)||ψ||||Pψ||.
Hence,||Pψ||≤1forany|ψ∈Hwith||ψ||=1and(2.
45)impliesthat||P||≤1.
Ontheotherhand,theresultsofExercise2.
11showthatthereexist|ψj∈Hwithψj=1,suchthatP|ψj=|ψj.
ThusPψj=1and(2.
45)thenimpliesthat||P||=1.
Finally,foraunitaryoperatorU∈U(H)weknowalreadyfrom(2.
37)that||Uψ||=||ψ||forany|ψ∈H.
Hence,(2.
45)impliesthat||U||=1asclaimed.
Solution2.
15(i)Toshow,let{|ej=U|ej}beanONBinH.
ItfollowsthatUkj=ek|Uej=ek|ejandthus(UU)kl=∑jUkjUjl=∑jUkjUlj=∑jek|ejel|ej=∑jek|ejej|el=ek|∑jejej|el=|el=ek|el=δkl,suchthatU∈U(H).
Toprove,letU∈U(H)and|ej=U|ej.
Forany{aj}Citfollowsthat∑jaj|ej=0∑jajU|ej=0U∑jaj|ej=0UU∑jaj|ej=0(2.
37)∑jaj|ej=0Def.
2.
3aj=0j,652SolutionstoExercisessuchthatthe{|ej}Harelinearlyindependent.
Moreover,wehaveforany|ψ∈HU|ψ=(2.
11)∑jej|Uψ|ej=(2.
30),(2.
31)∑jUej|ψ|ej=∑jej|ψ|ej|ψ=(2.
37)UU|ψ=∑jej|ψU|ej=∑jej|ψ|ejshowingthatanyvectorinHcanbewrittenasalinearcombinationofthe|ej.
Finally,wehaveej|ek=Uej|Uek=(2.
30)ej|UUek=(2.
37)ej|ek=(2.
10)δjkcompletingtheproofthat{|ej}isanONBinH.
(ii)∑jej|Aej=∑jUej|AUej=∑jej|UAUej=∑j(UAU)jj=∑j,k,lUjkAklUlj=∑k,lAkl∑jUljUjk=∑k,lAkl∑j(UU)lk=δlk=∑kAkk=∑kek|Aek.
Solution2.
16(i)ForanyA,B∈L(H)wehavetr(AB)=∑j(AB)jj=∑j,kAjkBkj=∑j,kBkjAjk=∑k(AB)kk=tr(BA).
(ii)Theimplicationisobvious.
ToprovesupposeforallA∈L(H)wehavetr(AB)=0.
DeneArsastheoperatorthathasasthej,k-thmatrixelement(Ars)jk=δrjδsk.
Thenwendforanyr,s0=tr(ArsB)=∑j,k(Ars)jkBkj=∑j,kδrjδskBkj=Brs,suchthatB=0.
Solution2.
17Lett→U(t,t0)beasolutionof(2.
69).
ToshowtheunitarityofU(t,t0)considerSolutionstoExercises653ddt||U(t,t0)ψ||2=(2.
5)ddtU(t,t0)ψ|U(t,t0)ψ=ddtU(t,t0)ψ|U(t,t0)ψ+U(t,t0)ψ|ddtU(t,t0)ψ=(2.
69)iH(t)U(t,t0)ψ|U(t,t0)ψ+U(t,t0)ψ|iH(t)U(t,t0)ψ=(2.
4),(2.
6)iH(t)U(t,t0)ψ|U(t,t0)ψU(t,t0)ψ|H(t)U(t,t0)ψ=H(t)=H(t)iH(t)U(t,t0)ψ|U(t,t0)ψU(t,t0)ψ|H(t)U(t,t0)ψ=(2.
30)0.
Hence,forany|ψ∈Handt≥t0||U(t,t0)ψ||=const=||U(t0,t0)ψ||=(2.
69)||ψ||and(2.
37)impliesthatU(t,t0)∈U(H)forallt≥t0.
Supposet→V(t,t0)isanothersolutionof(2.
69).
TheproofthatithastobeequaltoU(t,t0)isarepetitionoftheaboveargumentswithUreplacedbyUV.
ddtU(t,t0)V(t,t0)ψ2=(2.
5)ddtU(t,t0)V(t,t0)ψ|U(t,t0)V(t,t0)ψ.
.
.
(2.
69),(2.
4),(2.
6)=iH(t)U(t,t0)V(t,t0)ψ|U(t,t0)V(t,t0)ψU(t,t0)V(t,t0)ψ|H(t)U(t,t0)V(t,t0)ψ=H(t)=H(t),(2.
30)0.
Consequently,forany|ψ∈Handt≥t0U(t,t0)V(t,t0)ψ=const=U(t0,t0)V(t0,t0)ψ=(2.
69)0,whichimpliesthatU(t,t0)=V(t,t0)forallt≥t0.
654SolutionstoExercisesSolution2.
18Sinceforallt≥t0wehaveU(t,t0)U(t,t0)=1=U(t,t0)U(t,t0),(G.
65)itfollowsthatfort=t01=U(t0,t0)U(t0,t0)=(2.
71)U(t0,t0),verifyingtheinitialcondition.
Takingthederivativewithrespecttotonbothsidesin(G.
65)wendddtU(t,t0)U(t,t0)=U(t,t0)ddtU(t,t0).
MultiplyingbothsideswithiandwithU(t,t0)fromtherightandusingagain(G.
65)weobtainiddtU(t,t0)=U(t,t0)iddtU(t,t0)U(t,t0)=(2.
71)U(t,t0)H(t)U(t,t0)U(t,t0)=(G.
65)U(t,t0)H(t),proving(2.
73).
Solution2.
19(i)Tobeginwith,onehasσ21=01100110=1001=1andndsanalogouslyσ22=1=σ23.
Furthermoreσ1σ2=01100ii0=i1001=iσ3=iε123σ3σ2σ1=0ii00110=i1001=iσ3=iε213σ3σ1σ3=01101001=i0ii0=iσ2=iε132σ2=σ3σ1SolutionstoExercises655σ2σ3=0ii01001=i0110=iσ1=iε231σ1=σ2σ3Fromthisandσ2j=1followsσjσk=δjk1+iεjklσl.
(ii)Hence[σj,σk]=σjσkσkσj=δjk1+iεjklσlδkjδjk1iεkjlεjklσl=2iεjklσl.
(iii)Againwithσjσk=δjk1+iεjklσlitfollowsthat{σj,σk}=σjσk+σkσj=δjk1+iεjklσl+δkj1+iεkjl=εjklσl=2δjk1.
(iv)Thatσj=σjholdsiseasilyveriedbyusingthedeningmatricesof(2.
74)and(2.
35).
Itfollowsthatσjσj=σ2j=(2.
76)1andfrom(2.
37)thatσj∈U(2).
Solution2.
20Todeterminetheeigenvaluesofσxwesolvedet(σxλ1)=detλ11λ=λ21=0tondλ±=±1.
Let|↑x=v+1v+2beeigenvectorfortheeigenvalueλ+=+1and|↓x=v1v2beeigenvectorfortheeigenvalueλ=1,thatis,onehasσxv±1v±2=0110v±1v±2=v±2v±1=λ±v±1v±2.
Thenv±1=±v±2holds,andwiththenormalizationcondition(v±1)2+(v±2)2=1wend|↑x=1√211=|0+|1√2and|↓x=1√211=|0|1√2(G.
66)656SolutionstoExercisesaseigenvectors,andthus|↑x|0|2=12=|↓x|0|2fortheprobabilities.
Solution2.
21ForσxwehavedeterminedintheSolution20ofExercise2.
20theeigenvalues+1,1andtheeigenvectors|↑x=1√211,|↓x=1√211.
Withtheseweobtainσx=(+1)|↑x|↑x|+(1)|↓x|↓x|=1√2111√2(11)1√2111√2(11)=(2.
27)121111121111=0110.
Solution2.
22Recallfrom(2.
83)thatρi∈D(H)fori∈{1,2}impliesρi=ρi(G.
67)ψ|ρiψ≥0|ψ∈H(G.
68)tr(ρi)=1(G.
69)suchthatforu∈[0,1]uρ1+(1u)ρ2=uρ1+(1u)ρ2=(G.
67)uρ1+(1u)ρ2ψ|uρ1+(1u)ρ2ψ=(2.
4)uψ|ρ1ψ+(1u)ψ|ρ2ψ≥(G.
68)0|ψ∈HDef.
2.
12uρ1+(1u)ρ2≥0tr(uρ1+(1u)ρ2)=utr(ρ1)+(1u)tr(ρ2)=(G.
69)1andthusuρ1+(1u)ρ2∈D(H).
SolutionstoExercises657Solution2.
23Inordertoshow(2.
84),weneedtoprovethatUρUsatisesalldeningproperties(2.
80)–(2.
82).
Tobeginwith,wehave(UρU)=(2.
47)(U)ρU=(2.
31)UρU=(2.
80)UρUprovingthatUρUisself-adjoint.
Asforpositivity,weobservethatforany|ψ∈Hψ|UρUψ=(2.
30)Uψ|ρUψ≥Def.
2.
12and(2.
81)0andthus,againaccordingtoDenition2.
12,itfollowsthatUρU≥0.
Lastly,tr(UρU)=(2.
58)tr(UUρ)=(2.
37)tr(ρ)=(2.
82)1verifying(2.
82)forUρUaswell.
Solution2.
24Letthedensityoperatorbegivenasρψ=|ψψ|(G.
70)forapurestate|ψandletA=∑kλk|ekek|(G.
71)beanobservablegivenindiagonalformwiththeeigenvalues{λk}and{|ek}anONBconsistingoftherespectiveeigenvectors.
Moreover,letPλdenotetheprojec-tionontotheeigenspaceofλ∈{λk}.
Weproceedtoverifythatthegeneralizationsfortheexpectationvalue,measurementprobability,projectionontothestateaftermeasurementandtimeevolutiongiveninPostulate6forρψcoincidewiththestate-mentsmadeforapurestate|ψinthePostulates1–4.
658SolutionstoExercisesExpectationValueAρψ=(2.
85)trρψA=(G.
70)tr(|ψψ|A)=(G.
71)tr|ψψ|∑kλk|ekek|=∑kλktr(|ψψ|ekek|)=(2.
57)∑k,jλkej|ψψ|ekek|ej=δjk=∑kλkψ|ekek|ψ=ψ|∑kλk|ekek|ψ=(G.
71)ψ|Aψ=(2.
60)AψMeasurementProbabilityPρψ(λ)=(2.
86)tr(ρPλ)=(G.
70)tr(|ψψ|Pλ)=Def.
2.
11tr|ψψ|P2λ=(2.
58)tr(Pλ|ψψ|Pλ)=(2.
57)∑kek|Pλψψ|Pλek=Def.
2.
11∑kek|PλψPλψ|ek=Pλψ|∑k|ekek|Pλψ=Pλ|ψ=Pλψ|Pλψ=||Pλψ||2=(2.
62)Pψ(λ)(G.
72)ProjectionFrom(G.
72)weseethattrρψPλ=||Pλψ||2(G.
73)andthusPλρψPλtrρψPλ=(G.
70),(G.
73)Pλ|ψψ|Pλ||Pλψ||2=Def.
2.
11Pλ|ψψ|Pλ||Pλψ||2=(2.
33)Pλ|ψPλψ|||Pλψ||2=Pλ|ψ||Pλψ||Pλψ|||Pλψ||=ρPλ|ψ||Pλψ||,thatis,PλρPλtr(ρPλ)isthedensityoperatorofthepurestatePλ|ψ||Pλψ||.
TimeEvolutionLetρ(t0)=ρψ(t0)=|ψ(t0)ψ(t0)|betheinitialstateandρ(t)bethestateattimet.
ThenwehaveSolutionstoExercises659ρ(t)=(2.
88)U(t,t0)ρ(t0)U(t,t0)=U(t,t0)|ψ(t0ψ(t0)|U(t,t0)=(2.
33)|U(t,t0)ψ(t0)U(t,t0)ψ(t0)|=(2.
70)ρU(t,t0)|ψ(t0)=(2.
71)ρψ(t),thatis,ρ(t)isthedensityoperatorofthepurestate|ψ(t)=U(t,t0)|ψ(t0).
Solution2.
25WehaveAρ=(2.
85)tr(ρA)=(2.
100)tr∑jpj|ψjψj|A=∑jpjtr(|ψjψj|A)=(2.
57)∑jpj∑kψk|ψj=δjkψj|Aψk=∑jpjψj|Aψj(G.
74)andthusAψ=(2.
60)ψ|Aψ=(2.
100)∑j√pjψj|A∑k√pkψk=(2.
4),(2.
6)∑j,k√pjpkψj|Aψk=∑jpjψj|Aψj+∑j=k√pjpkψj|Aψk=(G.
74)Aρ+∑j=k√pjpkψj|Aψk.
Solution2.
26Tobeginwith,wehaveρ=25|↑x↑x|+35|00|=(G.
66),(2.
78)251√2111√2(11)+3510(10)=(2.
29)151111+351000=154111.
Obviouslytr(ρ)=1.
Todeterminetheeigenvaluesp1,2,wesolvedet(ρλ1)=det154λ111λ=λ2λ+325=0660SolutionstoExercisesandndp±=12±√1310.
Let|ψ±=u±v±betheeigenvectorsfortheeigenvaluespi,thatis,154111u±v±=154u±+v±u±+v±=p±u±v±.
Asasolutionofthatwendafternormalization|ψ±=1266√132±√133.
Withthisweobtainp+|ψ+ψ+|+p|ψψ|=12+√1310266√132√1332√133+12√131026+6√132√1332√133=12+√1310266√1342√1362√136226√13+12√131026+6√1342√1362√13622+6√13=.
.
.
=1108222=154111=ρ.
Toshowthatρ>ρ2,werstobservethatρρ2=1541111541112=1252055512517552=1253003.
Nowlet|φ=φ1φ2∈H{0}bearbitrary.
Thenφ|(ρρ2)φ=φ1φ21253003φ1φ2=3(φ1)2+(φ2)225>0|φ∈H{0}andthusρ>ρ2.
SolutionstoExercises661Solution2.
27Let|,|ψ∈H.
Ontheonehand,wehaveρ+ψ=(|+|ψ)(|+ψ|)=||+|ψ|+|ψ|+|ψψ|andontheotherhandρ+eiαψ=|+|eiαψ|+eiαψ|=|+eiα|ψ|+eiαψ|=||+eiα|ψ|+eiα|ψ|+|ψψ|,suchthatρ+eiαψρ+ψ=eiα1|ψ|+eiα1|ψ|.
Solution2.
28Generally,wehavefortheprobabilitytomeasuretheeigenvalueλiofA=∑j|ejλjej|inthestateρPeiρ=(2.
86)tr(Peiρ).
(G.
75)Forpurestatesρψ=|ψψ|thisbecomesPeiρψ=(2.
101)|ei|ψ|2.
(G.
76)ForA=σzonethenhasλ1=+1,λ2=1,|e1=|0=10,|e2=|1=01.
(i)With|ψ=|↑x=|0+|1√2,Eq.
(G.
76)becomesPe1ρ|↑x=|e1|↑x|2=0||0+|1√22=12.
(ii)With|ψ=|↓x=|0|1√2,itfollowssimilarlythatPe1ρ|↓x=|e1|↓x|2=0||0|1√22=12.
662SolutionstoExercises(iii)Likewise,with|ψ=1√2(|↑x+|↓x)=|0,itfollowsfrom(G.
76)thatPe1ρ|0=|e1|0|2=|0|0|2=1.
(iv)Finally,onehaswithρ=12(|↑x|↑x|+|↓x|↓x|)and|↑x=1√2(|0+|1)=1√211aswellas|↓x=1√2(|0|1)=1√211thatρ=121√2111√211+1√2111√211=141111+1111=121001=121.
Then(G.
75)impliesPe1ρ=trPe1121=12.
Solution2.
29From(2.
76)inExercise2.
19weknowthatσjσk=δjk1+iεjklσl.
Usingthis,wenda·σb·σ=∑j,kajbkσjσk=(2.
76)∑j,kajbkδjk1+iεjklσl=∑j,kajbkδjk1+i∑j,kajbkεjklσl=(a·b)1+i(a1b2ε123σ3+a2b1ε213σ3+a1b3ε132σ2+a3b1ε312σ2+a2b3ε231σ1+a3b2ε321σ1)=(a·b)1+i(a1b2a2b1)σ3+i(a3b1a1b3)σ2+i(a2b3a3b2)σ1=(a·b)1+i(a*b)·σ.
SolutionstoExercises663Solution2.
30Wehavetr(ρxσj)=(2.
127)tr121+x·σσj=12trσj+3∑k=1xkσkσj=12tr(σj)=0+123∑k=1xktr(σkσj)=(2.
76)123∑k=1xktr1δkj+iεkjlσl=123∑k=1xkδkjtr(1)=2+iεkjltr(σl)=0=xj.
Solution2.
31WithA2=1wehaveeiαA=∞∑n=0(iα)nn!
An=∞∑k=0(iα)2k2k!
A2k=1+∞∑j=0(iα)2j+1(2j+1)!
A2j+1=A=1∞∑k=0(iα)2k2k!
=cosα+A∞∑j=0(iα)2j+1(2j+1)!
=isinα=cosα1+isinαA.
Solution2.
32Letn∈S1R3andα,β∈R.
ThenwehaveDn(α)Dn(β)=(2.
130)cosα21isinα2n·σcosβ21isinβ2n·σ=cosα2cosβ21sinα2sinβ2(n·σ=1)2icosα2sinβ2+sinα2cosβ2=sinα+β2n·σ664SolutionstoExercises=cosα2cosβ2sinα2sinβ2=cosα+β21isinα+β2n·σ=cosα+β21isinα+β2n·σ=Dn(α+β).
Solution2.
33FromLemma2.
32weknowalreadythatthereexistα,β,γ,δ∈Rsuchthatinthestandardbasis{|0,|1}thematrixofUisgivenbyU=(2.
133)eiαeiβ+δ2cosγ2eiδβ2sinγ2eiβδ2sinγ2eiβ+δ2cosγ2.
(G.
77)Ontheotherhand,wehaveDz(δ)=(2.
31)cosδ21isinδ2z·σ=cosδ21isinδ2σz=cosδ2isinδ200cosδ2+isinδ2=eiδ200eiδ2andDy(γ)=(2.
31)cosγ21isinγ2y·σ=cosγ21isinγ2σy=cosγ2sinγ2sinγ2cosγ2suchthatDz(β)Dy(γ)Dz(δ)=eiβ200eiβ2cosγ2sinγ2sinγ2cosγ2eiδ200eiδ2=eiβ+δ2cosγ2eiδβ2sinγ2eiβδ2sinγ2eiβ+δ2cosγ2.
Togetherwith(G.
77)thisresultsinU=eiαDz(β)Dy(γ)Dz(δ).
SolutionstoExercises665Solution2.
34σxDy(η)σx=(2.
130)σxcosη21isinη2y·σσx=cosη2σ2x=1isinη2σxσy=iσzσx=cosη21+sinη2σzσx=iσy=cosη21+isinη2σy=(2.
131)Dy(η).
Similarly,oneshowsthesecondequationin(2.
151).
Solution2.
35LetA=abcd∈L(H).
Settingz0=a+d2,z1=b+c2,z2=ibc2,z3=ad2,yields3∑α=0zασα=z0+z3z1iz2z1+iz2z0z3=abcd=A.
FromLemma2.
35weknowthatthereexistα,ξ∈Randn∈S1R3suchthatforanyA∈U(H)A=eiαDn(ξ)=(2.
130)eiαcosξ21isinξ2n·σ=z01+z·σ,wherewenowhavesetz0=eiαcosξ2,z=isinξ2n,suchthat|z0|2+|z|2=cos2ξ2+sin2ξ2|n|2=cos2ξ2+sin2ξ2=1.
666SolutionstoExercisesSolutionstoExercisesfromChapter3Solution3.
36(a|)|ψ(ξ,η)=(3.
1)ξ|aη|ψ=(2.
4)aξ|η|ψ=(3.
1)a||ψ(ξ,η)Similarly,oneshows|(a|ψ)=a(||ψ).
Nextwehavea(||ψ)+b(||ψ)(ξ,η)=(3.
3)a(||ψ)(ξ,η)+b(||ψ)(ξ,η)=(3.
1)aξ|η|ψ+bξ|η|ψ=(a+b)ξ|η|ψ=(3.
1)(a+b)||ψ(ξ,η)and(|1+|2)|ψ(ξ,η)=(3.
1)ξ|(|1+|2)η|ψ=(ξ|1+ξ|2)η|ψ=ξ|1η|ψ+ξ|2η|ψ=(3.
1)|1|ψ+|2|ψ(ξ,η).
Similarly,oneshows|(|ψ1+|ψ2)=||ψ1+||ψ2.
Solution3.
37SupposetheΨab∈Caresuchthat∑a,bΨab|eafb=0∈HAHB.
Hence,(3.
1)impliesthatforany(ξ,η)∈HA*HBSolutionstoExercises667∑a,bΨab|eafb(ξ,η)=(3.
3),(3.
1)∑a,bΨabea|ξfb|η=0andinparticularforevery(ξ,η)=(ea,fb)0=∑a,bΨabea|eaδa,afb|fbδb,b=Ψa,b.
AccordingtoDenition2.
3thevectorsintheset{|eafb}arethenlinearlyinde-pendent.
Solution3.
38Let{|ea}beanONBinHAand{|fb}beanONBinHB.
TheexpressionΨ|Φasdenedin(3.
7)ispositive-denitesinceforany|Ψ=∑a,bΨab|eafbwehaveΨ|Ψ=∑a,b|Ψab|2≥0andthusΨ|Ψ=0Ψab=0a,b|Ψ=0.
Moreover,let{|ea:=UA|ea=∑a1ea1|UAea|ea1=∑a1UAa1a|ea1}HA{|fb:=UB|fb=∑b1fb1|UBfb|fb1=∑b1UBb1b|fb1}HBbeotherONBsinHA,resp.
HB.
FromExercise2.
15weknowthatthenthemapsUA:HA→HA,UB:HB→HBarenecessarilyunitary.
Thus,wehave|Φ=∑a1,b1Φa1b1|ea1fb1=∑a,bΦab|eafb=∑a,bΦab∑a1UAa1a|ea1∑b1UBb1b|fb1=∑a1,b1∑a,bUAa1aUBb1bΦab|ea1fb1fromwhichitfollowsthatΦa1b1=∑a,bUAa1aUBb1bΦab.
668SolutionstoExercisesSimilarly,weobtainΨa1b1=∑a,bUAa1aUBb1bΨabandthusnally∑a1,b1Ψa1b1Φa1b1=∑a1,b1∑a,bUAa1aUBb1bΨab∑a2,b2UAa1a2UBb1b2Φa2b2=∑a,b∑a2,b2∑a1,b1UAa1aUAa1a2UBb1bUBb1b2ΨabΦa2b2=∑a,b∑a2,b2∑a1UAaa1UAa1a2=δaa2∑b1UBbb1UBb1b2=δbb2ΨabΦa2b2=∑a,bΨabΦab,thatis,Ψ|Φasdenedin(3.
7)doesnotdependonthechoiceoftheONBs{ea}HAand{fb}HB.
Solution3.
39Φ+|Φ+=1200+11|00+11=1200|00+11|00+00|11+11|11=(3.
4)120|0=10|0+1|0=01|0+0|1=00|1+1|1=11|1=1.
Φ+|Φ=1200+11|0011=1200|00=100|11=0+11|00=011|11=1=0.
Analogously,oneshowsΦ|Φ=1=Ψ±|Ψ±Ψ+|Ψ=0=Φ±|Ψ±=Φ|Ψ±.
SolutionstoExercises669Solution3.
40Fori∈{1,2}let|i∈HAand|ψi∈HB.
ThenwehaveMAMB1ψ1|2ψ2=(2.
30)1ψ1|MAMB2ψ2=1ψ1|MA2MBψ2=(3.
4)1|MA2ψ1|MBψ2=(2.
30)(MA)1|2(MB)ψ1|ψ2=(3.
4)(MA)1(MB)ψ1|2ψ2=(MA)(MB)1ψ1|2ψ2.
Solution3.
41Let{|ea}HAand{|fb}HBbetwootherONBs.
FromExercise2.
15weknowthatthenthereexistunitaryoperatorsUA∈UHAandUB∈UHBsuchthat|ea=UA|ea=∑aUAaa|ea|fb=UB|fb=∑bUBbb|fb.
(G.
78)LetMa1b1,a2b2bethematrixofMintheONB{|eafb}.
ThenMa1b1,a2b2=(2.
22)ea1fb1|Mea2fb2=(G.
78)∑a1b1a2b2UAa1a1|ea1UBb1b1|fb1|MUAa2a2|ea2UBb2b2|fb2=(2.
22)∑a1b1a2b2UAa1a1UBb1b1UAa2a2UBb2b2ea1fb1|Mea2fb2=∑a1b1a2b2UAa1a1UBb1b1UAa2a2UBb2b2Ma1b1,a2b2,wherewecanusethat(2.
35)impliesUAa1a1UBb1b1=UAa1a1UBb1b1670SolutionstoExercisesandweobtain∑a1a2bMa1b,a2b|ea1ea2|=∑a1a2ba1b1a2b2UAa1a1UBbb1UAa2a2UBb2bMa1b1,a2b2|ea1ea2|(G.
79)=∑a1b1a2b2∑bUBb2bUBbb1Ma1b1,a2b2∑a1UAa1a1|ea1∑a2UAa2a2ea2|.
HerewecanusethatUAandUBareunitary,henceUB(UB)=1Bandthus∑bUBb2bUBbb1=δb2b1(G.
80)aswellasUA(UA)=1Aandthus∑a1UAa1a1|ea1=(G.
78)∑a1aUAa1a1UAaa1|ea=∑a∑a1UAaa1UAa1a1=δaa1|ea=|ea1.
Likewise,wehave∑a2UAa2a2ea2|=ea2|.
(G.
81)Inserting(G.
80)–(G.
81)into(G.
79)yields∑a1a2bMa1b,a2b|ea1ea2|=∑a1b1a2b2Ma1b1a2b2δb1b2|ea1ea2|=∑a1a2Ma1b,a2b|ea1ea2|,whichshowsthatin(3.
46)therightsideintheequationfortrB(M)doesnotdependonthechoiceofthetheONBs{|ea}and{|fb}.
Solution3.
42WehavetrtrB(M)=tr1AtrB(M)=(3.
48)tr(1A1B)M=tr(M),andtheproofofthesecondidentityissimilar.
SolutionstoExercises671Solution3.
43Let{|ea}beanONBinHAand{|fb}beanONBinHB.
Then{|eafb}isanONBinHAHBandthematrixofMAMBinthisbasisisgivenbytherightsideof(3.
35).
ConsequentlytrMAMB=(2.
57)∑a,bMAMBab,ab=(3.
33)∑aMAaa∑bMBbb=(2.
57)trMAtrMB.
NowtrBMAMB=∑a1,a2trBMAMBa1a2|ea1ea2|,(G.
82)wheretrBMAMBa1a2=(3.
52)∑bMAMBa1b,a2b=(3.
33)MAa1a2∑bMBbb=(2.
57)MAa1a2trMB,andthus(G.
82)becomestrBMAMB=MAtrMB.
TheprooffortrAMAMB=MBtrMAis,ofcourse,similar.
Solution3.
44Accordingto(3.
44)onehasingeneralfora|Ψ∈HAHBthatρA(Ψ)=∑a1,a2,bΨa2bΨa1b|ea1ea2|,wherethe{|eaj}areanONBinHA.
WithHA=H=HB,|e0=|0A,|e1=|1AasONBinHAthisbecomesρA(Ψ)=Ψ00Ψ00+Ψ01Ψ01|0A0|+Ψ00Ψ10+Ψ01Ψ11|1A0|+Ψ10Ψ00+Ψ11Ψ01|0A1|+Ψ10Ψ10+Ψ11Ψ11|1A1|.
(G.
83)FortheBELLstates672SolutionstoExercises|Φ±=1√2(|00±|11)|Ψ±=1√2(|01±|10)wendΦ±00=±Φ±11=Ψ±01=±Ψ±10=1√2(G.
84)Φ±01=Φ±10=Ψ±00=Ψ±11=0.
(G.
85)Inserting(G.
84)and(G.
85)into(G.
83)resultsinρA(Φ±)=ρA(Ψ±)=12|0A0|+|1A1|=121A.
Similarly,onendsusing(3.
45),thatρB(Φ±)=ρB(Ψ±)=12|0B0|+|1B1|=121B.
Solution3.
45Anybasisvj|j∈{1,.
.
.
dimV}ofVcanbeusedtoformabasisvj1···vjnofVnsuchthatanyvectorw∈Vncanbewrittenintheformw=∑j1.
.
.
jnwj1.
.
.
jnvj1···vjn.
ThisallowsusforanysetofA1,.
.
.
,An∈L(V)todenetheactionofA1···Anonanyw∈VnbyA1···Anw=∑j1.
.
.
jnwj1.
.
.
jn(A1vj1)···(Anvjn).
suchthatA1···An∈LVnanditfollowsthatL(V)nLVn.
(G.
86)UsingthatdimL(V)=dimV2(G.
87)anddimVn=dimVn,(G.
88)SolutionstoExercises673wenddimL(V)n=(G.
88)dimL(V)n=(G.
87)dimV2n(G.
89)anddimLVn=(G.
87)dimVn2=(G.
88)dimV2n(G.
90)and(G.
86)togetherwith(G.
89)and(G.
90)implythatL(V)n=L(Vn).
Solution3.
46Firstnotethatforany|ψ∈HA{0}wehave(|ψψ|1B)2=|ψψ|ψψ|1B=(2.
5)||ψ||2(|ψψ|1B).
(G.
91)UsinganONB{|ea}HA,wendthenψ|∑b1,b2K(b1,b2)K(b1,b2)ψ=(2.
43)∑a1,a2ψ|ea1ea1|∑b1,b2K(b1,b2)K(b1,b2)ea2ea2|ψ=∑a1,a2ea2|ψψ|ea1ea1|∑b1,b2K(b1,b2)K(b1,b2)ea2=(2.
57)tr|ψψ|∑b1,b2K(b1,b2)K(b1,b2)=(3.
84)tr|ψψ|trB(1AρB)VV(1AρB)=(3.
47)tr(|ψψ|1B)(1AρB)VV(1AρB)=(G.
91)1||ψ||2tr(|ψψ|1B)2(1AρB)VV(1AρB)=(2.
58)1||ψ||2tr(|ψψ|1B)(1AρB)VV(1AρB)(|ψψ|1B)=1||ψ||2tr(|ψψ|ρB)VV(|ψψ|ρB).
674SolutionstoExercisesSolution3.
47UsinganONB{|eafb}HAHB,weobtaintr(|ψψ|ρB)VV(|ψψ|ρB)=(2.
57)∑a,beafb|(|ψψ|ρB)VV(|ψψ|ρB)eafb=(2.
30)∑a,b(|ψψ|ρB)eafb|VV(|ψψ|ρB)eafb=(3.
31)∑a,b(|ψψ|ρB)eafb|VV(|ψψ|ρB)eafb=(3.
81),(2.
36)∑a,b(|ψψ|ρB)eafb|VV(|ψψ|ρB)eafb=∑a,b|ψψ|eaρB|fb|VV(|ψψ|eaρB|fb)=(2.
4),(2.
6)∑a,b|ea|ψ|2|ψρB|fb|VV(|ψρB|fb)≤(3.
73)κ∑a,b|ea|ψ|2|ψρB|fb||ψρB|fb=(2.
12),(3.
4)κ||ψ||2∑bψ|ψρB|fb|ρB|fb=(2.
5)κ||ψ||4∑bρBfb2=(3.
79)κ||ψ||4∑b||√qbfb||2=(2.
7)κ||ψ||4∑bqb||fb||2=1=κ||ψ||4∑bqb=(3.
77)κ||ψ||4.
Solution3.
48CombiningtheONB{|fb}ofHBusedin(3.
87)todeneˇVwithanONB{|ea}ofHAtoformanONB{|eafb}ofHAHBwendˇV(eafb|ψf1=(2.
30)eafb|ˇV(ψf1)=(3.
87)eafb|∑lKl|ψ|fl=(3.
4)∑lea|Klψfb|fl=δbl=ea|Kbψ.
(G.
92)Withthisweobtainforevery|ψf1∈{HA}SolutionstoExercises675ψf1|ˇV(eafb)=(2.
1)ˇV(eafb)|ψf1=(G.
92)ea|Kbψ=(2.
1)Kbψ|ea=(2.
30),(2.
31)ψ|Kbea=∑lψ|Kleafl|fb=δlb=(3.
4)∑lψ|Klfl||eafbprovingtheclaim(3.
88).
Solution3.
49Leta1,.
.
.
,am,b1,.
.
.
,bnm∈CnbesuchthatA=a1···am,B=b1···bnm,wheretheajaregivenandthebjareyettobedetermined.
Moreover,setV=AB.
ThenwehaveVV=a1·a1···a1·ama1·b1···a1·bnm.
.
.
.
.
.
.
.
.
.
.
.
am·a1···am·amam·b1···am·bnmb1·a1···b1·amb1·b1···b1·bnm.
.
.
.
.
.
.
.
.
.
.
.
bnm·a1···bnm·ambnm·b1···bnm·bnm,whereu·v=∑nj=1ujvjdenotesthescalarproductinCn.
ForVVtohaveformgivenin(3.
90)thebjhavetosatisfyal·bk=0l∈{1,.
.
.
,m};k∈{1,.
.
.
,nm}(G.
93)bj·bk=cδjkj,k∈{1,.
.
.
,nm}.
(G.
94)676SolutionstoExercisesEachofthenmvectorsbjhasncomponentsgivingusaltogethern(nm)unknowns.
Equation(G.
93)givesmequationswhereasduetothesymmetry(G.
94)provides(nm)(nm+1)2equations.
Aslongas(nm)(nm+1)2+m≤n(nm)(G.
95)wecanndthebjandthusthematrixB∈Mat(n*(nm),C)deliveringtherequiredform(3.
90)forVV.
Rearrangingtermsshowsthat(G.
95)isequivalenttom(m+1)≤n(n1).
Sincebyassumptionn>mitfollowsthatn1≥mandn≥m+1whichguaranteesm(m+1)≤n(n1)andthus(G.
95).
Solution3.
50SinceanorthogonalprojectionPBsatises1APB=Def.
2.
111A(PB)2=(1APB)2(G.
96)and1APB=Def.
2.
111A(PB)=(3.
31)(1APB)(G.
97)wehavetr(1APB)U(ρAρB)U=(G.
96)tr(1APB)2U(ρAρB)U=(2.
58)tr(1APB)U(ρAρB)U(1APB)=(G.
97)tr(1APB)U(ρAρB)U(1APB)=(2.
47)tr(1APB)U(ρAρB)(1APB)U=(3.
101)trV(ρAρB)V=(3.
49)trtrBV(ρAρB)V=(3.
100)trK(ρA).
SolutionstoExercises677Solution3.
51Foranyx1,x2∈B1R3andμ∈[0,1]wehaveρμx1+(1μ)x2=(3.
107)121+μx1+(1μ)x2·σ=μ121+x1·σ+(1μ)121+x2·σ=(3.
107)μρx1+(1μ)ρx2(G.
98)andthusKμx1+(1μ)x2=(3.
108)trK(ρμx1+(1μ)x2)σ=(G.
98)tr(K(μρx1+(1μ)ρx2)σ)=(3.
106)tr(μK(ρx1)σ+(1μ)K(ρx2)σ)=μtr(K(ρx1)σ)+(1μ)tr(K(ρx2)σ)=(3.
108)μK(x1)+(1μ)K(x2).
SolutionstoExercisesfromChapter4Solution4.
52Accordingtothestartingassumption,ρAandρBaregivenasinDenition4.
1,thatis,eachofthemisself-adjoint,positiveandhastrace1.
From(3.
32)itfollowsthatthenρAρBisself-adjoint.
InordertoshowthepositivityoftheρAρBnoteatrstthatρAρB=ρA11ρB=1ρBρA1,(G.
99)wherealsoρA1=ρA11ρB=1ρB.
BothρA1aswellas1ρBarepositivebecauseforanarbitraryvector678SolutionstoExercises|Ψ=∑a,bΨab|ea|fb∈HAHBwendthatΨ|ρA1Ψ=(3.
8)∑a1a2,b1b2Ψa1b1Ψa2b2ea1fb1|ρA1ea2fb2=(3.
29)∑a1a2,b1b2Ψa1b1Ψa2b2ea1|ρAea2fb1|fb2=δb1b2=∑a1a2,bΨa1bΨa2bea1|ρAea2=∑b∑a1Ψa1bea1=:ψb|ρA∑a2Ψa2bea2=∑bψb|ρAψb≥0≥0,wherethepositivityofρAwasusedinthepenultimateline.
Similarly,oneshowsthat1ρBispositive.
SincetheρA1aswellasthe1ρBareself-adjointandpositiveandaccordingto(G.
99)commute,itfollowsthatforeverypairρA1,1ρBthereexistsanONB|eafbinwhichbotharediagonalρA1=∑a,bλAa,b|eafbeafb|1ρB=∑a,bλBa,b|eafbeafb|,whereduetothepositivityoftheρA1,1ρBwealsohaveλXa,b≥0forX∈{A,B}.
(G.
100)With(G.
99)oneobtainsthusρAρB=∑a,bλAa,bλBa,b|eafbeafb|andbecauseof(G.
100)itfollowsthatρAρBispositive.
Finally,thetracepropertyforρAρBfollowsfromtrρAρB=(3.
57)trρA=1trρA=1=1.
SolutionstoExercises679Solution4.
53WiththeresultsofExercise2.
20asgivenin(G.
66)wehave|↑x=1√2(|0+|1)and|↓x=1√2(|0|1)suchthat|↑x|↑x+|↓x|↓x=|0+|1√2|0+|1√2+|0|1√2|0|1√2=12(|00+|01+|10+|11)+12(|00|01|10+|11)=|00+|11.
Solution4.
54Perdenition(2.
125)and(2.
126)onehas|↑n=eiφ2cosθ2eiφ2sinθ2=eiφ2cosθ2|0+eiφ2sinθ2|1|↓n=eiφ2sinθ2eiφ2cosθ2=eiφ2sinθ2|0+eiφ2cosθ2|1andthus|↑n|↓n|↓n|↑n=eiφ2cosθ2|0+eiφ2sinθ2|1eiφ2sinθ2|0+eiφ2cosθ2|1eiφ2sinθ2|0+eiφ2cosθ2|1eiφ2cosθ2|0+eiφ2sinθ2|1=eiφcosθ2sinθ2|00+cos2θ2|01sin2θ2|10+eiφcosθ2sinθ2|11eiφcosθ2sinθ2|00sin2θ2|01+cos2θ2|10+eiφcosθ2sinθ2|11=|01|10=(3.
28)√2|Ψ.
680SolutionstoExercisesSolution4.
55Sincenintheresult(4.
25)ofExercise4.
54isarbitrary,wecanchoosen=nAandwrite|Ψas|Ψ=1√2|↑nA|↓nA|↓nA|↑nA.
(G.
101)withΣAnA=nA·σandΣBnB=nB·σitthenfollowsthatΣAnAΣBnBΨ=Ψ|nA·σnB·σΨ(G.
102)=1√2Ψ|nA·σ|↑nA=+|↑nAnB·σ|↓nAnA·σ|↓nA=|↓nAnB·σ|↑nA=1√2Ψ||↑nAnB·σ|↓nA+|↓nAnB·σ|↑nA.
InthelasttermwecanusethefollowingidentitynB·σ|↓nA=nB·σnA·σ|↓nA=nB·σnA·σ|↓nA=(2.
121)(nB·nA)1+i(nB*nA)·σ|↓nA.
(G.
103)Analogously,oneshowsnB·σ|↑nA=(nB·nA)1+i(nB*nA)·σ|↑nA.
(G.
104)Inserting(G.
103)and(G.
104)in(G.
102)yieldsΣAnAΣBnBΨ=nB·nA√2Ψ||↑nA|↓nA|↓nA|↑nAi√2Ψ||↑nA(nB*nA)·σ|↓nA+i√2Ψ||↓nA(nB*nA)·σ|↑nA=(G.
101)nB·nAΨ|Ψ=1i2↑nA↓nA↓nA↑nA|↑nA(nB*nA)·σ|↓nA+i2↑nA↓nA↓nA↑nA|↓nA(nB*nA)·σ|↑nASolutionstoExercises681=(3.
4)nB·nA(G.
105)i2↓nA|(nB*nA)·σ|↓nA+↑nA|(nB*nA)·σ|↑nA.
InordertoshowΣAnAΣBnBΨ=nB·nA,(G.
106)weprovethatingeneralform,n∈S1R3↓n|m·σ↓n+↑n|m·σ↑n=0(G.
107)holds.
Withm=nB*nAandn=nAitthenfollowsthatthesecondtermin(G.
105)vanishes.
Toshow(G.
107),weconsiderrstm·σ|↑nintheONB{|↑n,|↓n}:m·σ|↑n=am|↑n+bm|↓n.
(G.
108)Ifbm=0,itfollowsthatm·σ|↑n=am|↑n,(G.
109)andamisaneigenvalueofm·σwitheigenvector|↑n.
From(2.
29)itfollowsimmediately,that(m·σ)2=1,andthustheeigenvaluesofm·σaregivenby±1.
Theeigenspacefortheeigenvalueamisone-dimensionalandorthogonaltotheeigenvector|↓nfortheeigenvalueam.
Hence,m·σ|↓n=am|↓n,(G.
110)and(G.
107)followsfrom(G.
109)and(G.
110).
Incasebm=0,weobtainfrom(G.
108)becauseof↓n|↑n=0rst↓n|m·σ↓n=am.
(G.
111)Ontheotherhand,becauseof(m·σ)2=1itfollowsfrom(G.
108)alsothat|↑n=amm·σ|↑n+bmm·σ|↓n=amam|↑n+bm|↓n+bmm·σ|↓n.
Takingonbothsidesthescalarproductwith↓n|yields,becauseofbm=0and↓n|↑n=0,thus↓n|m·σ↓n=am.
(G.
112)682SolutionstoExercisesFrom(G.
111)and(G.
112)follows(G.
107)alsointhecasebm=0andthusnally(G.
106).
Alternatively,onecanverify(G.
106)alsobyanexplicitcalculation,makinguseoftherepresentationsn,|↑nA|↓nA,nA·σin(2.
122)–(2.
123)and(2.
125)–(2.
126).
Butthatisequallylengthy.
Solution4.
56Sincenintheresult(4.
25)ofExercise4.
54isarbitrary,wecanchoosen=nAandrepresent|Ψas|Ψ=1√2|↑nA|↓nA|↓nA|↑nA.
(G.
113)WithΣAnA=nA·σwethushaveΣAnA1Ψ=Ψ|nA·σ1Ψ=(G.
113)1√2Ψ|nA·σ|↑nA=+|↑nA|↓nAnA·σ|↓nA=|↓nA|↑nA=1√2Ψ|↑nA↓nA+↓nA↑nA=(G.
113)12↑nA↓nA↓nA↑nA|↑nA↓nA+↓nA↑nA=0,whereweused↑nA|↑nA=1and↑nA|↓nA=0inthelaststep.
Analogously,oneshowsthat1ΣBnBΨ=0.
Solution4.
57WithΣn=n·σm·σ|↑m=(2.
124)|↑m(G.
114)m·σ=m·σ(G.
115)onehasSolutionstoExercises683Σn|↑m=↑m|(n·σ)↑m=(G.
114)12(m·σ)↑m|(n·σ)↑m+↑m|(n·σ)(m·σ)↑m=(G.
115)12↑m|(m·σ)(n·σ)+(n·σ)(m·σ)↑m=(2.
121)12↑m|(m·n)1+i((m*n)·σ)+(n·m)1+i((n*m)·σ)↑m=n·m+i2↑m|m*n+n*m=0·σ↑m=n·m.
Solution4.
58Tobeginwith,wehavePλa|Ψ=(4.
49)(|eaea|1B)∑a1,bΨa1b|ea1|fb=∑a1,bΨa1b|eaea|ea1=δaa1|fb=∑bΨab|ea|fb,whichimpliesPλa|ΨΨ|Pλa=(3.
8)∑b1,b2Ψab1Ψab2|ea|fb1ea|fb2|=(3.
36)∑b1,b2Ψab1Ψab2|eaea||fb1fb2|.
(G.
116)Inserting(G.
116)into(4.
51)yieldsρ=∑a∑b1,b2Ψab1Ψab2|eaea||fb1fb2|(G.
117)forthedensityoperatorofthecompositesystem.
FromCorollary3.
20weknowthatthenthesub-systeminHBisdescribedby684SolutionstoExercisesρB(ρ)=(3.
56)trA(ρ)=(G.
117)trA∑a∑b1,b2Ψab1Ψab2|eaea||fb1fb2|=∑a∑b1,b2Ψab1Ψab2trA|eaea||fb1fb2|=(3.
57)∑a∑b1,b2Ψab1Ψab2tr(|eaea|)=1|fb1fb2|=∑a∑b1,b2Ψab1Ψab2|fb1fb2|,whereweusedinthelastequationthattr(|eaea|)=tr(ρea)=1foranypurestate|ea.
SolutionstoExercisesfromChapter5Solution5.
59Tobeginwith,wehaveforanyV∈U(H)(V1)(V1)=VVVV+1=(2.
37)21VV(G.
118)aswellas1n+1+|aa|V1|bb|=(3.
31)1n+1+|aa|V1|bb|=(2.
35)1n+1+|aa|V1|bb|.
(G.
119)WiththisweobtainSolutionstoExercises6851n+1+|aa|V1|bb|1n+1+|aa|V1|bb|=(G.
119)1n+1+|aa|V1|bb|1n+1+|aa|V1|bb|=1n+1+|aa|V1|bb|+|aa|V1|bb|+|aa|V1V1|bb|=1n+1+|aa|V1V1+V+V21|bb|=(G.
118)1n+1.
Solution5.
60Firstweshow(5.
15).
PerdenitiononehasΛ1(V)=12+|11|(V1)=11+|11|V|11|1=|00|+|11|1+|11|V|11|1=|00|1+|11|V.
(G.
120)Theproofof(5.
16)withprojections|00|,.
.
.
isacumbersomewritingdownofmanytermsandlengthy.
Amoreconcisealternativeproofcanbegivenifweusethematrixrepresentationinthecomputationalbasis.
Inthisonehaswith(G.
120)atrstΛ1(X)=|00|1+|11|X=10(1,0)1001+01(0,1)0110=10001001+00010110=1000010000000000+0000000000010010=1000010000010010.
(G.
121)Analogously,wehave686SolutionstoExercisesΛ1(X)=11+X1|11|=10011001+11110001=1000010000100001+0000010100000101=1000000100100100(G.
122)andH2=1√211111√21111=121111111111111111.
(G.
123)With(G.
121)and(G.
123)onethenobtainsH2Λ1(X)H2=14111111111111111110000100000100101111111111111111=1000000100100100=(G.
122)Λ1(X).
Theproofof(5.
17)issimplerintheoperator-representation.
With(G.
120)itfollowsthatΛ1(M(α))=|00|1+|11|M(α)=|00|1+|11|eiα1=|00|+eiα|11|1=P(α)1.
Solution5.
61Sincecomplexnumberscanbemultipliedtoanyfactorinatensorproduct,thatis,sinceforanyc∈CSolutionstoExercises687···c|ψ···|ψ···c|.
.
.
holds,onehasS(n)jk0l=n1|ψl=|ψn1.
.
.
ψj+1|00|ψj|ψj1.
.
.
ψk+1|00|ψk|ψk1.
.
.
ψ0+|ψn1.
.
.
ψj+1|11|ψj|ψj1.
.
.
ψk+1|11|ψk|ψk1.
.
.
ψ0+|ψn1.
.
.
ψj+1|01|ψj|ψj1.
.
.
ψk+1|10|ψk|ψk1.
.
.
ψ0+|ψn1.
.
.
ψj+1|10|ψj|ψj1.
.
.
ψk+1|01|ψk|ψk1.
.
.
ψ0=|ψn1.
.
.
ψj+1|00|ψk|ψj1.
.
.
ψk+1|00|ψj|ψk1.
.
.
ψ0+|ψn1.
.
.
ψj+1|11|ψk|ψj1.
.
.
ψk+1|11|ψj|ψk1.
.
.
ψ0+|ψn1.
.
.
ψj+1|00|ψk|ψj1.
.
.
ψk+1|11|ψj|ψk1.
.
.
ψ0+|ψn1.
.
.
ψj+1|11|ψk|ψj1.
.
.
ψk+1|00|ψj|ψk1.
.
.
ψ0=|ψn1.
.
.
ψj+1|00|ψk|ψj1.
.
.
ψk+1|ψj|ψk1.
.
.
ψ0+|ψn1.
.
.
ψj+1|11|ψk|ψj1.
.
.
ψk+1|ψj|ψk1.
.
.
ψ0=|ψn1.
.
.
ψj+1|ψk|ψj1.
.
.
ψk+1|ψj|ψk1.
.
.
ψ0.
Thisproves(5.
31).
Fromthat(5.
32)followssincethesecondapplicationofS(n)jkreversestheexchangeofthequbits|ψjand|ψk.
AsS(n)jkactsonlyonthefactorspacesHjandHk,andS(n)lmactsonlyonthefactorspacesHlandHm,itfollowsforj,k/∈{l,m}thatS(n)jkS(n)lm=S(n)lmS(n)jk,prov-ing(5.
33).
Forthesamereason,(5.
34)followsdirectlyfromthesuccessiveapplica-tionoftheS(n)n1jjinS(n).
Solution5.
62Fortheproofof(5.
46)oneobtainsfromDenition5.
18thatT|x|y(V)T|x|y(W)=(5.
44)2n1∑z=0z=x,y|zz|+v00|xx|+v01|xy|+v10|yx|+v11|yy|2n1∑z=0z=x,y|zz|+w00|xx|+w01|xy|+w10|yx|+w11|yy|.
Takingintoaccountthatvectorsofthecomputationalbasis|xand|ysatisfyx|y=δxy,thisthenbecomes688SolutionstoExercisesT|x|y(V)T|x|y(W)=2n1∑z=0z=x,y|zz|+(v00w00+v01w10)|xx|+(v00w01+v01w11)|xy|+(v10w00+v11w10)|yx|+(v10w01+v11w11)|yy|=2n1∑z=0z=x,y|zz|+(VW)00|xx|+(VW)01|xy|+(VW)10|yx|+(VW)11|yy|=(5.
44)T|x|y(VW).
Toprove(5.
47),oneusesthatthematrixrepresentationofVisgiveninthecom-putationalbasisbyV=v00v10v01v11(G.
124)andthat|ab|=|ba|holds.
WiththiswethushaveT|x|y(V)=(5.
44)2n1∑z=0z=x,y(|zz|)+(v00|xx|)+(v01|xy|)+(v10|yx|)+(v11|yy|)=(2.
32),(2.
36)2n1∑z=0z=x,y|zz|+v00|xx|+v01|yx|+v10|xy|+v11|yy|=(5.
44),(G.
124)T|x|y(V).
Inordertoprove(5.
48)weexploit(5.
46)and(5.
47)T|x|y(V)T|x|y(V)=(5.
47)T|x|y(V)T|x|y(V)=(5.
46)T|x|y(VV)=T|x|y(1)=(5.
44)1n.
SolutionstoExercises689Solution5.
63Letx=2n1∑j=0xj2j2L21r>1sincewecanassumeL>2.
Hence,itfollowsfrom(G.
135)thats(0)=Jks(0)=0s(0)=Jk3(1Jk)π2tanα0forα∈[πr2L+1,0[.
Intheinterval[πr2L+1,πr2L+1]thefunctions(α)thustakesamaximumatα=0anddecreasestotheleftandrightofα=0.
Hence,insidetheintervalitisgreaterthanattheboundaries±πr2L+1.
Duetos(α)=s(α)wecanchooseαmin=πr2L+1.
Finally,onehasinthegivenintervalthats(α)≥0sothattherealsos(α)2≥s(αmin)2holds.
Solution6.
73PerDenition6.
15wehavefhidesHg1,g2∈Gf(g1)=f(g2)g11g2∈Handsince698SolutionstoExercisesg11g2∈Hh∈H:g11g2=hh∈H:g2=g1h(F.
25)g2H=g1Htheclaim(6.
88)follows.
Solution6.
74Foranyg1,g2∈GwehaveΨA[g1]H|ΨA[g2]H=(6.
99)1|H|∑k1∈[g1]H∑k2∈[g2]Hk1|k2=(6.
89)1|H|∑k1∈[g1]H∑k2∈[g2]Hδk1,k2.
(G.
137)FromLemmaF.
20weknowthatthetwocosets[g1]Hand[g2]Hareeitheridenticalordisjoint,suchthat∑k1∈[g1]H∑k2∈[g2]Hδk1,k2=∑k1,k2∈[g1]Hδk1,k2if[g1]H=[g2]H0if[g1]H=[g2]H=∑k∈[g1]H1if[g1]H=[g2]H0if[g1]H=[g2]H=|H|if[g1]H=[g2]H0if[g1]H=[g2]H,(G.
138)whereinthelastequationweusedTheoremF.
21,whichtellsusthatthenumberofdistinctcosetsofHisequalto|H|.
Inserting(G.
138)into(G.
137)thenyieldstheclaim(6.
101).
SolutionstoExercises699Solution6.
75Toprovetheclaim,wehavetoshowthatHasdenedin(6.
115)satisestherequirementsofDenitionF.
6.
Clearly,thissetHisasubsetofG=ZN*ZN.
Withthechoiceu=0italsocontainstheneutralelementeG=([0]NZ,[0]NZ)ofthatgroup,verifying(F.
14).
Foranytwoelements([ui]NZ,[dui]NZ)∈H,wherei∈{1,2},wehave[u1]NZ,[du1]NZ+G[u2]NZ,[du2]NZ=(F.
35)u1+ZNu2NZ,du1+ZN(du2)NZ=(F.
35)[(u1+u2)modN]NZ,[(du1+du2)modN]NZ=(F.
35)[u1+u2]NZ,[(d(u1+u2))modN]NZ=(D.
20)[u1+u2]NZ,[(d(u1+u2)modN)modN]NZ=(F.
35)[u1+u2]NZ,(d(u1+ZNu2)NZ∈H,proving(F.
16).
Lastly,forany[u]NZ∈ZNwehavethat([u]NZ,[du]NZ)∈H,andthatitsinverse([u]NZ,[du]NZ)isalsoanelementofH,verifying(F.
15).
Solution6.
76From(6.
119)weknowthatanyχ∈H⊥isoftheformχdnmodN,n.
Forsuchcharacterswehaveforany([x]NZ,[y]NZ)∈GχdnmodN,n([x]NZ,[y]NZ)=(6.
117)e2πi(dnmodN)x+nyN=e2πidnx+nyN=e2πidx+yNn=(6.
117)χd,1([x]NZ,[y]NZ)n=(F.
61)χnd,1([x]NZ,[y]NZ),whichshowsthateveryelementofH⊥issomepowerofχd,1,implyingH⊥=χd,1.
700SolutionstoExercisesSolution6.
77Weinferfrom(6.
75)thatH=([m]6Z,[3m]6Z)∈Z6*Z6[m]6Z∈Z6=([0]6Z,[0]6Z),([1]6Z,[3]6Z),([2]6Z,[0]6Z),([3]6Z,[3]6Z),([4]6Z,[0]6Z),([5]6Z,[3]6Z)andfrom(6.
119)thatH⊥=χ3n,n∈Z6*Z6[n]6Z∈Z6=χ0,0,χ3,1,χ0,2,χ3,3,χ0,4,χ3,5.
ForthesecharacterswendKer(χ0,0)=Z6*Z6=GKer(χ3,1)=([x]6Z,[y]6Z)∈Z6*Z6[3x+y]6Z=0=([0]6Z,[0]6Z),([1]6Z,[3]6Z),([2]6Z,[0]6Z),([3]6Z,[3]6Z),([4]6Z,[0]6Z),([5]6Z,[3]6Z)=HKer(χ0,2)=([x]6Z,[y]6Z)∈Z6*Z6[2y]6Z=0=([0]6Z,[0]6Z),([1]6Z,[3]6Z),([2]6Z,[0]6Z),([3]6Z,[3]6Z),([4]6Z,[0]6Z),([5]6Z,[3]6Z),([0]6Z,[3]6Z),([1]6Z,[0]6Z),([2]6Z,[3]6Z),([3]6Z,[0]0Z),([4]6Z,[3]6Z),([5]5Z,[0]6Z)Ker(χ3,3)=([x]6Z,[y]6Z)∈Z6*Z6[9x+3y]6Z=0=([0]6Z,[0]6Z),([1]6Z,[3]6Z),([2]6Z,[0]6Z),([3]6Z,[3]6Z),([4]6Z,[0]6Z),([5]6Z,[3]6Z),([0]6Z,[2]6Z),([1]6Z,[1]6Z),([2]6Z,[2]6Z),([3]6Z,[1]0Z),([4]6Z,[2]6Z),([5]5Z,[1]6Z)Ker(χ0,4)=([x]6Z,[y]6Z)∈Z6*Z6[4y]6Z=0=([0]6Z,[0]6Z),([1]6Z,[3]6Z),([2]6Z,[0]6Z),([3]6Z,[3]6Z),([4]6Z,[0]6Z),([5]6Z,[3]6Z),([0]6Z,[3]6Z),([1]6Z,[3]6Z),([2]6Z,[3]6Z),([3]6Z,[0]0Z),([4]6Z,[3]6Z),([5]5Z,[0]6Z)Ker(χ3,5)=([x]6Z,[y]6Z)∈Z6*Z6[9x+5y]6Z=0=([0]6Z,[0]6Z),([1]6Z,[3]6Z),([2]6Z,[0]6Z),([3]6Z,[3]6Z),([4]6Z,[0]6Z),([5]6Z,[3]6Z)=H.
Withχ3,1([x]6Z,[y]6Z)=(6.
117)e2πi3x+y6=eπi(x+y3)wealsohaveSolutionstoExercises701χ0,0([x]6Z,[y]6Z)=1=χ3,1([x]6Z,[y]6Z)0χ3,1([x]6Z,[y]6Z)=eπi(x+y3)=χ3,1([x]6Z,[y]6Z)1χ0,2([x]6Z,[y]6Z)=eπi2y3=χ3,1([x]6Z,[y]6Z)2χ3,3([x]6Z,[y]6Z)=eπi(x+y)=χ3,1([x]6Z,[y]6Z)3χ0,4([x]6Z,[y]6Z)=eπi4y3=χ3,1([x]6Z,[y]6Z)4χ3,5([x]6Z,[y]6Z)=eπix+5y3=χ3,1([x]6Z,[y]6Z)5,conrming(6.
120).
Solution6.
78TocalculatethetraceinHAweusethat,becauseof(6.
113),wecanutilizethebasis|r|sr,s∈{0,.
.
.
,N1}HAsuchthattrPu,vFGρAFG=(2.
57)∑r,s∈{0,.
.
.
,N1}rs|(Pu,vFGρAFG)rs=(6.
123)∑r,s∈{0,.
.
.
,N1}r|u=δrus|v=δsvuv|(FGρAFG)rs=uv|(FGρAFG)uv=(6.
122)1N2∑[g]H∈G/H[n]NZ,[m]NZ∈ZNe2πidx+yN(nm)u|dnmodNdmmodN|uv|n=δvnm|v=δmv=1N2∑[g]H∈G/H|u|dvmodN|2=|u|dvmodN|2N2∑[g]H∈G/H1=|u|dvmodN|2N2|G/H|=(F.
36)|u|dvmodN|2N2|G||H|=(6.
111),(6.
116)|u|dvmodN|2N.
Solution6.
79Fortheproofof(6.
152)notethat(6.
149)impliessinθ0=mNandcosθ0=1mN.
(G.
139)702SolutionstoExercisesItfollowsthenthat|Ψ0=(6.
148)1√NN1∑x=0|x=(6.
138)1√N√Nm|ΨS⊥+√m|ΨS=(G.
139)cosθ0|ΨS⊥+sinθ0|ΨS,proving(6.
152).
Since||Ψ0||=1,theprojectorontothesubspaceHsub=Span{|Ψ0}isPsub=|Ψ0Ψ0|.
ConsequentlyRΨ0asdenedin(6.
150)coincideswiththedenitionofareectionabout|Ψ0givenin(6.
147).
Solution6.
80Withcos((2j+1)α)=ei(2j+1)α+ei(2j+1)α2=eiα2e2iαj+eiα2e2iαjweobtainJ1∑j=0cos((2j+1)α)=eiα2J1∑j=0e2iαj=1ei2Jα1ei2α+eiα2J1∑j=0e2iαj=1ei2Jα1ei2α=eiα21ei2Jα1ei2α+eiα21ei2Jα1ei2α=eiJα2eiJαeiJαeiαeiα+eiJα2eiJαeiJαeiαeiα=eiJα+eiJα2eiJαeiJαeiαeiα=cos(Jα)sin(Jα)sinα=2cos(Jα)sin(Jα)2sinα=sin(2Jα)2sinα.
SolutionstoExercisesfromChapter7Solution7.
81Recallingfrom(7.
1)thatfora,b∈F2SolutionstoExercises703a+F2b=a2b=(a+b)mod2=0ifa=b1ifa=b,theclaims(i)-(iii)areobvious.
Toshow(iv),considerdH(u,v)+dH(v,w)dH(u,w)=k∑j=1uj2vj+vj2wjuj2wj=:aj,whereuj2vj,vj2wj,uj2wj∈{0,1}andthusforanyj∈{1,.
.
.
,k}uj=wjaj≥0uj=wjanduj=vjvj=wjaj=0uj=wjanduj=vjvj=wjaj=0.
Hence,weobtaindH(u,v)+dH(v,w)dH(u,w)≥0.
Solution7.
82(i)RecallthatthekernelofanylinearmapF:V→Wbetweennite-dimensionalvectorspacesVandWisdenedasKer(F)=w∈VFw=0.
(G.
140)Foranyw∈Fk2itfollowsfrom(7.
8)thatGw∈Ker(H)andthusHGw=(G.
140)0,verifyingthatHG=0.
(ii)Weusethefollowingresultfrombasiclinearalgebra:foranylinearmapF:V→Wbetweennite-dimensionalvectorspacesVandWwehavedimF{V}=dimVdimKer(F).
ApplyingthistoH:Fn2→Fnk2,wenddimH{Fn2}=dimFn2dimKer(H)=(7.
8)ndimG{Fk2}=nk,whereinthelastequationweusedthatperdenitionGisofmaximalrankk.
(iii)Let704SolutionstoExercisesH=hT1.
.
.
hTnk,wherethehj∈Fn2forj∈{1,.
.
.
,nk}arelinearlyindependent.
Denehj=h1+h2ifj=1hjifj=1.
(G.
141)Thenthehjarelinearlyindependent.
Toprovethis,supposeaj∈F2forj∈{1,.
.
.
,nk}aresuchthat0=nk∑j=1ajhj=(G.
141)a1(h1+h2)+nk∑j=2ajhj=a1h1+(a1+a2)h2+a3h3+···+ankhnk.
Sincethehjarelinearlyindependent,wemusthavea1=a1+a2=a3=···=ank=0fromwhichitfollowsthataj=0forallj∈{1,.
.
.
,nk}.
Thus,wehaveshownthatnk∑j=1ajhj=0aj=0j∈{0,.
.
.
,nk},whichmeansthatthehjarelinearlyindependent.
Therefore,H=hT1.
.
.
hTnkhasmaximalrankdimH{Fn2}=nk,andwehavedimKer(H)=ndimH{Fn2}=k=dimKer(H).
(G.
142)Moreover,u∈Ker(H)n∑l=1(hj)lul=0j∈{1,.
.
.
,nk}n∑l=1(hj)lul=0j∈{1,.
.
.
,nk}u∈Ker(H),SolutionstoExercises705whichimpliesKer(H)Ker(H),andtogetherwith(G.
142)thisgivesKer(H)=Ker(H)=(7.
8)G{Fk2}.
Consequently,Hisaparitycheckmatrixaswell.
ButHcannotbeequaltoHsincethiswouldrequireh1=h1and(G.
141)showsthatthenh2=0,whichisimpossiblesincethehjareassumedlinearlyindependent.
Solution7.
83Foranya,b∈Fn2wehavesync(a2b)=(7.
11)H(a2b)=Ha2Hb=(7.
11)sync(a)2sync(b).
Solution7.
84Evaluatingtheencodingmapfora|ψ=a|0+b|1∈Hwitha,b∈C,wendrstA1|ψ=(7.
30)A1a|0+b|1|08=(7.
31)|11|12X12X12a|0+b|1|08+|00|18a|0+b|1|08=a|09+b|1|02|1|02|1|02=a|09+b|1003,(G.
143)whereweusedX|0=σx|0=|1.
Next,wehaveA2A1|ψ=(7.
31),(G.
143)H123a|09+b|1003(G.
144)=(2.
160),(2.
161)a|0+|1√2|023+b|0|1√2|023andnally,706SolutionstoExercisesCq|ψ=A3A2A1|ψ=(7.
31),(G.
144)|11|XX+|00|123a|0+|1√2|023+b|0|1√2|023=a|11|XX+|00|12|0+|1√2|023+b|11|XX+|00|12|0|1√2|023=a|11|XX+|00|12|000+|100√23+b|11|XX+|00|12|000|100√23=a|000+|111√23+b|000|111√23.
Solution7.
85Inthefollowingweusethat0|1=0=1|0(G.
145)|00|+|11|=1(G.
146)X2=σ2x=(2.
76)1(G.
147)H2=(2.
163)1.
(G.
148)Therefore,wehaverstA21=(7.
31)|11|12X12X12+|00|182=(G.
145)|11|12X12X122+|00|182=(G.
147)|11|18+|00|18=(|11|+|00|)18=(G.
146)19SolutionstoExercises707andthenA22=(7.
31)H123H123=H2123=(G.
148)133=19.
Finally,weobtainA23=(7.
31)|11|XX+|00|123|11|XX+|00|123=|11|X2X2+|00|123=(G.
147)|11|12+|00|123=(|11|+|00|)123=(G.
146)133=19.
Solution7.
86KeepinginmindthattheUabarejustcomplexnumbers,wehaveEa=(7.
41)m∑b=1UabEb=m∑b=1(UabEb)=(2.
32)m∑b=1UabEb=(2.
34)m∑b=1UbaEb,(G.
149)whichimplies∑aEaρEa=(7.
41),(G.
149)∑a∑bUabEbρ∑cUcaEc=∑b,c∑aUcaUabEbρEc=∑b,c(UU)cb=δcbEbρEc=∑bEbρEb,708SolutionstoExercisesandsimilarly,∑aEaEa=(7.
41),(G.
149)∑a∑bUbaEb∑cUacEc=∑b,c∑aUbaUacEbEc=∑b,c(UU)bc=δbcEbEc=∑bEbEb.
Solution7.
87Asquantumoperations,SandTareconvex-linear,andwehaveforeveryρ1,ρ2∈D(H)andμ∈[0,1]S(μρ1+(1μ)ρ2)=μS(ρ1)+(1μ)S(ρ2).
(G.
150)LetTS(ρ)tr(S(ρ))=ρρ∈D(H).
(G.
151)UsingtheoperatorsumrepresentationforTwithTldenotingtheoperationelements,wehaveforanyρ∈D(H)1tr(S(ρ))∑lTlS(ρ)Tl=∑lTlS(ρ)tr(S(ρ))Tl=(3.
97)TS(ρ)tr(S(ρ))=(G.
151)ρ,whichimplies∑lTlS(ρ)Tl=tr(S(ρ))ρ.
(G.
152)Consequently,wehaveforanyρ1,ρ2∈D(H)andμ∈[01,]μρ1+(1μ)ρ2=(G.
151)TSμρ1+(1μ)ρ2trSμρ1+(1μ)ρ2=(G.
150)TμS(ρ1)+(1μ)S(ρ2)tr(μS(ρ1)+(1μ)S(ρ2))=(3.
97)∑lTlμS(ρ1)+(1μ)S(ρ2)tr(μS(ρ1)+(1μ)S(ρ2))TlSolutionstoExercises709=μ∑lTlS(ρ1)Tl+(1μ)∑lTlS(ρ2)Tlμtr(S(ρ1))+(1μ)tr(S(ρ2))=(G.
152)μtr(S(ρ1))ρ1+(1μ)tr(S(ρ2))ρ2μtr(S(ρ1))+(1μ)tr(S(ρ2)),whichimpliesμtr(S(ρ1))μtr(S(ρ1))+(1μ)tr(S(ρ2))1ρ1=(1μ)1tr(S(ρ2))μtr(S(ρ1))+(1μ)tr(S(ρ2))ρ2.
Sinceρ1andρ2andμ∈[0,1]arearbitrary,itfollowsthatthetermsintheparen-thesishavetovanishfromwhichitfollowsthattr(S(ρ1))=tr(S(ρ2)andthustr(S(ρ))=constasclaimed.
Solution7.
88Aψ|Aψ|ψ2=(2.
5)Aψψ|Aψψ|Aψψ|Aψψ=(2.
4),(2.
6)Aψ|Aψψ|AψAψ|ψAψ|ψψ|Aψ+Aψ|ψψ|Aψψ|ψ=(2.
6)Aψ|Aψ|ψ|Aψ|2(2||ψ||2=1)=(2.
31),(2.
30)ψ|AAψ|ψ|Aψ|2Solution7.
89Theclaimistriviallytrue.
Toprove,leta:S1H→C|ψ→ψ|Aψandforall|ψ∈Hwith||ψ||=1letA|ψ=a(|ψ)|ψ.
(G.
153)710SolutionstoExercisesMoreover,fori∈{1,2}let|ψi∈Hbetwolinearlyindependentvectorssatisfying||ψi||=1,andletz1,z2∈Cwithz1z2=0besuchthat||z1|ψ1+z2|ψ2||=1aswell.
ThenitfollowsthatAz1|ψ1+z2|ψ2=(G.
153)a(z1|ψ1+z2|ψ2)z1|ψ1+z2|ψ2(G.
154)SinceAisalinearoperator,wealsohaveAz1|ψ1+z2|ψ2=z1A|ψ1+z2A|ψ2=(G.
153)a(|ψ1)z1)|ψ1+a(|ψ2)z2)|ψ2.
(G.
155)Equatingtherightsidesof(G.
154)and(G.
155)andusingthatthe|ψiarelinearlyindependent,itfollowsthattheirrespectivecoefcientshavetocoincideandthusa(|ψ1)=a(z1|ψ1+z2|ψ2)=a(|ψ2).
ThisimpliesthataisconstantontheunitsphereS1H,thatis,a(|ψ)=const=a∈CandthusA|ψ=a|ψ|ψ∈S1H.
(G.
156)Butthenforany|∈H{0}wehavethat|||||∈S1HwhichimpliesA|||||=(G.
156)a|||||,anditfollowsthatA|=a|forall|∈Hsincethisisalsotriviallytruefor|=0.
Solution7.
90Werstshowthatthereisag∈P9withwP(g)=3suchthatΨ0|gΨ1=0=f(g)δ01,wherethebasiscodewords|Ψ0and|Ψ1aregivenby(7.
33).
Forthisconsiderg=(12Z)3=11Z11Z11Z,(G.
157)whichsatiseswP(g)=3.
Notingthat(12Z)|000=|0|0Z|0=|0|0|0=|000(12Z)|111=|1|1Z|1=|1|1(|1)=|111,(G.
158)SolutionstoExercises711weobtaing|Ψ1=(G.
157),(7.
33)(12Z)3|000|111√23=(12Z)|000(12Z)|111√23=(G.
158)|000+|111√23=(7.
33)|Ψ0.
Therefore,wehaveg∈P9:wP(g)=3andΨ0|gΨ1=Ψ0|Ψ0=1=0=f(g)δ01.
Itremainstoshowthatforanyh∈P9withwP(h)≤2andx,y∈{0,1}wehave,instead,Ψx|hΨy=f(h)δxy.
Wedothisintwosteps,rstaddressingthecasex=y,andinasecondstepweshowthatitholdsforthecasex=yaswell.
Tobeginwith,wenotethatwithΣjαasdenedin(7.
43)anyh∈P9withwP(h)≤2isoftheformh=icΣjαΣlβ(G.
159)withc,α,β∈{0,.
.
.
,3}andj,l∈{0,.
.
.
,8}.
Wealsointroducethefollowingintu-itiveandhelpfulnotations.
|ψ±:=|000±|111√2∈H3|Ψ+:=|Ψ0=|000+|111√23=|ψ+3|Ψ:=|Ψ1=|000|111√23=|ψ3.
Forj∈{0,.
.
.
,8}wesetj:=j3andˇj:=jmod3.
Therefore,weobtainΣjα|Ψ±=δj2Σˇjα|ψ±|ψ±|ψ±+δj1|ψ±Σˇjα|ψ±|ψ±+δj0|ψ±|ψ±Σˇjα|ψ±.
(G.
160)712SolutionstoExercisesItfollowsthatΣjαΨ+|ΣlβΨ=0(G.
161)since,dueto(3.
4),eachoftheninescalarproductsformedbyusing(G.
160)intheleftsideof(G.
161)willalwaysinvolvescalarproductsoftensorfactorsinH3oftheformψ+|ψ=0.
Hence,wehaveforanyh∈P9withwP(h)≤2thatΨ0|hΨ1=(G.
159),(G.
160)Ψ+|icΣjαΣlβΨ=(2.
4),(2.
30)ic(Σjα)Ψ+|ΣlβΨ=(Σjα)=ΣjαicΣjαΨ+|ΣlβΨ=(G.
161)0=f(h)δ01Finally,weshowthatforanyh∈P9withwP(h)≤2wehaveΨ0|hΨ0=f(h)=Ψ1|hΨ1.
ForthisnoterstthatΣjαΨ±|ΣlβΨ±=(G.
160)δjlΣˇjαψ±|Σˇlβψ±(G.
162)+(1δjl)Σˇjαψ±|ψ±ψ±|Σˇlβψ±.
Herewehaveψ±|Σˇlβψ±=(G.
160)12000|Σˇlβ000+111|Σˇlβ111±000|Σˇlβ111±111|Σˇlβ000=(3.
4)120|σβ0+1|σβ1=2δβ0±0|σβ10|12=0±1|σβ01|02=0=δβ0.
(G.
163)Likewise,weobtainΣˇjαψ±|Σˇlβψ±=(Σjα)=Σjα(Σˇjα)ψ±|Σˇlβψ±=(2.
30)ψ±|ΣˇjαΣˇlβψ±=(G.
160)12000|ΣˇjαΣˇlβ000+111|ΣˇjαΣˇlβ111±000|ΣˇjαΣˇlβ111±111|ΣˇjαΣˇlβ000,SolutionstoExercises713where000|ΣˇjαΣˇlβ111=δˇjˇl0|σασβ10|12=0+(1δˇjˇl)0|σα10|σβ10|1=0=0and,similarly,111|ΣˇjαΣˇlβ000=0,suchthatΣˇjαψ±|Σˇlβψ±=12000|ΣˇjαΣˇlβ000+111|ΣˇjαΣˇlβ111=:ˇC(α,ˇj),(β,ˇl)(G.
164)Inserting(G.
163)and(G.
164)into(G.
162)givesΣjαΨ±|ΣlβΨ±=δjlˇC(α,ˇj),(β,ˇl)+(1δjl)δα0δβ0=:C(α,j),(β,l)(G.
165)suchthat,nally,Ψ0|hΨ0=(G.
159),(G.
160)Ψ+|icΣjαΣlβΨ+=(2.
4),(2.
30)ic(Σjα)Ψ+|ΣlβΨ+=(Σjα)=ΣjαicΣjαΨ+|ΣlβΨ+=(G.
165)icΣjαΨ|ΣlβΨ=(Σjα)=Σjαic(Σjα)Ψ|ΣlβΨ=(2.
4),(2.
30)Ψ|icΣjαΣlβΨ=(G.
159),(G.
160)Ψ1|hΨ1.
Solution7.
91FromFig.
7.
6wehaveA1=|11|11X1+|00|1111A2=1|11|1X1+1|00|111B1=|11|111X+|00|1111B2=11|11|1X+11|00|11suchthatA2A1=|11||11|111+|11||00|1X1+|00||11|1X1+|00||00|111B2B1=|11|1|11|11+|11|1|00|1X+|00|1|11|1X+|00|1|00|11.
714SolutionstoExercisesAftermultiplyingouttermbyterminB2B1A2A1andusing0|1=0,1|1=1=0|0aswellasX2=1wendS=|11||11||11|11+|11||11||00|1X+|11||00||11|X1+|11||00||00|XX+|00||11||11|XX+|00||11||00|X1+|00||00||11|1X+|00||00||00|11(3.
36)=(|111111|+|000000|)11+(|110110|+|001001|)1X+(|101101|+|010010|)X1+(|100100|+|011011|)XX,whichis(7.
109).
Solution7.
92Leth1,h2∈Pn,andletgjbeoneofthenkgeneratorsofS.
Thenwehave(1)lj(h1h2)gjh1h2=(7.
122)h1h2gj=(7.
122)h1(1)lj(h2)gjh2=(7.
122)(1)lj(h1)+lj(h2)gjh1h2suchthatlj(h1h2)=lj(h1)+lj(h2)mod2=(5.
2)lj(h1)2lj(h2)(G.
166)andthussynq(h1h2)=(7.
121)l1(h1h2),.
.
.
,lnk(h1h2)=(G.
166)l1(h1)2l1(h2),.
.
.
,lnk(h1)2lnk(h2)=(7.
121)synq(h1)2synq(h2).
SolutionstoExercises715Solution7.
93PerDenitionF.
16wehavethath∈N(S)meansthathS=Shandthusforanyg∈Sthereexistsag∈Ssuchthathg=gh.
(G.
167)Consequently,forany|Ψ∈HCqgh|Ψ=(G.
167)hg|Ψ=g∈Sh|Ψ,whichmeansthath|Ψisleftunchangedbytheactionofanyg∈S.
ButHCqisthesubspaceofallvectorsleftunchangedbyeveryelementofS,whichimpliesthath|Ψ∈HCq.
SolutionstoExercisesfromChapter8Solution8.
94AsperDenition2.
8,wehaveforany|ψ,|∈Hψ|A(s)=A(s)ψ|.
Consequentlyddsψ|A(s)=ddsA(s)ψ|.
(G.
168)Thelinearityandcontinuityproperties(seeDenition2.
1andExercise2.
5)ofthescalarproductallowustopullthederivativesinsidesothat(G.
168)impliesψ|.
A(s)=ddsA(s)ψ|=(2.
30)ψ|ddsA(s)forany|ψ,|∈Handthus.
A(s)=ddsA(s).
A(s)=ddsA(s)=(2.
31)ddsA(s).
716SolutionstoExercisesSolution8.
95From(8.
8)wehaveε2≥|||Φ|Ψ||2=(2.
5)ΦΨ|ΦΨ=(2.
5)||Φ||2+||Ψ||2Φ|ΨΨ|Φ=(2.
1)22Re(Φ|Ψ),wherewealsousedtheassumption||Φ||=1=||Ψ||inthelastequation.
Thus,Re(Φ|Ψ)≥1ε22withwhichweobtain|Φ|Ψ|2=Re(Φ|Ψ)2+Im(Φ|Ψ)2≥Re(Φ|Ψ)2≥1ε222=1+ε44ε2≥1ε2.
Solution8.
96Foranycomputationalbasisvector|x=|xn1.
.
.
x0∈HnwehaveHini|x=(8.
24)n1∑j=0Σjz|x=(8.
26)n2n1∑j=0xj|x.
Hence,each|xisaneigenvectorofHiniwitheigenvalueEini,x=n2n1∑j=0xj,(G.
169)wherexj∈{0,1},andwecandeterminetheeigenvalueEini,xbythenumberlx=nn1∑j=0xj(G.
170)ofthexjin|x=|xn1.
.
.
x0whichsatisfyxj=0.
Thelowestsuchnumberisl2n1=0witheigenvalueEini,l2n1=nandeigenvector|2n1=|1.
.
.
1.
TheSolutionstoExercises717highestlxisl0=nwitheigenvalueEini,l0=nandeigenvector|0.
.
.
0.
Consequently,theeigenvaluesareoftheformEini,l=(G.
169),(G.
170)2lnforl∈{0,.
.
.
,n},andforagivenltherearenldistinct|xn1.
.
.
x0suchthatl=n∑n1j=0xj.
Solution8.
97Foranycomputationalbasisvector|x=|xn1.
.
.
x0∈HnwehaveHn|x=(8.
24)n1∑i,j=0i=jJijΣizΣjz+n1∑j=0KjΣjz+c1n|x=(8.
26)n1∑i,j=0i=jJij(12xi)(12xj)+n1∑j=0Kj(12xj)+c1n|x=4n1∑i,j=0i=jxiJijxj2n1∑i,j=0i=j(xiJij+Jijxj)2n1∑j=0Kjxj+n1∑i,j=0i=jJij+n1∑j=0Kj+c|x.
Using(8.
25),weobtain4n1∑i,j=0i=jxiJijxj2n1∑i,j=0i=j(xiJij+Jijxj)2n1∑j=0Kjxj+n1∑i,j=0i=jJij+n1∑j=0Kj+c=4n1∑i,j=0i=jxiQij4xj2n1∑i,j=0i=jxiQij+Qijxj42n1∑j=014n1∑i=0i=j(Qij+Qji)12Qjjxj+n1∑i,j=0i=jQij4+n1∑j=014n1∑i=0i=j(Qij+Qji)12Qjj+14n1∑i,j=0i=jQji+12n1∑j=0Qjj718SolutionstoExercises=n1∑i,j=0i=jxiQijxj+n1∑j=0Qjjxj=xj∈{0,1}n1∑i,j=0i=jxiQijxj+n1∑j=0Qjjx2j=n1∑i,j=0xiQijxj=(8.
23)B(x).
Solution8.
98From(2.
36)weknowthat|ΨΨ|=|ΨΨ|forall|Ψ∈Handsincef(s)∈RitfollowsthatHini,HnandHT(s)areallself-adjoint.
Bydenition||Ψ0||2=1.
Hence,wehaveforany|Φ∈H|Φ|Ψ0|2≤(2.
16)||Φ||2||Ψ0||2=1=||Φ||2=(2.
5)Φ|Φandthus0≤Φ|Φ|Φ|Ψ0|2=(2.
1)Φ|ΦΦ|Ψ0Ψ0|Φ=Φ|1|Ψ0Ψ0|Φ=(8.
28)Φ|HiniΦprovingthepositivityofHini.
ToshowthisforHnwerecallthatanyorthogonalprojectionPsatisesperdenitionP2=PandP=Paswellasfrom(2.
55)that||P||=1.
Consequently,forany|Φ∈HΦ|PSΦ=Φ|P2SΦ=Φ|PSPSΦ=PSΦ|PSΦ=(2.
5)||PSΦ||2≤(2.
51)||PS||2||Φ||2=(2.
55)||Φ||2=(2.
5)Φ|Φandthus0≤Φ|ΦΦ|PSΦ=Φ|1PSΦ=(8.
30)Φ|HnΦ,SolutionstoExercises719provingthepositivityofHn.
AsaconsequenceofthepositivityofHiniandHnandthepropertiesoftheschedulef:[0,1]→[0,1],wehavethusforany|Φ∈HthatΦ|HT(s)Φ=(8.
32)1f(s)≥0Φ|HiniΦ≥0+f(s)≥0Φ|HnΦ≥0≥0.
Solution8.
99Notethatfors∈]0,1[wehavef(s)0inbothcasesandsE>0inCasej=1andsE≤0inCasej=2.
Consequently,wehaves(1)j(4b2)2(Es)=s+E(1)j(Es)(Es),where(1)j(Es)(Es)=√sE(Es)ifj=1√Es(Es)ifj=2=1√sEifj=11√Esifj=2=(1)j(1)j(Es),suchthats(1)j(4b2)2(Es)=(1)js+E(1)j(Es).
Insertingthisinto(G.
188),weobtain(ca)(1)j(4b2)b(a+c)2ac2=(1)j(Ez+)(Ez)(Ep+)(Ep)s+E(1)j(Es)=(8.
151)hj(s,E)732SolutionstoExercisesprovingtheclaim(8.
152).
Solution8.
111Thestatementsfors=0ands=1areeasilyobtainedbyinsertingthesevaluesin(8.
151).
Fors∈]0,1[werstobtain(1+s)2>1+s2>(1s)2+s2=12s+2s21+s>√1+s2>√12s+2s22+2s>1+s+√1+s2>1+√12s+2s21+s>121+s+√1+s2>121+√12s+2s2s+>p+>z+.
(G.
189)Similarly,wehave1>s2s>2s212s+2s2>14s+4s2=(12s)2√12s+2s2>12s>√12s+2s21+√12s+2s2>2(1s)>1√12s+2s2121+√12s+2s2>1s>121√12s+2s2z+>s>zand√1+s2>12s>2s√1+s212s+2s2>1+2s22s√1+s2=(s√1+s2)2√12s+2s2>s√1+s2>√12s+2s21+√12s+2s2>2(1s)>1√12s+2s2121+√12s+2s2>121+s√1+s2>121√12s+2s2z+>p>z.
(G.
190)Together(G.
189)–(G.
190)implyfor0s6s>8s21+s2>9s26s+1=(13s)213s>√1+s222s>1+s√1+s21s>121+s√1+s2s>pSolutionstoExercises733andconverselyfor34≤s0.
Thusαq2=(8.
160)2(q2)+12(L1)π12andthusSolutionstoExercises735αq2=1214kπ1,theonlyremainingpossibilityforp±(s)∈Iq(s)toholdwouldbethecasek=1andthusL=3andq=k+1=2.
Consequently,αq2=α0=π4andcosαq2=1√2,andtheonlyremainingpossibilityisp±∈I2(s)=(8.
162)1s√2,1+s√2.
Itfollowsfromthedenition(8.
151)ofthep±thatinthiscase1s√21.
Solution8.
115Tobeginwith,wehaveH(t)H(t)=(8.
210)Hκ(t)H(t)=(8.
206),(8.
208)1κ(t)JHini+κ(t)JHn1ttiniTHinittiniTHn=κ(t)JttiniTHnκ(t)JttiniTHini=(2.
7)κ(t)JttiniT||HnHini||.
(G.
192)736SolutionstoExercisesUsingthatT=JΔt,weobtainκ(t)JttiniT=κ(t)JttiniJΔt=1Jκ(t)ttiniΔt=(8.
209)1JttiniΔtttiniΔt∈[0,1[≤1J(G.
193)sothatH(t)H(t)=(G.
192)κ(t)JttiniT||HnHini||≤(G.
193)1J||HnHini||.
SolutionstoExercisesfromAppendixBSolutionB.
116(i)Weshowcj∈{0,1}byinductioninj.
Theinduction-startatj=0isgivenbythestartingassumptionc0=0.
Fortheinductivestepfromjtoj+1wesupposethatcj∈{0,1}holdstrueforj.
Thenthepossiblevaluesforcj+1asafunctionofthepossiblevaluesoftheaj,bjandcjareasshowninTableG.
1andcj+1∈{0,1}issatised.
(ii)Toprove(B.
8),notethattheassumptions0≤a,bMi|fi(N)|≤Ci|gi(N)|N→∞.
ForM:=max{M1,M2}wethenhaveforallN>M:(i)|f1(N)+f2(N)|≤|f1(N)|+|f2(N)|≤C1|g1(N)|+C2|g2(N)|≤max{C1,C2}(|g1(N)|+|g2(N)|)andthusf1(N)+f2(N)∈O(|g1(N)|+|g2(N)|).
(ii)|f1(N)f2(N)|≤|f1(N)||f2(N)|≤C1|g1(N)|C2|g2(N)|=C1C2|g1(N)g2(N)|andthusf1(N)f2(N)∈O(g1(N)g2(N)).
(iii)ForN>Mwehave,byassumption,|g1(N)|N.
Foranyx∈Rwehave0≤xxNthisinturnimplies12aN1)aaNNSolutionD.
120Letu,v,uj∈Zandk,a,N∈N.
Werstshow(D.
20).
SolutionstoExercises739u(vmodN)modN=(D.
1)u(vmodN)u(vmodN)NN=(D.
1)uvvNNuvvNNNN=uvuvNNuvNuvNN=uvuvNNuvNN+uvNN=uvuvNN=(D.
1)uvmodN.
Repeatedapplicationof(D.
20)thenyields(D.
21):k∏j=1(ujmodN)modN=(D.
20)k1∏j=1(ujmodN)ukmodN=.
.
.
=k∏j=1ujmodN.
Withuj=u,then(D.
22)followsasaspecialcaseof(D.
21).
Toprove(D.
23),itsufcestoshowthisforu1andu2.
Theclaimthenfollowsfromrepeatedapplicationofthestatementforu1andu2.
Fortheleftsideonehasforu1andu2bydenitionu1modN+u2modNmodN=u1u1NN+u2u2NNmodN=u1u1NN+u2u2NNu1u1NN+u2u2NNNN=u1+u2u1NNu2NNu1+u2Nu1Nu2NN=u1+u2u1NNu2NNu1+u2Nu1Nu2NN740SolutionstoExercises=u1+u2u1+u2N=u1+u2modN.
SolutionstoExercisesfromAppendixFSolutionF.
121Supposerstthatbesidesethereisane∈Gsuchthatforeveryg∈Gwealsohavege=g(G.
195)gg1=e.
(G.
196)Thisimpliesg1e=(G.
195)g1gg1e=gg1=(F.
3)ee=(G.
196)ee=(G.
195)e,showingthateisunique.
Now,supposethath1andh2aretwoinversesofg∈G,thatis,gh1=e=gh2.
(G.
197)Thenitfollowsfori∈{1,2}thatg=(F.
2)ge=(F.
3)ghih1i=(G.
197)eh1i(G.
198)andthushig=(G.
198)hieh1i=(F.
2)hih1i=(F.
3)e.
Consequently,wealsohaveh1g=e=h2g,(G.
199)SolutionstoExercises741whichnallyimpliesh1=(F.
2)h1e=(F.
3)h1gg1=(G.
199)h2gg1=(F.
3)h2e=(F.
2)h2.
SolutionF.
122From(F.
2)wehaveforg=ethatee=eandfrom(F.
3)weseethatthene=e1,proving(F.
4).
Next,considerghh1g1=ghh1g1=(F.
3)geg1=(F.
2)gg1=(F.
3)e,whichproves(F.
5).
Toshow(F.
6)notethat(F.
3)impliese=g1g11.
Multi-plyingbothsideswithgandusingthat,becauseof(F.
2),wehaveontheleftsidege=g,weobtaing=gg1g11=(F.
3)eg11=(F.
4)e1g11=(F.
5)g1e1=(F.
2)g11,whichproves(F.
6).
Next,wehaveh=ghg1=gg1=(F.
3)e(F.
3)h1=g1(G.
200)(G.
200)h11=g11(F.
6)h=gproving(F.
7).
SolutionF.
123Toprove(F.
8),wenotethatg1g1=(F.
5)g1g11=(F.
6)g1g,(G.
201)whichimpliese=(F.
3)g1gg1g1=(G.
201)g1gg1g=(F.
3)g1eg=(F.
2)g1g,proving(F.
8).
Toshow(F.
9),wenotethat742SolutionstoExerciseseg=(F.
7)(eg)11=(F.
5)g1e11=(F.
4)g1e1=(F.
2)g11=(F.
7)g.
Toshow(F.
10),letgh=gkforsomeg,h,k∈G.
Multiplyingbothsidesfromtheleftbyg1andusing(F.
8)impliesh=k.
Multiplyingthisinturnbygfromtheleftyieldsgh=gk.
Hence,gh=gkifandonlyifh=k.
Theproofoftheequivalenceofhg=kgwithh=kissimilar.
SolutionF.
124AnysubgroupcontainstheneutralelementeG,whichisthenalsocontainedinH∩.
Letg1,g2∈H∩.
Theng1,g2∈Hjforeveryj∈I.
SinceeachHjisasubgroup,wethushavethatalsog1g2∈Hjforeveryj∈I,anditfollowsthatg1g2∈H∩.
Likewise,ifg∈H∩,theng∈Hjandthusg1∈Hjforeachj∈I,whichimpliesthatg1∈H∩andcompletestheproofthatH∩isasubgroup.
SolutionF.
125SinceeGg=geGforallg∈G,itfollowsthateG∈ClzG(S).
Leth1,h2∈ClzG(S).
Thenwehaveforeveryg∈S(h1h2)g=h1(h2g)=(F.
17)h1gh2=(F.
17)gh1h2andthush1h2∈ClzG(S).
Finally,foranyh∈ClzG(S)andg∈Shg=(F.
17)ghgh1=h1g(F.
17)h1∈ClzG(S).
SolutionF.
126LetgbeanyelementofthegroupG.
Sincee∈H,itfollowsfrom(F.
19)thate∈Hgaswelland(F.
14)issatisedforHg.
Nowleth∈Hg,thatis,thereexistsanh∈Hsuchthath=ghg1.
Butwealsohavefrom(F.
19)thatgh1g1∈Hg.
Hence,hgh1g1=ghg1gh1g1=eandthus(h)1=gh1g1∈Hg,whichshowsthat(F.
15)issatisedforHg.
Finally,leth1,h2∈Hg,which,dueto(F.
19),meansthatthereexisth1,h2∈Hsuchthathj=ghjg1forj∈{1,2}.
Sinceh1h2∈H,itfollowsthath1h2=gh1g1gh2g1=gh1h2g1∈Hg,whichshowsthat(F.
16)isalsosatisedforHg.
SolutionstoExercises743SolutionF.
127TheneutralelementeofGclearlysatisesSe=eSe1=S.
Conse-quently,e∈NorG(S),and(F.
14)issatised.
Foranyh1,h2∈NorG(S)wehaveSh1h2=(F.
18)h1h2S(h1h2)1=h1h2Sh12h11=(F.
18)h1Sh2h11=(F.
20)h1Sh11=(F.
18)Sh1=(F.
20)Ssuchthath1h2∈NorG(S),verifying(F.
16).
Finally,foranyh∈NorG(S)wehavehSh1=(F.
18)Sh=(F.
20)SS=h1S(h1)1=(F.
18)Sh1suchthath1∈NorG(S),and(F.
15)issatisedaswell.
SolutionF.
128TheneutralelementeofGclearlysatiseseg=geandsoe∈Ctr(G),verifying(F.
14).
Foranyh1,h2∈Ctr(G)wehaveh1h2g=(F.
21)h1gh2=(F.
21)gh1h2andthush1h2∈Ctr(G),showingthat(F.
16)holds.
Moreover,foranyh∈Ctr(G)andg∈Gwehavehg=ghwhichimpliesgh1=h1gandthush1∈Ctr(G)aswell,verifying(F.
15).
Finally,wendforanyg∈GthatCtr(G)g=(F.
18)ghg1h∈Ctr(G)=(F.
21)hgg1h∈Ctr(G)=Ctr(G),provingthatCtr(G)isnormal.
744SolutionstoExercisesSolutionF.
129DenitionF.
15ofanormalsubgroupHimpliesHisnormalg∈Gh∈Hh∈Handh∈Hh∈H:ghg1=hg∈Gh∈Hh∈Handh∈Hh∈H:gh=hg(F.
22),(F.
23)g∈GgH=Hg.
SolutionF.
130Associativityoftheproductfollowsfromtheassociativityofoftheproductsineachgroup.
TheneutralelementisgivenbyeG1*G2:=(eG1,eG2)(G.
202)sinceforany(g1,g2)∈G1*G2(g1,g2)·*(eG1,eG2)=(F.
37)(g1eG1,g2eG2)=(g1,g2).
Similarly,any(g1,g2)∈G1*G2hastheinverse(g1,g2)1=(g11,g12)since(g1,g2)·*(g1,g2)1=(F.
37)(g1g11,g2g12)=(eG1,eG2)=(G.
202)eG1*G2.
IfG1andG2arebothnitewiththeirnumberofelements|G1|and|G2|,thenthesetG1*G2isniteaswellandhasthenumberofelements|G1||G2|.
SolutionF.
131Bythedeningproperty(F.
40)ofastabilizer,wehaveforeverym∈Mthate.
m=m,whichimpliesthate∈StaG(Q)andthusveries(F.
14).
Leth,g∈StaG(Q)andm∈Mbearbitrary.
Thenwehave(hg).
m=(F.
41)h.
(g.
m)=(F.
42)h.
m=(F.
42)msuchthathg∈StaG(Q),whichproves(F.
16).
Finally,wendSolutionstoExercises745m=(F.
40)e.
m=(F.
8)(g1g).
m=(F.
41)g1.
(g.
m)=(F.
42)g1.
m,andthusg1∈StaG(Q),whichshows(F.
15)andcompletestheproofthatStaG(G)isasubgroupofG.
SolutionF.
132Foranyg∈G1wehave(g)(g1)=(F.
44)(gg1)=(eG1)=(F.
47)eG2andthus(g1)=(g)1.
SolutionF.
133Fori∈{1,2}letχi∈Gianddene(χ1,χ2):G1*G2→U(1)(g1,g2)→χ1(g1)χ2(g2),(G.
203)whichisahomomorphism,sinceforanygi,gi∈Gi(χ1,χ2)(g1,g2)·*(g1,g2)=(F.
39)(χ1,χ2)(g1g1,g2g2)=(G.
203)χ1(g1g1)χ2(g2g2)=(F.
44)χ1(g1)χ1(g1)χ2(g2)χ2(g2)=(G.
203)(χ1χ2)(g1,g2)(χ1χ2)(g1,g2).
Hence,(χ1,χ2)∈G1*G2,andsinceweknowfromTheoremF.
34thatG1,G2andG1*G2aregroupsandfromExerciseF.
130thatG1*G2isagroup,thusG1*G2≤G1*G2.
(G.
204)Moreover,wehave|G1*G2|=(F.
38)|G1||G2|=(F.
70)|G1||G2|=(F.
38)|G1*G2|=(F.
70)|G1*G2|,which,togetherwith(G.
204),impliesG1*G2=G1*G2.
746SolutionstoExercisesSolutionF.
134Letχ∈G,andsetSχ=∑h∈Hχ(h).
Thenforanyˇh∈HSχχ(ˇh)=∑h∈Hχ(h)χ(ˇh)=∑h∈Hχ(hˇh)=Sχ,(G.
205)whereinthepenultimateequationwehaveusedthatχ∈Hom(G,U(1))andthussatises(F.
43).
Itfollowsfrom(G.
205)thatforeveryχ∈Gandˇh∈HSχχ(ˇh)1=0.
(G.
206)Now,letχ∈H⊥.
Then(F.
72)impliesthatHKer(χ),anditfollowsthatχ(h)=1forallh∈H.
ThisimpliesSχ=|H|.
Ontheotherhand,ifthereexistsanˇh∈Hsuchthatχ(ˇh)=1,thenthisisequiv-alenttoHKer(χ)andthisinturntoχ/∈H⊥.
Moreover,(G.
206)impliesthatinthiscasewemusthaveSχ=0.
SolutionF.
135Byassumption,HisasubgroupofGandfromLemmaF.
30weknowthatthekernelofahomomorphismisasubgroup.
Sinceeachcharacterisbydenitionahomomorphism,itskernelisalsoasubgroupandfromExerciseF.
124weknowthatanyintersectionofasetofsubgroupsisagainasubgroup.
Conse-quently,χ∈H⊥Ker(χ)isasubgroupofG.
Now,leth∈H.
Thenbydenition(F.
72)ofH⊥wehaveforanyχ∈H⊥thatHKer(χ).
Hence,Hχ∈H⊥Ker(χ)andeachofthembeingasubgroup,theclaim(F.
77)isproven.
SolutionstoExercises747SolutionF.
136WehaveFG=(F.
107)1|G|∑g∈Gχ∈Gχ(g)(|χg|)=(2.
32)1|G|∑g∈Gχ∈Gχ(g)(|χg|)=(2.
36)1|G|∑g∈Gχ∈Gχ(g)|gχ|=(F.
62)1|G|∑g∈Gχ∈Gχ1(g)|gχ|(G.
207)suchthatFGFG=(F.
107),(G.
207)1|G|∑g1,g2∈Gχ1,χ2∈Gχ1(g1)χ12(g2)|χ1g1|g2=(F.
106)δg1g2χ2|=1|G|∑χ1,χ2∈G∑g∈Gχ1(g)χ12(g)|χ1χ2|=(F.
76)∑χ∈G|χχ|=(F.
106)1H,anditfollowsfrom(2.
37)thatFGisunitary.
SolutionF.
137Withthechangeofvariablesu=r1+r2v=r1r2,(G.
208)itfollowsrstfrom(F.
109)thatr3=uandthen(r1r2)(r1r3)(r2r3)=(r1r2)(r1+u)(r2+u)=(r1r2)(2u2+v)(G.
209)aswellasA=(F.
110)(u2+v)(G.
210)B=(F.
111)uv.
(G.
211)748SolutionstoExercisesConsequently,wehave(r1r2)(r1r3)(r2r3)2=(G.
209)(r1r2)2(2u2+v)2=(G.
208)(u24v)(2u2+v)2=4u615u2v212vu44v3(G.
212)aswellas4A3=(G.
210)4(u2+v)3=4u6+12v2u212vu44v327B2=(G.
211)27u2v2(G.
213)suchthatΔE=(F.
108)(4A3+27B2)=(G.
213)4u615u2v212vu44v3=(G.
212)(r1r2)(r1r3)(r2r3)2.
SolutionF.
138Clearly,thematrixproductisassociativeandσ0=1=eP∈Pisaneutralelementundermatrixmultiplication.
Foranytwoelementsiaσα,ibσβ∈P,wehavefortheirproductiaσαibσβ=ia+bσασβ=(2.
76)ia+bσβifα=0ia+bσαifβ=0ia+b(δαβσ0+iεαβγσγ)ifα=0=β=ia+bσβifα=0ia+bσαifβ=0ia+bσ0ifα=β=0ia+b+cσγwithc=0or1ifα=0=β=α,(G.
214)and,notingthatid=idmod4,weseethatiaσαibσβ∈P=icσγc,γ∈{0,.
.
.
,3}.
SolutionstoExercises749Itfollowsfrom(G.
214)thatforanyiaσα∈Piaσαiaσα=iaiaσασα=σ0=1,provingnotonlythatanyelementinPhasaninverseinP,butthatalsotheinverseisgivenbyitsadjointandthusPByselectingabasisinH,wecanidentifyeveryelementinthematrixgroupU(2)bijectivelywithanelementinU(H).
Theelementsiaσα∈Paregivenbyspecifyingoneofthefourexponentsa∈{0,.
.
.
,3}togetherwithoneofthefourindicesα∈{0,.
.
.
,3},givingaltogether16distinctelementsandprovingthat|P|=16.
SolutionF.
139Toprove(F.
127),werstneedtoshowthatanyelementiaσα∈Pcanbewrittenintheformiaσα=∏p≥0σupxσvpyσwpzwithup,vp,wp∈N0.
First,weshowhowiaσ0fora∈{0,.
.
.
,3}canbewritteninthisform:σ0=σ2x=σ0xiσ0=σzσxσy=iσzσ0=(σzσxσy)2iσ0=(σzσxσy)3.
Withthis,wecangenerateiaσjforj∈{1,2,3}bymultiplyingσjwiththepowersofσzσxσygivenabove.
Forexample,iσy=σzσx,σy=σzσx(σzσxσy),iσy=σzσx(σzσxσy)2,whichshowsthatwecangenerateiaσyfora∈{1,2,3}andinthesamewaythiscanbedoneforσxandσz.
Toshow(F.
128),werstnotethatasasetiσ0={±σ0,±iσ0}.
(G.
215)Now,letg=iaσα∈Ctr(P).
Thisimpliesgibσβ=ibσβgforallb,β∈{0,.
.
.
,3}.
Hence,σαhastobesuchthatσασβ=σβσαβ∈{0,.
.
.
,3},whichcanonlybesatisedbyα=0.
Itfollowsthatg=iaσ0witha∈{0,.
.
.
,3},whichimpliesg∈{±σ0,±iσ0}.
With(G.
215),wethushaveCtr(P)iσ0.
750SolutionstoExercisesSinceσ0=1,theconverseinclusionisobvious,and(F.
128)isproven.
SolutionF.
140Withg=(F.
141)ic(g)Σxx(g)Σzz(g)(G.
216)h=(F.
141)ic(h)Σxx(h)Σzz(h)(G.
217)gh=(F.
141)ic(gh)Σxx(gh)Σzz(gh)(G.
218)wehavegh=(G.
216),(G.
217)ic(g)+c(h)Σxx(g)Σzz(g)Σxx(h)Σzz(h)=(F.
140)ic(g)+c(h)(1)z(g)2x(h)Σxx(g)Σxx(h)Σzz(g)Σzz(h)=(F.
139)ic(g)+c(h)+2z(g)2x(h)Σxx(g)2x(h)Σzz(g)2z(h)=(G.
218)ic(gh)Σxx(gh)Σzz(gh),andsinceLemmaF.
68tellsusthattherepresentationofghwiththehelpofc(gh),x(gh)andz(gh)isunique,theclaims(F.
143)–(F.
145)follow.
SolutionF.
141First,weshowthatNorPn(S)ClzPn(S).
Forthisletg∈NorPn(S).
ByDenitionF.
16thisimpliesgS=Sg,whichmeansthath∈Sh∈S:gh=hg.
(G.
219)FromPropositionF.
70weknowthatforanyh,g∈Pnwehaveeitherhg=ghorhg=gh.
Hence,(G.
219)becomesh∈Sh∈S:±hg=hg,andwemusthaveeitherh=horh=h.
Supposeh=h.
SinceSisasubgroupandh,h∈S,itfollowsthatthenhh1=1n∈S,whichwehaveexcluded.
Therefore,wemusthaveh=h,and(G.
219)impliesSolutionstoExercises751gh=hgg∈NorPn(S)andh∈SandthusNorPn(S)ClzPn(S).
(G.
220)Toprovetheconverseinclusion,letg∈ClzPn(S).
ThenitfollowsfromthedenitionofClzin(F.
17)thatgh=hgh∈SandthusgS=Sg,whichimpliesg∈NorPn(S).
Hence,NorPn(S)ClzPn(S),andthistogetherwith(G.
220)completestheproofoftheclaim.
SolutionstoExercisesfromAppendixGSolutionG.
142Wehaveforeveryj∈Iandz∈Cσ(A)(Az1)∑j∈IPjλjz=(2.
42)∑k∈IλkPkz1∑j∈IPjλjz=∑k,j∈IλkPkPjλjz∑j∈IzPjλjz=(2.
44)∑k,j∈IλkδkjPjλjz∑j∈IzPjλjz=∑j∈IλjPjλjz∑j∈IzPjλjz=∑j∈IPj=(2.
43)1.
Inthesamewayoneveriesthat∑j∈IPjλjz(Az1)=1.
Consequently,wehave∑j∈IPjλjz=(Az1)1=(G.
1)Rz(A)SolutionG.
143From(G.
1)inDenitionG.
1oftheresolventweknowthat752SolutionstoExercisesRzHT(s)HT(s)z1=1.
(G.
221)SincewerequireHTtosatisfytheAdiabaticAssumption(AA),thefunctions→HT(s)istwicedifferentiable.
Takingthederivativewithrespecttosonbothsidesof(G.
221)impliesddsRzHT(s)HT(s)z1=(G.
1)RzHT(s)1=RzHT(s).
HT(s)fromwhichtheclaim(G.
7)follows.
SolutionG.
144TheclaimactuallyfollowsfromtheresultsofExercise2.
18,butwegivetheproofhereoncemoreforUA,j(s).
Sinceforallj∈Iands∈[0,1]wehaveUA,j(s)UA,j(s)=1=UA,j(s)UA,j(s),(G.
222)itfollowsthat1=UA,j(0)UA,j(0)=(G.
21)UA,j(0),provingthatUA,j(0)satisestheinitialconditionin(G.
22).
Takingthederivativewithrespecttosonbothsidesin(G.
222),wend.
UA,j(s)UA,j(s)+UA,j(s).
UA,j(s)=0.
Multiplyingbothsideswithi,withUA,j(s)fromtheright,andusingagain(G.
222),weobtaini.
UA,j(s)=UA,j(s)i.
UA,j(s)UA,j(s)=(G.
21)UA,j(s)HA,j(s)UA,j(s)UA,j(s)=(G.
222)UA,j(s)HA,j(s),proving(G.
22).
SolutionG.
145From(G.
24)weseethatSolutionstoExercises753Aλj1Pj{H}⊥∑k∈I{j}1λkλjPkPj{H}⊥=(G.
24)∑k,l∈I{j}λlλjλkλjPlPkPj{H}⊥=(2.
44)∑k∈I{j}PkPj{H}⊥=1Pj{H}⊥.
Consequently,wehaveAλj1Pj{H}⊥1=∑k∈I{j}1λkλjPkPj{H}⊥.
(G.
223)Now,(2.
44)andPj=Pjimplythatforall|Φ,|Ψ∈Honehas(1Pj)Φ|PjΨ=0andthus(1Pj):H→Pj{H}⊥H.
Usingthisin(G.
223),gives1PjAλj1Pj{H}⊥11Pj=∑k∈I{j}1λkλj1PjPkPj{H}⊥1Pj=∑k∈I{j}1λkλj1PjPk1Pj=∑k∈I{j}1λkλjPkPjPkPkPj+PjPkPj=(2.
44)∑k∈I{j}1λkλjPk,whichproves(G.
25).
Theclaim(G.
26)thenfollowsfrom(G.
25)and(2.
44),whereas(G.
27)followsimmediatelyfrom(G.
26).
SolutionG.
146Wehave754SolutionstoExercisesˇRj.
HTPjA+APj.
HTˇRj+.
HTˇRjA+AˇRj.
HTPjΨ2≤(2.
51)ˇRj2.
HTPjA+APj.
HTˇRj+.
HTˇRjA+AˇRj.
HTPjΨ2≤(2.
18)ˇRj2.
HTPjA+APj.
HTˇRjΨ+.
HTˇRjA+AˇRj.
HTPjΨ2≤(2.
51)ˇRj2.
HTPjA+APj.
HTˇRjΨ+.
HTˇRjA+AˇRj.
HTPjΨ2≤(2.
51),(2.
53)2.
HT||A||ˇRj2PjˇRjΨ+ˇRjPjΨ2≤||Pj||=1,(G.
27)2.
HT||A||ˇRj2ˇRj(1Pj)Ψ+ˇRjPjΨ2≤(2.
53)2.
HT||A||ˇRj22(1Pj)Ψ+PjΨ2.
(G.
224)Herewecanfurtherusetheestimate(1Pj)Ψ+PjΨ2=(1Pj)Ψ2+PjΨ2+2(1Pj)ΨPjΨ≤(2.
15)||Ψ||2+2(1Pj)=1Pj=1||Ψ||2=3||Ψ||2,which,insertedinto(G.
224),yieldstheclaim(G.
41).
References1.
C.
H.
Bennett,G.
Brassard,inProceedingsofIEEEInternationalConferenceonComputers,Systems,andSignalProcessing,Bangalore,India(NewYork,1984)2.
J.
F.
Clauser,M.
A.
Horne,A.
Shimony,R.
A.
Holt,Phys.
Rev.
Lett.
25,15(1969)3.
A.
Ekert,Phys.
Rev.
Lett.
67,661(1991)4.
A.
Einstein,B.
Podolsky,N.
Rosen,Phys.
Rev.
47,777(1935)5.
M.
Planck,AnnalenderPhysik4(3),553(1901)6.
A.
Einstein,AnnalenderPhysik17,132(1905)7.
E.
Schr¨odinger,NaturwissenschaftenHeft48,807(1935)8.
J.
S.
Bell,Rev.
Mod.
Phys.
38(3),447(1966)9.
A.
Aspect,J.
Dallibard,G.
Roger,Phys.
Rev.
Lett.
49,1804(1982)10.
N.
Wiener,Cybernetics:orControlandCommunicationintheAnimalandtheMachine(TheMITPress,1948)11.
C.
E.
Shannon,BellSys.
Tech.
J.
27,379(1948)12.
R.
Feynman,Int.
J.
Theor.
Phys.
21(6/7),467(1982)13.
A.
Turing,Proc.
Lond.
Math.
Soc.
42,230(1936)14.
P.
Benioff,Phys.
Rev.
Lett.
48(23),1581(1982)15.
W.
K.
Wootters,W.
H.
Zurek,Nature299,802(1982)16.
D.
Deutsch,Proc.
R.
Soc.
Lond.
Ser.
A400,97(1985)17.
D.
Deutsch,Proc.
R.
Soc.
Lond.
Ser.
A425(1868),73(1989)18.
C.
H.
Bennet,G.
Brassard,C.
Crepeau,R.
Jozsa,A.
Perez,W.
K.
Wootters,Phys.
Rev.
Lett.
70(13),1895(1993)19.
P.
Shor,inProceedingsofthe35thAnnualSymposiumonFoundationsofComputerScience(IEEEComputerSocietyPress,1994),pp.
124–13420.
P.
Shor,SIAMJ.
Comput.
26(5),1484(1997)21.
L.
K.
Grover,inProceedingsofofthe28thAnnualACMSymposiiumonTheoryofComputing(1996),pp.
212–21922.
L.
Grover,Phys.
Rev.
Lett.
79(2),325(1997)23.
D.
Bouwmeester,J.
W.
Pan,K.
Mattle,M.
Eibl,H.
Weinfurter,A.
Zeilinger,Nature390,575(1997)24.
I.
L.
Chuang,N.
Gershenfeld,M.
Kubinec,Phys.
Rev.
Lett.
80(15),3408(1998)25.
L.
M.
K.
Vandersypen,G.
Breyta,M.
Steffen,C.
S.
Yannoni,M.
H.
Sherwood,I.
L.
Chuang,Nature414(6866),883(2001)26.
X.
S.
Ma,T.
Herbst,T.
Scheidl,D.
Wang,S.
Kropatschek,W.
Naylor,B.
Wittmann,A.
Mech,J.
Koer,E.
Anisimova,V.
Makarov,T.
Jennewein,R.
Ursin,A.
Zeilinger,Nature489,269(2012)27.
J.
G.
Ren,P.
Xu,H.
L.
Yong,L.
Zhang,S.
K.
Liao,Nature549,70(2017).
https://doi.
org/10.
1038/nature23675SpringerNatureSwitzerlandAG2019W.
Scherer,MathematicsofQuantumComputing,https://doi.
org/10.
1007/978-3-030-12358-1755756References28.
A.
Calderbank,P.
Shor,Phys.
Rev.
A54(2),10(1996)29.
A.
M.
Steane,Phys.
Rev.
Lett.
77(5),793(1997)30.
A.
Barenco,C.
H.
Bennett,R.
Cleve,D.
P.
DiVincenzo,N.
Margolus,P.
Shor,T.
Sleator,J.
A.
Smolin,H.
H.
Weinfurter,Phys.
Rev.
A52(5),4083(1995)31.
D.
P.
DiVincenzo,Phys.
Rev.
A51(2),1015(1995)32.
B.
Apolloni,C.
Carvalho,D.
deFalco,Stoch.
Process.
TheirAppl.
33(2),233(1989)33.
W.
vanDam,M.
Mosca,U.
Vazirani,inProceedingsofthe42ndAnnualSymposiumonFoundationsofComputerScience(2001),pp.
279–287.
https://doi.
org/10.
1109/SFCS.
2001.
95990234.
D.
Aharonov,W.
vanDam,J.
Kempe,Z.
Landau,S.
LLoyd,O.
Regev,SIAMRev.
50(4),755(2008).
https://doi.
org/10.
1137/08073447935.
M.
Freedman,A.
Kitaev,M.
Larsen,Z.
Wang,Bull.
Am.
Math.
Soc.
40,31(2003)36.
A.
Kitaev,Ann.
Phys.
303,2(2003)37.
A.
Galindo,P.
Pascal,QuantumMechanics,vol.
I&II(Springer,2012)38.
A.
Messiah,QuantumMechanics,vol.
I&II(Dover,2017)39.
C.
Cohen-Tannoudji,B.
Diu,F.
Laloe,QuantumMechanics,vol.
I&II(Wiley,1991)40.
J.
J.
Sakurai,J.
J.
Napolitano,ModernQuantumMechanics,2ndedn.
(Pearson,2013)41.
J.
T.
Cushing,QuantumMechanics:HistoricalContingencyandtheCopenhagenHegemony(TheUniveristyofChicagoPress,1994)42.
R.
Omn`es,UnderstandingQuantumMechanics(PrincetonUniversityPress,1999)43.
B.
d'Espagnat,VeiledReality:AnAnalysisofQuantumMechanicalConcepts(WestviewPress,2003)44.
J.
S.
Bell,SpeakableandUnspeakableinQuantumMechanics:CollectedPapersonQuantumPhilosophy,revisededn.
(CambridgeUniversityPress,2004)45.
F.
Lalo¨e,DoWeReallyUnderstandQuantumMechanics(CambridgeUniversityPress,2012)46.
S.
Gao,TheMeaningoftheWaveFunction(CambridegUniversityPress,2017)47.
F.
T.
Boge,QuantumMechanicsBetweenOntologyandEpistemology(Springer,2018)48.
R.
A.
Meyers(ed.
),EncyclopediaofComplexityandSystemsScience(Springer,2009)49.
C.
Nayak,S.
H.
Simon,A.
Stern,M.
Freedman,S.
D.
Sarma,Rev.
Mod.
Phys.
80,1083(2008)50.
M.
Reed,B.
Simon,MethodsofModernMathematicalPhysicsI:FunctionalAnalysis(Aca-demicPress,NewYorkCity,1978)51.
D.
Werner,Funktionalanalysis(Springer,2011)52.
A.
M.
Gleason,IndianaUniv.
Math.
J.
6,88517893(1957)53.
B.
P.
Rynne,M.
A.
Youngson,LinearFunctionalAnalysis(Springer,2008)54.
E.
Kreyszig,IntroductoryFunctionalAnalysiswithApplications(Wiley,1989)55.
Y.
Choquet-Bruhat,C.
DeWitt-Morette,Analysis,ManifoldsandPhysics(North-Holland,1982)56.
A.
Lucas,Front.
Phys.
2,5(2014).
https://doi.
org/10.
3389/fphy.
2014.
0000557.
K.
Kraus,EffectsandOperations:FundamentalNotionsofQuantumTheory(Springer,1983)58.
K.
Kraus,Ann.
Phys.
64,311(1971)59.
I.
Bengtsson,K.
Zyczkowski,GeometryofQuantumStates(CambridgeUniversityPress,2006)60.
W.
F.
Stinespring,inProceedingsoftheAmericanMathematicalSociety(1955),pp.
211–21661.
M.
A.
Nielsen,I.
Chuang,QuantumComputationandQuantumInformation(CambridgeUni-versityPress,2010)62.
K.
Parthasarathy,AnIntroductiontoQuantumStochasticCalculus(Birkh¨auserBasel,1991)63.
J.
S.
Bell,Physics1,195(1964)64.
R.
Werner,Phys.
Rev.
A40,4277(1989)65.
M.
Zukowski,A.
Zeilinger,M.
Horne,A.
Ekert,Phys.
Rev.
Lett.
71(26),4287(1993).
https://doi.
org/10.
1103/PhysRevLett.
71.
428766.
S.
Bose,V.
Vedral,P.
Knight,Phys.
Rev.
A57(2),822(1998).
https://doi.
org/10.
1103/PhysRevA.
57.
82267.
J.
W.
Pan,D.
Bouwmeester,H.
Weinfurter,A.
Zeilinger,Phys.
Rev.
Lett.
80(18),3891(1998)References75768.
D.
Dieks,Phys.
Lett.
A92,271(1982)69.
J.
Audretsch,EntangledSystems(Wiley-VCH,2007)70.
M.
Fernandez,ModelsofComputation:AnIntroductiontoComputabilityTheory(Springer,2009)71.
M.
Reck,A.
Zeilinger,H.
J.
Bernstein,P.
Bertani,Phys.
Rev.
Lett.
73(1),58(1994)72.
A.
Vedral,V.
Barenco,A.
Ekert,Phys.
Rev.
A54,147(1996)73.
R.
Jozsa,Proc.
R.
Soc.
Lond.
A454,323(1998)74.
N.
D.
Mermin,QuantumComputerScience:AnIntroduction(CambridgeUniversityPress,20017)75.
D.
Deutsch,R.
Jozsa,Proc.
R.
Soc.
Lond.
Ser.
A439(1907),553(1992)76.
C.
Bennett,S.
Wiesner,Phys.
Rev.
Lett.
69,2881(1992)77.
C.
H.
Bennet,G.
Brassard,A.
K.
Ekert,Sci.
Am.
70,26(1992)78.
R.
L.
Rivest,A.
Shamir,L.
M.
Adleman,Commun.
ACM51(2),2738(1978)79.
J.
Hoffstein,J.
Pipher,J.
H.
Silverman,AnIntroductiontoMathematicalCryptography(Springer,2014)80.
Wikipedia.
http://en.
wikipedia.
org/wiki/RSAnumbers81.
T.
Kleinjung,K.
Aoki,J.
Franke,A.
K.
Lenstra,E.
Thome,J.
W.
Bos,P.
Gaudry,A.
Kruppa,P.
L.
Montgomery,D.
Osvik,H.
teRiele,A.
Timofeev,P.
Zimmermann,inAdvancesinCryp-tology'96CRYPTO2010,ed.
byT.
Rabin,LectureNotesinComputerScience,vol.
6223(Springer,2010),pp.
333–350.
http://dx.
doi.
org/10.
1007/978-3-642-14623-71882.
E.
Corporation.
RSA-768isFactored!
http://www.
emc.
com/emc-plus/rsa-labs/historical/rsa-768-factored.
htm83.
A.
K.
Lenstra,W.
HendrikJr.
(eds.
),TheDevelopmentoftheNumberFieldSieve.
No.
1554inLectureNotesinMathematics(Springer,1993)84.
C.
Pomerance,Not.
AMS43(12),1476(1996)85.
R.
Crandall,C.
Pomerance,PrimeNumbers:AComputationalPerspective.
LectureNotesinStatistics(Springer,2006).
https://books.
google.
co.
uk/booksid=ZXjHKPS1LEAC86.
J.
B.
Rosser,L.
Schoenfeld,Ill.
J.
Math.
6,64(1962)87.
A.
Childs,W.
vanDam,Rev.
Mod.
Phys.
82,1(2010)88.
M.
Mosca,inEncyclopediaofComplexityandSystemsScience(Springer,2008).
arXiv:0808.
0369v189.
W.
Dife,M.
E.
Hellman,IEEETrans.
Inf.
Theory22(6),644(1976)90.
G.
H.
Hardy,E.
M.
Wright,AnIntroductiontotheTheoryofNumbers(OxfordUniversityPress,2008)91.
A.
M.
Antonopoulos,MasteringBitcoin,2ndedn.
(O'Reilly,2017)92.
A.
Khalique,K.
Singh,S.
Sood,Int.
J.
Comput.
Appl.
2(2),21(2010).
https://doi.
org/10.
5120/631-87693.
D.
L.
R.
Brown.
Sec2:RecommendedEllipticCurveDomainParameters.
http://www.
secg.
org/sec2-v2.
pdf94.
M.
Boyer,G.
Brassard,P.
Hyer,A.
Tapp,FortschrittederPhysik49,493(1998)95.
S.
Jordan.
QuantumAlgorithmZoo.
http://math.
nist.
gov/quantum/zoo/96.
W.
vanDam,Y.
Sasaki,inDiversitiesinQuantumComputationandQuantumInformation(WorldScientic,2012),pp.
79–105.
https://doi.
org/10.
1142/9789814425988000397.
L.
C.
Washington,EllipticCurves,2ndedn.
(Chapman&Hall/CRC,2008)98.
S.
J.
Devitt,W.
J.
Munro,K.
Nemoto,Rep.
Prog.
Phys.
76(7),076001(2013)99.
P.
Shor,Phys.
Rev.
A52(5),R2493(1995)100.
D.
Gottesmann,inQuantumInformationScienceandItsContributionstoMathematics,vol.
68(AmericanMathematicalSociety,2010),pp.
13–58.
arXiv:0904.
2557v1101.
D.
A.
Lidar,T.
A.
Brun(eds.
),QuantumErrorCorrection(CambridgeUniversityPress,2013)102.
D.
Gottesmann,Phys.
Rev.
A54,1862(1996)103.
A.
R.
Calderbank,E.
M.
Rains,P.
W.
Shor,N.
J.
A.
Sloane,Phys.
Rev.
Lett.
78,405(1997)104.
V.
Pless,IntroductiontotheTheoryofError-CorrectingCodes,3rdedn.
(Wiley-Interscience,1998)758References105.
A.
M.
Steane,inQuantumComputers,AlgorithmsandChaos,ed.
byP.
Z.
G.
Casati,D.
L.
She-pelyansky(2006)106.
F.
Gaitan,QuantumErrorCorrectionandFaultTolerantQuantumComputing(CRCPress,2008)107.
A.
Kitaev,inProceedingsofthe3rdInternationalConferenceofQuantumCommunicationandMeasurement,ed.
byO.
Hirota,A.
S.
Holevo,C.
M.
Caves(PlenumPress,1997),pp.
181–188108.
A.
Kitaev,TopologicalQuantumCodesandAnyons,vol.
58(AmericanMathematicalSoci-ety,2002),pp.
267–272109.
M.
Born,V.
Fock,Zeitschriftf¨urPhysik51(3–4),165(1928).
https://doi.
org/10.
1007/BF01343193110.
T.
Kato,J.
Phys.
Soc.
Jpn.
5,435(1950).
https://doi.
org/10.
1143/JPSJ.
5.
435111.
S.
Jansen,M.
B.
Ruska,R.
Seiler,J.
Math.
Phys.
48,102111(2007).
https://doi.
org/10.
1063/1.
2798382112.
E.
Farhi,J.
Goldstone,S.
Gutmann,M.
Sipser,Quantumcomputationbyadiabaticevolution(2000).
arXiv:0001106v1113.
J.
Roland,N.
J.
Cerf,Phys.
Rev.
A65(2002)114.
T.
Albash,D.
A.
Lidar,Adiabaticquantumcomputing.
ArXiv:1611.
04471v1115.
M.
W.
Hirsch,S.
Smale,DifferentialEquations,DynamicalSystemsandLinearAlgebra(AcademicPress,1974)116.
P.
Deift,M.
B.
Ruskai,W.
Spitzer,QuantumInf.
Process.
6,121(2007)117.
C.
Moler,C.
V.
Loan,SIAMRev.
45(1),1(2003)118.
K.
L.
Pudenz,D.
A.
Lidar,QuantumInf.
Process.
12(5)(2011).
arXiv:1109.
0325v1119.
A.
Das,S.
Suzuki,Eur.
Phys.
J.
Spec.
Top.
224,5(2015)IndexAAbeliangroup,560AbelianHiddenSubgroupProblem(AHSP),302Adiabaticassumption,409generator,627genericalgorithm,413intertwiner,628schedule,414searchalgorithm,420theorem,636Algorithmadiabaticgeneric,413DEUTSCH–JOZSA,250EUCLID,517GROVER,335SHOR,274Alice,91Amplitudeamplication,324Ancilla,204register,204Anti-linear,13Asymmetriccipher,256Auxiliaryregister,204BBasisBELL,89codeword,356computational,87expansionofvector,16HILBERTspace,15orthonormal,15BB84,258BELLbasis,89inequality,144CHSH-generalization,148telephone,154Binaryaddition,162factor-wise,206exponentiation,233fractions,239quantumgate,169representation,86Bit-iperror,367Bit-phase-iperror,367BLOCHrepresentation,62Bob,91Bra-vector,18CCenter,569Centralizer,567Characterconjugate,580ofabeliangroup,580trivial,581Charactergroup,583Cipher,256asymmetric,256symmetric,256Circuitclassical,165quantumlengthof,201plain,201withancilla,204ClassicalAND-gate,162SpringerNatureSwitzerlandAG2019W.
Scherer,MathematicsofQuantumComputing,https://doi.
org/10.
1007/978-3-030-12358-1759760Indexcircuit,165code,349generatorof,349codeword,349computationalprocess,161errordetectionandcorrectionprotocol,354NOT-gate,162OR-gate,163TOFFOLI-gate,163XOR-gate,163Clockspace,443states,443Codeclassical,349distanceof,349quantum,356distanceof,381Codewordclassical,349quantum,356Coherent,55Commutator,26Compatible,35Computationalbasis,87processclassical,161quantummechanical,169Conjugate,567character,580subgroup,568Continuedfractionconvergent,545nite,545sequenceofconvergents,545Controlledquantumgate,176Convergentofcontinuedfraction,545Coprime,517Correctablequantumerror,369Correlation,504EPR,146Cosetleft,569right,569Counterstates,443Covariance,504Cyclicgroup,565DDecodingclassicalmaximum-likelihood,354quantum,356Decoherence,56Decryption,256Degenerate,23Densequantumcoding,251Densityoperator,44reduced,103DEUTSCH'sproblem,247Diagonalform,24Diagonalizable,24Directproductgroup,575Discardingtheancilla,205Discretegroup,560logarithm,310DiscreteLogarithmProblem(DLP),310Discriminantofellipticcurve,601Distance,347HAMMING,348ofaquantumcode,381ofclassicalcode,349Divisible,516Dualgroup,583space,18EEigenspace,23Eigenstate,34Eigenvalue,23gap,623Eigenvector,23EINSTEIN-PODOLSKY-ROSENparadox,137EK91,262Ellipticcurve,601discriminant,601WEIERSTRASSequation,601Encodingclassical,349quantum,356Encryption,256Entangled,129maximally,133Entanglementswapping,133Environmentalrepresentation,120EPRcorrelations,146paradox,137EquationIndex761SCHR¨ODINGER,38WEIERSTRASS,601Errorbit-ip,367bit-phase-ip,367correctingcodeclassical,349quantum,356m-qubit,365operationinquantumcode,365operators,365phase-ip,367EUCLIDalgorithm,517EULERfunction,525theoremof,526Exchangeoperator,181Expectationvalue,12ofarandomvariable,503quantummechanicalinapurestate,30inmixedstate,45FField,600Finite-dimensional,14Finitegroup,560FirstGroupIsomorphismTheorem,579FOURIERtransformdiscrete,238ongroup,599quantum,237FunctionEULER-,525hash,318measurable,501GGapofeigenvalues,623Gateclassical,161AND,162NOT,162OR,163reversible,161TOFFOLI,163universal,165XOR,163quantum,169binary,169HADAMARD,171NOT,171unary,169universal,175Generallineargroup,562Generatoradiabatic,627ofcyclicgroup,565GRAY-coded,193Greatestcommondivisor,517Group,559abelian,560character,580cyclic,565directproduct,575discrete,560dual,583nite,560nitelygenerated,565FOURIERtransformon,599generallinear,562generated,565generator,565homomorphism,576isomorphism,576leftaction,575ofcharacters,583orderof,560orthogonal,565PAULI,609quotient,573specialorthogonal,565specialunitary,564unitary,564GROVERiteration,330HHADAMARD-gate,171transformation,74Half-prime,525Hamiltonian,38HAMILTONoperator,38HAMMINGdistance,348weight,348Hashfunction,318Hermitian,22HiddenSubgroupProblem(HSP),302Hidingasubgroup,301HILBERTspace,12Homomorphism,576762IndexIIncoherent,55Incompatible,35Independentgroupelements,566InequalityBELL,144CHSH-generalization,148SCHWARZ-,17Integerpart,515Interference,32Invariantsubgroup,568Isomorphism,576KKernelofahomomorphism,576Ket-vector,18k-localoperator,105KRAUSoperator,120LLANDAUsymbolbig,513little,513Leftaction,575coset,569Lengthofquantumcircuit,201Linearlyindependent,14Logicalqubit,356MMatrixelement,19ofanoperator,19PAULI,40representation,19Maximalsubgroup,563Maximum-likelihooddecoding,354Max-minprinciple,474Meanvalue,11Measurablefunction,501space,501Measure,501probability,502space,501Measurementofaquantumregister,213probability,30sharp,34Minimalsubgroup,563Mixedstate,44m-qubiterror,365MultiplicativeinversemoduloN,523Nn-foldPAULIgroup,611No-CloningTheorem,159Non-degenerate,23Normofavector,13ofanoperator,26Normalizer,568Normalsubgroup,568Normed,14OObservable,12,29Operationelement,120Operator,22adjoint,22bounded,26density,44diagonalizable,24HAMILTON,38k-local,105KRAUS,120norm,26positive,26recovery,369resolvent,621self-adjoint,22strictlypositive,26super-,22unitary,23Operator-sumrepresentation,120Oracle,327OrdermoduloN,528ofagroup,560ofgroupelement,560polynomial,513Orthogonal,14group,565Orthonormalbasis(ONB),15PParadoxEINSTEIN-PODOLSKY-ROSEN,137EPR,137Paritycheckmatrix,349Partialtrace,100Index763PAULIgroup,609matrices,40n-foldgroup,611Phaseshiftconditional,242Phase-iperror,367Physicalqubit,356Polynomialorder,513Positiveoperator,26PrimitiverootmoduloN,528Probabilitydistribution,502discrete,502measure,502space,502ProblemAbelianHiddenSubgroup(AHSP),302DEUTSCH's,247DiscreteLogarithm(DLP),310Product-state,128Projectionoperator,25orthogonal,25postulate,37Projector,25Propersubgroup,563QQECC,356q-register,169QuadraticUnconstrainedBinaryOptimiza-tion(QUBO),417QuantumaddermoduloN,226adiabatictheorem,636channel,121code,356codeword,356computationalprocess,169copier,158decoding,356encoding,356encodingspace,356errorcorrectable,369correctingcode,356detectionandcorrectionprotocol,385detectionandcorrectionprotocolforstabilizerQECC,401operationincode,365operators,365FOURIERtransform,237gate,169binary,169controlled,176unary,169universal,175multipliermoduloN,229No-CloningTheorem,159-NOT-gate,171operation,120parallelism,212plaincircuit,201register,169measurement,213observation,213read-out,213Qubit,58logical,356physical,356space,58state,58Quotientgroup,573RRandomvariable,502discrete,502Ray,32Read-outofaquantumregister,213Recoveryoperationfromquantumerror,369Reducedresolvent,629Reectionaboutasubspace,328Registerancilla,204auxiliary,204Relativefrequency,11Remainderafterdivision,515Resolventofanoperator,621reduced,629Reversibleclassicalgate,161Rightcoset,569SScalarproduct,12Scheduleofadiabaticalgorithm,414SCHMIDTdecomposition,107SCHR¨ODINGERequation,38SCHWARZ-inequality,17Searchadiabaticalgorithm,420764IndexGROVERalgorithm,335,338Separable,129state,128σ-algebra,501Smallestcommonmultiple,517SpaceHILBERT-,12measurable,501probability,502qubit,58Span,14Specialorthogonalgroup,565unitarygroup,564Spectrum,23Spin,39rotation,64Stabilizer,575code,393State,12entangled,129mixed,44product-,128pure,30qubit,58separable,128vector,30Subgroup,563conjugate,568invariant,568maximal,563minimal,563normal,568proper,563Superoperator,22Superpositionprinciple,32Swapoperatorglobal,181Symmetriccipher,256Syndromeclassical,352detectionoperator,384extraction,385ofquantumerror,385ofstabilizerQECC,396TTarget-qubit,176Teleportation,253Tensorproduct,81TheoremAdiabatic,636EULER,526FirstGroupIsomorphism,579GLEASON,46No-Cloning,159PYTHAGORAS,17RIESZ,18Timeevolution,38Trace,28partial,100-preservingquantumoperation,121Trivialcharacter,581UUnaryquantumgate,169Uncertainty,33relation,35HEISENBERG,36Unitarygroup,564operator,23Unitvector,14Universalquantumgate,175VVariance,504WWavefunction,37collapseof,37WEIERSTRASSequation,601WeightHAMMING,348ofanelementofthePAULIgroup,611XX,171