The Existence of Quantum Entanglement Catalysts

XiaomingSun†RunyaoDuan‡MingshengYing§

arXiv:quant-ph/0311133v2 18 Jan 2005StateKeyLaboratoryofIntelligentTechnologyandSystems,

DepartmentofComputerScienceandTechnology,TsinghuaUniv.,Beijing,100084,China.

Abstract

Withoutadditionalresources,itisoftenimpossibletotransformoneentangledquantumstateintoanotherwithlocalquantumoperationsandclassicalcommunica-tion.JonathanandPlenio[Phys.Rev.Lett.83,3566(1999)]presentedaninterestingexampleshowingthatthepresenceofanotherstate,calledacatalyst,enablessuchatransformationwithoutchangingthecatalyst.Theyalsopointedoutthatingeneralitisveryhardtofindananalyticalconditionunderwhichacatalystexists.Inthispaperwestudytheexistenceofcatalystsfortwoincomparablequantumstates.Forthesimplestcaseof2×2catalystsfortransformationsfromone4×4statetoanother,anecessaryandsufficientconditionforexistenceisfound.Forthegeneralcase,wegiveanefficientpolynomialtimealgorithmtodecidewhetherak×kcatalystexistsfortwon×nincomparablestates,wherekistreatedasaconstant.

IndexTerms—Quantuminformation,entanglementstates,entanglementtrans-formation,entanglementcatalysts.

1Introduction

Entanglementisafundamentalquantummechanicalresourcethatcanbesharedamongspatiallyseparatedparties.Thepossibilityofhavingentanglementisadistinguishingfea-tureofquantummechanicsthatdoesnotexistinclassicalmechanics.Itplaysacentralroleinsomestrikingapplicationsofquantumcomputationandquantuminformationsuchasquantumteleportation[1],quantumsuperdensecoding[2]andquantumcryptography[3].Asaresult,entanglementhasbeenrecognizedasausefulphysicalresource[4].However,manyfundamentalproblemsconcerningquantumentanglementarestillunsolved.Animportantsuchproblemconcernstheexistenceofentanglementtransformation.SupposethatAliceandBobeachhaveonepartofabi-partitestate.Thequestiontheniswhat

xm97@mails.tsinghua.edu.cn

Email:dry02@mails.tsinghua.edu.cn§

Email:yingmsh@mail.tsinghua.edu.cn

‡

1

otherstatescantheytransformtheentangledstateinto?Sinceanentangledstateisseparatedspatially,itisnaturaltorequirethatAliceandBobcanonlymakeuseoflocaloperationsandclassicalcommunication(LOCC).Significantprogressinthestudyofen-tanglementwasmadebyBennett,Bernstein,PopescuandSchumacher[5]in1996.Theyproposedanentanglementconcentrationprotocolwhichsolvedtheentanglementtrans-formationproblemintheasymptoticcase.In1999,Nielsen[6]madeanotherimportant󰀆n√advance.Supposethereisabi-partitestate|ψ1󰀔=i=1

βi|i󰀔A|i󰀔Bwith

OSCsβ1≥β2≥···≥βn≥0.Itwasprovedthat|ψ1󰀔→|ψ2󰀔ispossibleunderLOCCifandonlyifλψ1≺λψ2,whereλψ1andλψ2arethevectorsoforderedSchmidtcoefficients,i.e.λψ1=(α1,...,αn),λψ2=(β1,...,βn),≺denotesthemajorizationrelation[7,8],i.e.for1≤l≤n,

ll󰀃󰀃

βi,αi≤

i=1

i=1

withequalitywhenl=n.ThisfundamentalcontributionbyNielsenprovidesuswithan

extremelyusefulmathematicaltoolforstudyingentanglementtransformation.AsimplebutsignificantfactimpliedbyNielsen’stheoremisthatthereexistincomparablestates|ψ1󰀔and|ψ2󰀔withbothtransformations|ψ1󰀔→|ψ2󰀔and|ψ2󰀔→|ψ1󰀔impossible.ShortlyafterNielsen’swork,aquitesurprisingphenomenonofentanglement,namely,entanglementcatalysis,wasdiscoveredbyJonathanandPlenio[9].Theygaveanexampleshowingthatonemayuseanotherentangledstate|c󰀔,knownasacatalyst,tomakeanimpossibletransformation|ψ󰀔→|φ󰀔possible.Furthermore,thetransformationisinfactoneof|ψ󰀔⊗|c󰀔→|φ󰀔⊗|c󰀔,sothatthecatalyst|c󰀔isnotmodifiedintheprocess.

