  We consider the problem of decoding corrupted error correcting codes with
NC$^0[\oplus]$ circuits in the classical and quantum settings. We show that any
such classical circuit can correctly recover only a vanishingly small fraction
of messages, if the codewords are sent over a noisy channel with positive error
rate. Previously this was known only for linear codes with large dual distance,
whereas our result applies to any code. By contrast, we give a simple quantum
circuit that correctly decodes the Hadamard code with probability
$\Omega(\varepsilon^2)$ even if a $(1/2 - \varepsilon)$-fraction of a codeword
is adversarially corrupted.
  Our classical hardness result is based on an equidistribution phenomenon for
multivariate polynomials over a finite field under biased input-distributions.
This is proved using a structure-versus-randomness strategy based on a new
notion of rank for high-dimensional polynomial maps that may be of independent
interest.
  Our quantum circuit is inspired by a non-local version of the
Bernstein-Vazirani problem, a technique to generate ``poor man's cat states''
by Watts et al., and a constant-depth quantum circuit for the OR function by
Takahashi and Tani.
