PaperlayerView exact revision on arXiv

Source-linked AI summary

BQP and the Polynomial Hierarchy

Scott Aaronson

arXiv:0910.4698v1quant-phcs.CC

TL;DR

The paper examines why separating quantum computation from the polynomial hierarchy requires stronger constant-depth circuit lower bounds than known examples. It develops low-degree polynomial methods and proves an oracle relation separation, while identifying coefficient control as a remaining limitation.

  • Problem

    Separating BQP from PH remains a longstanding challenge, despite established methods for other constant-depth circuit lower bounds and oracle separations.

  • Method

    The paper relates the problem to low-degree polynomial approximations, using sandwiching polynomials for almost k-wise independent distributions and studying ε-Bias Detection.

  • Results

    There exists an oracle relative to which FBQP is not contained in FBPP^PH, and BQP functions can have low-degree approximating polynomials, including a degree-4 polynomial distinguishing forrelated from uniform distributions.

  • Takeaways & Limitations

    The discussion suggests that an oracle separation between BQP and PH must accommodate massive coefficient cancellations characteristic of quantum algorithms, unlike more conservative classical polynomials.

  • Takeaways & Limitations

    The known LMN and Razborov–Smolensky approximations do not provide the coefficient control required by the Low-Fat Sandwich Conjecture.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses whether BQP lies within the polynomial hierarchy and presents formal evidence that quantum computation can exceed PH in relativized settings. It introduces Fourier-based problems connecting quantum query algorithms to AC0 lower bounds and pseudorandomness.

  • 1 Introduction: The paper asks whether BQP is contained in PH, a question that had received essentially no formal evidence before this work.The question includes whether BQP is in NP and, more generally, whether it is contained anywhere in PH.
  • 1.2 Our Results: Theorem 1 gives an oracle relative to which the relation version of BQP is not contained in the relation version of BPP with PH.Relation problems allow multiple valid outputs rather than requiring a single decision bit.
  • 1.2 Our Results: Fourier Fishing yields an unrelativized relation problem solvable in quantum logarithmic time but not in nonuniform AC0.The problem asks for inputs associated with unusually large squared Fourier coefficients of oracle-accessible Boolean functions.
  • 1.2 Our Results: Fourier Checking is a black-box decision problem whose separation from PH would follow from the Generalized Linial-Nisan Conjecture.The conjecture concerns almost k-wise independence and its indistinguishability from uniform distributions by constant-depth circuits.
  • 1.2 Our Results: The lower-bound strategy connects PH simulations to AC0 circuits and seeks low-degree sandwiching polynomials with additional coefficient control.Braverman’s proof of the original Linial-Nisan Conjecture supplies the starting point, while the generalized requirement remains harder.
  • 1.2 Our Results: The paper also proves, unconditionally, oracle separations placing BQP outside BPPpath and SZK, and interprets oracle results as query-complexity lower bounds.Relativized separations can be scaled down exponentially to obtain unrelativized BQLOGTIME-versus-AC0 results.

2 Preliminaries

The paper defines the Fourier-based problems and complexity classes used to study quantum–classical separations, including relation versions, AC0, BQLOGTIME, and postselection-based BPPpath.

  • Fourier problems: Fourier Fishing asks for strings identifying large Fourier coefficients among independently random Boolean functions.The promise version replaces random inputs with a worst-case promise that the tuple is good.
  • Fourier problems: Fourier Checking distinguishes independent function pairs from pairs drawn from the forrelated distribution.Forrelated pairs retain uniform individual functions while correlating one function with the Fourier transform of the other.
  • Complexity classes: FBQP and FBPP are relation classes whose algorithms output any valid polynomial-length witness, rather than a single decision bit.The paper notes that these classes do not currently admit amplification, so success probabilities matter.
  • Complexity classes: AC0 consists of nonuniform polynomial-size, constant-depth, unbounded-fanin AND/OR/NOT circuits, while BQLOGTIME uses O(log n) quantum gates.BQLOGTIME circuits are LOGTIME-uniform and may make random-access queries to the input.
  • Complexity classes: BPPpath is probabilistic polynomial time with postselection, and the paper uses it alongside PH-related classes in oracle comparisons.Postselection discards computation runs that do not produce a desired result.

3 Quantum Algorithms

