Improved Circuit Lower Bounds With Applications to Exponential Separations Between Quantum and Classical Circuits
<|reference_start|>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^0 that not only contains AC^0 but can--with a single gate--compute functions that require exponential-size TC^0 circuits. His main result was that switching-lemma lower bounds for AC^0 lift to GC^0 with no loss in parameters, even though GC^0 requires exponential-size TC^0 circuits. Informally, GC^0 is AC^0 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^0[p] (GC^0 with MODp gates) and the polynomial method. Specifically, we show that polynomial-method lower bounds for AC^0[p] lift to GC^0[p] with no loss in parameters. As an application, we prove Majority requires depth-d GC^0[p] circuits of size $2^{\Omega(n^{1/2(d-1)})}$, matching the state-of-the-art lower bounds for AC^0[p]. We also show that E^NP requires exponential-size GCC^0 circuits (the union of GC^0[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^0-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^0 circuits, generalizing Raz and Tal's relativized separation of BQP from the polynomial hierarchy.   2. There's a search problem that QNC^0 circuits can solve but average-case hard for exponential-size GC^0 circuits.   3. There's a search problem that QNC^0/qpoly circuits can solve but average-case hard for exponential-size GC^0[p] circuits.   4. There's an interactive problem that QNC^0 circuits can solve but exponential-size GC^0[p] circuits cannot.<|reference_end|>
@article{grewal2024improved,
    title={Improved Circuit Lower Bounds and Quantum-Classical Separations},
    author={Sabee Grewal and Vinayak M. Kumar},
    journal={arXiv preprint arXiv:2408.16406},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.16406},
    primaryClass={quant-ph cs.CC}
}