Separating quantum circuits from classical LLMs

• URL: http://arxiv.org/abs/2608.03962v1
• Date: Tue, 04 Aug 2026 17:28:24 GMT
• Title: Separating quantum circuits from classical LLMs
• Abstract summary: We prove unconditional separations between low-depth quantum computation and classical language-model architectures.<n>Our work initiates the study of quantum advantage in the era of large language models.
• Score: 2.986556069071589
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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^{Ω(1)}$. Together, our work initiates the study of quantum advantage in the era of large language models.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• A Provable Oracle-Free Quantum Algorithm for Nonlinear Dynamics on Hybrid Oscillator-Qubit Processors [14.814423713691623]
  We develop a hybrid qubit-qumode algorithm for nonlinear ordinary differential equations of the form $dotmathbfx=mathbff(mathbfx)$ with warped degree$L$.<n>The algorithm propagates the state density and returns the trajectory as the peak of that density in the small-noise limit.
  arXiv  Detail & Related papers  (2026-07-30T17:10:47Z)
• Exponential Reduction of Mesh Dependence in Quantum Estimation of Parabolic PDE Observables [3.3636842548621275]
  We develop a quantum PDE algorithm that estimates linear and quadratic observables and places fine-coarse cancellation inside the circuit before measurement.<n>We also give a non-Fourier realization based on energyorthogonal dyadic midpoint details in one dimension.
  arXiv  Detail & Related papers  (2026-07-20T16:09:24Z)
• Wavelet Variance Equipartition as a Threshold for World-Model Quality and Quantum Kernel TN-Simulability [0.0]
  We identify the wavelet scaling exponent $$ as a critical diagnostic.<n>We establish $= 1/2$ as a sharp transition boundary for the classical simulability of amplitude-encoded quantum kernels.<n>We prove this variance scales strictly as $Var[X] = (d-2)$.
  arXiv  Detail & Related papers  (2026-05-12T05:41:12Z)
• Practical framework for simulating permutation-equivariant quantum circuits [0.0]
  We introduce a practical algorithm for $S_n$-equivariant circuits under the assumption that the gate generators are at most $k$-local, with $kin O(1)$.<n>The resulting method runs in $O(n+1)$ time for constant depth, where $$ is the matrix multiplication exponent, significantly lowering the degree compared to existing techniques.
  arXiv  Detail & Related papers  (2026-03-13T15:18:18Z)
• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  We introduce a Markov Chain Monte Carlo (MCMC) algorithm that dramatically accelerates the simulation of quantum many-body systems.<n>We validate our algorithm on benchmark quantum physics problems, accurately reproducing known theoretical results.<n>Our work provides a powerful tool for large-scale probabilistic inference and opens avenues for physics-inspired generative models.
  arXiv  Detail & Related papers  (2025-10-13T07:57:21Z)
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits [0.0]
  Controlled operations are fundamental building blocks of quantum algorithms. Decomposing $n$-control-NOT gates into arbitrary single-qubit and CNOT gates is a crucial but non-trivial task.
  arXiv  Detail & Related papers  (2023-12-20T17:23:11Z)
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
  We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. We obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices.
  arXiv  Detail & Related papers  (2023-08-16T17:54:56Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Interactive quantum advantage with noisy, shallow Clifford circuits [0.0]
  We show a strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. A key component of this reduction is showing average-case hardness for the classical simulation tasks. We show that is true even for quantum tasks which are $oplus$L-hard to simulate.
  arXiv  Detail & Related papers  (2021-02-13T00:54:45Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.