arXiv paper: Separating quantum circuits from classical LLMs

A new arXiv paper by Srinivasan Arunachalam, Arkopal Dutt, Hari Krovi, and a fourth co-author proves unconditional separations between low-depth quantum circuits and classical transformer and diffusion language models. The authors show a distribution that a constant-depth quantum circuit (QNC⁰) can sample, but which no constant-round diffusion language model—even with sublinear chain-of-thought and token remasking—can approximate within constant distance. They also present a function that a quantum circuit of depth O(log log n) followed by a single AND gate can compute, while any constant-depth decoder-only transformer would need width growing polynomially with input length. The work establishes the first rigorous quantum advantage in the context of modern large language models.