Entanglementcatalysisisanotherusefulprotocolthatquantummechanicsprovides.Thereforetoexploitthefullpowerofquantuminformationprocessing,wefirsthavetosolvethefollowingbasicproblem:givenapairofincomparablestates|ψ1󰀔and|ψ2󰀔with|ψ1󰀔→|ψ2󰀔and|ψ2󰀔→|ψ1󰀔,determinewhetherthereexistsacatalyst|c󰀔suchthat|ψ1󰀔⊗|c󰀔→|ψ2󰀔⊗|c󰀔.AccordingtoNielsen’stheorem,solvingtheproblemrequiresdeterminingwhetherthereisastate|c󰀔forwhichthemajorizationrelationλψ1⊗c≺λψ2⊗cholds.AspointedoutbyJonathanandPlenio[9],itisverydifficulttofindananalyticalandbothnecessaryandsufficientconditionfortheexistenceofacatalyst.Thedifficultyismainlyduetolackofsuitablemathematicaltoolstodealwithmajorizationoftensorproductstates,andespeciallytheflexibleorderingoftheOSCsoftensorproducts.In[9],JonathanandPlenioonlygavesomesimplenecessaryconditionsfortheexistenceofcatalysts,butnosufficientconditionwasfound.Thosenecessaryconditionsenabledthemtoshowthatentanglementcatalysiscanhappeninthetransformationbetweentwon×nstateswithn≥4.Oneofthemainaimsofthepresentpaperistogiveanecessaryandsufficientconditionforentanglementcatalysisinthesimplestcaseofentanglementtransformationbetween4×4stateswitha2×2catalyst.Forgeneralcase,thefactthatananalyticalconditionunderwhichincomparablestatesarecatalyzableisnoteasytofindleadsusnaturallytoanalternativeapproach;thatis,toseeksomeefficientalgorithmtodecidecatalyzabilityofentanglementtransformation.Indeed,an

2

algorithmtodecidetheexistenceofcatalystswasalreadypresentedbyBandyopadhyayandRoychowdhury[10].Unfortunately,fortwon×nincomparablestates,todeterminewhetherthereexistsak×kcatalystforthem,theiralgorithmrunsinexponentialtimewithcomplexityO([(nk)!]2),andsoitisintractableinpractice.TheintractabilityofBandyopadhyayandRoychowdhury’salgorithmstimulatedustofindamoreefficientalgorithmforthesamepurpose,andthisisexactlythesecondaimofthepresentpaper.

Thispaperisorganizedasfollows.Inthesecondsectionwedealwithentanglementcatalysisinthesimplestcaseofn=4andk=2.Anecessaryandsufficientconditionunderwhicha2×2catalystexistsforanentanglementtransformationbetween4×4statesispresented.ThisconditionisanalyticallyexpressedintermsoftheOSCsofthestatesinvolvedinthetransformation,andthusitiseasilycheckable.Also,someinterestingexamplesaregiventoillustratetheuseofthiscondition.Thethirdsectionconsidersthegeneralcase.Weproposeapolynomialtimealgorithmtodecidetheexistenceofcatalysts.Suppose|ψ1󰀔and|ψ2󰀔aretwogivenn×nincomparablestates,andkisanyfixednaturalnumber.Withtheaidofouralgorithm,onecanquicklyfindallk×kcatalystsforthetransformation|ψ1󰀔→|ψ2󰀔usingonlyO(n2k+3.5)time.ComparingtothetimecomplexityO([(nk)!]2)ofthealgorithmgivenin[10],forconstantk,ouralgorithmimprovesthecomplexityfromsuperexponentialtopolynomial.Wemakeconclusionsinsection4,andsomeopenproblemarealsodiscussed.

simplifythepresentation,intherestofthepaper,weidentifythestate|ψ󰀔=󰀆nTo√

