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 queries, every amplitude of a quantum algorithm is a polynomial of degree at most in the input bits, so every acceptance probability is a polynomial of degree at most . If an algorithm computes with error at most 1/3, that polynomial approximates to within 1/3 on every input. So , where 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 and 1 otherwise. A polynomial must jump from 0 to near 1 between and , then stay flat out to . Chebyshev polynomials grow fastest just outside , so they do it best. With 36 and degree 4, the plate draws . Its error is , below 1/3 once is about . A linear program finds the true optimum: approximate degree 2, 3, 4, 6, 7 for = 9, 16, 25, 64, 100, about . Either way degree grows as , so search needs queries: Grover is optimal. For PARITY the polynomial must alternate at every weight, needing degree , so . 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 again. The two methods are complementary: the 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 bound for OR, the bound for parity, and the adversary method with Reichardt’s tightness theorem.
· · ·
Three questions to carry with you.
And one to work out. At least how many quantum queries does PARITY of 100 bits need?
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.