PaperlayerView exact revision on arXiv

Source-linked AI summary

The Need for Structure in Quantum Speedups

Scott Aaronson, Andris Ambainis

arXiv:0911.0996v3quant-phcs.CC

TL;DR

The paper asks whether unstructured black-box problems can yield large quantum speedups. It proves a polynomial relation for permutation-invariant problems and studies consequences of a conjecture about influential variables in bounded low-degree polynomials, including a conditional random-oracle result.

  • Problem

    The paper asks whether quantum and classical randomized query complexities are polynomially related for unstructured problems.

    Source: §1 · p. 2

  • Method

    The paper proves a query-complexity bound for permutation-invariant problems and derives further query-complexity results from a conjecture about low-degree polynomials.

    Source: §1.1 · p. 3, §1.2 · pp. 5–7

  • Results

    R(f) = O(Q(f)^7 polylog Q(f)) for permutation-invariant partial functions; the stated consequences also include Dε+δ(f) ≤ (Qε(f)/δ)^O(1) and, if P = P#P, BQPA ⊂AvgPA with probability 1 for a random oracle.

    Source: §1.2 · pp. 5, 7

  • Takeaways & Limitations

    The bound proves polynomial relatedness for permutation-invariant problems, resolving Watrous’s conjecture as stated in the paper.

    Source: §1.2 · p. 5

    The authors seek to improve the symmetric-problem bound and conjecture that its exponent can be reduced to 2.

    Source: §4 · p. 24

Abstract

from arXiv · show

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 7th root of the classical randomized query complexity. (An earlier version of this paper gave the 9th root.) This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O'Donnell et al. (2005) and Dinur et al. (2006), we conjecture that every bounded low-degree polynomial has a "highly influential" variable. Assuming this conjecture, we show that every T-query quantum algorithm can be simulated on most inputs by a poly(T)-query classical algorithm, and that one essentially cannot hope to prove P!=BQP relative to a random oracle.

1 Introduction

The introduction asks how problem structure shapes quantum speedups, noting that large classical–quantum query gaps make upper bounds non-obvious. It presents a polynomial relationship between quantum and randomized query complexity for permutation-invariant problems and explores conditional consequences of a bounded-polynomial influence conjecture, alongside related subsequent results.

1 Introduction

  • The contrast between structured-problem speedups and Grover’s optimal quadratic gain for unstructured search motivates asking whether unstructured quantum and randomized query costs are polynomially related.Source: §1 · pp. 1–2

1.1 Formalizing the Problem

  • Permutation invariance formalizes unstructuredness for problems such as collision; Watrous conjectured polynomially related randomized and quantum query complexities, and Boolean inputs already satisfy R(f)=O(Q(f)^2).Source: §1.1 · pp. 3–4

1.2 Our Results

  • R(f)=O(Q(f)^7 polylog Q(f)) for every permutation-invariant partial function f, resolving Watrous’s conjecture.Source: §1.2 · p. 5
  • The proof estimates element multiplicities, identifies a hard core of input types, and uses a chopping hybrid with SetEquality lower bounds or the quantum adversary theorem.Source: §1.2 · p. 6
  • They conjecture that every bounded low-degree polynomial has a variable with influence at least (ε/d)^O(1); assuming this, quantum algorithms admit poly(T)-query classical simulations on most inputs.The assumption also yields Dε+δ(f) ≤ (Qε(f)/δ)^O(1) for Boolean functions.Source: §1.1 · p. 4, §1.2 · pp. 6–7
  • If P=P#P, then BQPA ⊂ AvgPA with probability 1 for a random oracle A.Source: §1.2 · p. 7
  • Dinur et al. also imply that any T-query quantum algorithm can be simulated on most inputs using 2^O(T) classical queries.Source: §1.2 · p. 7
  • Query-complexity gaps can be superexponential, including N^Ω(1) versus O(1), so even an exponential upper bound is far from obvious.Source: §1.2 · p. 7

1.3 Subsequent Work

  • Yuen’s hybrid argument gave an Ω(N^1/5/log N) lower bound for distinguishing a random function from a random permutation, later improved to a tight Ω(N^1/3) bound by Zhandry [33].The later bound used completely different ideas.Source: §1.3 · pp. 7–8
  • Montanaro [25] proved Conjecture 6 for multilinear polynomials whose Fourier coefficients all have equal absolute value; extending the technique to arbitrary polynomials remains open.The open question includes arbitrary multilinear polynomials.Source: §1.3 · p. 8
  • Baˇckurs and Bavarian [7] bounded the sum of L1-influences by O(d^3 log d), salvaging the original L1-based argument; this version uses L2-influences instead.The paper also proves the L1 and L2 versions of Conjecture 6 equivalent and gives the folklore bound that the L2-influence sum is at most d.Source: §1.3 · p. 8

