Quantum Lower Bound for the Collision Problem

arXiv:quant-ph/0111102v120Nov2001QuantumLowerBoundfortheCollisionProblemScottAaronson∗February1,2008AbstractThecollisionproblemistodecidewhetherafunctionX:{1,...,n}→{1,...,n}isone-to-oneortwo-to-one,giventhatoneoftheseisthecase.WeshowalowerboundofΩn1/5onthenumberofqueriesneededbyaquantumcomputertosolvethisproblemwithboundederrorprobability.ThebestknownupperboundisOn1/3,butobtaininganylowerboundbetterthanΩ(1)wasanopenproblemsince1997.Ourproofusesthepolynomialmethodaugmentedbysomenewideas.WealsogivealowerboundofΩn1/7fortheproblemofdecidingwhethertwosetsareequalordisjointonaconstantfractionofelements.Finallywegiveimplicationsoftheseresultsforquantumcomplexitytheory.1IntroductionThepowerofquantumcomputinghasbeenintensivelystudiedforadecade[4,3,13,21,2,1,22].Apartfrompossibleapplications—suchasspeedingupcombinatorialsearch[13]andbreakingpublic-keycryptog-raphy[21]—amajormotivationforthisworkhasbeentobetterunderstandquantumtheoryitself.Thus,researchershavetriedtodiscovernotjustthecapabilitiesofquantumcomputingbutalsothelimitations.Thistaskisdifficult,though;proving(forexample)thatquantumcomputerscannotsolveNP-completeproblemsinpolynomialtimewouldimplyP6=NP.Apopularalternativeistostudyrestrictedmodelsofcomputation,andparticularlythequerymodel,inwhichonecountsonlythenumberofqueriestotheinput,notthenumberofcomputationalsteps.AnearlyresultofBennett,Bernstein,Brassard,andVazirani[3]showedthataquantumcomputerneedsΩ(√n)queriestosearchalistofnitemsforonemarkeditem.(Thisboundistight,asevidencedbyGrover’salgorithm[13].)Subsequently,Bealsetal.[2],Ambainis[1],andothersobtainedlowerboundsformanyotherproblems.Butoneproblem,thecollisionproblem,resistedattemptstoprovealowerbound[6,1].Becauseofitssimplicity,theproblemwaswidelyconsideredabenchmarkforourunderstandingofquantumquerycomplexity.Thecollisionproblemofsizen,orColn,isdefinedasfollows.LetX=x1...xnbeasequenceofnintegersdrawnfrom{1,...,n},withneven.Weareguaranteedthateither(1)Xisone-to-one(thatis,apermutationof{1,...,n}),or∗ComputerScienceDepartment,UniversityofCalifornia,Berkeley,CA94720-1776.Email:[e-mail]alScienceFoundationGraduateFellowshipandbytheInstituteforQuantumInformationattheCaliforniaInstituteofTechnology.1(2)Xistwo-to-one(thatis,eachelementof{1,...,n}appearsinXtwiceornotatall).Theproblemistodecidewhether(1)or(2)holds.WeshowthatQ2(Coln)=Ωn1/5
,whereQ2isbounded-errorquantumquerycomplexityasdefinedbyBealsetal.[2].DetailsoftheoraclemodelaregiveninSection3.Thebestknownupperbound,duetoBrassard,Høyer,andTapp[5],isOn1/3
;thus,ourboundisprobablynottight.Previously,though,nolowerboundbetterthanthetrivialΩ(1)boundwasknown.HowgreataspeedupquantumcomputersyieldfortheproblemwasapparentlyfirstaskedbyRains[18].Previouslowerboundtechniquesfailedfortheproblembecausetheydependedonafunction’sbeingsensitivetomanydisjointchangestotheinput.Forexample,Bealsetal.[2]showedthatforalltotalBooleanfunctionsf,Q2(f)=Ωpbs(f),wherebs(f)istheblocksensitivity,definedbyNisan[16]tobe,informally,themaximumnumberofdisjointchanges(toanyparticularinputX)towhichfissensitive.Inthecaseofthecollisionproblem,though,everyone-to-oneinputdiffersfromeverytwo-to-oneinputinatleastn/2places,sotheblocksensitivityisO(1).Ambainis’adversarymethod[1],ascurrentlyformulated,facesarelatedobstacle.Inthatmethodweconsiderthealgorithmandinputasabipartitequantumstate,andupper-boundhowmuchtheentanglementofthestatecanincreaseviaasinglequery.Yetunderthesimplestmeasuresofentanglement,thealgorithmandinputcanbecomehighlyentangledafterO(1)queries,againbecauseeveryone-to-oneinputisfarfromeverytwo-to-oneinput.Ourproofisanadaptationofthepolynomialmethod,introducedtoquantumcomputingbyBealsetal.[2].Theirideawastoreducequestionsaboutquantumalgorithmstoeasierquestionsaboutmultivariatepolynomials.Inparticular,ifaquantumalgorithmmakesTqueries,thenitsacceptanceprobabilityisapolynomialovertheinputbitsofdegreeatmost2T.Sobyshowingthatanypolynomialapproximatingthedesiredoutputhashighdegree,oneobtainsalowerboundonT.Tolower-boundthedegreeofamultivariatepolynomial,akeytechnicaltrickistoconstructarelatedunivariatepolynomial.Bealsetal.[2],usingalemmaduetoMinskyandPapert[15],replaceapolynomialp(X)(whereXisabitstring)byq(|X|)(where|X|denotestheHammingweightofX),satisfyingq(k)=EX|X|=kp(X)anddeg(q)≤deg(p).Weconstructtheunivariatepolynomialinadifferentway.Weconsiderauniformdistributionoverk-to-oneinputs,wherekmightbegreaterthan2.Eventhoughtheproblemistodistinguishk=1fromk=2,theacceptanceprobabilitymustliebetween0and1forallk,andthatisasurprisinglystrongconstraint.Weshowthattheacceptanceprobabilityisclosetoaunivariatepolynomialinkofdegreeatmost2T.WethenobtainalowerboundbygeneralizingaclassicalapproximationtheoryresultofEhlichandZeller[11]andRivlinandCheney[19].Muchoftheproofdealswiththecomplicationthatkdoesnotdivideningeneral.Shi[20]hasrecentlyimprovedourmethodtoobtainalowerboundofΩn1/4
forthecollisionproblem.Thepaperisorganizedasfollows.Section2motivatesthecollisionlowerboundwithinquantumcomputing,pointingoutconnecti