Simple Algorithm
Quantum Computing · Rydberg State · 32 min

Query Complexity & the Polynomial Method

Proving what quantum algorithms cannot do.

Upper bounds come from clever algorithms; lower bounds need a proof that no algorithm can do better. In the query model such proofs exist. The polynomial method and the adversary method show that search needs Ω(N)\Omega(\sqrt N) queries, parity needs N/2N/2, and quantum speedups for total functions are at most polynomial.

What you’ll learn

  • Define deterministic, randomized and quantum query complexity and the relations among them.
  • Prove that a TT-query algorithm's acceptance probability is a polynomial of degree at most 2T2T.
  • Derive Q2(PARN)=N/2Q_2(\mathrm{PAR}_N)=N/2 and Q2(ORN)=Ω(N)Q_2(\mathrm{OR}_N)=\Omega(\sqrt N) from symmetrization and Markov's inequality.
  • State and apply Ambainis's adversary bound, and summarize what is known about the limits of quantum query speedups.

The query model, formally

Q2(f)≤R2(f)≤D(f)≤N,Q2(f)≤QE(f)≤D(f).Q_2(f)\le R_2(f)\le D(f)\le N,\qquad Q_2(f)\le Q_E(f)\le D(f).
The trivial relations. Every interesting question is about how large the gaps can be.

For partial functions (promise problems) the gaps can be enormous: Simon's problem, or forrelation, with 11 quantum query versus Ω~(N)\tilde\Omega(\sqrt N) classical ones (Aaronson & Ambainis 2015). For total functions, defined on all of {0,1}N\{0,1\}^N, they turn out to be at most polynomial. Proving such statements needs lower-bound techniques, and there are two great families.

The polynomial method

DerivationProof by induction on the number of queries
  1. ∣ψx(0)⟩=U0∣0⟩⟹deg⁡αi,b,z(0)(x)=0\ket{\psi^{(0)}_x}=U_0\ket{0}\quad\Longrightarrow\quad\deg\alpha^{(0)}_{i,b,z}(x)=0

    Before any query the amplitudes do not depend on xx.

  2. Ox: αi,b,z ⟼ (1−xi) αi,b,z+xi αi, b⊕1, zO_x:\ \alpha_{i,b,z}\ \longmapsto\ (1-x_i)\,\alpha_{i,b,z}+x_i\,\alpha_{i,\,b\oplus1,\,z}

    A query flips bb exactly when xi=1x_i=1. New amplitudes are linear in the old ones with coefficients of degree 11 in xx, so the degree rises by at most 11.

  3. Uj: α ⟼ Uj α(degree unchanged)U_j:\ \alpha\ \longmapsto\ U_j\,\alpha\qquad(\text{degree unchanged})

    Input-independent unitaries form linear combinations with constant coefficients.

  4. P(x)=∑k∈acc∣αk(x)∣2=∑k∈acc[(Re⁡αk)2+(Im⁡αk)2]P(x)=\sum_{k\in\mathrm{acc}}\abs{\alpha_k(x)}^2=\sum_{k\in\mathrm{acc}}\Big[\big(\operatorname{Re}\alpha_k\big)^2+\big(\operatorname{Im}\alpha_k\big)^2\Big]

    Real and imaginary parts are real polynomials of degree ≤T\le T, so PP has degree ≤2T\le 2T. Multilinearize with xi2=xix_i^2=x_i, which never raises the degree.

Let deg⁡(f)\deg(f) be the degree of the unique multilinear polynomial equal to ff on {0,1}N\{0,1\}^N, and the approximate degree deg⁡~(f)\widetilde{\deg}(f) the least degree of a real polynomial pp with ∣p(x)−f(x)∣≤13\abs{p(x)-f(x)}\le\frac13 for every input. The lemma gives at once

QE(f) ≥ 12deg⁡(f),Q2(f) ≥ 12 deg⁡~(f).Q_E(f)\ \ge\ \tfrac12\deg(f),\qquad\qquad Q_2(f)\ \ge\ \tfrac12\,\widetilde{\deg}(f).
Predict before you look

What is the bounded-error quantum query complexity of the parity of N=64N=64 bits?

Show the answer

32 queries

N/2=32N/2=32: Deutsch's algorithm on each of the 32 pairs, and the polynomial method shows nothing does better, even with bounded error. A speedup of only a factor of 2.

Search needs √N: the approximate degree of OR