i=1

Theseinequalitiesaremerelynecessaryconditionsfortheexistenceofcatalyst|φ󰀔,anditiseasytoseethattheyarenotsufficient.Inthefollowingtheoremwegiveaconditionwhichisbothnecessaryandsufficient.

Theorem2.1Thereexistsacatalysts|φ󰀔fortwostates(|ψ1󰀔,|ψ2󰀔)with|ψ1󰀔→|ψ2󰀔,ifandonlyif

󰀅󰀄󰀄

β1β4α1+α2−β1

,1−≤minmax

β3−α3α2−β2

α4−β4

β1−α1

󰀅

β2+β3

,1−

α1+α2

,

α3+α4

|φ󰀔=(c,1−c)isacatalystfor(|ψ1󰀔,|ψ2󰀔).

Proof:Assume|ψ1󰀔→|ψ2󰀔but|ψ1󰀔⊗|φ󰀔→|ψ2󰀔⊗|φ󰀔underLOCC.FromEq.(8)in[9]

weknowEq.(1)holds.SoEq.(2)andEq.(3)holdtoo.

AroutinecalculationshowsthattheSchmidtcoefficientsof|ψ1󰀔|φ󰀔and|ψ2󰀔|φ󰀔are

A={α1c,α2c,α3c,α4c;α1(1−c),α2(1−c),α3(1−c),α4(1−c)}

and

B={β1c,β2c,β3c,β4c;β1(1−c),β2(1−c),β3(1−c),β4(1−c)},

respectively.SorttheelementsinAandBindecreasingorderanddenotetheresultedsequencesbya(1)≥a(2)≥···≥a(8)andb(1)≥b(2)≥···≥b(8).Itisclearthata(1)=α1c,a(8)=α4(1−c),b(1)=β1c,andb(8)=β4(1−c).Since|ψ1󰀔⊗|φ󰀔→|ψ2󰀔⊗|φ󰀔,Nielsen’stheoremtellsusthat

ll󰀃󰀃

b(i)(∀1≤l≤8)a(i)≤

i=1

i=1

Since{βi}isordered,andc≥0.5,thus

β1c≥β2c≥β3c≥β4c,β1(1−c)≥β2(1−c)≥β3(1−c)≥β4(1−c),βic≥βi(1−c)(5)Nowwearegoingtodemonstratethat

β1c≥β1(1−c)>β2c≥β3c>β2(1−c)≥β3(1−c)>β4c≥β4(1−c).

(6)

andconsequentlyfixtheorderingofB.Thekeyideais:thesumofthebiggestlnumbers

inasetisgreaterthanorequalthesumofanylnumbersinthisset.

First,bydefinitionof{a(i)}wehavea(1)+a(2)≥α1c+α2c.SoNielsen’stheoremleadstob(1)+b(2)≥a(1)+a(2)≥α1c+α2c.Frominequality(1),α1+α2>β1+β2,sob(1)+b(2)>β1c+β2c,i.e.b(2)>β2c.Combiningthiswithinequality(5),weseethattheonlycaseisb(2)=β1(1−c),b(3)=β2candβ1(1−c)>β2c.

4

Similarly,wehave

a(1)+a(2)+a(3)+a(4)≥α1c+α2c+α1(1−c)+α2(1−c)=α1+α2.

Soitholdsthat

b(1)+b(2)+b(3)+b(4)≥a(1)+a(2)+a(3)+a(4)≥α1+α2>β1+β2.

Thisimpliesb(4)>β2(1−c).Thenitmustbethatb(4)=β3c,andβ3c>β2(1−c).

Nowwhatremainsistodeterminetheorderbetweenb(5)andb(7).Weconsiderb(7)first.Nielsen’stheoremyieldsb(7)+b(8)≤a(7)+a(8).Bydefinition,weknowthata(7)+a(8)≤α3(1−c)+α4(1−c).Therefore,

b(7)+b(8)≤α3(1−c)+α4(1−c)=(α3+α4)(1−c)<(β3+β4)(1−c),

thelastinequalityisdueto(2).Sinceb(8)=β4(1−c),itfollowsthatb(7)<β3(1−c).Furthermore,weobtainb(7)=β4c,b(6)=β3(1−c),andβ3(1−c)>β4c.