2 Quantum Lower Bound for All Symmetric Problems

This section proves a 7th-root quantum lower bound for permutation-symmetric problems, using classical estimates of input multiplicities, type-based distinctions, and SetEquality reductions.

2 Quantum Lower Bound for All Symmetric Problems

  • R(f) = O(Q(f)^7 polylog Q(f)) for every permutation-symmetric f.This is Theorem 5, the section’s main result.Source: §2 · p. 8

2.1 Randomized Upper Bound

  • With O(T^{1+c} log T) queries, the randomized algorithm computes f when every 1-type and 0-type differ in some multiplicity by more than 2N/T^c.It estimates each input-value multiplicity by sampling; the estimate is within N/T^c for all values with probability 1−O(1/T).Source: §2.1 · pp. 9, 11

2.2 The Chopping Procedure

  • The chopping procedure transforms the hardest-to-distinguish types through intermediate types, while arranging their quantum lower bounds to avoid a 1/log N loss.The types are modified in stages to make their multiplicity partitions more similar; the intermediate distinguishing biases can decrease quadratically while the lower bounds remain uniformly large, with 1/log T factors.Source: §2.2 · pp. 11–12

2.3 Quantum Lower Bounds

  • For consecutive types in the chopping sequence, the proof lower-bounds quantum distinguishing complexity using different arguments for few versus many chopped elements.When d = ∥Aℓ−Aℓ−1∥ ≤ N/2, Lemma 16 gives an Ambainis-adversary lower bound for the transition.Source: §2.3 · pp. 14–15
  • Zhandry [33] proves Q(SetEquality) = Ω(N^1/3), a tight lower bound by the upper bound of Brassard, Høyer, and Tapp.SetEquality distinguishes equal sets from disjoint sets under the promise that neither input sequence has repeats.Source: §2.3 · p. 16
  • 3SetEquality has quantum query complexity Ω(N^1/3), obtained by randomly permuting either candidate set into Z to reduce SetEquality.The reduction uses Theorem 17, Zhandry [33]’s Ω(N^1/3) lower bound for SetEquality.Source: §2.3 · pp. 16–17
  • For Aℓ formed by chopping r rows from Aℓ−1, the proof embeds a size-r 3SetEquality instance to obtain Lemma 19’s quantum lower bound.The construction makes the resulting input belong to Aℓ−1 or Aℓ according to which sets are equal.Source: §2.3 · p. 17

2.4 Putting Everything Together

  • The proof finds adjacent Aℓ and Aℓ−1 distributions distinguishable with bias at least βℓ, then combines the chopping and unchopping bounds.It chooses c = 2/5 before deriving the final query bound.Source: §2.4 · pp. 17–18
  • The proof gives the bound O(Q(f)^7 log^15 Q(f)); the preceding step gives T = O(Q(f)^5 log^10 Q(f)) before applying Lemma 12.Source: §2.4 · p. 18

3 Quantum Lower Bounds Under The Uniform Distribution

This section connects a conjecture about influential variables in bounded low-degree polynomials to classical simulation of quantum query algorithms. Under the conjecture, it derives polynomial-query simulations and complexity consequences; unconditionally, it gives exponential-query simulations.

3.1 Consequences of Our Influence Conjecture

  • Under Conjecture 6, a deterministic classical algorithm can approximate a T-query quantum algorithm’s acceptance probability within ε on a 1−δ fraction of inputs using poly(T, 1/ε, 1/δ) queries.The argument uses the fact that a T-query algorithm’s acceptance probability is a degree-at-most-2T polynomial, then repeatedly queries influential variables.Source: §3 · p. 19, §3.1 · p. 20
  • Under Conjecture 6, Dε+δ(f) ≤ (Qε(f)/δ)^O(1) for Boolean functions.This follows by applying the classical simulation to a quantum algorithm that computes f correctly on a 1−ε fraction of inputs.Source: §3.1 · p. 21
  • Under Conjecture 6 and P = P#P, BQPA ⊂ AvgPA with probability 1 for a random oracle.The result applies to all BQPA languages simultaneously for a probability-1 set of random oracles.Source: §3.1 · p. 22

3.2 Unconditional Results

  • For any Boolean input X ∈ {0, 1}^N and α, δ > 0, a T-query quantum algorithm’s acceptance probability can be approximated within additive α on a 1−δ fraction of inputs using 2^O(T)/(α^4δ^4) deterministic classical queries.The classical queries are nonadaptive.Source: §3.2 · p. 23
  • Unconditionally, Dε+δ(f) ≤ 2^O(Qε(f))/δ^4 for Boolean functions.Source: §3.2 · p. 23

