Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ADAM BENE WATTS:
All reports by Author Adam Bene Watts:

TR19-089 | 21st June 2019
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal

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

Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, ... more >>>




ISSN 1433-8092 | Imprint