acceptodds
Under review as a conference paper at ICLR 2027

Separating Quantum Circuits from Classical LLMs

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: - **Distributional separation.** We give a distribution that is sampleable by circuits (i.e., a family of constant-depth quantum circuits consisting of bounded fan-in gates) that no constant-round diffusion language model () 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 s rely on. - **Functional separation.** We exhibit a function computable in (i.e., a family of -depth circuits, where is the input length, followed by a single classical gate) such that any constant-depth decoder-only transformer computing the function must be *large*: it would have to have width . Together, our work initiates the study of quantum advantage in the era of large language models.

Primary area:
foundation or frontier models, including LLMs
Keywords:
quantum circuits, transformers, diffusion models

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_KHD2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper studies two separations between shallow quantum circuits and restricted language-model architectures. It claims a Boolean functional separation between an O(log⁡log⁡n)O(\log\log n)-depth quantum circuit with one final classical AND gate and constant-depth decoder-only Transformers of subpolynomial width. It also claims that a block-parity distribution is easy for QNC0QNC^0 but hard to approximate by constant-round DLMs with GC0[log⁡n]GC^0[\log n] scheduling and denoising, bounded workspace, and bounded token revision or remasking.

The DLM proof combines a product-mixture bound, entropy accounting over the execution, and a reduction from last-bit generation to parity prediction. The paper is theoretical; its validation consists of circuit constructions and proofs.

Critical strengths
  1. The paper addresses a meaningful question about the computational limits of restricted language-model architectures. Its intended contribution is more specific than a standard circuit separation: it accounts for the generation process and the resources available during that process.

  2. The strongest technical idea is the DLM execution analysis. The proof does not simply assume that previously generated bits are uniform external inputs. It introduces a reweighted execution law, bounds the extra entropy loss, and uses a coupling argument to replace selected generated bits by uniform inputs. This is a useful approach to handling adaptive generation and is not supplied directly by a static product-mixture lower bound.

Critical weaknesses
  1. Important proof gaps affect both main results.

For the functional result, Theorem B.5 requires bandwidth B≤TB\le T on the TT-parameterized IterInx instance. Lemma B.9 produces an IterInx protocol with bandwidth TtTt, but Theorem B.10 applies B.5 without changing the instance or establishing a stronger bound. Thus, the application is outside the stated regime. The Boolean equality task in Theorem B.7 also needs to be aligned with the value-output task used in Theorem B.10.

For the DLM result, Section C.4.3 deletes blocks that are found to have been revised after observing the full execution, and then applies the monotone-model argument. This future-dependent selection does not automatically preserve the required conditional product structure. The entropy bound from Corollary C.6 is also reused without accounting for overwritten values. These are substantive gaps, not just missing notation. Separately, Theorem C.4 uses 1−εb1-\varepsilon_b where the product-bias identity requires 1−2εb1-2\varepsilon_b; this local error appears repairable.

  1. The novelty and theoretical importance need a more precise account.

Chen, Peng, and Wu [1] provide the communication framework and the underlying Transformer lower bound. Jiang, Haghtalab, and Chen [2] already prove a parity-sampling lower bound for standard AC0AC^0 DLMs. Ahmed et al. [3] prove an exponential product-mixture lower bound for a uniform parity distribution. The present paper goes beyond these individual results by targeting approximate sampling with workspace and revisions, and by treating entropy-deficient conditional laws. Therefore, these references do not directly cover the full claimed theorem. However, the paper should identify which additional argument establishes the stronger result.

The quantum interpretation also needs care. A parity block can be sampled by a classical NC0NC^0 circuit: take independent uniform r1,…,rB−1r_1,\ldots,r_{B-1}, set r0=rB=0r_0=r_B=0, and output xi=ri−1⊕rix_i=r_{i-1}\oplus r_i. This also underlies the revision construction in [2]. Hence, the sampling result concerns restrictions on the DLM generation mechanism, rather than a task that requires quantum computation. The paper does not yet explain sufficiently what the quantum comparison adds beyond this classical architectural limitation.

[1] Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical Limitations of Multi-Layer Transformer. FOCS, 2025.

[2] Haozhe Jiang, Nika Haghtalab, and Lijie Chen. Diffusion Language Models are Provably Optimal Parallel Samplers. ICLR, 2026.

