A Hypercontractive Inequality for Matrix-Valued Fu

arXiv:0705.3806v2[quant-ph]14Aug2008AHypercontractiveInequalityforMatrix-ValuedFunctionswithApplicationstoQuantumComputingandLDCsAvrahamBen-Aroya∗OdedRegev†RonalddeWolf‡AbstractTheBonami-BecknerhypercontractiveinequalityisapowerfultoolinFourieranalysisofreal-valuedfunctionsontheBooleancube.Inthispaperwepresentaversionofthisinequalityformatrix-valuedfunctionsontheBooleancube.ItsproofisbasedonapowerfulinequalitybyBall,Carlen,andLieb.Wealsopresentanumberofapplications.First,weanalyzemapsthatencodenclassicalbitsintomqubits,insuchawaythateachsetofkbitscanberecoveredwithsomeprobabilitybyanappropriatemeasure-mentonthequantumencoding;weshowthatifm0.7n,thenthesuccessprobabilityisexponentiallysmallink.ThisresultmaybeviewedasadirectproductversionofNayak’squantumrandomaccesscodebound.Itinturnimpliesstrongdirectproducttheoremsfortheone-wayquantumcommunicationcomplexityofDisjointnessandotherproblems.Second,weprovethaterror-correctingcodesthatarelocallydecodablewith2queriesrequirelengthexponentialinthelengthoftheencodedstring.Thisgiveswhatisarguablythefirst“non-quantum”proofofaresultoriginallyderivedbyKerenidisanddeWolfusingquantuminformationtheory,andanswersaquestionbyTrevisan.∗SchoolofComputerScience,Tel-AvivUniversity,Tel-Aviv69978,Israel.SupportedbytheAdamsFellowshipProgramoftheIsraelAcademyofSciencesandHumanities,bytheIsraelScienceFoundation,andbytheEuropeanCommissionundertheIntegratedProjectQAPfundedbytheISTdirectorateasContractNumber015848.†SchoolofComputerScience,Tel-AvivUniversity,Tel-Aviv69978,Israel.SupportedbytheBinationalScienceFoundation,bytheIsraelScienceFoundation,andbytheEuropeanCommissionundertheIntegratedProjectQAPfundedbytheISTdirectorateasContractNumber015848.‡CentrumvoorWiskundeenInformatica(CWI),Amsterdam,TheNetherlands.SupportedbyaVenigrantfromtheNetherlandsOrganizationforScientificResearch(NWO)andalsopartiallysupportedbytheEuropeanCommissionundertheIntegratedProjectQAPfundedbytheISTdirectorateasContractNumber015848.1Introduction1.1Ahypercontractiveinequalityformatrix-valuedfunctionsFourieranalysisofreal-valuedfunctionsontheBooleancubehasbeenwidelyusedinthetheoryofcomput-ing.ApplicationsincludeanalyzingtheinfluenceofvariablesonBooleanfunctions[30],probabilistically-checkableproofsandassociatedhardnessofapproximation[23],analysisofthresholdphenomena[31],noisestability[43,48],votingschemes[50],learningundertheuniformdistribution[41,42,27,44],com-municationcomplexity[51,34,18],etc.OneofthemaintechnicaltoolsinthisareaisahypercontractiveinequalitythatissometimescalledtheBonami-Becknerinequality[10,6],thoughitshistorywouldalsojustifyothernames(seeLecture16of[49]forsomebackgroundandhistory).Forafixedρ∈[0,1],considerthelinearoperatorTρonthespaceofallfunctionsf:{0,1}n→Rdefinedby(Tρ(f))(x)=Ey[f(y)],wheretheexpectationistakenoveryobtainedfromxbynegatingeachbitindependentlywithprobability(1−ρ)/2.Inotherwords,thevalueofTρ(f)atapointxisobtainedbyaveragingthevaluesoffoveracertainneighborhoodofx.OneimportantpropertyofTρforρ1isthatithasa“smoothing”effect:any“highpeaks”presentinfaresmoothedoutinTρ(f).Thehypercontractiveinequalityformalizesthisintuition.Tostateitprecisely,definethep-normofafunctionfbykfkp=(12nPx|f(x)|p)1/p.Itisnotdifficulttoprovethatthenormisnondecreasingwithp.Also,thehigherpis,themoresensitivethenormbecomestopeaksinthefunctionf.Thehypercontractiveinequalitysaysthatforcertainqp,theq-normofTρ(f)isupperboundedbythep-normoff.ThisexactlycapturestheintuitionthatTρ(f)isasmoothedversionoff:eventhoughweareconsideringahighernorm,thenormdoesnotincrease.Moreprecisely,thehypercontractiveinequalitysaysthataslongas1≤p≤qandρ≤p(p−1)/(q−1),wehavekTρ(f)kq≤kfkp.(1)Themostinterestingcaseforusiswhenq=2,sinceinthiscaseonecanviewtheinequalityasastatementabouttheFouriercoefficientsoff,aswedescribenext.LetusfirstrecallsomebasicdefinitionsfromFourieranalysis.ForeveryS⊆[n](whichbysomeabuseofnotationwewillalsoviewasann-bitstring)andx∈{0,1}n,defineχS(x)=(−1)x·StobetheparityofthebitsofxindexedbyS.TheFouriertransformofafunctionf:{0,1}n→Risthefunctionbf:{0,1}n→Rdefinedbybf(S)=12nXx∈{0,1}nf(x)χS(x).Thevaluesbf(S)arecalledtheFouriercoefficientsoff.Thecoefficientbf(S)maybeviewedasmeasuringthecorrelationbetweenfandtheparityfunctionχS.SincethefunctionsχSformanorthonormalbasisofthespaceofallfunctionsfrom{0,1}ntoR,wecanexpressfintermsofitsFouriercoefficientsasf=XS⊆[n]bf(S)χS.(2)UsingthesamereasoningweobtainParseval’sidentity,kfk2=XS⊆[n]bf(S)21/2.1TheoperatorTρhasaparticularlyelegantdescriptionintermsoftheFouriercoefficients.Namely,itsimplymultiplieseachFouriercoefficientbf(S)byafactorofρ|S|:Tρ(f)=XS⊆[n]ρ|S|bf(S)χS.Thehigher|S|is,thestrongertheFouriercoefficientbf(S)is“attenuated”byTρ.UsingParseval’sidentity,wecannowwritethehypercontractiveinequality(1)forthecaseq=2asfollows.Foreveryp∈[1,2],XS⊆[n](p−1)|S|bf(S)2!1/2≤12nXx∈{0,1}n|f(x)|p!1/p.(3)ThisgivesanupperboundonaweightedsumofthesquaredFouriercoefficientsoff,whereeachcoefficientisattenuatedbyafactor(p−1)|S|.Weareinterestedingeneralizingthishypercontractiveinequalitytomatrix-valuedfunctions.LetMbethes