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 queries, parity needs , 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 -query algorithm's acceptance probability is a polynomial of degree at most .
- Derive and 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
For partial functions (promise problems) the gaps can be enormous: Simon's problem, or forrelation, with quantum query versus classical ones (Aaronson & Ambainis 2015). For total functions, defined on all of , they turn out to be at most polynomial. Proving such statements needs lower-bound techniques, and there are two great families.
The polynomial method
Before any query the amplitudes do not depend on .
A query flips exactly when . New amplitudes are linear in the old ones with coefficients of degree in , so the degree rises by at most .
Input-independent unitaries form linear combinations with constant coefficients.
Real and imaginary parts are real polynomials of degree , so has degree . Multilinearize with , which never raises the degree.
Let be the degree of the unique multilinear polynomial equal to on , and the approximate degree the least degree of a real polynomial with for every input. The lemma gives at once
What is the bounded-error quantum query complexity of the parity of bits?
Show the answer
32 queries
: 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
Symmetrize the acceptance polynomial of a -query algorithm for OR. The univariate has degree and is controlled only at the integers .
Mean value theorem on : rises by at least there.
Every real lies within of an integer with , and moving from to changes by at most .
Markov brothers' inequality: a degree- polynomial on an interval of length satisfies . Apply it to .
increases with , and gives . Every bounded-error search algorithm makes at least queries.
The matching upper bound is Grover's algorithm (plus one final query to verify the candidate), and Chebyshev polynomials achieve degree directly. Paturi (1992) determined the approximate degree of every symmetric Boolean function.
What is the exact quantum query complexity : deciding with certainty whether some bit is ?
Show the answer
C.
An exact algorithm must reject every with probability , so every rejecting amplitude vanishes off , while some is nonzero at . The only multilinear polynomials vanishing on are multiples of , of degree . So : 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 , and relate everything: and , so , another proof of Grover's optimality. For parity, relate inputs at Hamming distance : and , so .
Neither method dominates. Positive-weight adversary bounds are capped by certificate complexity (about for total functions), hence at for element distinctness, whose true complexity is : 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 (Nisan–Szegedy), so , while classically . Combining, . Exponential separations, such as Simon's and Shor's, therefore require a promise on the input.
Key takeaways
- After queries the amplitudes are polynomials of degree , so and .
- Symmetrization plus approximation theory gives and ; exact OR needs all queries.
- The adversary method bounds how fast queries can separate the states of related inputs; its negative-weight version characterizes up to constants.
- For total functions quantum query speedups are polynomial (, 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.
A -query quantum algorithm accepts input with probability . As a multilinear polynomial in , has degree at most
Show the answer
B.
Each query raises the degree of the amplitudes by at most one, so amplitudes have degree , and probabilities, being sums of squared moduli, have degree .
Why is ?
- Parity is not symmetric, so symmetrization fails
- Each query reveals one bit, and parity depends on all bits
- A symmetrized polynomial approximating parity must cross between every two consecutive weights, so its degree is at least
- Parity is NP-hard
Show the answer
C. A symmetrized polynomial approximating parity must cross between every two consecutive weights, so its degree is at least
The symmetrized polynomial satisfies for odd and for even , so has roots in . Hence and .
Simon's problem has an exponential quantum query speedup, yet . Why is there no contradiction?
- Simon's bound counts time, not queries
- The theorem applies only to exact algorithms
- The polynomial method does not apply to Simon's oracle
- 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 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.
Apply Ambainis's bound to search with , and . What do you get?
- , , , hence
- , , hence
- , , , hence
- , hence
Show the answer
A. , , , hence
is related to all unit vectors (), each only to (). For a fixed index , only differs from at (), and differs from its only partner at a single index (). So .
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).