IBM Research Proves Quantum Circuits Outperform LLMs on Two Problems

IBM Research on September 15, 2026, published an account of work proving unconditional theoretical separations between shallow quantum circuits and large language models: one functional problem and one sampling problem for which shallow quantum circuits hold a provable advantage over LLMs.

The post’s byline lists Srinivasan Arunachalam, Arkopal Dutt, Hari Krovi, Rik Sengupta, and Ryan Mandelbaum. It describes the paper “Separating quantum circuits from classical LLMs,” by Arunachalam, Dutt, Krovi, and Sengupta, which was posted on arXiv on August 4, 2026, and runs 60 pages with six figures. The abstract frames the work as initiating the study of quantum advantage in the era of large language models. The authors describe the results as theoretical rather than immediately practical, pointing to the gap between the mature, large-scale hardware behind modern LLMs and the error-prone quantum computers currently available.

A Research Line From 2018 to LLMs

The work follows a line of research on shallow quantum circuits, in which a circuit’s depth remains constant as the number of qubits increases. A 2018 result published in Science by IBM researchers Sergey Bravyi, David Gosset, and Robert König showed that a certain model of constant-depth quantum circuits can solve specific search problems that no comparable constant-depth classical circuit can solve. In the years since, researchers have steadily strengthened that separation against increasingly expressive models of classical computation, while the quantum side has remained shallow, according to the post.

Given the ubiquity of LLMs in computational tasks, the authors sought separations for two basic types of problems. Functional problems involve computing the value of a function, returning the correct output for a given input, such as fetching a specific piece of information in response to a prompt. Sampling problems involve generating an output according to a desired probability distribution, such as producing new text or images in response to a prompt.

One Functional and One Sampling Separation

Functional Separation: The Iterated Index Function

For the functional case, the paper focuses on decoder-only transformers, the architecture behind many prominent LLMs, including GPT, Claude, and Llama. A transformer tokenizes raw input, embeds the tokens as a sequence of vectors, and repeatedly re-weights those vectors across multiple layers, using learned parameters and a scaled dot-product mechanism called attention. Decoder-only models generate new tokens sequentially in response to a prompt.

Earlier complexity research on transformers had identified the iterated index function as a problem demanding substantial computational resources. The post illustrates it with an index entry at the back of one book that points to an index entry in a second book, which points to an entry in a third, and so on; the problem asks where that chain of references ends after many successive books.

Adapting the earlier result supplied a lower bound showing that solving the iterated index problem demands sufficiently large computational resources from transformers. The authors then showed the problem is solvable by a quantum circuit of close-to-constant depth augmented with a single classical AND gate, and that this depth cannot be made truly constant. The abstract states that the function is computable in O(log log n)-depth QNC^0 circuits with a single classical AND gate applied afterward, whereas any constant-depth decoder-only transformer computing it must have width n^Ω(1).

Sampling Separation: Parity and Diffusion Language Models

The second result concerns distributional problems, whose best-known examples arise in image generation handled by diffusion models such as DALL·E and Stable Diffusion. The paper studies diffusion language models, which are trained by adding random noise to text and learning to undo the corruption one step at a time; at test time, they start from noise and iteratively remove it until the output takes the desired form.

The classical problem here, parity-sampling, is similar to the one Bravyi and his co-authors used to compare quantum and classical shallow circuits in 2018. Given a string of 0s and 1s, parity asks whether the string contains an even or an odd number of 1s. A constant-depth quantum circuit can use entanglement and interference to predict the parity of an unknown string and thereby efficiently sample strings of a specified parity.

Prior work had shown limits on how well diffusion language models could solve a version of this sampling problem, but those results did not cover models equipped with chain-of-thought, in which a model generates and works through intermediate tokens, an ability earlier research has generally found to make models significantly more capable. The authors proved that even when a diffusion language model is given access to some amount of chain-of-thought, it still cannot efficiently match the distribution that the shallow quantum circuit produces. The abstract also states that there is a distribution sampleable by constant-depth QNC^0 circuits which no constant-round diffusion language model using shallow scheduling and denoising can sample within constant distance, even with sublinear chain-of-thought and output-token revision and remasking allowed.

Limitations and Next Directions

The authors describe the work as firmly theoretical, consisting of mathematical proofs. They acknowledge that current quantum computers are limited in their abilities and subject to noise and errors, while classical LLMs have access to state-of-the-art computing hardware at scale. The work identifies no exact scale at which quantum systems will outperform LLMs on the specific problems studied; the authors state only that asymptotically, quantum circuits will outperform LLMs when the two are compared directly.

The authors said they hope the insights pave the way for concrete benchmarks that compare quantum systems and LLMs on these hard problems. Among the open questions they named are which problems separate shallow quantum circuits from models more powerful than LLMs, and how less restricted quantum circuits compare. Their stated long-term goal is to chart the complete landscape of unconditional separations between fully general quantum and classical computation, a goal they describe as remaining a long way off.

In the meantime, they wrote, the work should motivate the development of algorithms and applications for quantum computing, given that some problems lie beyond the reach of the LLM architectures studied while remaining tractable for even limited models of fault-tolerant quantum computing. The authors also raise the possibility that quantum computation could eventually augment classical AI systems, letting them handle tasks that would otherwise demand substantially greater computational resources, and they say they are optimistic about a future of fully realized hybrid quantum-classical computation.