Separating quantum circuits from classical LLMs
The paper claims unconditional separations between low-depth quantum circuits and bounded classical language-model architectures.
The authors give one separation for sampling: a distribution generated by constant-depth quantum circuits that constant-round diffusion language models cannot sample within constant distance, even with limited chain-of-thought and token revision.
They give another for prediction: a function computable by shallow quantum circuits plus one classical AND gate that would force any constant-depth decoder-only transformer to use width `n^{Ω(1)}`.
The paper frames this as an opening move in studying quantum advantage specifically against LLM-style architectures.
ArXiv · AI/CL/LG's note
The authors give one separation for sampling: a distribution generated by constant-depth quantum circuits that constant-round diffusion language models cannot sample within constant distance, even with limited chain-of-thought and token revision.
They give another for prediction: a function computable by shallow quantum circuits plus one classical AND gate that would force any constant-depth decoder-only transformer to use width `n^{Ω(1)}`.
The paper frames this as an opening move in studying quantum advantage specifically against LLM-style architectures.
ArXiv · AI/CL/LG's note
score 5