Lower Bounds on Quantum Query Complexity

arXiv:quant-ph/0509153v121Sep2005LowerBoundsonQuantumQueryComplexityPeterHøyer∗[e-mail]ˇSpalek†[e-mail]2005AbstractShor’sandGrover’sfamousquantumalgorithmsforfactoringandsearchingshowthatquantumcomputerscansolvecertaincomputationalproblemssignificantlyfasterthananyclassicalcomputer.Wediscussherewhatquantumcomputerscannotdo,andspecificallyhowtoprovelimitsontheircomputationalpower.Wecoverthemainknowntechniquesforprovinglowerbounds,andexemplifyandcomparethemethods.1IntroductionTheveryfirstissueoftheJournaloftheACMwaspublishedinJanuary1954.Itwasthefirstjournaldevotedtocomputerscience.Forits50thanniversaryvolume,publishedinJanuary2003,editors-in-chiefJosephY.HalpernaskedwinnersoftheTuringAwardandtheNevanlinnaPrizetodiscussuptothreeproblemsthattheythoughtwouldbemajorproblemsforcomputerscienceinthenext50years.NevanlinnaPrizewinnerLeslieG.Valiant[Val03]describesthreeproblems,thefirstofwhichisonphysicallyrealizablemodelsforcomputationandformalizesthesettingbydefining:“WethereforecallourclassPhP,theclassofphysicallyconstructiblepolynomialresourcecomputers.”Hethenformulatestheproblemby:“[t]ophraseasinglequestion,thefullcharacterizationofPhP,”andarguesthat“thissinglequestionappearsatthistimetobescientifi-callythemostfundamentalincomputerscience.”OnJanuary26,thisyear,NobelLaureateDavidGrossgaveaCERNColloquiumpresenta-tionon“Thefutureofphysics”[Gro05].Hediscusses“25questionsthatmightguidephysics,inthebroadestsense,overthenext25years,”andincludesasquestions15and16“Complexity”and“QuantumComputing.”InJuly,thisyear,theSciencemagazinecelebratedits125thanniversaryby“explor[ing]125bigquestionsthatfacescientificenquiryoverthenextquarter-century”[Sei05].∗DepartmentofComputerScience,UniversityofCalgary.SupportedbyCanada’sNaturalSciencesandEngi-neeringResearchCouncil(NSERC),theCanadianInstituteforAdvancedResearch(CIAR),andTheMathematicsofInformationTechnologyandComplexSystems(MITACS).†CWIandUniversityofAmsterdam.SupportedinpartbytheEUfifthframeworkprojectRESQ,IST-2001-37559.WorkconductedinpartwhilevisitingtheUniversityofCalgary.1Amongthetop25,isthequestionof“Whatarethelimitsofconventionalcomputing?”CharlesSeifewrites:“[T]hereisarealmbeyondtheclassicalcomputer:thequantum,”andhediscussestheissueofdetermining“whatquantum-mechanicalpropertiesmakequantumcomputerssopow-erful.”InthisissueoftheBulletinoftheEATCS,wewouldliketoofferanintroductiontothetopicofstudyinglimitationsonthepowerofquantumcomputers.Canquantumcomputersreallybemorepowerfulthantraditionalcomputers?Whatcanquantumcomputersnotdo?Whatprooftechniquesareusedforprovingboundsonthecomputationalpowerofquantumcomputers?Itisahighlyactiveareaofresearchandflourishingwithprofoundandbeautifultheorems.Thoughdeep,itisfortunatelyalsoanaccessiblearea,basedonbasicprinciplesandsimpleconcepts,andonethatdoesnotrequirespecializedpriorknowledge.Oneaimofthispaperistoshowthisbyprovidingafairlycompleteintroductiontothetwomostsuccessfulmethodsforprovinglowerboundsonquantumcomputations,theadversarymethodandthepolynomialmethod.Oursurveyisbiasedtowardstheadversarymethodsinceitislikelytheleastfamiliarmethodandityieldsverystronglowerbounds.ThispaperismeanttobesupplementedbytheexcellentsurveyofBuhrmananddeWolf[BW02]ondecisiontreecomplexities,publishedin2002inthejournalTheoreticalComputerScience.Wedemonstratethemethodsonarunningexample,andforthis,weuseoneofthemostbasicalgorithmicquestionsonemaythinkof:thatofsearchinganorderedset.CanoneimplementorderedsearchingsignificantlyfasteronaquantumcomputerthanapplyingastandardΘ(logN)binarysearchalgorithm?Therestofthepaperisorganizedasfollows.Wemotivateanddefineourmodelsofcompu-tationinthenextsection.WethendiscussverybasicprinciplesusedinprovingquantumlowerboundsinSection3andusethemtoestablishourfirstlower-boundmethod,theadversarymethod,inSection4.WediscusshowtoapplythemethodinSection5,anditslimitationsinSection6.Wethengiveanintroductiontothesecondmethod,thepolynomialmethod,inSection7.WecomparethetwomethodsinSection8andgiveafewfinalremarksinSection9.Wehaveaimedatlimitingpriorknowledgeonquantumcomputingtoabareminimum.Sen-tencesandparagraphswithketsandbras(|thisisaketiandhthisisabra|)caneithersafelybeskipped,orsubstitutedwithcolumn-vectorsandrow-vectors,respectively.2QuantumquerycomplexityManyquantumalgorithmsaredevelopedfortheso-calledoraclemodelinwhichtheinputisgivenasanoraclesothattheonlyknowledgewecangainabouttheinputisinaskingqueriestotheoracle.Theinputisafinitebitstringx∈{0,1}NofsomelengthN,wherex=x1x2...xN.ThegoalistocomputesomefunctionF:{0,1}N→{0,1}moftheinputx.Someofthefunctionsweconsiderareboolean,somenot.Weusetheshorthandnotation[N]={1,2,...,N}.Asourmeasureofcomplexity,weusethequerycomplexity.ThequerycomplexityofanalgorithmAcomputingafunctionFisthenumberofqueriesusedbyA.ThequerycomplexityofFistheminimumquerycomplexityofanyalgorithmcomputingF.Weareinterestedinprovinglowerboundsonthequerycomplexityofspecificfunctionsandconsidermethodsforcomputing2suchlowerbounds.Analternativemeasureofcomplexitywouldbetousethetimecomplexitywhichcountsthenumberofbasi