Towards the Classical Communication Complexity of

arXiv:quant-ph/0207090v331Jul2002TowardstheClassicalCommunicationComplexityofEntanglementDistillationProtocolswithIncompleteInformationAndrisAmbainis∗[e-mail]†[e-mail]1,2008AbstractQuantumentanglementdistillationprotocolsareLOCCprotocolsbetweenAliceandBobthatconvertimperfectEPRpairs,or,ingeneral,partiallyentangledbipartitestatesintoperfectornear-perfectEPRpairs.Theclassicalcommunicationcomplexityoftheseprotocolsistheminimalamountofclassicalcommunicationneededfortheconversion.Inthispaper,wefocusonthecommunicationcomplexityofprotocolsthatoperatewithincompleteinformation,i.e.,wheretheinputsaremixedstatesand/orpreparedadversarially.Westudy3modelsofimperfectEPRpairs.Inthemeasure-rmodel,routofnEPRpairsaremeasuredbyanadversary;inthedepolarizationmodel,Bob’sshareofqubitsunderwentadepolarizationchannel;inthefidelitymodel,theonlyinformationAliceandBobpossessisthefidelityofthesharedstate.Forthemeasure-rmodelandthedepolarizationmodel,weprovetightandalmost-tightboundsontheoutcomeofLOCCprotocolsthatdon’tusecommunication.Forthefidelitymodel,weprovealowerboundonthecommunicationcomplexitythatmatchestheupperboundgivenbyAmbainis,Smith,andYang[ASY02].1Introduction1.1EntanglementDistillationProtocolsQuantumentanglementplaysacentralroleinquantuminformationtheory.Thephenomenonofhavingentangledstatesseparatedbyspace,isoneofthequintessentialfeaturesinquantummechanics.Infact,oneofthemostfundamentalproblemsinquantuminformationtheoryistounderstandentanglement.Inparticular,averyimportantquestionishowtoquantifyentanglement:howdowemeasuretheamounttheentanglementofageneralbipartitestate?Notonlyisquantumentanglementconceptuallyinteresting,itisveryuseful“inpractice”.IfAliceandBobshareEPRpairs[EPR35],thentheycanperformteleportation[BBC+93]:AlicecantransmitanunknownqubittoBobbysimplysending2classicalbits.Inthissense,sharedEPRpairs(pairedwithaclassicalcommunicationchannel)areequivalenttoaquantumchannel.Furthermore,EPRpairsmake“superdensecoding”[BW92]possible,whereAlicecantransmit2classicalbitstoBobbyonlysendingonequbit,providedthatAliceandBobshareanEPRpairapriori.However,qubitsarepronetoerrors,andEPRpairsmaydecohereandbecomeimperfect.CanAliceandBobperformreliableteleportationandsuperdensecodingiftheyshareimperfectEPRpairs?EntanglementDistillationProtocols(EDPs)provideanswerstobothquestionsmentionedabove.Informally,EDPsaretwo-partyprotocolsthattakeimperfectEPRpairs(orgeneralentangledstates)asinput,andoutputbipartitestatesthatarenear-perfectEPRpairs.Duringtheexecutionoftheprotocol,bothparties(denotedbyAliceandBob)canperformlocalquantumoperations(unitarytransformationsandmeasurements)ontheirshareofqubits,andcommunicateclassicalinformation.AliceandBobarenotallowedtosendqubitstoeachother.Protocolsofthistypearecalled“LOCCprotocols”,standingfor“LocalOperationClassicalCommunication”.WithEDPs,onecanderiveaquantity,namelythe“distillableentanglement”,foranybipartitestate.ThedistillableentanglementofastateisthemaximumnumberofEPRpairsAliceandBobcanoutputusingtheoptimalEDP,whichprovedtobeaveryimportantquantityinmeasuringtheamountofentanglementforbipartitestates.Thisanswersthefirstquestionwementionedabove.Forthesecondquestion,AliceandBobcanengageinanEDPto“distill”nearperfectEPRpairsfromimperfectones,andthenusethedistiledEPRpairstoperformteleportationandsuperdensecodingreliably.∗SupportedbyNSFGrantCCR-9987845andtheStateofNewJersey.†ThisresearchwassponsoredbyNationalScienceFoundation(NSF)grantsCCR-0122581andCCR-0085982.Theviewsandconclusionscontainedinthisdocumentarethoseoftheauthorandshouldnotbeinterpretedasrepresentingtheofficialpolicies,eitherexpressedorimplied,oftheNSFortheUSgovernment.1Therehavebeennumerousresearcheffortsonentanglementdistillationprotocols.Weonlylistsomeofthemostrelevantworkhere.Toourknowledge,Bennett,Bernstein,Popescu,andSchumacherarethefirsttoconsidertheproblemofproducingEPRpairsfrom“lessentangled”states.Intheirseminalpaper[BBP+96a],theygaveaprotocolthatconvertsmanyidenticalcopiesofpurestate|φi=(cosθ|01i+sinθ|10i)toperfectEPRpairs.Theycallthisprocess“entanglementconcentration”.Inthesameyear,Bennett,Brassard,Popescu,Schumacher,Smolin,andWootters[BBP+96b]studiedtheproblemof“extracting”near-perfectEPRpairsfromidenticalcopiesofmixedentangledstates.Thisisthefirsttimethatthenotion“entanglementpurificationprotocols”waspresented,whichwererenamedto“entanglementdistillationprotocols”later1.TheyalsopointedoutthatEDPscanbeusedtosendquantuminformationthroughanoisychannel.Later,Bennett,DiVincenzo,SmolinandWootters[BDS+96]improvedtheefficiencyoftheprotocolsin[BBP+96b]andprovedaresultthatcloselyrelatedEDPstoquantumerrorcorrectingcodes,whichisanalternativemeanstotransmitquantuminformationreliablythroughanoisychannel.Horodecki,Horodecki,andHorodecki[HHH96,HHH96]andRains[R98a,R98b,R00]gavevariousasymptoticboundsondistillableentanglementforarbitraryentangledstates.TheyconsideredthesituationwherenidenticalcopiesofastatearegivenasinputtoanLOCCprotocol,whichthenoutputsmEPRpairs.Theystudiedtheasympototicbehaviorofm/nasnapproachesinfinity.