Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1007.0305

Pseudorandom generators and the BQP vs. PH problem

Bill Fefferman, Christopher Umans

Published Jul 2, 2010• 16 citations
arXivHTMLPDF

Abstract

It is a longstanding open problem to devise an oracle relative to which BQP does not lie in the Polynomial-Time Hierarchy (PH). We advance a natural conjecture about the capacity of the Nisan-Wigderson pseudorandom generator [NW94] to fool AC_0, with MAJORITY as its hard function. Our conjecture is essentially that the loss due to the hybrid argument (which is a component of the standard proof from [NW94]) can be avoided in this setting. This is a question that has been asked previously in the 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 the PH. This entails giving an explicit construction of unitary matrices, realizable by small quantum circuits, whose row-supports are "nearly-disjoint." (2) We give a simple framework (generalizing the setting of Aaronson [A10]) in which any efficiently quantumly computable unitary gives rise to a distribution that can be distinguished from the uniform distribution by an efficient quantum algorithm. When applied to the unitaries we construct, this framework yields a problem that can be solved quantumly, and which forms the basis for the desired oracle. (3) We prove that Aaronson's "GLN conjecture" [A10] implies our conjecture; our conjecture is thus formally easier to prove. The GLN conjecture was recently proved false for depth greater than 2 [A10a], but it remains open for depth 2. If true, the depth-2 version of either conjecture would imply 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 the Nisan-Wigderson generator that can be broken by quantum computers, but not by the relevant modes of classical computation, if our conjecture is true.

DOI
10.48550/arxiv.1007.0305

Related papers

On Quantum Computing and Pseudorandomness

William Jason Fefferman

The relationship between efficient verification and quantum computing is one of the most important and least well-understood questions in the theory of computation. In particular, is there a problem that can be solved efficiently on a quantum computer that cannot be verified? In this thesis we give evidence that BQP ⊄ PH, relating the classes of languages decidable with a quantum computer to a generalization of NP. In so doing we connect a question in pseudorandomness, first studied [BSW03] to the problem of finding an oracle relative to which BQP ⊄ PH. The primary technical challenge is to construct a unitary matrix, realized by an efficient quantum circuit and whose rows are supported on nearly disjoint subsets. Using this matrix and assuming the validity of the aforementioned question in pseudorandomness, we show an instantiation of the Nisan-Wigderson pseudorandom generator that can be broken with quantum computers, but not with the relevant mode of classical computation.

•Feb 2, 2011•0 citations

BQP and the Polynomial Hierarchy

Scott Aaronson

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis. First, we show that there exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not in AC0. Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years.

arXiv:0910.4698•Oct 25, 2009•46 citations

On beating the hybrid argument.

Bill Fefferman, Ronen Shaltiel, Christopher Umans +1 more

The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor $k$ equal to the bit-length of the distributions: $\epsilon$-distinguishability implies $\epsilon/k$-predictability. This paper studies the consequences of avoiding this loss -- what we call “beating the hybrid argument” -- and develops new proof techniques that circumvent the loss in certain natural settings. Our main results are: We give an instantiation of the Nisan-Wigderson generator (JCSS '94) that can be broken by quantum computers, and that is $o(1)$-unpredictable against $AC^0$. We conjecture that this generator indeed fools $AC^0$. Our conjecture implies the existence of an oracle relative to which BQP is not in the PH, a longstanding open problem. We show that the “INW generator” by Impagliazzo, Nisan, and Wigderson (STOC '94) with seed length $O(\log n \log \log n)$ produces a distribution that is $1/\log n$-unpredictable against poly-logarithmic width (general) read-once oblivious branching programs. (This was also observed by other researchers.) Obtaining such generators where the output is indistinguishable from uniform is a longstanding open problem. We identify a property of functions $f$, “resamplability,” that allows us to beat the hybrid argument when arguing indistinguishability of \[G^{\otimes k}_f(x_1,\ldots,x_k) = (x_1,f(x_1),x_2,f(x_2),\ldots,x_k,f(x_k))\] from uniform. This gives new pseudorandom generators for classes such as $AC^0[p]$ with a stretch that, despite being sub-linear, is the largest known. We view this as a first step towards beating the hybrid argument in the analysis of the Nisan-Wigderson generator (which applies $G^{\otimes k}_f$ on correlated $x_1,\ldots,x_k$) and proving the conjecture in the first item. An extended abstract of this paper appeared in the Proceedings of the 3rd Innovations in Theoretical Computer Science (ITCS) 2012.