DerivationLower bound via Markov's inequality
  1. q(0)≤13,q(k)≥23  (1≤k≤N),0≤q(k)≤1  (k=0,…,N)q(0)\le\tfrac13,\qquad q(k)\ge\tfrac23\ \ (1\le k\le N),\qquad 0\le q(k)\le1\ \ (k=0,\dots,N)

    Symmetrize the acceptance polynomial of a TT-query algorithm for OR. The univariate qq has degree d≤2Td\le 2T and is controlled only at the integers 0,…,N0,\dots,N.

  2. h:=max⁡t∈[0,N]∣q′(t)∣ ≥ 13h:=\max_{t\in[0,N]}\abs{q'(t)}\ \ge\ \tfrac13

    Mean value theorem on [0,1][0,1]: qq rises by at least 13\frac13 there.

  3. max⁡t∈[0,N]∣q(t)−12∣ ≤ 12+h2\max_{t\in[0,N]}\Big|q(t)-\tfrac12\Big|\ \le\ \tfrac12+\tfrac{h}{2}

    Every real t∈[0,N]t\in[0,N] lies within 12\frac12 of an integer kk with ∣q(k)−12∣≤12\abs{q(k)-\frac12}\le\frac12, and moving from kk to tt changes qq by at most h/2h/2.

  4. h ≤ 2d2N max⁡[0,N]∣q−12∣ ≤ d2N (1+h)h\ \le\ \frac{2d^2}{N}\,\max_{[0,N]}\Big|q-\tfrac12\Big|\ \le\ \frac{d^2}{N}\,(1+h)

    Markov brothers' inequality: a degree-dd polynomial on an interval of length NN satisfies max⁡∣p′∣≤2d2Nmax⁡∣p∣\max\abs{p'}\le\frac{2d^2}{N}\max\abs{p}. Apply it to p=q−12p=q-\frac12.

  5. d2 ≥ N h1+h ≥ N4⟹T ≥ d2 ≥ N4d^2\ \ge\ N\,\frac{h}{1+h}\ \ge\ \frac N4\qquad\Longrightarrow\qquad T\ \ge\ \frac d2\ \ge\ \frac{\sqrt N}{4}

    h/(1+h)h/(1+h) increases with hh, and h≥13h\ge\frac13 gives 14\frac14. Every bounded-error search algorithm makes at least N/4\sqrt N/4 queries.

The matching upper bound is Grover's algorithm (plus one final query to verify the candidate), and Chebyshev polynomials achieve degree O(N)O(\sqrt N) directly. Paturi (1992) determined the approximate degree of every symmetric Boolean function.

Check your understanding

What is the exact quantum query complexity QE(ORN)Q_E(\mathrm{OR}_N): deciding with certainty whether some bit is 11?

  1. ⌈π4N ⌉\lceil\frac{\pi}{4}\sqrt N\,\rceil
  2. N/2N/2
  3. NN
  4. log⁡2N\log_2 N
Show the answer

C. NN

An exact algorithm must reject every x≠0Nx\ne0^N with probability 00, so every rejecting amplitude αk(x)\alpha_k(x) vanishes off 0N0^N, while some is nonzero at 0N0^N. The only multilinear polynomials vanishing on {0,1}N∖{0N}\{0,1\}^N\setminus\{0^N\} are multiples of ∏i(1−xi)\prod_i(1-x_i), of degree NN. So T≥NT\ge N: exact search has no quantum speedup. Grover's speedup needs a little error.

The adversary method

The polynomial method constrains what the output can look like. The adversary method instead tracks how quickly queries can make the final states for different inputs distinguishable.

For search, take X={0N}X=\{0^N\}, Y={e1,…,eN}Y=\{e_1,\dots,e_N\} and relate everything: m=Nm=N and m′=ℓ=ℓ′=1m'=\ell=\ell'=1, so Q2(ORN)=Ω(N)Q_2(\mathrm{OR}_N)=\Omega(\sqrt N), another proof of Grover's optimality. For parity, relate inputs at Hamming distance 11: m=m′=Nm=m'=N and ℓ=ℓ′=1\ell=\ell'=1, so Ω(N)\Omega(N).

Neither method dominates. Positive-weight adversary bounds are capped by certificate complexity (about C0(f)C1(f)\sqrt{C_0(f)C_1(f)} for total functions), hence at O(N)O(\sqrt N) for element distinctness, whose true complexity is Θ(N2/3)\Theta(N^{2/3}): the lower bound came from the polynomial method (Aaronson & Shi 2004), the algorithm from a quantum walk (Ambainis 2007). Conversely, some functions have quantum query complexity polynomially larger than their approximate degree (Ambainis 2006).

How large can quantum speedups be?

Proof idea: block sensitivity satisfies deg⁡~(f)=Ω(bs(f))\widetilde{\deg}(f)=\Omega\big(\sqrt{bs(f)}\big) (Nisan–Szegedy), so Q2(f)=Ω(bs(f))Q_2(f)=\Omega\big(\sqrt{bs(f)}\big), while classically D(f)≤C(f) bs(f)≤bs(f)3D(f)\le C(f)\,bs(f)\le bs(f)^3. Combining, D(f)≤bs(f)3=O(Q2(f)6)D(f)\le bs(f)^3=O(Q_2(f)^6). Exponential separations, such as Simon's and Shor's, therefore require a promise on the input.

