THE QUANTUM COMMUNICATION COMPLEXITY OF SAMPLING

THEQUANTUMCOMMUNICATIONCOMPLEXITYOFSAMPLING∗ANDRISAMBAINIS†,LEONARDJ.SCHULMAN‡,AMNONTA-SHMA§,UMESHVAZIRANI¶,ANDAVIWIGDERSONSIAMJ.COMPUT.c2003SocietyforIndustrialandAppliedMathematicsVol.32,No.6,pp.1570–1585Abstract.Samplingisanimportantprimitiveinprobabilisticandquantumalgorithms.Inthespiritofcommunicationcomplexity,givenafunctionf:X×Y→{0,1}andaprobabilitydistributionDoverX×Y,wedefinethesamplingcomplexityof(f,D)astheminimumnumberofbitsthatAliceandBobmustcommunicateforAlicetopickx∈XandBobtopicky∈Yaswellasavaluezsuchthattheresultingdistributionof(x,y,z)isclosetothedistribution(D,f(D)).Inthispaperweinitiatethestudyofsamplingcomplexity,inboththeclassicalandquantummodels.Wegiveseveralvariantsofadefinition.Wecompletelycharacterizesomeofthesevariantsandgiveupperandlowerboundsonothers.Inparticular,thisallowsustoestablishanexponentialgapbetweenquantumandclassicalsamplingcomplexityfortheset-disjointnessfunction.Keywords.communicationcomplexity,quantumcommunicationcomplexity,quantuminfor-mationtheory,set-disjointness,thelog-rankconjectureincommunicationcomplexityAMSsubjectclassifications.68M10,68Q10,68R05DOI.10.1137/S0097539799354761.Introduction.Acentralquestioninquantuminformationtheoryistheamountofinformationthatcanbeencodedintonqubits.Therearedifferentwaystoformulatethisquestionand,surprisingly,theyyieldcompletelydifferentanswers.Themostnaturalvariantofthisquestionisthemaximalamountofmutualinforma-tionthatcanexistbetweenaclassicalrandomvariableXandaclassicalprobabilitydistributionYthatisobtainedfromashortquantumencodingofX.MorethantwodecadesagoHolevo[10]provedthatthemutualinformationcanbeatmostthenum-berofqubitscommunicated.Thatis,although2n−1complexnumbersarenecessarytospecifythestateofnquantumbits,onlynbitsofinformationcanberetrievedfromasuperpositiononnquantumbits,andcommunicatingqubitsisnotmoreusefulthanjustcommunicatingclassicalbits.However,thereissomethinginquantumbitsthatismorepowerfulthanclassicalones.ThefirstdemonstrationofthatwasbyBennettandWiesner[5]whoshowedthatifthetwopartiessharepredefinedentangledqubits(thatareabsolutelyindependentofthemessage),thenAlicecancommunicate2nclassicalbitstoBobusingonlyn∗ReceivedbytheeditorsApril12,1999;acceptedforpublication(inrevisedform)June2,2003;publishedelectronicallyOctober2,2003.AnearlierversionofthispaperappearedintheProceedingsofthe39thAnnualSymposiumonFoundationsofComputerScience(FOCS),PaloAlto,CA,IEEEComputerSociety,Washington,DC,1998,pp.342–351.†InstituteofMathematicsandComputerScience,UniversityofLatvia,RainaBulv.29,Riga,LV-1459Latvia([e-mail]).‡DivisionofEngineeringandAppliedScience,CaliforniaInstituteofTechnology,Pasadena,CA91125([e-mail]).§ComputerSciences,Tel-AvivUniversity,Tel-Aviv,Israel69978([e-mail]).¶ComputerScienceDivision,UniversityofCalifornia,Berkeley,CA94720-1776([e-mail]).Thisauthor’sworkwassupportedinpartbyDARPAgrantF30602-01-2-0524andNSFITRgrantCCR-0121555.ComputerScienceDepartment,TheHebrewUniversity,Jerusalem91904,Israel,andSchoolofMathematics,TheInstituteforAdvancedStudies,Princeton,NJ([e-mail]).Thisauthor’sworkwassupportedbygrant69/96oftheIsraelScienceFoundation,foundedbytheIsraelAcademyforSciencesandHumanities.1570THEQUANTUMCOMMUNICATIONCOMPLEXITYOFSAMPLING1571communicationqubits.AnotherexamplewassuppliedbyAmbainisetal.[3]andbyNayak[14],whereAlice’staskwastoencodemclassicalbitsintonqubits(mn)suchthatBobcouldchoosetoreadanyoneofthemencodedbitsofhischoice(therebypossiblydestroyingtheinformationabouttheremainingm−1bits).OnthepositivesidetheyshowedaschemebeatingHolevo’sbound,butonthenegativesidetheyshowedthatncanbenosmallerthanΩ(m).Arichhuntinggroundforrelevantexamplesisthecommunicationcomplexitymodel[21,20].Buhrman,Cleve,andWigderson[6]consideredthedisjointnessfunc-tion,whereAliceandBobgettwosubsetsx,yof[1,...,n],andDISJ(x,y)=1iffxandyaredisjoint.Itiswellknownthatanyclassicalprobabilisticprotocolmustex-changealinearnumberofcommunicationbits.Ontheotherhand,theyshowedthatthetaskcanbecarriedoutwithonlyO(√nlog(n))quantumbits.TheresultisbasedonGrover’squantumsearchalgorithm[9].Thisprovidedthefirstasymptoticsepa-rationinpowerbetweenclassicalandquantumcommunication.Recently,Razborov[17]showedanΩ(√n)lowerboundonthequantumcommunicationcomplexityoftheproblem,andAaronsonandAmbainis[1]showedthatRazborov’sboundistightuptoconstantfactors.Buhrman,Cleve,andWigderson[6]alsogaveanothercommunicationtaskbasedontheDeutsch–Jozsaproblem[8],wherethenumberofclassicalbitsrequiredtocomputeafunctionwithzeroerrorisexponentiallylargerthanthecorrespondingnumberofquantumbits.However,thereisaprobabilisticprotocolwithasmallerrorprobabilitywherethenumberofbitsexchangedisassmallasthenumberexchangedbythequantumprotocol.Raz[19]showedsuchanexponentialgapforapartialfunctioneveninthepresenceoferrors.However,theresultappliesonlyforpartialfunctionswhenthetwoplayersaregivenapromisethattheirinputscomefromasmall(infact,tiny)setofpossibleinputs.Inthispaperwegivethefirstexampleofacommuni