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.

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…