A theoretical separation between quantum computers & LLMs

IBM Research has drawn a new line between quantum computing and large language models. In a recent arXiv paper, the team says shallow quantum circuits can solve one functional problem and one sampling problem that restricted LLM-style models cannot handle efficiently.

The work sits in a long-running theoretical effort: compare quantum systems not against unlimited classical machines, which can simulate almost anything given enough resources, but against tighter classical models. IBM points back to a 2018 Science result from Sergey Bravyi, David Gosset, and Robert König showing that constant-depth quantum circuits could crack search problems that comparable constant-depth classical circuits could not. This new paper pushes that idea toward models that look more like modern AI.

On the functional side, the team studies decoder-only transformers, the architecture behind systems including GPT, Claude, and Llama. The target problem is iterated index, a chained lookup task where one entry points to another and another after that. IBM says previous work had already shown transformers need substantial resources here. The new result is the quantum half: a close-to-constant-depth circuit, plus a single classical AND gate, can solve it. The authors also say that depth cannot be meaningfully reduced further.

The second result is about distributional output rather than a single correct answer. Here the paper focuses on diffusion language models and a parity-sampling problem. IBM says earlier lower bounds did not cover models with chain-of-thought, which can expose intermediate steps and make a model more capable. Their proof says even with some chain-of-thought, a diffusion language model still cannot efficiently match the distribution produced by the shallow quantum circuit.

None of this is a claim about near-term products. The paper is explicit that today’s quantum hardware is noisy and small, while current LLMs run on much larger and more mature systems. The point is asymptotic: there are tasks where shallow quantum circuits have an inherent advantage over the LLM models studied here. IBM says the hope is that these theoretical separations eventually help define benchmarks for quantum systems and AI.