Theory of Computing•Jan 1, 2013•28 citations

A Counterexample to the Generalized Linial-Nisan Conjecture

Scott Aaronson

In earlier work, we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture: that "almost k-wise independent" distributions are indistinguishable from the uniform distribution by constant-depth circuits. The original Linial-Nisan Conjecture was recently proved by Braverman; we offered a $200 prize for the generalized version. In this paper, we save ourselves $200 by showing that the GLN Conjecture is false, at least for circuits of depth 3 and higher. As a byproduct, our counterexample also implies that Pi2P is not contained in P^NP relative to a random oracle with probability 1. It has been conjectured since the 1980s that PH is infinite relative to a random oracle, but the highest levels of PH previously proved separate were NP and coNP. Finally, our counterexample implies that the famous results of Linial, Mansour, and Nisan, on the structure of AC0 functions, cannot be improved in several interesting respects.

arXiv:1110.6126•Oct 27, 2011•17 citations

BQP and the Polynomial Hierarchy

Scott Aaronson

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis. First, we show that there exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not in AC[superscript 0]. Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years.

•Jan 1, 2010•12 citations

A Counterexample to the Generalized Linial-Nisan Conjecture

Scott Aaronson

In earlier work [1], we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture: that “almost k-wise independent” distributions are indistinguishable from the uniform distribution by constant-depth circuits. The original Linial-Nisan Conjecture was recently proved by Braverman [7]; we offered a $200 prize for the generalized version. In this paper, we save ourselves $200 by showing that the GLN Conjecture is false, at least for circuits of depth 3 and higher. As a byproduct, our counterexample also implies that Π p 2 ̸ ⊂ PNP relative to a random oracle with probability 1. It has been conjectured since the 1980s that PH is infinite relative to a random oracle, but the highest levels of PH previously proved separate were NP and coNP. Finally, our counterexample implies that the famous results of Linial, Mansour, and Nisan [12], on the structure of AC 0 functions, cannot be improved in several interesting respects. 1

