We have some quantum circuit $C$ with $k$ ancillae and $n$ input bits of depth $d$ and size $s$, and we can define a function $f$ which, for any $x \in \{0, 1\}^n$, is the random variable which is the first bit of output from $C|x, 0^k\rangle$, i.e. $Pr(f(x) = 1) = |(C|x, 0^k\rangle)_0|^2$. We define the sensitivity of this function at $x$ as $s(f, x) = \sum_{y : ham(x, y) = 1} |Pr(f(x) = 1) - Pr(f(y) = 1)|$ and the average sensitivity $S(f) = \mathbb{E_x[s(f, x)]}$. We know by an extension of Boppana's 97 paper on the average sensitivity of circuits to probabilistic classical circuits (those which we can compare these to), that these have average sensitivity $O(log(s))^{d-1}$. I think exploring the average sensitivity of these quantum circuits would be a nice way to resolve some of the open problems stated here.

My intuition is that the average sensitivity will be higher than in the classical case, but still lower than the maximal average sensitivity which one gets for parity, showing that $QAC_{wf}^k \neq QAC^k$.

I'd be quite satisfied with approaches to use or just interesting discussions of this as answers, as I don't expect for someone to actually resolve this here.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.