Separating quantum circuits from classical LLMs
2026-08-04 • Artificial Intelligence
Artificial IntelligenceComputational Complexity
AI summaryⓘ
The authors show that certain simple quantum computations can do tasks that typical classical large language models, like transformers and diffusion models, cannot do efficiently. They demonstrate a specific example where a small-depth quantum circuit can generate samples that these classical models cannot closely imitate, even with advanced features like revising their output. They also provide a function that quantum circuits with very low depth can compute easily, but classical transformer models would need to be very large to compute. This work suggests quantum models might have fundamental advantages in language tasks compared to current classical models.
Quantum computationQNC^0 circuitsDiffusion language modelsTransformersDistributional separationFunctional separationLow-depth circuitsQuantum advantageLanguage modelsComputational complexity
Authors
Srinivasan Arunachalam, Arkopal Dutt, Hari Krovi, Rik Sengupta
Abstract
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: 1. Distributional separation. We give a distribution that is sampleable by $\textsf{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 ($\textsf{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 $\textsf{DLM}$s rely on. 2. Functional separation. We exhibit a function computable in $\land \circ \textsf{QNC}^0[\log\log n]$ (i.e., a family of O$(\log\log n)$-depth $\textsf{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^{Ω(1)}$. Together, our work initiates the study of quantum advantage in the era of large language models.