[3] Mansoor Ahmed, Yue-Tsz Fan, Hemanth Venkateswara, and Murray Patterson. Latent-Kernel Discrete Flow Maps for Few-Step Generation. arXiv:2607.27529, 2026.

Questions for authors
  1. What lower bound justifies applying Theorem B.5 to the bandwidth-TtTt protocol obtained in Lemma B.9, on the same TT-parameterized instance?

  2. What is the exact Boolean function for which both the quantum upper bound and the Transformer lower bound hold? Please justify the transition between computing IterMultInx and testing [β=IterMultInx(X)][\beta=\mathrm{IterMultInx}(X)] with the stated resources.

  3. Can the authors give a complete revision/remasking proof that preserves the required conditional distributions and explicitly accounts for overwritten information in the entropy bound? Please also correct the product-bias identity in Theorem C.4.

  4. Which precise lemma provides the advance beyond [2] and [3]? Given the simple classical NC0NC^0 sampler for block parity, what additional theoretical insight is established by the quantum comparison?

1 comment

Thank you very much for the careful technical assessment. Here are specific responses.

  • Claimed Proof Gaps:

We thank the reviewer for pointing out the need to clarify the parameterization. As established in Lemma B.9, our reduction preserves the number of communication epochs and incurs a bandwidth overhead of tt, where t=TOL(1)t=T^{O_L(1)} for every fixed LL (Lemma B.8). We agree that applying Theorem B.5 directly with bandwidth TtTt requires additional justification.

One natural way to address this is through the tokenization convention of Chen–Peng–Wu, where each entry of a function table is treated as one token. In our setting, the tt replicated tables can equivalently be viewed as a single vector-valued function Zℓ:[Nℓ−1]→[Nℓ−1]tZ_\ell:[N_{\ell-1}]\to[N_{\ell-1}]^t, with each vector-valued entry represented as one token. Under this structured-token interpretation, the number of token positions is unchanged, and restricting to diagonal instances yields an IterInx protocol without the multiplicative tt bandwidth overhead.

We acknowledge that this interpretation requires making the token alphabet and embedding assumptions explicit. If instead all inputs are represented at the bit level, a more direct adaptation of the Chen–Peng–Wu communication lower-bound argument to the replicated setting may be necessary. We believe this is a promising route, but do not claim that it follows immediately from the existing theorem. We will clarify the precise model and parameter dependence in the revision. The quantum upper-bound construction is unaffected by this distinction.

DLM result. We thank the reviewer for raising these concerns. We agree that conditioning on the future-dependent set of untouched blocks does not automatically preserve the product structure. In fact, we explicitly acknowledge this subtlety in Section C.4.3 and Footnote 25. Our intended argument is not to condition on untouched blocks, but rather to discard the at most RR revised blocks after execution and account for their contribution through a counting argument. In particular, since each revision affects at most one block, the number of exceptional blocks is bounded by RR in every execution. The goal is to apply the product-mixture argument to the original, pre-round conditional distributions, where conditional independence is preserved, and charge any subsequent revisions to this exceptional-block budget. This avoids conditioning on a future-dependent selection of blocks.

Similarly, the entropy accounting must account for overwritten values. The intended extension is to track the information generated during revisions separately, charging the additional entropy contribution to the at most RR revision events. Since s+R=o(M)s+R=o(M) in our parameter regime, these additional contributions are asymptotically negligible. We will make the corresponding counting and entropy arguments precise in the revised version.

We also thank the reviewer for identifying the typo in Theorem C.4; we will correct the product-bias identity to use 1−2εb1-2\varepsilon_b.

  • Novelty and Theoretical Importance: We will take into account the citations provided by the reviewer and ensure we highlight them appropriately in our revisions.
Reviewer_x9wsOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies separations between shallow quantum circuits and resource-restricted models of transformers and diffusion language models (DLMs). 1) For the functional separation, it proposes an iterated multi-index problem, intended to be computable by an O(log⁡log⁡n)O(\log\log n)-depth, bounded-fan-in quantum circuit followed by a single classical AND gate, while requiring polynomial width for the decoder-only transformers under consideration. The construction combines replicated inputs with consistency checks and seeks to transfer an existing transformer lower bound to the modified problem. 2) For the distributional separation, the target is a product of uniform even-parity distributions on blocks of bits. The paper claims that this distribution is sampleable in QNC0\mathrm{QNC}^{0}, but not approximately sampleable by constant-round DLMs with shallow GC0[log⁡n]\mathrm{GC}^{0}[\log n] scheduling and denoising, under restricted workspace and revision/remasking budgets. Its principal proposed ingredients are a lower bound on mixtures of product distributions and a reduction from final-bit generation to parity prediction.