Finally,onlyβ2(1−c)leaves,sob(5)=β2(1−c).Combiningtheabovearguments,wefinishtheproofofinequality(6).

Clearly,inequality(6)impliesthat

β2

β1+β2

,

β3

ProofofTheorem2.1(continued):Nowtheabovelemmaguaranteesaquiteeasywayto󰀆l

dealwithi=1a(i):enumeratingsimplyallthepossiblecases.Forexample,a(1)+a(2)=α1c+α1(1−c)orα1c+α2c󰀆,i.e.a(1)+a(2)=max{α1c+α1(1−c),α1c+α2c}.The󰀆8(i)(i)arethesame.Whatwestillneedtodonowistotreatmentsfor3i=1a,...,i=1a󰀆󰀆l

(i)≤(i)(1≤l≤8).Weputthissolvesystematicallytheinequalitiesoflai=1i=1b

dauntingbutroutinepartintheAppendix.󰀁Theabovetheorempresentsanecessaryandsufficientconditionwhena2×2catalystexistsforatransformationfromone4×4statetoanother.Moreover,itisalsoworthnotingthatthetheoremisindeedconstructive.Thesecondpartofitgivesall2×2catalysts(ifany)forsuchatransformation.Toillustratetheutilityoftheabovetheorem,letusseesomesimpleexamples.

Example2.1ThisexampleisexactlytheoriginalexamplethatJonathanandPlenio[9]usedtodemonstrateentanglementcatalysis.Let|ψ1󰀔=(0.4,0.4,0.1,0.1)and|ψ2󰀔=(0.5,0.25,0.25,0).Then

󰀅󰀄

α1+α2−β1

=max{0.6,1−2/3}=0.6,max

β3−α3

󰀄

β4β1

,1−min

α2−β2

β2+β3

α1+α2

,β1−α1

,1−

α4−β4

󰀅

=min{25/38,10/11,1−0}=25/38,

α3+α4

and0.52<0.65<25/38,Theorem2.1guaranteesthat|φ󰀔isreallyacatalyst;anditallowsustofindmuchmorecatalysts|φ󰀔=(c,1−c)withc∈[0.52,25/38].

3Anefficientalgorithmfordecidingexistenceofcatalysts

Inthelastsection,wewasabletogiveanecessaryandsufficientconditionunderwhicha2×2catalystexistsforantransformationbetween4×4states.ThekeyideaenablingustoobtainsuchaconditionisthattheorderamongtheSchmidtcoefficientsofthetensorproductofthecatalystandthetargetstateinthetransformationisuniquelydeterminedbyNielsen’sTheorem.However,thesameideadoesnotworkwhenwedealwithhigher

6

dimensionalstates,anditseemsveryhardtofindananalyticalconditionforexistenceofcatalystinthecaseofhigherdimension.Ontheotherhand,existenceofcatalystsisadominantprobleminexploitingthepowerofentanglementcatalysisinquantuminformationprocessing.Suchadilemmaforcesustoexplorealternativelythepossibilityoffindinganefficientalgorithmfordecidingexistenceofcatalysts.Themainpurposeistogiveapolynomialtimealgorithmtodecidewhetherthereisak×kcatalystfortwoincomparablen×nstates|ψ1󰀔,|ψ2󰀔,wherek≥2isafixednaturalnumber.

Toexplaintheintuitionbehindouralgorithmmoreclearly,wefirstcopewiththecaseofk=2.Assume|ψ1󰀔=(α1,...,αn),and|ψ2󰀔=(β1,...,βn)aretwon×nstates,andassumethatthepotentialcatalystforthemisa2×2stateφ=(x,1−x).TheSchmidtcoefficientsof|ψ1󰀔|φ󰀔and|ψ2󰀔|φ󰀔arethengivenas

Ax={α1x,α2x,...,αnx;α1(1−x),...,αn(1−x)}

and

Bx={β1x,β2x,...,βnx;β1(1−x),...,βn(1−x)},

