Demonstrating a theoretical separation between quantum computers and large language models

For which computational problems will quantum approaches outperform classical ones, and by exactly how much? Answering these questions is one of the most important goals in modern theoretical computer science. However, proving theoretical limits on the capabilities of classical computing models is exceedingly challenging, since many idealized classical models can simulate arbitrary Turing machines given enough resources. Instead, we pit quantum computation against more limited computational models — such as certain restricted versions of large language models (LLMs).

Our research follows a line of work on shallow quantum circuits; namely, circuits in which the depth of the circuit remains constant as the number of qubits increases. A landmark result by IBM researchers Sergey Bravyi, David Gosset, and Robert König, published in Science in 2018, showed that a certain model of constant-depth quantum circuits can solve specific search problems that no comparable constant-depth classical circuit can solve. Since then, researchers have steadily strengthened this result, proving various notions of a quantum separation versus increasingly expressive models of classical computation. Within this line of work, the classical opponent has become increasingly powerful, while the quantum side has remained remarkably shallow.

Given the success and ubiquity of LLMs in computational tasks today, we were naturally interested in whether there was a theoretical separation between shallow quantum circuits and LLMs. Specifically, our work sought such separations for two basic types of computational problems:

• Functional separations: computing the value of a function, i.e., returning the correct output for a given input, such as retrieving a specific piece of information in response to a prompt.
• Sampling separations: given an input, generating an output according to a desired probability distribution — for example, producing new text or images in response to a prompt.

Our recent work, posted on arXiv, proves the existence of one problem in each of these classes for which shallow quantum circuits have a provable advantage over LLMs. These are, of course, theoretical rather than immediately practical or implementable results. Current large language models run on far more mature and much larger computational resources than the noisy, smaller-scale quantum computers available today.

Nevertheless, our work demonstrates what is possible at scale as quantum technology advances. In particular, we prove that there are computational tasks for which shallow quantum circuits have an inherent advantage over LLMs; we hope these insights open the door to developing concrete benchmarks that compare quantum systems and LLMs on these hard problems.

A separation between shallow quantum circuits and LLMs for a functional problem

Functional problems arise in everyday uses of LLMs, ranging from search to messaging apps. LLMs typically solve these problems using a core architecture called a transformer. Given raw input data, a transformer tokenizes the input, embeds the resulting tokens as a sequence of vectors, and then repeatedly re-weights those vectors across multiple layers, using learned parameters and a scaled dot-product mechanism called attention to capture relationships between tokens.

Specifically, our work focuses on decoder-only transformers, which power many prominent LLMs today (including GPT, Claude, and Llama). This architecture is commonly used in autoregressive language models: given an input prompt, the model generates new tokens sequentially, producing the desired output.

Previous work on the computational complexity of transformers had already identified problems that require substantial computational resources. One such problem is the so-called iterated index function.

Imagine looking up an entry in the index at the back of a book — but instead of pointing you to a page in the same book, the entry points you to an index entry in a second book. That entry, in turn, points to an index entry in a third book, and so on. The iterated index problem asks where you end up after following this chain of references through many successive books.

Adapting this existing result gave us the classical half of a potential separation: a lower bound showing that transformers need sufficiently large computational resources to solve the iterated index problem. To complete the separation, what remained was to show a corresponding upper bound, namely, to show that this problem is solvable by shallow quantum circuits.

We showed, indeed, that the problem is solvable by a close-to-constant-depth quantum circuit equipped with a single classical AND gate. We also showed that this depth cannot be meaningfully improved (e.g., it cannot be made truly constant).

Image caption: Illustration of a shallow quantum circuit computing the index function (looking up a bit in a data table). This forms a building block for our separation between quantum circuits and bounded-resource transformers. Inset $\mathcal{A}^j$ are parallel short-depth circuits which checks each possible index and returns the bit at the matching address in the data table.

A separation between shallow quantum circuits and LLMs for a distributional problem

Distributional problems represent another fundamental use case for today’s large language models. Rather than producing a single correct answer as in a functional problem, the goal here is to generate one of many possible outputs according to a desired probability distribution. The best-known examples of distributional problems arise in image generation, addressed today by diffusion models such as DALL·E or Stable Diffusion.

Our paper explores diffusion language models (DLMs), which are trained by “corrupting” text with random noise, and then teaching them to recover the original text by reversing the corruption process step by step, iteratively revealing tokens. At test time, given a prompt, these models begin with random noise and iteratively remove it until they produce an output in the desired form.

We once again turned to previous classical work, which had studied a problem called parity-sampling — a problem similar to the one used by Bravyi et al. to compare quantum and classical shallow circuits in 2018. This is a problem that is “hard” for diffusion models alone, and can be described as follows. Given a string of 0s and 1s, one can ask for its parity — whether it has an even or an odd number of 1s.

This problem has a straightforward quantum approach using a constant-depth quantum circuit: using properties like entanglement and interference, one can predict the parity of an unknown string, and thereby efficiently sample strings with a specified parity. But how do classical models fare?

Previous work on diffusion language models had already shown limitations on how well they could solve a version of this sampling problem. However, those results did not cover DLMs equipped with chain-of-thought, the ability to “show their work” by generating and consuming intermediate tokens, which has generally been shown to make a model significantly more powerful.

Our goal was to extend the classical lower bound to this stronger model. We proved that even when a diffusion language model is given access to some amount of chain-of-thought, it still cannot efficiently reproduce the distribution generated by the shallow quantum circuit. This yields our second separation: this time, for a sampling problem rather than a functional problem.

Where do we go from here?

Our work is firmly theoretical and consists of mathematical proofs. We must acknowledge that today’s 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 an unprecedented scale.

Indeed, our work does not identify the exact scale at which quantum systems will outperform these classical LLMs for the specific problems studied — only that asymptotically, quantum circuits will outperform LLMs when the two are compared directly.

We believe that work like ours helps underpin efforts to build quantum computers. Over the past decade or so, researchers have found problems for which shallow quantum circuits could overtake increasingly powerful models of classical computing. We hope to continue pushing that frontier.

For what problems do shallow quantum circuits beat more powerful models beyond LLMs? How do less restricted quantum circuits compare? Ultimately, our goal is to map the full landscape of unconditional separations between fully general quantum and classical computation — but that holy grail remains a long way off.

In the meantime, this work should continue to motivate the development of algorithms and applications for quantum computing — especially given the existence of problems beyond the reach of the LLM models studied here, but tractable even by limited models of fault-tolerant quantum computing.

This also raises a broader possibility: rather than viewing quantum computers and LLMs only as competitors, perhaps quantum computation could eventually augment classical AI systems, allowing them to solve tasks that would otherwise require substantially greater computational resources. This work helps understand the distinctions between quantum computing and artificial intelligence, making us optimistic about a future with fully-realized quantum-classical hybrid models of computation.