Critical strengths

Representing each denoising round, after hiding the workspace, as a limited mixture of coordinate-wise product distributions gives a concrete approach to studying the resources required to generate correlations. Extending this approach to approximate sampling with revision/remasking would be consequential because it addresses mechanisms explicitly included in the paper’s DLM model, rather than only analyzing an entirely irreversible sampler. This is the strongest potential contribution, although its value depends on resolving the proof issues below.

Critical weaknesses
  1. The mixture representation in Equation 4 does not, by itself, justify comparing a transcript-conditioned execution to the residual target distribution in Equation 5. Closeness of the final output distribution in total variation does not automatically imply closeness of the corresponding transcript-conditioned distributions. A separate argument is needed to show that the chosen reference execution retains the asserted residual parity law and remains close after conditioning on adaptive scheduling and workspace-dependent histories. This bridge is essential to applying the mixture lower bound, but it is not established in the sketch.
  2. On page 5, item 5 b states that IterMultInx\mathrm{IterMultInx} reduces to IterInx\mathrm{IterInx}, and then concludes that hardness transfers from IterInx\mathrm{IterInx}. As written, this is the wrong direction for that inference: a lower-bound transfer requires an appropriate reduction from the known hard problem IterInx\mathrm{IterInx} to IterMultInx\mathrm{IterMultInx}, or an explicit simulation showing that a small transformer for the latter would yield one for the former.
Questions for authors
  1. What precise lemma connects final-output total-variation closeness to the transcript-conditioned comparison needed for Equations 4–5? Please state the quantitative bound that justifies the uniform replacement in Step 4 and explain how the argument handles the value-dependent selection of untouched blocks in Step 5. The admissible approximation error and the required relationships among B,M,s,RB,M,s,R should be explicit.
  2. Please state the theorem with explicit depth quantifiers and give the resource-preserving reduction underlying item 5b. Is the result “for every fixed transformer depth LL, there exists a hard function family fLf_L,” or does one fixed function family resist all constant transformer depths? The cited Chen Peng Wu, FOCS'2025 result is depth-indexed, and its composition task becomes easy for a small transformer with one additional layer.
1 comment

Thank you for your detailed reading of the paper and for identifying parts that need further clarification. We provide specific responses below.

1. Mixture lower bound. We fully agree with the reviewer that total-variation closeness of the final output distributions does not imply closeness after conditioning on every individual execution transcript. However, our proof does not rely on such an inference; the required quantitative argument is already provided in Appendix C. We believe the concern may stem from the brevity of the proof sketch in the extended abstract.

Specifically, we construct a reference execution distribution QQ (Eq. 49), and Lemma C.5(a) establishes TV(P,Q)≤2η\mathsf{TV}(P,Q)\leq 2\eta for the entire execution, including adaptive scheduling and workspace information. Applying the conditional TV inequality (Lemma A.1), the expected conditional distance is at most 4η4\eta. Markov's inequality then bounds the probability of bad transcripts by 4η/η04\eta/\eta_0, precisely as used in Lemma C.7.

Importantly, we do not require the conditional reference distribution to be uniform over residual parity cosets. Theorem C.4 handles arbitrary distributions supported on these cosets, with the entropy deficiency explicitly accounted for. Thus, the requested quantitative bridge is already established in Lemmas A.1, C.5, and C.7. We will clarify this connection in the main-text proof sketch.

Uniform replacement and parameters. Lemma C.8 gives the explicit replacement error 6Tη+T,defb⋆6T \eta + \sqrt{T,def_{b^\star}}, where defb⋆≤4(s+2η)/Mdef_{b^\star}\leq 4(s+2\eta)/M. Our choices B=n0.01B=n^{0.01}, M=n0.99M=n^{0.99}, and s=R=n0.9s=R=n^{0.9} ensure s+R=o(M)s+R=o(M). The approximation error η\eta is a sufficiently small positive constant depending on the number of denoising rounds TT.

