Sometimes you see quantum popping up everywhere. I just did the opposite and gave a classical talk at a quantum workshop, part of an AMS meeting held at Northeastern University, which poured yet another avalanche of talks onto the Boston area. I spoke about the complexity of distributions, also featured in an earlier post, including a result I posted two weeks ago which gives a boolean function such that the output distribution of any AC circuit has statistical distance from for uniform . In particular, no AC circuit can compute much better than guessing at random *even if the circuit is allowed to sample the input itself. *The slides for the talk are here.

The new technique that enables this result I’ve called *entropy polarization*. Basically, for every AC circuit mapping any number of bits into bits, there exists a small set of restrictions such that:

(1) the restrictions preserve the output distribution, and

(2) for every restriction , the output distribution of the circuit restricted to either has min-entropy or . Whence *polarization*: the entropy will become either very small or very large.

Such a result is useless and trivial to prove with ; the critical feature is that one can obtain a much smaller of size .

Entropy polarization can be used in conjunction with a previous technique of mine that works for high min-entropy distributions to obtain the said sampling lower bound.

It would be interesting to see if any of this machinery can yield a separation between quantum and classical sampling for constant-depth circuits, which is probably a reason why I was invited to give this talk.

Why do most major lower bounds stop at AC0?

Perhaps because a slightly stronger lower bound for AC^0 would imply lower bounds for models which seem extremely powerful, like NC^1 or L.