Abstract
A recent line of work has shown the unconditional advantage of constant-depth quantum computation, or QNC⁰, over NC⁰, AC⁰, 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 QNC⁰ can be used to help compute parity itself. We study AC⁰∘ QNC⁰ -- a hybrid circuit model where AC⁰ operates on measurement outcomes of a QNC⁰ circuit, and conjecture AC⁰∘ QNC⁰ cannot achieve Ω(1) correlation with parity. As evidence for this conjecture, we prove: When the QNC⁰ circuit is ancilla-free, this model achieves only negligible correlation with parity. 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 QNC⁰ circuit is given arbitrary quantum advice. By known results this confirms the conjecture for linear-size AC⁰ circuits. Towards a switching lemma for AC⁰∘ QNC⁰, 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 DTdepth[f]. Our results suggest that while QNC⁰ 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.