  A recent line of work has shown the unconditional advantage of constant-depth
quantum computation, or $\mathsf{QNC^0}$, over $\mathsf{NC^0}$,
$\mathsf{AC^0}$, and related models of classical computation. Problems
exhibiting this advantage include search and sampling tasks related to the
parity function, and it is natural to ask whether $\mathsf{QNC^0}$ can be used
to help compute parity itself. We study $\mathsf{AC^0\circ QNC^0}$ -- a hybrid
circuit model where $\mathsf{AC^0}$ operates on measurement outcomes of a
$\mathsf{QNC^0}$ circuit, and conjecture $\mathsf{AC^0\circ QNC^0}$ cannot
achieve $\Omega(1)$ correlation with parity. As evidence for this conjecture,
we prove:
  $\bullet$ When the $\mathsf{QNC^0}$ circuit is ancilla-free, this model
achieves only negligible correlation with parity.
  $\bullet$ For the general (non-ancilla-free) case, we show via a connection
to nonlocal games that the conjecture holds for any class of postprocessing
functions that has approximate degree $o(n)$ and is closed under restrictions,
even when the $\mathsf{QNC^0}$ circuit is given arbitrary quantum advice. By
known results this confirms the conjecture for linear-size $\mathsf{AC^0}$
circuits.
  $\bullet$ Towards a switching lemma for $\mathsf{AC^0\circ QNC^0}$, we study
the effect of quantum preprocessing on the decision tree complexity of Boolean
functions. We find that from this perspective, nonlocal channels are no better
than randomness: a Boolean function $f$ precomposed with an $n$-party nonlocal
channel is together equal to a randomized decision tree with worst-case depth
at most $\mathrm{DT}_\mathrm{depth}[f]$.
  Our results suggest that while $\mathsf{QNC^0}$ is surprisingly powerful for
search and sampling tasks, that power is "locked away" in the global
correlations of its output, inaccessible to simple classical computation for
solving decision problems.
