Search papers, labs, and topics across Lattice.
This paper establishes unconditional separations between low-depth quantum circuits and classical language model architectures, demonstrating that certain distributions can be sampled by quantum circuits but not by constant-round diffusion language models, even with advanced features like chain-of-thought reasoning. Additionally, it identifies a function computable by shallow quantum circuits that necessitates a significantly larger transformer model to compute, highlighting the limitations of classical architectures. These findings initiate a new line of inquiry into quantum advantages in the context of large language models, suggesting fundamental differences in computational capabilities.
Quantum circuits can sample distributions that classical language models cannot, revealing a profound computational divide that challenges the supremacy of classical architectures.
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.