The paper gives simple quantum algorithms for Fourier Fishing and Fourier Checking. Fourier Fishing succeeds overwhelmingly on random inputs, while Fourier Checking uses constant queries to distinguish the promised cases.

  • Fourier Fishing: Fourier Fishing samples each function’s Fourier spectrum with one quantum query and outputs a string for each function.Hadamard transforms and computational-basis measurement bias the output toward larger Fourier coefficients.
  • Fourier Fishing: 1−1/exp(n) is the success probability of FF-ALG on uniformly random function tuples.The result combines the algorithmic guarantee on good tuples with the fact that random tuples are good with overwhelming probability.
  • Fourier Checking: Fourier Checking uses O(1) queries to distinguish independent Boolean-function pairs from forrelated pairs.The algorithm prepares a uniform superposition, queries f and g, applies Hadamard gates, and accepts on the all-zero outcome.
  • Fourier Checking: Promise Fourier Checking is solvable with constant error probability using O(1) queries to f and g.The promise thresholds are p(f,g)≥0.05 and p(f,g)≤0.01.
  • Fourier Checking: p(f,g)≥0.07 for almost every forrelated pair, supporting constant-error quantum detection.The analysis obtains p(f,g)≥(cos 1.3)^2≈0.072 with probability 1−1/exp(N).

4 The Classical Complexity of Fourier Fishing

Fourier Fishing has an exponential constant-depth circuit lower bound, yielding an oracle separation for relation classes and a non-oracle separation between quantum logarithmic time and AC0.

  • Classical lower bound: Fourier Fishing is not in FBPPPH, despite having a quantum algorithm using one query to each input function.The lower bound is unconditional and strengthens the elementary exponential classical-query lower bound.
  • AC0 reduction: ε-Bias Detection asks whether independently sampled bits have bias 1/2 or 1/2+ε, and its AC0 lower bound drives the Fourier Fishing reduction.The reduction converts a distinguisher for ε-Bias Detection into a circuit distinguishing adjacent Hamming weights.
  • Pseudorandomness: The Fourier Fishing construction uses distributions that remain information-theoretically close to uniform while slightly biasing a hidden Fourier coefficient.This indistinguishability transfers success from uniformly random functions to the constructed distribution.
  • Oracle separation: Theorem 16 gives FBQPA̸⊂FBPPPHA with probability 1 for a random oracle A.The separation follows by combining the Fourier Fishing circuit lower bound with standard diagonalization.
  • Non-oracle separation: There exists an unrelativized relation problem in BQLOGTIME but not in nonuniform AC0.The paper obtains this by scaling the oracle construction down exponentially.

5 The Classical Complexity of Fourier Checking

Fourier Checking has exponential classical query lower bounds supported by almost k-wise independence, and this pseudorandomness yields oracle separations from postselection and statistical zero knowledge.

  • Almost k-wise independence: The forrelated distribution is O(·)-almost k-wise independent, despite correlating g with the Fourier transform of f.The proof first analyzes real Gaussian functions and then transfers the result to Boolean sign functions.
  • Pseudorandomness consequences: Almost k-wise independence makes the distribution indistinguishable from uniform for BPPpath and SZK machines under the stated superpolynomial-error condition.The BPPpath argument expands postselected acceptance probabilities over computation paths, while the SZK argument uses samplable distributions.
  • Oracle separations: Theorem 21 gives an oracle A relative to which BQPA̸⊂BPPpathA.The same framework also yields BQPA̸⊂SZKA.
  • Oracle construction: The oracle encodes, at each input length, either a uniformly random or a forrelated function pair, allowing BQP to identify the hidden case.Theorem 9 supplies the quantum distinguisher, while almost k-wise independence blocks the relevant classical simulations.

6 The Generalized Linial-Nisan Conjecture

