  In this work we explore a correspondence between quantum circuits and
low-degree polynomials over the finite field F_2. Any quantum circuit made up
of Hadamard, Z, controlled-Z and controlled-controlled-Z gates gives rise to a
degree-3 polynomial over F_2 such that calculating quantum circuit amplitudes
is equivalent to counting zeroes of the corresponding polynomial. We exploit
this connection, which is especially clean and simple for this particular gate
set, in two directions. First, we give proofs of classical hardness results
based on quantum circuit concepts. Second, we find efficient classical
simulation algorithms for certain classes of quantum circuits based on
efficient algorithms for classes of polynomials.
