Skip to content
Preprint

Separating quantum circuits from classical LLMs

Aug 2026 · 2 citations
Physics Computer Science

TL;DR

This work proves unconditional separations between low-depth quantum computation and the corresponding bounded-resource classical language-model architectures in both regimes, and initiates the study of quantum advantage in the era of large language models.

Abstract

Modern large language models - transformers and diffusion language models - are built around two canonical algorithmic tasks: prediction and generation. We prove unconditional separations between low-depth quantum computation and the corresponding bounded-resource classical language-model architectures in both regimes. Concretely, we exhibit the following: 1. Distributional separation. We give a distribution that is sampleable by $\textsf{QNC}^0$ circuits (i.e., a family of constant-depth quantum circuits consisting of bounded fan-in gates) that no constant-round diffusion language model ($\textsf{DLM}$) with shallow scheduling and denoising can sample within constant distance, even when allowed sublinear chain-of-thought and output-token revision/remasking events, the very features modern $\textsf{DLM}$s rely on. 2. Functional separation. We exhibit a function computable in $\land \circ \textsf{QNC}^0[\log\log n]$ (i.e., a family of O$(\log\log n)$-depth $\textsf{QNC}^0$ circuits, where $n$ is the input length, followed by a single classical $\mathsf{AND}$ gate) such that any constant-depth decoder-only transformer computing the function must be large: it would have to have width $n^{\Omega(1)}$. Together, our work initiates the study of quantum advantage in the era of large language models.

View source

Similar papers

Preprint Sep 2026

Verifiable quantum advantage in extremely low depth

This paper gives a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer, and shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks w...

Alexandru Gheorghiu · 4 citations
Preprint Sep 2026

Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D

We consider quantum circuits consisting of $d$ layers of nearest-neighbor two-qubit gates acting on $n$ qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any s...

Robert Koenig, Marco Tomamichel · 1 citation
Preprint Sep 2026

A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics

Developing classical simulation algorithms for noisy quantum circuits is essential to delineating the limits of quantum advantage. Existing classical sampling approaches for general circuits require circuit depths to grow logarithmically with system size, so that noise drives the global output state close to a trivial...

Jon Nelson, Joel Rajakumar, Chao Yin et al. · 1 citation
Sep 2026

Depth-Optimal Quantum Compilation

We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $\delta>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+\delta}(1/\varepsilon))$ cle...

F. Vasconcelos · 1 citation · ⚡1
#natural language process... Preprint Sep 2026

Circuit Hypernetworks for Quantum-Augmented Diffusion Language Models

HyperQ is introduced, which adds token-conditioned quantum residual branches to a frozen masked-diffusion language model, and support token-conditioned circuit emission as a tractable architectural approach to quantum-augmented language modelling.

Xiaoqiang Wang, Meng-Yang Xiong, Jun Dai et al. · 0 citations
Preprint Sep 2026

Computational Work Extraction: The Complexity of Catalysts

We prove maximal separations: $n$-qubit systems can have $\Theta(n)$ ergotropy, while every efficient process extracts negligible work, even for Hamiltonians consisting of single-qubit terms. We establish an unconditional existential separation and give an explicit construction in the random oracle model. Assuming the...

A. S. Arora, Shantanav Chakraborty, Alexandru Cojocaru et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.