Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.

Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal

Browse the full STOC paper archive.