Separating Quantum Circuits from Classical LLMs

The paper claims unconditional complexity separations between low-depth quantum circuits and bounded classical language-model architectures. For generation, it constructs a distribution sampleable by constant-depth QNC⁰ circuits but not approximable within constant distance by a constant-round diffusion language model with shallow scheduling, even with sublinear chain-of-thought and token remasking. For prediction, it gives a function in AND ∘ QNC⁰[log log n] for which any constant-depth decoder-only transformer requires width n^{Ω(1)}. These are theoretical results for restricted architecture classes, not evidence that quantum computers outperform deployed LLMs.