•Oct 27, 2011•2 citations
It is a longstanding open problem to devise an oracle relative to which BQP does not lie in the Polynomial-Time Hierarchy (PH). We advance a natural conjecture about the capacity of the Nisan-Wigderson pseudorandom generator [NW94] to fool AC_0, with MAJORITY as its hard function. Our conjecture is essentially that the loss due to the hybrid argument (which is a component of the standard proof from [NW94]) can be avoided in this setting. This is a question that has been asked previously in the 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 the PH. This entails giving an explicit construction of unitary matrices, realizable by small quantum circuits, whose row-supports are "nearly-disjoint." (2) We give a simple framework (generalizing the setting of Aaronson [A10]) in which any efficiently quantumly computable unitary gives rise to a distribution that can be distinguished from the uniform distribution by an efficient quantum algorithm. When applied to the unitaries we construct, this framework yields a problem that can be solved quantumly, and which forms the basis for the desired oracle. (3) We prove that Aaronson's "GLN conjecture" [A10] implies our conjecture; our conjecture is thus formally easier to prove. The GLN conjecture was recently proved false for depth greater than 2 [A10a], but it remains open for depth 2. If true, the depth-2 version of either conjecture would imply 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 the Nisan-Wigderson generator that can be broken by quantum computers, but not by the relevant modes of classical computation, if our conjecture is true.
The relationship between efficient verification and quantum computing is one of the most important and least well-understood questions in the theory of computation. In particular, is there a problem that can be solved efficiently on a quantum computer that cannot be verified? In this thesis we give evidence that BQP ⊄ PH, relating the classes of languages decidable with a quantum computer to a generalization of NP. In so doing we connect a question in pseudorandomness, first studied [BSW03] to the problem of finding an oracle relative to which BQP ⊄ PH. The primary technical challenge is to construct a unitary matrix, realized by an efficient quantum circuit and whose rows are supported on nearly disjoint subsets. Using this matrix and assuming the validity of the aforementioned question in pseudorandomness, we show an instantiation of the Nisan-Wigderson pseudorandom generator that can be broken with quantum computers, but not with the relevant mode of classical computation.
The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis. First, we show that there exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not in AC0. Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years.
The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor kkk equal to the bit-length of the distributions: ϵ\epsilonϵ-distinguishability implies ϵ/k\epsilon/kϵ/k-predictability. This paper studies the consequences of avoiding this loss -- what we call “beating the hybrid argument” -- and develops new proof techniques that circumvent the loss in certain natural settings. Our main results are: We give an instantiation of the Nisan-Wigderson generator (JCSS '94) that can be broken by quantum computers, and that is o(1)o(1)o(1)-unpredictable against AC0AC^0AC0. We conjecture that this generator indeed fools AC0AC^0AC0. Our conjecture implies the existence of an oracle relative to which BQP is not in the PH, a longstanding open problem. We show that the “INW generator” by Impagliazzo, Nisan, and Wigderson (STOC '94) with seed length O(log⁡nlog⁡log⁡n)O(\log n \log \log n)O(lognloglogn) produces a distribution that is 1/log⁡n1/\log n1/logn-unpredictable against poly-logarithmic width (general) read-once oblivious branching programs. (This was also observed by other researchers.) Obtaining such generators where the output is indistinguishable from uniform is a longstanding open problem. We identify a property of functions fff, “resamplability,” that allows us to beat the hybrid argument when arguing indistinguishability of Gf⊗k(x1,…,xk)=(x1,f(x1),x2,f(x2),…,xk,f(xk))G^{\otimes k}_f(x_1,\ldots,x_k) = (x_1,f(x_1),x_2,f(x_2),\ldots,x_k,f(x_k))Gf⊗k​(x1​,…,xk​)=(x1​,f(x1​),x2​,f(x2​),…,xk​,f(xk​)) from uniform. This gives new pseudorandom generators for classes such as AC0[p]AC^0[p]AC0[p] with a stretch that, despite being sub-linear, is the largest known. We view this as a first step towards beating the hybrid argument in the analysis of the Nisan-Wigderson generator (which applies Gf⊗kG^{\otimes k}_fGf⊗k​ on correlated x1,…,xkx_1,\ldots,x_kx1​,…,xk​) and proving the conjecture in the first item. An extended abstract of this paper appeared in the Proceedings of the 3rd Innovations in Theoretical Computer Science (ITCS) 2012.
In earlier work, we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture: that "almost k-wise independent" distributions are indistinguishable from the uniform distribution by constant-depth circuits. The original Linial-Nisan Conjecture was recently proved by Braverman; we offered a $200 prize for the generalized version. In this paper, we save ourselves $200 by showing that the GLN Conjecture is false, at least for circuits of depth 3 and higher. As a byproduct, our counterexample also implies that Pi2P is not contained in P^NP relative to a random oracle with probability 1. It has been conjectured since the 1980s that PH is infinite relative to a random oracle, but the highest levels of PH previously proved separate were NP and coNP. Finally, our counterexample implies that the famous results of Linial, Mansour, and Nisan, on the structure of AC0 functions, cannot be improved in several interesting respects.
The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis. First, we show that there exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not in AC[superscript 0]. Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years.
In earlier work [1], we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture: that “almost k-wise independent” distributions are indistinguishable from the uniform distribution by constant-depth circuits. The original Linial-Nisan Conjecture was recently proved by Braverman [7]; we offered a $200 prize for the generalized version. In this paper, we save ourselves $200 by showing that the GLN Conjecture is false, at least for circuits of depth 3 and higher. As a byproduct, our counterexample also implies that Π p 2 ̸ ⊂ PNP relative to a random oracle with probability 1. It has been conjectured since the 1980s that PH is infinite relative to a random oracle, but the highest levels of PH previously proved separate were NP and coNP. Finally, our counterexample implies that the famous results of Linial, Mansour, and Nisan [12], on the structure of AC 0 functions, cannot be improved in several interesting respects. 1