respectively.Sortthemindecreasingorderanddenotetheresultingsequencesbya(1)(x)≥a(2)(x)≥···≥a(2n)(x)andb(1)(x)≥b(2)(x)≥···≥b(2n)(x).ByNielsen’stheoremweknowthatanecessaryandsufficientconditionfor|ψ1󰀔|φ󰀔→|ψ2󰀔|φ󰀔is

l󰀃i=1

a(i)(x)≤

l󰀃i=1

b(i)(x)(l=1,...,2n).

Nowthedifficultyarisesfromthefactthatwedonotknowtheexactorderofelements

inAandB.Letusnowconsiderthisprobleminadifferentway.Ifwefixxtosomeconstantx0,wecancalculatetheelementsinA,Bandsortthem.Thenifwemovesxslightlyfromx0tox0+ǫ,theorderoftheelementsinA(orB)doesnotchange,exceptthecasethatxgoesthroughapointx∗withαi(1−x∗)=αjx∗(orβi(1−x∗)=βjx∗),i.e.x∗=αi

βi+βj)forsomeialgorithm:

7

Algorithm11.ρi,j←

αi

βi+βj,

1≤i2.Sort{ρi,j}∪{δi,j}innondecreasingorder,theresultedsequenceisdenotedbyγ(1)≤

2

γ(2)≤···≤γ(n−n)3.γ(0)←0.5,γ(n5.

c←

2−n+1)

←1

4.Fori=0ton2−ndo

γ(i)+γ(i+1)

󰀁󰀂󰀁n󰀂2k2where|Γ|=2k22=O(n).Inthek−dimensionalspaceR,theseO(n)hyperplanes

canatmostdividethewholespaceintoO(O(n2)k)=O(n2k)differentparts.Notethenumberofpartsgeneratedbythesehyperplanesisapolynomialofn.Nowweenumerateallthesepossibleparts.Ineachpart,fordifferentx,theelementsinAx(orBx)hasthesameorder.Thenwecansolvetheinequalities

l󰀃i=1

a(i)(x)≤

l󰀃i=1

b(i)(x)(1≤l≤nk)

andchecktheorderconstrainsbylinearprogramming.Followingthewell-knownresult

thatlinearprogrammingissolvableinO(n3.5)time,ouralgorithmrunsinO(n2k+3.5)time,itisapolynomialtimeofnwheneverkisagivenconstant.󰀁

Indeed,Theorem3.1isconstructivetoo,anditsproofgivesanalgorithmwhichisablenotonlytodecidewhetheracatalystofagivendimensionexistsbutalsotofindallsuchcatalystswhentheydoexist.Thealgorithmbeforethistheoremisjustamoreexplicitpresentationoftheproofforthecaseofk=2.

4Conclusionanddiscussion

Inthispaper,weinvestigatetheproblemconcerningexistenceofcatalystsforentanglementtransformations.Itissolvedforthesimplestcaseinananalyticalway.Wegiveanecessaryandsufficientconditionfortheexistenceofa2×2catalystforapairoftwoincomparable4×4states.Forthegeneralcase(k×kcatalystsforn×nstates),althoughwefailtogiveananalyticalcondition,anefficientpolynomialtimealgorithmisfoundwhenkistreatedasaconstant.However,ifkisavariable,rangingoverallpositiveintegers,theproblemofdeterminingtheexistenceofcatalystsstillremainsopen.WebelieveitisNP-hard,sincethesetAx={α1x1,...,αnx1;α1x2,...,αnx2;...,αnxk}intheproofofTheorem3.1potentiallyhasexponentialkindofdifferentorders.

Acknowledgements:Theauthorsareverygratefultotheanonymousrefereesfortheirinvaluablecommentsandsuggestionsthathelpedtoimprovethepresentationinthispaper.

References

[1]C.H.Bennett,G.Brassard,C.Crepeau,R.Josza,A.Peres,andW.K.Wooters,

“TeleportinganunknownquantumstateviadualclassicalandEinstein-Podolsky-Rosenchannels”,Phys.Rev.Lett.,vol.70,pp.1895–1899,Mar.1993.[2]C.H.BennettandS.J.Wiesner,“Communicationviaone-andtwo-particleoperators

onEinstein-Podolsky-Rosenstates”,Phys.Rev.Lett.,vol.69,pp.2881–2884,Nov.1992.

9