4 Open Problems

The open problems ask how to sharpen the symmetric-problem bounds, extend their scope, and find alternative proof routes. The paper also leaves open how to establish the influence conjecture or bypass it for quantum-derived polynomials.

4 Open Problems

  • The authors conjecture that the symmetric-problem bound R(f)=O(Q(f)^7 polylog Q(f)) can be improved to R(f)=O(Q(f)^2).Their proof reduces from the non-symmetric SetEquality problem.Source: §4 · p. 24
  • Removing the assumption M ≥ N from the symmetric-problem lower bound remains open and may require replacing the chopping procedure.Source: §4 · p. 24
  • The authors conjecture polynomial relatedness of R(f) and Q(f) for partial functions symmetric only under input permutations, and pose the analogous question for symmetric promises.Source: §4 · p. 24
  • They ask whether the symmetric-function bound can be reproved using only the polynomial method, and whether proving Conjecture 6 or targeting quantum acceptance polynomials could settle further questions.Source: §4 · pp. 24–25

6 Appendix: The Boolean Case

For partial symmetric Boolean functions, the appendix proves a quadratic upper bound on randomized query complexity in terms of quantum query complexity. Its sampling argument estimates Hamming weight, while a quantum lower bound supplies the other half of the comparison.

6 Appendix: The Boolean Case

  • R(f)=O(Q(f)^2) for every partial symmetric Boolean function f.This extends the quadratic relation beyond total symmetric Boolean functions.Source: §6 · p. 27
  • A randomized algorithm samples input bits to estimate Hamming weight and decide f, using O(γ^2) queries when the relevant weight gap is γ.The sampling estimate succeeds with probability at least 2/3 when its query count is chosen suitably.Source: §6 · p. 28
  • The proof combines the randomized sampling upper bound R(f)=O(γ^2) with a quantum lower bound Q(f)=Ω(γ).Source: §6 · pp. 27–28

7 Appendix: 1-Norm versus 2-Norm

The appendix establishes that the L1 and L2 formulations of the bounded-polynomial influence conjecture are equivalent. It notes that the paper switched to L2 after an identified gap in its earlier L1 argument.

7 Appendix: 1-Norm versus 2-Norm

  • The current paper uses L2-influences after an earlier L1-based argument revealed a gap; later work filled that gap, but switching norms was the simplest fix.Source: §7 · p. 28
  • The L1 version asserts that some variable has influence at least (Vr[p]/d)^O(1) for a degree-d polynomial bounded between 0 and 1.Source: §7 · p. 29
  • Conjectures 6 and 31, the L2- and L1-influence versions of the bounded-polynomial conjecture, are equivalent.Source: §7 · pp. 28–29

8 Appendix: Equivalent Form of Conjecture 4

The appendix proves that Conjectures 4 and 33 are equivalent. The two directions translate between classical approximation of a quantum algorithm’s acceptance probability and classical computation of Boolean functions on large domains, using a robust hint-bit lemma.

8 Appendix: Equivalent Form of Conjecture 4

  • The hint-bit lemma recovers an unknown p ∈ [0, 1] within additive error ±(b + 1)ε despite at most b < k/2 adversarially corrupted hints.Its correction procedure deletes out-of-order zero–one pairs, then removes remaining extreme zeroes and ones before estimating p.Source: §8 · pp. 29–30
  • Conjectures 4 and 33 are equivalent: average-case classical simulation of quantum acceptance probabilities and classical computation of Boolean functions on large domains imply one another.Conjecture 4 concerns approximating acceptance probability on most inputs; Conjecture 33 concerns computing a Boolean function on most points of a sufficiently large subset.Source: §8 · pp. 29–30
  • Under Conjecture 4, approximating a quantum algorithm’s acceptance probability lets a classical algorithm decide the Boolean function on at least a 1 − α fraction of its domain.The proof uses additive error ε = 1/7 and sets δ := αc for a domain S of size at least c2^N.Source: §8 · p. 30
  • For the converse, thresholding acceptance probability at k evenly spaced levels yields Boolean functions f_j with quantum query complexity O(kT).Conjecture 33 supplies classical algorithms for the threshold functions on their large domains; the proof then combines their outputs to approximate p(X).Source: §8 · pp. 30–31
  • Combining the threshold algorithms and a union bound gives a classical algorithm using poly(T, 1/ε, 1/δ) queries to approximate p(X) within ±ε on at least a 1 − δ fraction of inputs.At most two threshold predictions can fail for an input: the exceptional index and the index whose domain excludes that input.Source: §8 · p. 31
Loading 0911.0996v3…