Quantum communication and complexity

QuantumCommunicationandComplexityRonalddeWolfa;1aCWI,P.O.Box94079,Amsterdam,TheNetherlands.E-mail:[e-mail]mmunicationcomplexity,twodistributedpartieswanttocomputeafunctiondependingonboththeirinputs,usingaslittlecommunicationaspossible.Therequiredcommunicationcansometimesbesignicantlyloweredifweallowthepartiestheuseofquantumcommunication.Wesurveythemainresultsoftheyoungareaofquantumcommunicationcomplexity:itsrelationtoteleportationanddensecoding,themainexamplesoffastquantumcommunicationprotocols,lowerbounds,andsomeapplications.1IntroductionTheareaofcommunicationcomplexitydealswiththefollowingtypeofprob-lem.Therearetwoseparatedparties,calledAliceandBob.Alicereceivessomeinputx2X,Bobreceivessomey2Y,andtogethertheywanttocomputesomefunctionf(x;y).Asthevaluef(x;y)willgenerallydependonbothxandy,neitherAlicenorBobwillhavesucientinformationtodothecom-putationbythemselves,sotheywillhavetocommunicateinordertoachievetheirgoal.Inthismodel,individualcomputationisfree,butcommunicationisexpensiveandhastobeminimized.Howmanybitsdotheyneedtocom-municatebetweentheminordertosolvethis?Clearly,AlicecanjustsendhercompleteinputtoBob,butsometimesmoreecientschemesarepossible.ThismodelwasintroducedbyYao[52]andhasbeenstudiedextensively,bothforitsapplications(likelowerboundsonVLSIandcircuits)andforitsownsake.Wereferto[38,32]fordenitionsandresults.Aninterestingvariantoftheaboveisquantumcommunicationcomplexity:supposethatAliceandBobeachhaveaquantumcomputerattheirdis-posalandareallowedtoexchangequantumbits(qubits)and/ortomakeuse1PartiallysupportedbytheEUfthframeworkprojectQAIP,IST{1999{11234.PreprintsubmittedtoElsevierPreprint21October2000ofthequantumcorrelationsgivenbysharedEPR-pairs(entangledpairsofqubitsnamedafterEinstein,Podolsky,andRosen[27]).CanAliceandBobnowcomputefwithlesscommunicationthanintheclassicalcase?QuantumcommunicationcomplexitywasrstconsideredbyYao[53]forthemodelwithqubitcommunicationandnopriorEPR-pairs,anditwasshownlaterthatforsomeproblemstheamountofcommunicationrequiredinthequantumworldisindeedconsiderablylessthantheamountofclassicalcommunication.Inthissurvey,werstgivebriefexplanationsofquantumcomputationandcommunication,andthencoverthemainresultsofquantumcommunicationcomplexity:upperbounds(Section5),lowerbounds(Section6),andapplica-tions(Section7).Weincludeproofsofsomeofthecentralresultsandrefer-encestoothers.Someotherrecentsurveysofquantumcommunicationcom-plexityare[48,15,35],andamorepopularaccountcanbefoundin[47].Oursurveydiersfromtheseinbeingabitmoreextensiveanduptodate.2QuantumComputationInthissectionwebrieygivetherelevantbackgroundfromquantumcompu-tation,referringtothebookofNielsenandChuang[44]formoredetails.2.1StatesandoperationsTheclassicalunitofcomputationisabit,whichcantakeonthevalues0or1.Inthequantumcase,theunitofcomputationisaqubitwhichisalinearcombinationorsuperpositionofthetwoclassicalvalues:0j0i+1j1i:Moregenerally,anm-qubitstatejiisasuperpositionofall2mdierentclassicalm-bitstrings:ji=Xi2f0;1gmijii:Theclassicalstatejiiiscalledabasisstate.Thecoecientiisacom-plexnumber,whichiscalledtheamplitudeofjii.Theamplitudesforma2m-dimensionalcomplexvector,whichwerequiretohavenorm1(i.e.Pijij2=1).Ifsomesystemisinstatejiandsomeotherisinstateji,thentheirjointstateisthetensorproductjiji=jiji.Wecanbasicallydotwothingstoaquantumstate:measureitorperformaunitaryoperationtoit.Ifwemeasureji,thenwewillseeabasisstate;wewillseejiiwithprobabilityjij2.Sincethenumbersjij2induceaprobability2distributiononthesetofbasisstatestheymustsumto1,whichtheyindeeddobecausejihasnorm1.Ameasurement\collapsesthemeasuredstatetothemeasurementoutcome:ifweseejii,thenjihascollapsedtojii,andallotherinformationinjiisgone.Apartfrommeasuring,wecanalsotransformthestate,i.e.,changetheam-plitudes.QuantummechanicsstipulatesthatthistransformationUmustbealineartransformationonthe2m-dimensionalvectorofamplitudes:U0BBBBB@0:::0...1:::11CCCCCA=0BBBBB@0:::0...1:::11CCCCCA:Sincethenewvectorofamplitudesimustalsohavenorm1,itfollowsthatthelineartransformationUmustbenorm-preservingandhenceunitary.2ThisinturnimpliesthatUhasaninverse(infactequaltoitsconjugatetransposeU),hencenon-measuringquantumoperationsarereversible.2.2QuantumalgorithmsWedescribequantumalgorithmsinthequantumcircuitmodel[25,53],ratherthanthesomewhatmorecumbersomequantumTuringmachinemodel[24,12].AclassicalBooleancircuitisadirectedacyclicgraphofelementaryBooleangates(usuallyAND,OR,andNOT),onlyactingononeortwobitsatatime.Ittransformsaninitialvectorofbits(containingtheinput)intotheoutput.Aquantumcircuitissimilar,exceptthattheclassicalBooleangatesnowbecomeelementaryquantumgates.Suchagateisaunitarytransformationactingonlyononeortwoqubits,andimplicitlyactingastheidentityontheotherqubitsofthestate.Asimpleexampleofa1-qubitgateistheHadamardtransform,whichmapsbasisstatejbito1p2(j0i+(1)bj1i).Inmatrixform,thisisH=1p20B@11111CA:Anexampleofa2-qubitgateisthecontrolled-NOT(CNOT)gate,whichnegatesthesecondbitofthestatedepen