Improved Circuit Lower Bounds With Applications to Exponential Separations Between Quantum and Classical Circuits

Kumar used a switching lemma to prove exponential-size lower bounds for a circuit class GC⁰ that not only contains AC⁰ but can--with a single gate--compute functions that require exponential-size TC⁰ circuits. His main result was that switching-lemma lower bounds for AC⁰ lift to GC⁰ with no loss in parameters, even though GC⁰ requires exponential-size TC⁰ circuits. Informally, GC⁰ is AC⁰ with unbounded-fan-in gates that behave arbitrarily inside a sufficiently small Hamming ball but must be constant outside it. We show an analogous result for GC⁰p (GC⁰ with MODp gates) and the polynomial method. Specifically, we show that polynomial-method lower bounds for AC⁰p lift to GC⁰p with no loss in parameters. As an application, we prove Majority requires depth-d GC⁰p circuits of size 2^ (n^{1/2 (d-1) ) }, matching the state-of-the-art lower bounds for AC⁰p. We also show that ENP requires exponential-size GCC⁰ circuits (the union of GC⁰m for all m), extending the result of Williams. It is striking that the switching lemma, polynomial method, and algorithmic method all generalize to GC⁰-related classes, with the first two methods doing so without any loss. We also establish the strongest known unconditional separations between quantum and classical circuits: 1. There's an oracle relative to which BQP is not contained in the class of languages decidable by uniform families of size-2^n^{O (1) } GC⁰ circuits, generalizing Raz and Tal's relativized separation of BQP from the polynomial hierarchy. 2. There's a search problem that QNC⁰ circuits can solve but average-case hard for exponential-size GC⁰ circuits. 3. There's a search problem that QNC⁰/qpoly circuits can solve but average-case hard for exponential-size GC⁰p circuits. 4. There's an interactive problem that QNC⁰ circuits can solve but exponential-size GC⁰p circuits cannot.