NTU-IBM Quantum Hub shows shallow circuits beat language models on key tasks

Researchers are shifting the approach to proving quantum superiority by pitting quantum computation against restricted large language models, rather than attempting to surpass fully general Turing machines. Building on a line of work that followed research on shallow quantum circuits, and with Sergey Bravyi, David Gosset, and Robert König’s landmark Science publication in 2018, a team has now demonstrated the existence of one problem in each of two classes for which shallow quantum circuits have a provable advantage over LLMs. The research, recently posted on arXiv, proves shallow quantum circuits possess a provable advantage over LLMs in both functional tasks, like retrieving information as an example of computing the value of a function, and generating outputs based on desired probabilities.

Shallow Quantum Circuits Outperform Transformers on Iterated Index Researchers established a theoretical separation for shallow quantum circuits when solving the iterated index problem, a computational task demanding efficient data retrieval across multiple linked data sources.

The team demonstrated the circuits could solve the problem using a depth that, while not strictly constant, remains close to constant as the size of the data increases, a critical characteristic for scalability. They hope these insights will lead to the development of concrete benchmarks that compare quantum systems and LLMs on these hard problems, and builds on earlier work on shallow quantum circuits. To define the classical challenge, the researchers focused on the iterated index problem; this involves following a chain of references across multiple books, each directing to an index entry in the next. They first established a lower bound showing that transformers, a common architecture for LLMs, require substantial computational resources to accurately navigate this chain of references. This classical lower bound was then paired with their quantum upper bound, proving a theoretical separation; the shallow quantum circuit, equipped with a single classical AND gate, could solve the problem with demonstrably fewer computational steps. The circuit utilizes parallel short-depth circuits to check each possible index. By revisiting this established problem, the researchers aimed to broaden the scope of their comparison, demonstrating that shallow quantum circuits can also outperform LLMs in generating outputs according to a desired probability distribution. Parity-Sampling: Quantum Advantage in Distributional Tasks This builds on earlier work from 2018 by Sergey Bravyi, David Gosset, and Robert König, who demonstrated constant-depth quantum circuits could outperform comparable classical circuits in search problems, providing a historical benchmark for quantum advantage claims. The current findings, recently posted on arXiv, extend this comparison to the realm of artificial intelligence, pitting quantum systems against the architecture powering many modern AI applications. The research focuses on identifying tasks where shallow quantum circuits, circuits with a constant depth regardless of qubit count, inherently outperform LLMs, rather than attempting to surpass the theoretical limits of universal Turing machines. This approach acknowledges the difficulty of definitively proving superiority against unrestricted classical resources, and instead focuses on a practical comparison against a specific, powerful class of models. Parity-sampling was chosen as a test case because of its established difficulty for diffusion models, a type of generative AI. The problem involves calculating the parity, even or odd, of the number of ones within a binary string; a seemingly simple task that presents challenges for certain classical algorithms. These functional separations mirror everyday uses of LLMs, ranging from search engines to messaging applications. The researchers believe that identifying separations across both functional and distributional problems strengthens the case for quantum advantage in a broader range of computational tasks. Constant-Depth Quantum Circuits Separate from Diffusion Language Models Building on work on shallow quantum circuits, researchers have now extended the demonstrated separation to include a comparison against large language models, specifically examining limitations in how these models handle certain computational tasks. This latest research, available on arXiv, proves the existence of one problem in each of these classes for which shallow quantum circuits have a provable advantage over LLMs, even those leveraging advanced reasoning capabilities. Distributional problems, where the goal is to generate outputs aligned with a specific probability distribution, represent another type of problem explored; unlike functional problems computing the value of a function, these tasks mirror real-world LLM applications like text and image generation. A constant-depth quantum circuit can efficiently predict the parity of an unknown string using principles of entanglement and interference, enabling efficient sampling of strings with a specified parity, a feat that proves challenging for classical counterparts. Previous work had already highlighted limitations in diffusion language models when tackling a version of this sampling problem, but those findings did not account for chain-of-thought, a technique that enhances model performance by enabling intermediate token generation and consumption. The researchers note, emphasizing the specific computational bottleneck they targeted. While these results are theoretical, given the current limitations of quantum hardware, they suggest potential future applications as quantum technology matures.

The team’s work builds on a sustained focus on shallow quantum circuits, where circuit depth remains constant even as the number of qubits increases, a deliberate architectural choice aimed at achieving practical separation from classical models. This approach contrasts with attempts to prove quantum superiority against fully general Turing machines, a strategy deemed excessively challenging given the unlimited resources available to such models. Source: https://research.ibm.com/blog/quantum-circuits-vs-llms More like thisQuantum Research NewsIonQ’s research earns a quarter of IEEE Quantum Week’s top honorsQuantum Research NewsResearchers Simulate Quantum Behaviour with New FrameworkQuantum AlgorithmsResearchers Bound Error Weight Controlling Quantum Memory FailuresQuantum Research NewsResearchers Establish Growth Rate for Qubit Basis Equivalence Classes Exceeds 2 Raised to the Power of NStay currentSee today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals. Tags: The Neuron With a keen intuition for emerging technologies, The Neuron brings over 5 years of deep expertise to the AI conversation. Coming from roots in software engineering, they've witnessed firsthand the transformation from traditional computing paradigms to today's ML-powered landscape. Their hands-on experience implementing neural networks and deep learning systems for Fortune 500 companies has provided unique insights that few tech writers possess. From developing recommendation engines that drive billions in revenue to optimizing computer vision systems for manufacturing giants, The Neuron doesn't just write about machine learning—they've shaped its real-world applications across industries. Having built real systems that are used across the globe by millions of users, that deep technological bases helps me write about the technologies of the future and current. Whether that is AI or Quantum Computing. Latest Posts by The Neuron: IonQ’s research earns a quarter of IEEE Quantum Week’s top honors September 15, 2026 Dr. Safeer’s team—OUI—links physics & robotics with wave-based control September 15, 2026 NVIDIA charts a new path for enterprise quantum with what works.