  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$^0$)
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 $\oplus$L-hard problems. This implies a more
powerful class of constant-depth classical circuits (e.g., AC$^0[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$^0$ interactive tasks on $2 \times n$ and $1 \times n$ grids which require
classical simulations of power NC$^1$ and AC$^{0}[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.
