AC0 The Quantum Query Complexity of PaulBeame∗ Widad Machmouchi∗ ComputerScienceandEngineering ComputerScienceandEngineering UniversityofWashington UniversityofWashington Seattle,WA98195-2350 Seattle,WA98195-2350 2 [email protected] [email protected] 1 0 2 February 1,2012 n a J 1 3 Abstract ] Weshowthatanyquantumalgorithmdecidingwhetheraninputfunctionf from[n]to[n]is2-to-1 C or almost2-to-1requiresΘ(n) queriesto f. The same lowerboundholdsfordeterminingwhetheror C notafunctionf from[2n 2]to[n]issurjective. TheseresultsyieldanearlylinearΩ(n/logn)lower . bound on the quantum qu−ery complexityof AC0. The best previouslower boundknown for any AC0 s c function was the Ω((n/logn)2/3) bound given by Aaronson and Shi’s Ω(n2/3) lower bound for the [ elementdistinctnessproblem[1]. 2 v 2 2 4 2 . 8 0 0 1 : v i X r a ∗ResearchsupportedbyNSFgrantCCF-0830626 1 1 Introduction We study the quantum query complexity of Boolean functions that are computable with constant-depth polynomial-size circuits. Thequantumquerycomplexityofafunctionisthemaximumnumberofqueriesa quantumalgorithmneedstomaketoitsinputinordertoevaluatethefunction(eitherwithcertainty, orwith probability bounded away from 1/2 as we consider here). Both Boolean queries and n-ary queries can be naturaldepending onthecontext. StartingwithGrover’sO(√n)quantumqueryalgorithmforcomputingtheORofnbits,andcontinuing through recent work on read-once formula evaluation [12, 7, 16, 6], quantum query algorithms have been showntoprovidepolynomialspeed-upsoverclassicalqueryalgorithmsforcomputingmanytotalfunctions. Atthesametime,threemaintechniqueshavebeendevelopedtoderivelowerboundsonquantumquery complexity. ThefirsttwoarethepolynomialmethodofBealsetal.[8]andtheadversarymethodintroduced byAmbainis[2,19]. Thepolynomial methodusesthefactthattheprobability ofaquantum algorithm suc- ceedingisanapproximating polynomialforthefunctionthatitiscomputing. Ontheotherhand,Ambainis’ adversary method is based on tracking the state of the quantum algorithm on “difficult” inputs. In a recent body of work [13, 17, 18, 15], the adversary method was extended to characterize the query complexity of Boolean functions and of functions defined on large alphabets. This can formulated as a version of the adversarymethodthatincludesnegativeweights[13](positiveweightsdonothelp),asacertainmeasureon span programs computing the function [17], oras the optimum of asemi-definite program maximizing the spectral normofthevarious adversary matrices ofthefunction [18,15]. Anadversary matrixofafunction isarealsymmetricmatrixindexedbypairsofinputssuchthatifthefunctionevaluatestothesamevalueon apairofinputs, thenthecorresponding entryintheadversary matrixissetto0. Ourproofusestheoriginal adversary method[2]anddoesnotrequirethemachinery developedinthesubsequent work. The methods above have been used to show that some fairly simple functions do not benefit from sig- nificant improvement in query complexity using quantum queries. For example, since the parity of n bits requires degree Ω(n) to be approximated by a multivariate polynomial its quantum query complexity also mustbe linear. However, parity isstill asomewhat complex function since itcannot even beapproximated inAC0,theclassofdecision problems solvable byBoolean circuits withunbounded fan-in, constant depth, and polynomial size. Can the simple functions in AC0 always be computed using O(nβ) queries for some β < 1? Weshowthatthisisnotthecase. Thequantum querycomplexity ofanumberofproblems inAC0 hasbeenthoroughly investigated. The firstquantumquerylowerboundsin[9,8]showedthatGrover’salgorithm fortheORisasymptotically op- timal. In[2],AmbainisusedtheadversarymethodtoproveanΩ(√n)lowerboundonthequerycomplexity of an AND of ORs. Motivated in part by questions of the security of classical cryptographic constructions with respect to quantum adversaries, the collision problem of determining whether a function is 1-to-1 or 2-to-1onitsdomainhasbeenoneofthemostcelebratedexamplesinquantumquerycomplexity. Aaronson and Shi [1] proved an Ω(n1/3) lower bound on the query complexity of the collision problem with range 3n/2,whichyieldsanΩ(n2/3)lowerboundontheelementdistinctness problemwithrangeΘ(n2). Theel- ementdistinctness problem isequivalent tothegeneralcaseoftestingwhetherafunction is1-to-1(without the promise of being 2-to-1 in case that it is not 1-to-1). For the r-to-1 versus 1-to-1 problem, for integer r 2, Aaronson and Shi also proved a lower bound of Ω((n/r)1/3) when the range size is 3n/2. All of the≥seproblemscanbecomputedinAC0 andthesequerycomplexities areasymptotically optimalbyresults of Brassard et al. [10] and Ambainis [5]. Ambainis also was able to reduce the range size requirement for bothlowerbounds[3],aswasKutin[14]forthecollision problem, independently, bydifferent means. 2 The original adversary method has also been used to prove lower bounds for related search problems. In[11],theauthorsgiveanΩ(n)lowerboundforthequerycomplexitiesofavarietyofproblemswherethe goal is to produce a non-Boolean output, for example the index of some non-colliding input assuming that oneexists. In the original collision problem, the main question was whether or not the input function is 1-to-1, whereatmostO(n1/3)queriessufficeforthepromiseversionsoftheproblemandatmostO(n2/3)queries sufficeeveninthegeneralcase. Weshowthatifoneisconcernedwithwhetherornotafunctionisprecisely 2-to-1, the number of queries required is substantially larger. More precisely, we show an asymptotically tightlinearlowerboundfordeterminingwhetherornotafunctioniseitherprecisely2-to-1oralmost2-to-1 in that the function is 2-to-1 except for exactly two inputs that are mapped 1-to-1. This also implies an Ω(n/logn) lower bound on the Boolean quantum query complexity of AC0, thus substantially improving thepreviousbestlowerboundofΩ((n/logn)2/3)givenbytheresultsofAaronsonandShi. Usingtheoriginaladversary methoddevelopedbyAmbainis[2]weprovethefollowingtheorem: Theorem1. Letnbeapositiveeveninteger, bethesetoffunctionsf from[n]to[n]thatareeither2-to-1 F or almost 2-to-1 and φ : 0,1 be aBoolean function on such that φ(f) = 1iff f is2-to-1. Then F → { } F anyquantum algorithm deciding φrequiresΩ(n)queries. Notingthatdeterminingwhetherornotafunctionfrom[2n 2]to[n]issurjectivehasasaspecialcase − theproblemofdeterminingwhetherafunctionisa2-to-1oralmost2-to-1function,weobtainthefollowing lowerbound. Corollary 2. Letnbeapositive even integer and bethesetoffunctions from [2n 2]to[n]. Definethe G − function ONTO : 0,1 by ONTO(f) = 1 if and only if f is surjective. Then any quantum algorithm G → { } computing ONTO withprobability atleast2/3requiresΩ(n)queries. Since each value f(i) can be encoded using log n bits, the entire input is nlog n bits long. It iseasy 2 2 toseethatdeterminingwhethersuchafunctiongivenbythesebitsis2-to-1ornotisasimpleAC0 problem. Sinceeachqueryofoneofthebitsoff(i)isweakerthanqueryingalloff(i),weimmediatelyobtainlower boundsonthequerycomplexityofAC0. Corollary 3. Thequantum querycomplexity ofAC0 isΩ(n/logn). 2 Lower bounds on quantum query complexity Let n be a positive even integer and f : [n] [n′] for n′ > n/2 be a function. We say that f is 2-to-1 if → every point intheimage either hasexactly twopre-images orhasnopre-images in[n]. Wesayf isalmost 2-to-1iff is2-to-1onn 2pointsinthedomainand1-to-1ontheremaining2points,andeverypointhas − atmosttwopre-images. Weconsiderthefollowingproblem: 2-TO-1-VS-ALMOST-2-TO-1 Problem: Given a positive even integer n, integer n′ n/2+ 1, and a ≥ function f : [n] [n′]thatiseither2-to-1oralmost2-to-1, determinewhetherf is2-to-1. → The function f : [n] [n′] is given to us as a quantum oracle query which we can assume without → loss of generality is accessed using a special register i with answer register j. The oracle replaces a basis state i,j,Ψ by i,(f(i)+j) mod n′,Ψ . The quantum query complexity of f is the minimum number | i | i 3 of queries needed by the quantum algorithm to correctly determine withprobability atleast 2/3 whether f is2-to-1oralmost2-to-1. We will use the adversary method as developed by Ambainis to derive lower bounds on the quantum querycomplexityofBooleanfunctions. Theorem4(Ambainis[2]). Let bethesetoffunctionsf from[n]to[n′]andφ: 0,1 beaBoolean F F → { } function. Let A and B be two subsets of such that φ(f) = φ(g) if f A and g B. If there exists a F 6 ∈ ∈ relationR A B suchthat: ⊂ × 1. Foreveryf A,thereexistatleastmdifferent functions g B suchthat(f,g) R. ∈ ∈ ∈ 2. Foreveryg B,thereexistatleastm′ different functions f Asuchthat(f,g) R. ∈ ∈ ∈ 3. Foreveryx [n]andf A,thereexistatmostldifferent functions g B suchthat(f,g) Rand ∈ ∈ ∈ ∈ f(x)= g(x). 6 4. Foreveryx [n]andg B,thereexistatmostl′ differentfunctions f Asuchthat(f,g) Rand ∈ ∈ ∈ ∈ f(x)= g(x). 6 Thenanyquantumalgorithm computingφwithprobability atleast2/3requiresΩ mm′ queries. (cid:18)q ll′ (cid:19) Let bethesetoffunctionsfrom[n]to[n′]thatareeither2-to-1oralmost2-to-1andletφ: 0,1 F F → { } beaBoolean function such that φ(f) = 1ifandonly iff is2-to-1. Weprove, using theadversary method [2],thatthequantum querycomplexityofφisΩ(n). 2.1 Quantum query lowerbounds forthe 2-TO-1-VS-ALMOST-2-TO-1 and ONTO functions Theorem5. Letnbeapositive eveninteger, n′ n/2+1,and bethesetoffunctions f from[n]to[n′] ≥ F that areeither 2-to-1 oralmost 2-to-1. Letφ : 0,1 beaBoolean function suchthat φ(f) = 1iff f F → { } is2-to-1. Thenanyquantum algorithm computing φwithprobability atleast2/3requiresΩ(n)queries. Proof. Weusetheadversary method. LetAbethesetoffunctions in thatare2-to-1 andB bethesetof F functions thatarealmost2-to-1. Obviously, φ(A) = 1andφ(B) = 0. Wedenote thedistance between two functions f andg by d(f,g) = i [n]f(i) = g(i),f,g . |{ ∈ | 6 ∈ F}| For a function g B, we denote the two input points in [n] that g maps injectively by s(g) = s ,s 1 2 ∈ { } where s < s . That is, g(s ) = g(s ) and g(i) g(s ),g(s ) for all i / s(g). Consider the following 1 2 1 2 1 2 6 6∈ { } ∈ relationR A B: ⊆ × R = (f,g),f A,g B,d(f,g) = 2,f(s )= g(s )andf(s ) = g(s ) . 1 1 2 2 { ∈ ∈ } Inotherwords,therelationconsistsofpairsoffunctions inA B thatdifferonexactly2points, neitherof × whichisoneoftheinjectivelymappedpointsofthefunction inB. Claim 6. If (f,g) R and x,y / s(g) = s ,s where x = y are the points where f and g differ then 1 2 ∈ ∈ { } 6 f(x),f(y) = g(s ),g(s ) andg(x) = g(y). 1 2 { } { } 4 Since f(s ) = g(s ) = g(s ) = f(s ), and g(i) / g(s ),g(s ) for every i / s(g), we must have 1 1 2 2 1 2 6 ∈ { } ∈ f(x),f(y) = g(s ),g(s ) , otherwise f will not pair any input with s or s and hence not be 2-to-1. 1 2 1 2 { } { } Since x,y / s(g), it must be that x and y are paired inputs of g. However, since f is 2-to-1 and pairs up ∈ thefour points x,y,s ,s allother points mustbepaired witheach other byboth f andg since g agrees 1 2 { } withf ontheseotherpoints. Hencetheonlypointstowhichxandy canbepairedbyg areeachother, and therefore g(x) = g(y). Theclaimfollows. Wenowcheckthefourproperties ofR: 1. Letf bea2-to-1functioninA. Chooseanytwopointsx,y [n]suchthatf(x)= f(y). Foreachof ∈ 6 then′ n/2pointsz [n′]notintheimageoff wecandefineanalmost2-to-1functiong B such − ∈ ∈ that(f,g) Rbyhaving g agreewithf onallbutinputs x,y andsettingg(x) = g(y) = z. There ∈ { } are n(n 2)/2 choices of the pair of x and y and n′ n/2 choices of z, each of which produces a − − distinct g,foratotalofm =n(n 2)(2n′ n)/4distinct g B with(f,g) R. − − ∈ ∈ 2. Letg bean almost 2-to-1 function inB. Choose someordered pairof inputs (x,y) / s(g) such that ∈ g(s ) = g(x) = g(y) = g(s ). Define a 2-to-1 function f A such that (f,g) R as follows: 1 2 6 6 ∈ ∈ Let f agree with g on all inputs outside x,y . Define f(x) = g(s ) and f(y) = g(s ). There are 1 2 { } m′ = n 2choicesoftheorderedpair(x,y)sincetheren/2 1pairsofmatchedinputsforgand2 − − waystoordereachpair. 3. Fixafunction f Aandapointx [n]. Letg B besuchthat(f,g) Randf(x)= g(x). Then ∈ ∈ ∈ ∈ 6 f and g should differ an another point y [n]. By the claim, f(x) = f(y)and g(x) = g(y). There ∈ 6 are precisely n 2 choices of y. For each choice of y, the choice of g is determined by the value − z = g(x) = g(y)whichmustnotbeintheimageoff. (Indeedeachsuchchoiceyieldssuchavalidg.) Hencetherearepreciselyn′ n/2choicesofz. So,intotaltherearepreciselyl = (n 2)(2n′ n)/2 − − − choices ofg with(f,g) Randf(x) = g(x). ∈ 6 4. Fix a function g B and a point x [n]. Let f A be such that (f,g) R and f(x) = g(x). ∈ ∈ ∈ ∈ 6 Then f and g should differ on another point y [n]. (We must have x / s(g), otherwise there is ∈ ∈ no such f.) By the claim we must have g(x) = g(y). Therefore there is only one such choice for y. Moreover by the claim we must have f(x),f(y) = f(s ),f(s ) which yields precisely l′ = 2 1 2 { } { } suchfunctions f. Itfollowsthat m·m′ = n(n 2)/2. Thereforethequantumquerycomplexity ofφisΩ(n). q l·l′ − p Ifn′ = n/2+1thenobservethatanyalmost2-to-1functionissurjectivebutany2-to-1functionisnot. Thereforesincen= 2n′ 2weimmediatelyobtainthefollowingCorollary. − Corollary 7. Letnbeapositive even integer and bethesetoffunctions from [2n 2]to[n]. Definethe G − function ONTO : 0,1 by ONTO(f) = 1 if and only if f is surjective. Then any quantum algorithm G → { } computing ONTO withprobability atleast2/3requiresΩ(n)queries. 2.2 A near optimalquery lowerbound forAC0 Corollary 8. AC0 hasworst-case quantumquerycomplexity Ω(N/logN)onN-bitfunctions. 5 Proof. ThelowerboundinTheorem5isanasymptoticallyoptimalΩ(n)forthe2-to-1versusalmost2-to-1 problem. Eventhetotalfunction φwhichtakes asinputanarbitrary function f : [n] [n]anddetermines whetherornotitis2-to-1canbecomputedinAC0: → Werepresent theinputf : [n] [n]byN = nlog nbits,f wheref represents theℓ-thbitoff(i). The → 2 iℓ iℓ followingisanexplicitpolynomial-size constant-depth formulathatcomputesφ: log2n−1 [( f f ) ( f f )] iℓ jℓ jℓ iℓ ¬ ∨ ∧ ¬ ∨ ^i j_6=i ℓ^=0 log2n−1 [( f f ) ( f f ) ( f f ) ( f f ) ( f f ) ( f f )]. iℓ jℓ iℓ kℓ jℓ iℓ jℓ kℓ kℓ iℓ kℓ jℓ ∧ ¬ ∧ ∨ ¬ ∧ ∨ ¬ ∧ ∨ ¬ ∧ ∨ ¬ ∧ ∨ ¬ ∧ i6=j^6=k6=i ℓ_=0 The first part of the formula computes whether for each input i there is some input j = i such that all bits 6 of f(i) and f(j) agree and the second part determines whether for each triple of distinct inputs there is some bit on which some pair of f(i),f(j),f(k) disagree. This unbounded fan-in formula clearly has size O(n3logn)andisdepth4givenitsinputliterals. ThelowerboundofΩ(n)fromTheorem5isΩ(N/logN) asrequired. WenotethatasimilarresultholdsbasedontheONTOfunctionwhichhasanevensmallerAC0 formula: log2n−1 fjℓ iℓ j^∈[n]i∈[_2n−2] ℓ^=0 Wherej istheℓ-thbitofthebinaryencoding ofj,andxjℓ isxifj = 1and xifj = 0. Thisformulais ℓ ℓ ℓ ¬ onlydepth3andsizeO(n2logn). It is interesting to note the importance of the domain size in this problem. Testing surjectivity for functions from [n]to [n] is equivalent to testing whether two elements from the domain are mapped to the samepointintherange andthushasquery complexity Θ(n2/3),givenbytheelement distinctness problem [1]. 3 Discussion While we have shown that there is a function φ : [n]n 0,1 in AC0 requiring linear quantum query → { } complexity, when this is encoded using Boolean inputs it requires Ω(nlogn) bits and thus the quantum querylowerboundislowerthanthenumberofinputbitsbyanO(logn)factor. (Notethatthislowerbound holds even when the query algorithm is able to read the group of log n bits surrounding each query bit at 2 noextracost.) Thisdoesruleoutapolynomial speed-upbutitwouldbenicetoobtainalinearlowerbound fortheBooleancase. Also,ourresultsdonothingtoclosethegapinthelowerboundontheapproximatedegreeofAC0 func- tions. In [4], Ambainis used a standard recursive construction to obtain a Boolean function with quantum querycomplexitylargerthanitsapproximatedegreebyasmallpolynomialamount,thusgivingaseparation between query complexity and approximate degree. Determining the approximate degree of the 2-TO-1- VS-ALMOST-2-TO-1 orONTO functions, wouldyieldeitheramuchlargerdegreelowerboundforAC0 ora muchlargergapbetweenapproximate degreeandquantum querycomplexity thaniscurrentlyknown. 6 Acknowledgements WethankParikshitGopalanforsuggesting theproblem oftheapproximate degreeofAC0 whichmotivated thiswork. WealsothankScottAaronsonandDaveBaconforhelpful pointers. References [1] ScottAaronsonandYaoyunShi. Quantumlowerboundsforthecollisionandtheelementdistinctness problems. JournaloftheACM,51(4):595–605, 2004. [2] A. Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sci- ences,64:750–767, 2002. [3] A. Ambainis. Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness withsmallrange. TheoryofComputing, 1:37–46, 2005. [4] A. Ambainis. Polynomial degree vs. quantum query complexity. Journal of Computer and System Sciences, 72:220–238, 2006. [5] A. Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210–239, 2007. [6] A Ambainis. Quantum algorithms for formula evaluation. Technical Report arXiv:1006.3651, arxiv, 2010. [7] A.Ambainis, A.M.Childs, B.Reichardt, R.Spalek, and S.Zhang. AnyAND-ORformula ofsize N 1/2+o(1) canbeevaluated intimeN onaquantum computer. InProceedings 48th Annual Symposium onFoundations ofComputerScience, pages363–372, Berkeley,CA,October2007. IEEE. [8] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower boundsbypolynomials. JournaloftheACM,48(4):778–797, 2001. [9] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAMJournalonComputing,26(5):1510–1523, 1997. [10] G. Brassard, P. Høyer, and A. Tapp. Quantum algorithm for the collision problem. SIGACT News (Cryptology Column),28:14–19, 1997. [11] H.Buhrman,C.Durr,M.Heiligman,P.Høyer,F.Magniez,M.Santha,andR.deWolf. Quantumalgo- rithmsforelementdistinctness. InProceedings Sixteenth AnnualIEEEConferenceonComputational Complexity, pages1–31, Chicago,IL,June2001. [12] E.Farhi,J.Goldstone,andS.Gutmann. AquantumalgorothmfortheHamiltonianNANDtree.Theory ofComputing, 4:291–299, 2008. [13] P. Høyer, T. Lee, and R. Spalek. Negative weights make adversaries stronger. In Proceedings of the Thirty-NinthAnnualACMSymposium onTheoryofComputing, pages526–535, SanDiego,CA,June 2007. 7 [14] S. Kutin. Quantum lower bound for the collision problem with small range. Theory of Computing, 1(1):29–36, 2005. [15] T. Lee, R. Mittal, B. Reichardt, R. Sˇpalek, and M. Szegedy. Quantum query complexity of state conversion. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, pages344–353, PalmSprings,CA,October2011.IEEE. [16] B. W. Reichardt. Faster quantum algorithm for evaluating game trees. Technical Report arXiv:0907.1623, arxiv,2009. [17] B. W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearlytightforeveryBooleanfunction. InProceedingsofthe50thAnnualSymposiumonFoundations ofComputerScience, pages544–551, Atlanta,GA,2009.IEEE. [18] B. W. Reichardt. Reflections for quantum query algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 560–569, San Francisco, CA,January 2011.SocietyforIndustrial andAppliedMathematics. [19] R. Sˇpalek and M. Szegedy. All quantum adversary methods are equivalent. Theory of Computing, 2(1):1–18, 2006. 8