Quantum Communication Complexity (A Survey)

arXiv:quant-ph/0101005v11Jan2001QuantumCommunicationComplexity(asurvey)GillesBrassard∗D´epartementIRO,Universit´edeMontr´ealC.P.6128,succursalecentre-villeMontr´eal(Qu´ebec),[e-mail]15December2000AbstractCanquantumcommunicationbemoreefficientthanitsclassicalcounterpart?Holevo’stheoremrulesoutthepossibilityofcommunicatingmorethannbitsofclassicalinformationbythetransmissionofnquantumbits—unlessthetwopartiesareentangled,inwhichcasetwiceasmanyclassicalbitscanbecommu-nicatedbutnomore.Inapparentcontradiction,therearedistributedcomputa-tionaltasksforwhichquantumcommunicationcannotbesimulatedefficientlybyclassicalmeans.Inextremecases,theeffectoftransmittingquantumbitscannotbeachievedclassicallyshortoftransmittinganexponentiallylargernumberofbits.Inasimilarvein,canentanglementbeusedtosaveonclassicalcommunica-tion?Itiswellknownthatentanglementonitsownisuselessforthetransmissionofinformation.Yet,therearedistributedtasksthatcannotbeaccomplishedatallinaclassicalworldwhencommunicationisnotallowed,butthatbecomepossibleifthenon-communicatingpartiessharepriorentanglement.Thisleadstothequestionofhowexpensiveitis,intermsofclassicalcommunication,toprovideanexactsimulationofthespookypowerofentanglement.∗SupportedinpartbyCanada’sNsercandQu´ebec’sFcar.1IntroductionItiswellknownthattheuseofquantuminformationallowsfortasksthatwouldbeprovablyimpossibleinaclassicalworld,suchasthetransmissionofuncondition-allyconfidentialinformationbetweenpartiesthatshareonlyashortsecretkey[2,4].Apartfromthisquantumcryptography,arethereadvantagestobegainedinsettingupaninfrastructurethatwouldfacilitatethetransmissionofquantuminformation?Inparticular,arethereadvantagestobegainedintermsofcommunicationefficiency?Adifferentbutrelatedquestionconcernsquantumentanglement:canentangledpartiesmakebetteruseofaclassicalcommunicationchannelthantheirnon-entangledcoun-terparts?Betterstill:canentangledpartiesbenefitfromtheirentanglementiftheyarenotallowedanyformofdirectcommunication?Therearegoodreasonstobelieveatfirstthattheanswertoalltheabovequestionsisnegative.Inparticular,Holevo’stheorem[18]statesthatnomorethannbitsofexpectedclassicalinformationcanbecommunicatedbetweenunentangledpartiesbythetransmissionofnquantumbits—henceforthcalledqubits—regardlessofthecodingschemethatcouldbeused.Ifthecommunicatingpartiessharepriorentanglement,twiceasmuchclassicalinformationcanbetransmitted[5],butnomore.Thisappliesevenifthecommunicationisnotrestrictedtobeone-way[14].Itisthusreasonabletoexpectthatnosignificantsavingsincommunicationcanbeachievedbythetransmissionofqubits,andpossiblynosavingsatallifthecommunicatingpartiesdonotsharepriorentanglement.Asforthelastquestion,itiswellknownthatentanglementalonecannotbeusedtosignalinformation—otherwisefaster-than-lightcommunicationwouldbepossibleandcausalitywouldbeviolated—andthusitwouldseemthatentanglementisuselessifitisnotsupplementedbydirectformsofcommunication.Herewesurveystrikingresultstotheeffectthatalltheintuitioninthisparagraphiswrong.AfterareviewofclassicalcommunicationcomplexityinSection2,weconsiderinSection3thesituationinwhichquantumcommunicationisallowed.InSection4,wereverttoclassicalcommunicationbutallowunlimitedpriorentanglementbetweenthecommunicatingparties.Section5investigatesinmoredetailthepowerofpriorentan-glementwhennodirectcommunicationisallowedtotakeplace,whichwecallspookycommunicationcomplexity.InSection6,wedeterminehowexpensiveitistosimulatetheeffectofentanglementinapurelyclassicalworld.Finally,weconcludewithopenproblemsinSection7.Althoughwedonotcovertheimportanttopicoflowerboundsforquantumcommunicationcomplexity,weencouragethereadertoconsult[20,14]forearlyresultsand[11]forpowerfulnewtechniques.22ClassicalCommunicationComplexityLetAliceandBobbetwodistantpartieswhowishtocollaborateonacommontaskthatdependsondistributedinputs.Moreprecisely,letX,YandZbesetsandconsiderafunctionf:X×Y→Z.AssumeAliceandBobaregivensomex∈Xandy∈Y,respectively,andtheirgoalistocomputez=f(x,y).Sometimes,weaddapromiseP(x,y)forsomeBooleanfunctionP,inwhichcaseAliceandBobarerequiredtocomputethecorrectanswerf(x,y)onlywhenP(x,y)holds.Whetherornotthereisapromise,theobviousrecipeisforAlicetocommunicatextoBob,whichallowshimtocomputez.Onceobtained,BobcanthencommunicatezbacktoAliceifbothpartiesneedtoknowtheanswer.Ifweareconcernedwiththeamountofcommunicationrequiredtoachievethistask—payingnoattentiontothecomputingeffortinvolvedintheprocess—couldtherebemoreefficientsolutionsforsomefunctionsf?Forallfunctions?Theanswerisobviouslypositiveforthefirstquestion.Forexample,ifX=Y={0,1}nforsomeintegern,Z={0,1}andf(x,y)isdefinedtobe0ifandonlyifxandyhavethesameHammingweight(thesamenumberof1s),itsufficesforAlicetocommunicatetheHammingweightofxtoBobforhimtoverifythecondition.Thus,aboutlgnbits1ofcommunicationaresufficientforthistask,whichismuchmoreeconomicalthanifAlicehadtransmittedallnbitsofherinputtoBob.Theanswertothesecondquestion,however,isnegative:Therearefunctionsforwhichtheobvioussolutionisoptimal.Forinstance,nbitsofcommunicationarenecessaryandsufficientintheworstcase