Revision/remasking. Section C.4.3 explicitly recognizes that conditioning on a block being untouched need not preserve product structure. Our approach instead discards the at most RR touched blocks after execution and bounds their contribution by an additive R/M=o(1)R/M=o(1) term. We will provide additional details justifying the counting argument for this value-dependent selection.

2. Reduction direction. We thank the reviewer for raising this point. The reduction established in Lemma B.9 is, in fact, in the correct direction, namely IterInx≤IterMultInx\mathrm{IterInx}\leq\mathrm{IterMultInx}. We acknowledge that the informal wording in the proof overview on page 5 may suggest otherwise, and we will correct it.

Concretely, given an arbitrary IterInx instance, each player locally replicates its input tt times and runs the assumed IterMultInx protocol on the resulting diagonal instance. The consistency predicate is identically 11, so the protocol returns exactly the original IterInx output. This simulation preserves the number of communication epochs LL, with bandwidth increasing from TT to at most TtTt. Thus, hardness of IterInx transfers to IterMultInx, with the bandwidth overhead explicitly quantified in Lemmas B.8 and B.9. We will clarify this reduction in the revised exposition.

Depth quantifiers. Our result is depth-indexed: for every fixed transformer depth LL, we construct a corresponding hard function family fn,Lf_{n,L} requiring polynomial width for LL-layer decoder-only transformers. We do not claim that a single function family is hard for all constant depths. This dependence on LL is explicit in Appendix B.2.1 and Theorem B.10.

Reviewer_LhxSOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This theory paper studies the problem of whether there exist some problems that can be solved by shallow quantum circuits but cannot be solved by modern LLMs. Specifically, it gives two main results, includng a distributional seperation between QNC0 circuits and constrant round DLMs, and a functional seperation showing that a function requires O(log⁡log⁡n)O(\log \log n) depth quantum circuit needs to be computed with polynomial width transformers.

Critical strengths
  1. This paper studies a timely and important problem, that demonstrates a fundamental limitation for modern DLMs from a quantum circuit perspective. It is interesting to study this aspect.

  2. The technical aspects of this paper are solid and non-trivial. The DLM lower bound gives a mixture of product distributions and a reduction to parity computation. The removal of the input-copy assumption for the transformer separation is also interesting.

  3. This paper studies a novel setting, which gives uncomputable problems from a shallow quantum circuit perspective. This is quite new compared with previous Transformer expressivity works.

Critical weaknesses
  1. It would be better if the authors discussed the implications for practical LLMs. Currently, the DLM definitions used in this work are more of a theoretical model.

  2. This paper still requires careful checking. Here are some of the typos: a. p15, lines 793 and 795, "auxilliary"; b. p20, line 1034, "a iterative procedure"

  3. It would be better if the authors discussed more related works on Transformer expressivity and computational efficiency. Here are some of the works [1, 2, 3, 4].

[1] Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, Liwei Wang. "Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective". NeurIPS 2023.

[2] Bo Chen, Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, Jiahao Zhang. "Circuit Complexity Bounds for RoPE-based Transformer Architecture". EMNLP 2025.

[3] Zhao Song, Jianfei Xue, Jiahao Zhang, Lichen Zhang. "Sublinear Time Quantum Algorithm for Attention Approximation". ICLR 2026.

[4] Yu Huang, Zixin Wen, Aarti Singh, Yuejie Chi, Yuxin Chen. "Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization". NeurIPS 2025.

Questions for authors

In Appendix A.3.3, the authors assume a constant number of denoising rounds and constant-depth, polynomial-size circuits.

  1. How closely do these assumptions reflect practical DLMs?

  2. Can the authors connect this to modern DLM models, like LLaDA and Seed Diffusion?

1 comment

Thank you for the positive assessment and helpful suggestions. We'd like to highlight that our DLM definitions are motivated by the parallel masked-token prediction and remasking mechanisms used in models such as LLaDA and Seed Diffusion. We acknowledge that our assumptions describe a restricted asymptotic regime: constant rounds, polynomial-size GC0[log⁡n]\mathsf{GC}^0[\log n] scheduling/denoising, and bounded revisions. Nevertheless, our model captures important features such as adaptive scheduling, workspace/chain-of-thought, and remasking/revision. We will clarify the connections to practical models and which resource regimes fall outside our guarantees. For now, our work can be seen as initiating the study of asymptotic quantum advantages over classical LLMs which we believe is timely. We will incorporate the suggested references, clarify their relationship to our results, and correct the indicated typos.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.