Separating Quantum Circuits from Classical LLMs

Modern large language models – transformers and diffusion language models – are built around two canonical algorithmic tasks: *prediction and generation*. We prove unconditional separations between low-depth quantum computation and the corresponding bounded-resource classical language-model architectures in both regimes. Concretely, we exhibit the following: - **Distributional separation.** We give a distribution that is sampleable by ${\text{QNC}}^0$ circuits (i.e., a family of constant-depth quantum circuits consisting of bounded fan-in gates) that no constant-round diffusion language model ($\text{DLM}$) with shallow scheduling and denoising can sample within constant distance, even when allowed sublinear chain-of-thought and output-token revision/remasking events, the very features modern $\text{DLM}$s rely on. - **Functional separation.** We exhibit a function computable in $\wedge \circ {\text{QNC}}^0[\log \log n]$ (i.e., a family of $O(\log \log n)$-depth ${\text{QNC}}^0$ circuits, where $n$ is the input length, followed by a single classical $\mathsf{AND}$ gate) such that any constant-depth decoder-only transformer computing the function must be *large*: it would have to have width $n^{\Omega (1)}$. Together, our work initiates the study of quantum advantage in the era of large language models.