Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond

Recent work of Bravyi et al. and follow-up work by Bene Watts et al. demonstrates a quantum advantage for shallow circuits: constant-depth quantum circuits can perform a task which constant-depth classical i.e., AC$⁰$ circuits cannot. Their results have the advantage that the quantum circuit is fairly practical, and their proofs are free of hardness assumptions (e.g., factoring is classically hard, etc.). Unfortunately, constant-depth classical circuits are too weak to yield a convincing real-world demonstration of quantum advantage. We attempt to hold on to the advantages of the above results, while increasing the power of the classical model. Our main result is a two-round interactive task which is solved by a constant-depth quantum circuit (using only Clifford gates, between neighboring qubits of a 2D grid, with Pauli measurements), but such that any classical solution would necessarily solve oplusL-hard problems. This implies a more powerful class of constant-depth classical circuits e.g., AC$⁰[p]$ for any prime $p$ unconditionally cannot perform the task. Furthermore, under standard complexity-theoretic conjectures, log-depth circuits and log-space Turing machines cannot perform the task either. Using the same techniques, we prove hardness results for weaker complexity classes under more restrictive circuit topologies. Specifically, we give QNC⁰ interactive tasks on 2 times n and 1 times n grids which require classical simulations of power NC¹ and AC⁰[6], respectively. Moreover, these hardness results are robust to a small constant fraction of error in the classical simulation. We use ideas and techniques from the theory of branching programs, quantum contextuality, measurement-based quantum computation, and Kilian randomization.