First Unconditional Proof That Constant-Depth Quantum Circuits Can Do Things Transformers and Diffusion LMs Provably Cannot

arXiv 2608.03962·medium signalXBlueskyLinkedInCopy link

The paper proves two unconditional separations against the canonical LM tasks of prediction and generation. First, a distribution sampleable by constant-depth QNC^0 circuits that no constant-round diffusion language model with shallow scheduling and denoising can sample within constant distance — even given sublinear chain-of-thought and token revision/remasking, the exact features modern DLMs depend on. Second, a function in O(log log n)-depth QNC^0 followed by one AND gate that forces any constant-depth decoder-only transformer computing it to have width n^Ω(1).