##
This **preview** shows page *1-2-3-4-5-6*
out of 18 **pages**.

*View Full Document*

End of preview. Want to read all 18 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document**Unformatted text preview:**

Pseudorandom generators and the BQP vs. PH problemBill Fefferman∗Chris Umans†April 7, 2010AbstractIt is a longstanding open problem to devise an oracle relative to which BQP does not lie in thePolynomial-Time Hierarchy (PH). Very recently, Aaronson [Aar09] proposed a natural problem basedon the DFT, and a conjecture – the “Generalized Linial-Nisan conjecture” – about the power of AC0,that would imply the existence of an oracle (derived from this problem) relative to which BQP is not inPH.We advance a natural conjecture about the capacity of the Nisan-Wigderson pseudorandom generator[NW94] to fool AC0, with MAJORITY as its hard function. Our conjecture is essentially that the loss dueto the hybrid argument (which is a component of the standard proof from [NW94]) can be avoided in thissetting. This is a question that has been asked previously in the pseudorandomness literature [BSW03].We then make three main contributions:1. We prove that the Generalized Linial-Nisan (GLN) conjecture implies our conjecture. Our con-jecture is thus formally easier to prove, and it represents a meaningful consequence of the GLNconjecture beyond its original motivation.2. We show that our conjecture (by itself) implies the existence of an oracle relative to which BQP isnot in the PH. This entails giving an explicit construction of unitary matrices, realizable by smallquantum circuits, whose row-supports are “nearly-disjoint.”3. We give a simple framework (generalizing the setting of [Aar09]) in which any efficiently quan-tumly computable unitary gives rise to a distribution that can be distinguished from the uniformdistribution by an efficient quantum algorithm. When applied to the unitaries we construct, thisframework yields a problem that can be solved quantumly, and which forms the basis for thedesired oracle.Taken together, our results have the following interesting interpretation: they give an instantiation of theNisan-Wigderson generator that can be broken by quantum computers, but not by the relevant modes ofclassical computation, if our conjecture is true.∗Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA 91125. Supported by IQI.†Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA 91125. Supported by NSF CCF-0846991.1 IntroductionLet Utdenote a random variable uniformly distributed on t-bit strings. A pseudorandom generator (PRG)is a functionf : {0, 1}t→ {0, 1}mthat stretches a short “seed” into a longer output string, with the property that f(Ut) is computationallyindistinguishable from the uniform distribution.There is a vast literature constructing PRGs that achieve computational indistinguishability against awide variety of computational models (e.g. small circuits, small nondeterministic circuits, small branchingprograms, small constant-depth circuits). These constructions are typically “hardness vs. randomness”tradeoffs in the sense that they make use of a hard function (either unconditionally hard, or hard conditionedon a complexity assumption), and their proof of correctness takes the form of a reduction that transformsa computationally efficient distinguisher into an efficient algorithm for the hard function (thereby derivinga contradiction). This transformation entails the use of the hybrid argument [GM84, Yao82] which incursa loss of a factor 1/m in going from a distinguisher (with gap ε) to a predictor (with advantage ε/m) andfrom there to an efficient algorithm (with advantage ε/m).A question that has been raised in the pseudorandomness literature is whether this loss of a factor of 1/mcan be avoided (for an explicit framing of this question, and a discussion of its motivation, see [BSW03]).In certain settings, the answer is known to be “yes” – when the notion of “efficient” is small PH circuits,or bounded-width branching programs [BSW03]. In the present paper, we identify a setting in which thisquestion has surprising connections to a central unresolved question in quantum complexity: whether thereexists an oracle relative to which BQP is not in the PH.Our setting is a familiar one: we will work with the ubiquitous Nisan-Wigderson PRG [NW94], againstAC0circuits, with MAJORITY as its hard function. We need a precise statement for the discussion below,which can be given via two standard definitions:Definition 1.1 ([NW94]). A set family D = {S1, S2, . . . , Sm} is an (`, p) design if every set in the familyhas cardinality `, and for all i 6= j, |Si∩ Sj| 6 p.Definition 1.2 ([NW94]). Given a function f : {0, 1}`→ {0, 1}and an (`, p) design D = {S1, S2, . . . , Sm}in a universe of size t, the function NWfD: {0, 1}t→ {0, 1}mis given byNWfD(x) =¡f1(x|S1), f2(x|S2), f3(x|S3), . . . , fm(x|Sm)¢,where each fiis the function f with a fixed set of its inputs negated1, and x|Sdenotes the projection of x tothe coordinates in the set S.Generally speaking, the function NWfDis a PRG against a class of distinguishers as long as f is hardon average for that class of distinguishers. Recall that the majority function on ` bits is known to be hardfor AC0: no polynomial-size, constant-depth circuit can compute majority correctly on more than a 1/2 +Θ(`−1/2) fraction of the inputs [Smo93], and this is tight, since the function that simply outputs the firstbit of the input is correct on a random input with probability 1/2 + Θ(`−1/2). We make the followingquantitative conjecture:1The standard setup has each fi= f; we need the additional freedom in this paper for technical reasons. We know of no settingsin which this alteration affects the analysis of the NW generator.1Conjecture 1. Let D = {S1, S2, . . . , Sm} be an (`, O(1))-design in a universe of size t 6 poly(`), withm 6 p oly(`). Then for every constant-depth circuit of size at most poly(m),|Pr[C(Um) = 1] − Pr[C(N WMAJORITYD(Ut)) = 1]| 6 o(1).By the standard argument from [NW94, Nis92], a distinguishing circuit C with gap ε can be convertedto a predictor with advantage ε/m and then a slightly larger circuit that computes MAJORITY with successrate 1/2 + ε/m. Thus the above statement is true for m 6 o(√`); if the 1/m loss from the hybrid argumentcan be avoided (or reduced), it would be true for m as large as poly(`) as we conjecture is true. In Section6 we discuss intuition supporting this conjecture that relates specifically to the hardness ofMAJORITYforAC0.This paper contains three main results, which together make Conjecture 1 interesting and