DOC PREVIEW
Pseudorandom generators

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Pseudorandom generators and the BQP vs. PH problemBill Fefferman∗Chris Umans†October 13, 2010AbstractIt is a longstanding open problem to devise an oracle relative to which BQP does not lie in thePolynomial-Time Hierarchy (PH). We advance a natural conjecture about the capacity of the Nisan-Wigderson pseudorandom generator [NW94] to fool AC0, with MAJORITY as its hard function. Ourconjecture is essentially that the loss due to the hybrid argument (which is a component of the standardproof from [NW94]) can be avoided in this setting. This is a question that has been asked previously inthe pseudorandomness literature [BSW03]. We then make three main contributions:1. We show that our conjecture implies the existence of an oracle relative to which BQP is not in thePH. This entails giving an explicit construction of unitary matrices, realizable by small quantumcircuits, whose row-supports are “nearly-disjoint.”2. We give a simple framework (generalizing the setting of Aaronson [Aar10a]) in which any effi-ciently quantumly computable unitary gives rise to a distribution that can be distinguished fromthe uniform distribution by an efficient quantum algorithm. When applied to the unitaries we con-struct, this framework yields a problem that can be solved quantumly, and which forms the basisfor the desired oracle.3. We prove that Aaronson’s “GLN conjecture” [Aar10a] implies our conjecture; our conjecture isthus formally easier to prove. The GLN conjecture was recently proved false for depth greater than2 [Aar10b], but it remains open for depth 2. If true, the depth-2 version of either conjecture wouldimply an oracle relative to which BQP is not in AM, which is itself an outstanding open problem.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/√`) 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/√`). 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(Ut+m) = 1] − Pr[C(Ut, NWMAJORITYD(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(`) (and even larger) as we conjecture istrue. In Section 6 we discuss intuition supporting this conjecture that relates specifically to the hardness ofMAJORITY for AC0.This paper contains three main results, which together make Conjecture 1 interesting and worthy offurther study:• We show that our conjecture implies the existence of an


Pseudorandom generators

Download Pseudorandom generators
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Pseudorandom generators and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Pseudorandom generators 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?