130
Part Three · C · Complexity and cryptography

Lower bounds: polynomial and adversary methods

Proving that an algorithm exists is a matter of finding it. Proving that no faster algorithm exists, including every clever idea nobody has had yet, needs a different kind of argument. In the query model, where cost is the number of times you look at the input, quantum lower bounds can actually be proved. Two methods dominate: one turns algorithms into polynomials, the other tracks how fast an algorithm can tell inputs apart. Together they show that Grover’s search is optimal and that quantum computers cannot compute parity faster than halfway.

On the plate: a polynomial trying to imitate the OR function.

The polynomial method

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca and Ronald de Wolf observed in 1998 that after TT queries, every amplitude of a quantum algorithm is a polynomial of degree at most TT in the input bits, so every acceptance probability is a polynomial of degree at most 2T2T. If an algorithm computes ff with error at most 1/3, that polynomial approximates ff to within 1/3 on every input. So T≥deg⁡~(f)/2T \ge \widetilde{\deg}(f)/2, where deg⁡~\widetilde{\deg} is the approximate degree. For symmetric functions, Minsky and Papert’s symmetrization reduces this to a polynomial in one variable, the number of 1s in the input. Established

Imitating OR

OR is 0 when the Hamming weight ∣x∣=0|x| = 0 and 1 otherwise. A polynomial must jump from 0 to near 1 between ∣x∣=0|x| = 0 and ∣x∣=1|x| = 1, then stay flat out to NN. Chebyshev polynomials grow fastest just outside [−1,1][-1, 1], so they do it best. With N=N = 36 and degree d=d = 4, the plate draws p(w)=1−Td(N−wN−1)/Td(NN−1)p(w) = 1 - T_d\big(\tfrac{N-w}{N-1}\big)/T_d\big(\tfrac{N}{N-1}\big). Its error is 1/Td(1+1N−1)1/T_d(1 + \tfrac{1}{N-1}), below 1/3 once dd is about 1.25N1.25\sqrt N. A linear program finds the true optimum: approximate degree 2, 3, 4, 6, 7 for NN = 9, 16, 25, 64, 100, about 0.7N0.7\sqrt N. Either way degree grows as N\sqrt N, so search needs Ω(N)\Omega(\sqrt N) queries: Grover is optimal. For PARITY the polynomial must alternate at every weight, needing degree NN, so T≥N/2T \ge N/2. Established

The adversary method

Andris Ambainis introduced in 2000 a different argument. Imagine an adversary holding a superposition of inputs that the algorithm must tell apart, such as “no marked item” against “one marked item, somewhere”. Each query can increase the distinguishability of the paired states by only a bounded amount; total distinguishability must reach a constant; so the number of queries is bounded below. For search this gives Ω(N)\Omega(\sqrt N) again. The two methods are complementary: the Ω(N2/3)\Omega(N^{2/3}) bound for element distinctness came from the polynomial method, through Scott Aaronson and Yaoyun Shi’s 2004 collision bound, where the basic adversary method falls short. Peter Høyer, Troy Lee and Robert Špalek added negative weights in 2007, the generalized adversary; Ben Reichardt proved in 2009 that it is tight: for every function, it equals the true quantum query complexity up to a constant. Lower bounds in the query model are therefore, in principle, completely understood. Established

What you now have

Queries as polynomials, approximate degree, symmetrization, Chebyshev constructions and the N\sqrt N bound for OR, the N/2N/2 bound for parity, and the adversary method with Reichardt’s tightness theorem.

· · ·

Three questions to carry with you.

Why is the acceptance probability a polynomial of degree ≤ 2T?tap
Each query multiplies amplitudes by input-dependent signs, raising their degree by one; probabilities are squares.
Why does OR need degree about √N?tap
A bounded polynomial jumping sharply near the edge of its range must have degree ~√N, by Chebyshev extremality.
What did Reichardt prove?tap
The generalized adversary bound equals quantum query complexity up to a constant factor.

And one to work out. At least how many quantum queries does PARITY of 100 bits need?

T ≥

Sources: R. Beals et al., J. ACM 48, 778 (2001). A. Ambainis, J. Comput. Syst. Sci. 64, 750 (2002). P. Høyer, T. Lee and R. Špalek, Proc. 39th ACM STOC, 526 (2007). B. W. Reichardt, Proc. 50th IEEE FOCS, 544 (2009). S. Aaronson and Y. Shi, J. ACM 51, 595 (2004). R. de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415 (v5). Checked by code: linear-programming approximate degree of OR at error 1/3; Chebyshev construction degrees 4, 5, 7, 10, 13 for N = 9, 16, 25, 64, 100.

Next · Chapter 131
Verification of quantum computation

If a quantum computer gives you an answer you can't check, how do you know it didn't lie?

Turn the page