[3]C.H.BennettandG.Brassard,“Quantumcryptography:Publickeydistribution

andcointossing,”InProceedingsofIEEEInternationalConferenceonComputers,Systems,andSignalProcessing,pp.175–179,IEEE,NewYork,1984.[4]M.A.NielsenandI.L.Chuang,QuantumComputationandQuantumInformation,

CambridgeUniversityPress,Cambridge,2000.[5]C.H.Bennett,H.J.Bernstein,S.Popescu,andB.Schumacher,“Concentratingpar-tialentanglementbylocaloperations,”Phys.Rev.A,vol.53,pp.2046–2052,Apr.1996.[6]M.A.Nielsen,“ConditionsforaClassofEntanglementTransformations,”Phys.Rev.

Lett.,vol.83,pp.436–439,Jul.1999.[7]A.W.MarshallandI.Olkin,Inequalities:TheoryofMajorizationandItsApplica-tions,AcademicPress,NewYork,1979.[8]P.AlbertiandA.Uhlmann,StochasticityandPartialOrder:DoublyStochasticMaps

andUnitaryMixing,Dordrecht,Boston,1982.[9]D.JonathanandM.B.Plenio,“Entanglement-AssistedLocalManipulationofPure

QuantumStates”,Phys.Rev.Lett.,vol.83,pp.3566–3569,Oct.1999.[10]S.BandyopadhyayandV.Roychowdhury,“Efficiententanglement-assistedtransfor-mationforbipartitepurestates”,Phys.Rev.A,vol.65(4),Art.No.042306,Apr.2002.

5Appendix:ProofofTheorem2.1

ProofofTheorem2.1(remainingpart):Weneedtosolvethesystemofinequalities󰀆󰀆ll(i)(1≤l≤8).Thisiscarriedoutbythefollowingitems:(i)≤

i=1bi=1a

(1)First,wehave:

a(1)≤b(1)⇐⇒α1c≤β1c⇐⇒α1≤β1.

(9)

(2)Theinequalitya(1)+a(2)≤b(1)+b(2)mayberewrittenasmax{α1c+α1(1−c),α1c+α2c}≤β1c+β1(1−c)⇐⇒

c

≤

(10)

β1

α1+α2+α3−β2

,

β1−α1

(4)Itholdsthat

a(1)+a(2)+a(3)+a(4)c+α≤b(1)+b(2)+b(3)+b(4)max{αc),

⇐⇒

11(1−c)+α2c+α2(1−c),α1c+α2c+α3c+α1(1−α1c+α2c+α3c+α4c}≤β1c+β1(1−c)+β2c+β3c

⇐⇒

α1+α2−β1

β11−β2−β3

,

−α1β3−α3

≤c≤1−

β4

α3+α4,

α4≥β4

(7)Wehave

󰀃7a

(i)

b(i)i=1

≤

󰀃7i=1

⇐⇒a(8)≥b(8)⇐⇒α4≥β4

CombiningEq.(7,9-16)weobtain

c≤

󰀄

β1

ββ3+β4;1α1+α2+α3,β1−α1,β−β21−β2−β3

1−α1α2+α3+α4−β3

,1−

β4

β2+β3

,1−

α4−β4

1

ifα2+α3−β2−β3≤0,thistermisuseless.

11

(15)

(16)

itfollowsthat

β1

α1+α2

β3

β3+β4

α1+α2

α1+α2

<

<

,

β4

>1−β1

=

β1

β1+β4

β1β4

α2+α3+α4−β3α2+α3−β2−β3

>1−

≥

β1−α1

β2+β3

,1−

α4−β4

α1+α2

,

β1−α1

α3+α4

󰀅

.

Therefore,Eq.(4)isanecessaryconditionfortheexistenceofcatalyst.

Ontheotherhand,weclaimthatEq.(1)andEq.(4)arethesufficientconditions.Indeed,ifwechooseac󰀆satisfiesEq.(2.1),thencsatisfiesEq.(17)and(18).From󰀆k(i)Eq.(9-16)weknowthati=1a(i)≤ki=1b,i.e.|ψ1󰀔|φ󰀔→|ψ2󰀔|φ󰀔underLOCC.Thiscompletestheproof.󰀁

12