A quantum time-space lower bound for the counting

arXiv:0712.2545v1[quant-ph]15Dec2007AQuantumTime-SpaceLowerBoundfortheCountingHierarchy∗DietervanMelkebeekThomasWatsonUniversityofWisconsin-MadisonDecember16,2007AbstractWeobtainthefirstnontrivialtime-spacelowerboundforquantumalgorithmssolvingprob-lemsrelatedtosatisfiability.OurboundappliestoMajSATandMajMajSAT,whicharecom-pleteproblemsforthefirstandsecondlevelsofthecountinghierarchy,respectively.Weprovethatforeveryrealdandeverypositiverealǫthereexistsarealc1suchthateither:•MajMajSATdoesnothaveaquantumalgorithmwithboundedtwo-sidederrorthatrunsintimenc,or•MajSATdoesnothaveaquantumalgorithmwithboundedtwo-sidederrorthatrunsintimendandspacen1−ǫ.Inparticular,MajMajSATcannotbesolvedbyaquantumalgorithmwithboundedtwo-sidederrorrunningintimen1+o(1)andspacen1−ǫforanyǫ0.Thekeytechnicalnoveltyisatime-andspace-efficientsimulationofquantumcomputationswithintermediatemeasurementsbyprobabilisticmachineswithunboundederror.Wealsodevelopamodelthatisparticularlysuitableforthestudyofgeneralquantumcomputationswithsimultaneoustimeandspacebounds.However,ourargumentsholdforanyreasonableuniformmodelofquantumcomputation.1IntroductionSatisfiability,theproblemofdecidingwhetheragivenBooleanformulahasatleastonesatisfyingassignment,hastremendouspracticalandtheoreticalimportance.ItemergedasacentralproblemincomplexitytheorywiththeadventofNP-completenessinthe1970’s.Provinglowerboundsonthecomplexityofsatisfiabilityremainsamajoropenproblem.Complexitytheoristsconjecturethatsatisfiabilityrequiresexponentialtimeandlinearspacetosolveintheworstcase.Despitedecadesofeffort,thebestsingle-resourcelowerboundsforsatisfiabilityongeneral-purposemodelsofcomputationarestillthetrivialones–linearfortimeandlogarithmicforspace.However,sincethelate1990’swehaveseenanumberofresultsthatruleoutcertainnontrivialcombinationsoftimeandspacecomplexity.Onelineofresearch[6,7,19,5,20],initiatedbyFortnow,focusesonprovingstrongerandstrongertimelowerboundsfordeterministicalgorithmsthatsolvesatisfiabilityinsmallspace.Forsubpolynomial(i.e.,no(1))spacebounds,thecurrentrecordstatesthatnosuchalgorithmcanrunintimencforanyc2cos(π/7)≈1.8019.Asecondresearchdirectionaimstostrengthenthelower∗ResearchpartiallysupportedbyNSFawardsCCR-0133693andCCF-0523680.1boundsbyconsideringmorepowerfulmodelsofcomputationthanthestandarddeterministicone.DiehlandVanMelkebeek[5]initiatedthestudyoflowerboundsforproblemsrelatedtosatisfiabilityonrandomizedmodelswithboundederror.Theyshowedthatforeveryintegerℓ≥2,ΣℓSATcannotbesolvedintimencbysubpolynomial-spacerandomizedalgorithmswithboundedtwo-sidederrorforanycℓ,whereΣℓSATdenotestheproblemofdecidingthevalidityofagivenfullyquantifiedBooleanformulawithℓalternatingblocksofquantifiersbeginningwithanexistentialquantifier.ΣℓSATrepresentstheanalogueofsatisfiabilityfortheℓthlevelofthepolynomial-timehierarchy;Σ1SATcorrespondstosatisfiability.Provingnontrivialtime-spacelowerboundsforsatisfiabilityonrandomizedalgorithmswithboundedtwo-sidederrorremainsopen.Allenderetal.[2]consideredtheevenmorepowerful(butphysicallyunrealistic)modelofprobabilisticalgorithmswithunboundederror1.TheysettledforproblemsthatareevenharderthanΣℓSATforanyfixedℓ,namelyMajSATandMajMajSAT,theequivalentsofsatisfiabilityandΣ2SATinthecountinghierarchy.MajSATistheproblemofdecidingwhetheragivenBooleanformulaissatisfiedforatleasthalfoftheassignmentstoitsvariables.MajMajSATistheproblemofdecidingwhetheragivenBooleanformulaϕondisjointvariablesetsxandyhasthepropertythatforatleasthalfoftheassignmentstox,ϕissatisfiedforatleasthalfoftheassignmentstoy.RecallthatToda[16]provedthatthepolynomial-timehierarchyreducestotheclassPP,whichrepresentspolynomial-timeprobabilisticcomputationswithunboundedtwo-sidederrorandformsthefirstlevelofthecountinghierarchy.Apartfromdealingwithharderproblems,thequantitativestrengthofthelowerboundsbyAllenderetal.isalsosomewhatweaker.Inparticular,theyshowedthatnoprobabilisticalgorithmcansolveMajMajSATintimen1+o(1)andspacen1−ǫforanypositiveconstantǫ.Wereferto[13]foradetailedsurveyofthepastworkontime-spacelowerboundsforsatisfiabilityandrelatedproblems,includingapresentationoftheAllenderetal.lowerboundthatisslightlydifferentfromtheoriginalone.Inthispaperwestudythemostpowerfulmodelthatisconsideredphysicallyrealistic,namelyquantumalgorithmswithboundederror.Weobtainthefirstnontrivialtime-spacelowerboundforquantumalgorithmssolvingproblemsrelatedtosatisfiability.Intheboundedtwo-sidederrorrandomizedsetting,thereasonwecangetlowerboundsforΣℓSATforℓ≥2butnotforℓ=1relatestothefactthatweknowefficientsimulationsofsuchrandomizedcomputationsinthesecondlevelofthepolynomial-timehierarchybutnotinthefirstlevel.Inthequantumsettingthesituationisworse:weknowofnoefficientsimulationsinanylevelofthepolynomial-timehierarchy.ThebestsimulationstodateareduetoAdlemanetal.[1],whoshowedthatpolynomial-timequantumcomputationswithboundedtwo-sidederrorcanbesimulatedinPP.Buildingonthisconnection,webringthelowerboundsofAllenderetal.tobearonbounded-errorquantumalgorithms.OurmainresultshowsthateitheratimelowerboundholdsforquantumalgorithmssolvingMajMajSAToratime-spac