Key takeaways

  • After TT queries the amplitudes are polynomials of degree ≤T\le T, so Q2(f)≥deg⁡~(f)/2Q_2(f)\ge\widetilde{\deg}(f)/2 and QE(f)≥deg⁡(f)/2Q_E(f)\ge\deg(f)/2.
  • Symmetrization plus approximation theory gives Q2(PARN)=N/2Q_2(\mathrm{PAR}_N)=N/2 and Q2(ORN)=Θ(N)Q_2(\mathrm{OR}_N)=\Theta(\sqrt N); exact OR needs all NN queries.
  • The adversary method bounds how fast queries can separate the states of related inputs; its negative-weight version characterizes Q2Q_2 up to constants.
  • For total functions quantum query speedups are polynomial (D=O(Q24)D=O(Q_2^4), tight); exponential speedups need promises.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A TT-query quantum algorithm accepts input xx with probability P(x)P(x). As a multilinear polynomial in xx, PP has degree at most

  1. TT
  2. 2T2T
  3. T2T^2
  4. 2T2^T
Show the answer

B. 2T2T

Each query raises the degree of the amplitudes by at most one, so amplitudes have degree ≤T\le T, and probabilities, being sums of squared moduli, have degree ≤2T\le 2T.

Question 2

Why is Q2(PARN)≥N/2Q_2(\mathrm{PAR}_N)\ge N/2?

  1. Parity is not symmetric, so symmetrization fails
  2. Each query reveals one bit, and parity depends on all NN bits
  3. A symmetrized polynomial approximating parity must cross 12\tfrac12 between every two consecutive weights, so its degree is at least NN
  4. Parity is NP-hard
Show the answer

C. A symmetrized polynomial approximating parity must cross 12\tfrac12 between every two consecutive weights, so its degree is at least NN

The symmetrized polynomial qq satisfies q(k)≥23q(k)\ge\frac23 for odd kk and ≤13\le\frac13 for even kk, so q−12q-\frac12 has NN roots in [0,N][0,N]. Hence deg⁡~=N\widetilde{\deg}=N and Q2≥N/2Q_2\ge N/2.

Question 3

Simon's problem has an exponential quantum query speedup, yet D(f)=O(Q2(f)6)D(f)=O(Q_2(f)^6). Why is there no contradiction?

  1. Simon's bound counts time, not queries
  2. The Q26Q_2^6 theorem applies only to exact algorithms
  3. The polynomial method does not apply to Simon's oracle
  4. Simon's problem is a partial function (a promise problem); the theorem is about total functions
Show the answer

D. Simon's problem is a partial function (a promise problem); the theorem is about total functions

The polynomial relation uses that ff is defined on every input, through block sensitivity and certificates. Promise problems escape it, which is why every known exponential query speedup comes with a promise.

Question 4

Apply Ambainis's bound to search with X={0N}X=\{0^N\}, Y={e1,…,eN}Y=\{e_1,\dots,e_N\} and R=X×YR=X\times Y. What do you get?

  1. m=Nm=N, m′=1m'=1, ℓ=ℓ′=1\ell=\ell'=1, hence Ω(N)\Omega(\sqrt N)
  2. m=m′=Nm=m'=N, ℓ=ℓ′=1\ell=\ell'=1, hence Ω(N)\Omega(N)
  3. m=1m=1, m′=Nm'=N, ℓ=N\ell=N, hence Ω(1)\Omega(1)
  4. m=m′=1m=m'=1, hence Ω(1)\Omega(1)
Show the answer

A. m=Nm=N, m′=1m'=1, ℓ=ℓ′=1\ell=\ell'=1, hence Ω(N)\Omega(\sqrt N)

0N0^N is related to all NN unit vectors (m=Nm=N), each eie_i only to 0N0^N (m′=1m'=1). For a fixed index ii, only eie_i differs from 0N0^N at ii (ℓ=1\ell=1), and eie_i differs from its only partner at a single index (ℓ′=1\ell'=1). So mm′/(ℓℓ′)=N\sqrt{mm'/(\ell\ell')}=\sqrt N.

Further reading

  • R. Beals, H. Buhrman, R. Cleve, M. Mosca & R. de Wolf, "Quantum lower bounds by polynomials", J. ACM 48, 778–797 (2001); conference version FOCS 1998.
  • A. Ambainis, "Quantum lower bounds by quantum arguments", J. Comput. Syst. Sci. 64, 750–767 (2002); conference version STOC 2000.
  • E. Farhi, J. Goldstone, S. Gutmann & M. Sipser, "A limit on the speed of quantum computation in determining parity", Phys. Rev. Lett. 81, 5442 (1998).
  • N. Nisan & M. Szegedy, "On the degree of Boolean functions as real polynomials", Computational Complexity 4, 301–313 (1994).
  • H. Buhrman & R. de Wolf, "Complexity measures and decision tree complexity: a survey", Theoretical Computer Science 288, 21–43 (2002).