  We present a computational problem with the following properties: (i) Every
instance can be solved with near-certainty by a constant-depth quantum circuit
using only nearest-neighbor gates in 3D even when its implementation is
corrupted by noise. (ii) Any constant-depth classical circuit composed of
unbounded fan-in AND, OR, as well as NOT gates, i.e., an AC0-circuit, of size
smaller than a certain subexponential, fails to solve a uniformly random
instance with probability greater than a certain constant. Such an advantage
against unbounded fan-in classical circuits was previously only known in the
noise-free case or without locality constraints. We overcome these limitations,
proposing a quantum advantage demonstration amenable to experimental
realizations. Subexponential circuit-complexity lower bounds have traditionally
been referred to as exponential. We use the term colossal since our
fault-tolerant 3D architecture resembles a certain Roman monument.