The section proposes the Generalized Linial-Nisan (GLN) Conjecture, extending pseudorandomness against constant-depth circuits from exact to almost k-wise independence. Assuming GLN, the paper derives oracle separations and an unrelativized quantum-logarithmic-time separation from AC0.

  • Motivation and prior work: The original Linial-Nisan Conjecture says polylogarithmic independence fools AC0, and Braverman later proved this conjecture for constant-depth circuits.Bazzi and Razborov had previously proved the depth-2 case.
  • The GLN Conjecture: The GLN Conjecture posits that 1/n^Ω(1)-almost n^Ω(1)-wise independent distributions fool AC0 circuits of size 2^{n^o(1)} and constant depth.It is presented as a weaker-parameter extension of Braverman’s theorem sufficient for the paper’s applications.
  • Consequences for PH: Under GLN, sufficiently almost poly(n)-wise independent oracle distributions cannot be distinguished from uniform by PH machines with non-negligible bias.This statement supplies the PH indistinguishability consequence used in the oracle construction.
  • Consequences for PH: Assuming GLN, there exists an oracle A relative to which BQP^A is not contained in PH^A.The proof follows the earlier oracle-separation argument, with GLN replacing the corresponding indistinguishability lemma.
  • Consequences for AM: Assuming only the depth-2 GLN case, there exists an oracle A relative to which BQP^A is not contained in AM^A.The argument converts a hypothetical AM protocol for Fourier Checking into DNF formulas contradicting the depth-2 conjecture.
  • Unrelativized consequence: Assuming GLN, the paper obtains a promise problem in BQLOGTIME that is not in AC0 by scaling the oracle-based Fourier Checking separation down exponentially.The promise distinguishes cases with p(f,g) at most 0.01 from cases at least 0.05; an AC0 solver would distinguish the uniform and forrelated distributions.
  • Polynomial formulation: The Low-Fat Sandwich Conjecture asks for low-degree, low-fat sandwiching polynomials for every AC0 function and implies GLN.The paper notes that the converse follows from a linear-programming duality calculation that it omits.

7 Discussion

The discussion explains why separating BQP from PH is difficult: quantum algorithms themselves yield low-degree approximating polynomials, so standard AC0 lower-bound techniques cannot suffice. The proposed route requires low-degree approximations with coefficient control that prevents massive cancellations.

  • Why the problem is difficult: Known AC0 lower-bound methods generally argue that a function is not approximated by a low-degree polynomial, conflicting with the low-degree polynomials produced by quantum algorithms.The discussion identifies this conflict in both explicit polynomial methods and random-restriction arguments.
  • Why the problem is difficult: Quantum query algorithms have low-degree acceptance polynomials, so low-degree approximation alone cannot separate Fourier Checking from AC0.A T-query quantum algorithm has acceptance probability represented by a multilinear polynomial of degree at most 2T.
  • A proposed route: The Low-Fat Sandwich Conjecture strengthens ordinary low-degree approximation by requiring AC0 functions to admit degree n^o(1) sandwiching polynomials with controlled coefficient weight.The low-fat requirement is expressed through a linear-combination representation whose coefficient bound is n^o(1).
  • A proposed route: Low-fat polynomials would avoid the massive cancellations that let quantum polynomials distinguish almost k-wise independent distributions from uniformity.Theorem 29 is described as ruling out Fourier Checking for conservative polynomials without such cancellations.
  • Limits of existing techniques: Braverman’s proof does not provide the coefficient control required by the conjecture because LMN and Razborov–Smolensky approximations have many monomials and no reasonable coefficient bound.The authors therefore suspect that more constructive proofs of both approximation theorems are needed.

8 Open Problems

The paper closes with open problems about proving the GLN Conjecture, strengthening it, understanding low-fat approximation, and extending the relativized separations beyond PH. It also asks how far the Fourier Checking separation and related quantum–classical gaps can be pushed.

  • GLN and oracle separations: A first priority is proving the GLN Conjecture, beginning with the special case of DNFs, which would imply an oracle separation between BQP and AM.The authors offer prizes for the PH and AM cases.
  • GLN and oracle separations: The paper asks whether GLN extends to weaker or incomparable classes such as monotone DNFs, read-once formulas, and read-k-times formulas.
  • Low-fat approximation: An explicit function separating ordinary low-degree approximation from low-degree low-fat approximation remains an open challenge.The proposed function should have a degree-n^o(1) approximant but no degree-n^o(1) approximant satisfying the low-fat representation and error conditions.
  • Beyond PH: The authors ask whether there is an oracle relative to which BQP is not contained in IP or differs from IP with a BQP prover.
  • Beyond PH: The paper also asks whether GLN could yield oracles where NP is contained in BQP while PH is not contained in BQP or is infinite.
  • Unrelativized consequences: Further questions concern realizing Fourier Checking as an explicit computational problem and improving the success-probability gap between FBQP and FBPP^PH.The stated relation has quantum success 1−c^−n versus classical success at most 0.99.
Loading 0910.4698v1…