Polynomial degree vs. quantum query complexity

arXiv:quant-ph/0305028v423Nov2004Polynomialdegreevs.quantumquerycomplexityAndrisAmbainis∗AbstractThedegreeofapolynomialrepresenting(orapproximating)afunctionfisalowerboundforthequantumquerycomplexityoff.Thisobservationhasbeenasourceofmanylowerboundsonquantumalgorithms.Ithasbeenanopenproblemwhetherthislowerboundistight.WeexhibitafunctionwithpolynomialdegreeMandquantumquerycomplexityΩ(M1.321...).Thisisthefirstsuperlinearseparationbetweenpolynomialdegreeandquantumquerycomplexity.Thelowerboundisshownbyageneralizedversionofthequantumadversarymethod.1IntroductionQuantumcomputingprovidesspeedupsforfactoring[29],search[15]andmanyrelatedproblems.Thesespeedupscanbequitesurprising.Forexample,Grover’ssearchalgorithm[15]solvesanarbitraryexhaustivesearchproblemwithNpossi-bilitiesintimeO(√N).Classically,itisobviousthattimeΩ(N)wouldbeneeded.Thismakeslowerboundsparticularlyimportantinthequantumworld.IfwecansearchintimeO(√N),whycanwenotsearchintimeO(logcN)?(Amongotherthings,thatwouldhavemeantNP⊆BQP.)LowerboundofBennettetal.[10]showsthatthisisnotpossibleandGrover’salgorithmisexactlyoptimal.Currently,wehavegoodlowerboundsonthequantumcomplexityofmanyproblems.Theymainlyfollowbytwomethods1:thehybrid/adversarymethod[10,4]andthepolynomialsmethod[9].Thepolynomialsmethodisusefulforprovinglowerboundsbothinclassical[23]andquantumcomplexity[9].Itisknownthat∗DepartmentofCombinatoricsandOptimizationandInstituteforQuantumComputing,UniversityofWaterloo,200UniversityAvenueWest,Waterloo,ONN2L2T2,Canada,e-mail:[e-mail]fMathematicsandComputerScience,UniversityofLatvia,Rainabulv.19,R¯ıga,LV-1459,Latvia,supportedinpartbyLatviaScienceCouncilGrant01.03541Otherapproaches,suchasreducingquerycomplexitytocommunicationcomplexity[11]areknown,buthavebeenlesssuccessful.1.thenumberofqueriesQE(f)neededtocomputeaBooleanfunctionfbyanexactquantumalgorithmexactlyisatleastdeg(f)2,wheredeg(f)isthedegreeofthemultilinearpolynomialrepresentingf,2.thenumberofqueriesQ2(f)neededtocomputefbyaquantumalgorithmwithtwo-sidederrorisatleastgdeg(f)2,wheregdeg(f)isthesmallestdegreeofamultilinearpolynomialapproximatingf.Thisreducesprovinglowerboundsonquantumalgorithmstoprovinglowerboundsondegreeofpolynomials.Thisisawell-studiedmathematicalproblemwithmeth-odsfromapproximationtheory[14]available.QuantumlowerboundsshownbypolynomialsmethodincludeaQ2(f)=Ω(6pD(f))relationforanytotalBooleanfunctionf[9],lowerboundsonfindingmeanandmedian[22],collisionsandele-mentdistinctness[2,18].PolynomialsmethodisalsoakeypartofrecentΩ(√N)lowerboundonsetdisjointnesswhichresolvedalongstandingopenprobleminquantumcommunicationcomplexity[25].Giventheusefulnessofpolynomialsmethod,itisanimportantquestionhowtightisthepolynomialslowerbound.[9,13]provedthat,foralltotalBooleanfunctions,Q2(f)=O(deg6(f))andQE(f)=O(deg4(f)).ThesecondresultwasrecentlyimprovedtoQE(f)=O(deg3(f))[21].Thus,theboundistightuptopolynomialfactor.EvenstrongerresultwouldbeQE(f)=O(deg(f))orQ2(f)=O(gdeg(f)).Then,determiningthequantumcomplexitywouldbeequivalenttodeterminingthedegreeofafunctionasapolynomial.Ithasbeenanopenproblemtoproveordisproveeitherofthesetwoequalities[9,13].Inthispaper,weshowthefirstprovablegapbetweenpolynomialdegreeandquantumcomplexity:deg(f)=2dandQ2(f)=Ω(2.5d).Sincedeg(f)≥gdeg(f)andQE(f)≥Q2(f),thisimpliesaseparationbothbetweenQE(f)anddeg(f)andbetweenQ2(f)andgdeg(f).Toprovethelowerbound,weusethequantumadversarymethodof[4].Thequantumadversarymethodrunsaquantumalgorithmondifferentinputsfromsomeset.Ifeveryinputinthissetcanbechangedinmanydifferentwayssothatthevalueofthefunctionchanges,manyqueriesareneeded.ThepreviouslyknownversionofquantumadversarymethodgivesaweakerlowerboundofQ2(f)=Ω(2.1213...d).Whilethisalreadygivessomegapbe-tweenpolynomialdegreeandquantumcomplexity,wecanachievealargergapbyusinganew,moregeneralversionofthemethod.Thenewcomponentisthatwecarryoutthisargumentinaverygeneralway.Weassignindividualweightstoeverypairofinputsanddistributeeachweight2amongthetwoinputsinanarbitraryway.Thisallowsustoobtainbetterboundsthanwiththepreviousversionsofthequantumadversarymethod.Weapplythenewlowerboundtheoremtothreefunctionsforwhichdetermin-isticquerycomplexityissignificantlyhigherthanpolynomialdegree.Theresultisthat,forallofthosefunctions,quantumquerycomplexityishigherthanpolyno-mialdegree.Thebiggestgapispolynomialdegree2d=MandquerycomplexityΩ(2.5d)=Ω(M1.321...).SpalekandSzegedy[32]haverecentlyshownthatourmethodisequivalenttotwoothermethods,thespectralmethodof[8]thatwasknownpriortoourworkandtheKolmogorovcomplexitymethodof[19]thatappearedaftertheconferenceversionofourpaperwaspublished.Althoughallthreemethodsareequivalent,theyhavedifferentintuition.Itappearstousthatourmethodistheeasiesttouseforresultsinthispaper.2Preliminaries2.1QuantumqueryalgorithmsLet[N]denote{1,...,N}.WeconsidercomputingaBooleanfunctionf(x1,...,xN):{0,1}N→{0,1}inthequantumquerymodel(forasurveyonquerymodel,see[6,13]).Inthismodel,theinputbitscanbeaccessedbyqueriestoanoracleXandtheco