Separating quantum circuits from classical LLMs

Arkopal Dutt; Hari Krovi; Rik Sengupta; Srinivasan Arunachalam

REVIEW 3 major objections 5 minor 53 references

Separating quantum circuits from classical LLMs

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves unconditional separations between shallow quantum circuits and bounded classical LLM architectures, both for function computation and for distribution sampling.

desk verdict First QNC^0-vs-LLM separations with real content, but the transformer lower bound has a bandwidth-regime gap at the CPW25 invocation and the DLM result is narrower than the title suggests. read the letter →

arxiv 2608.03962 v1 pith:2LH55IH4 submitted 2026-08-04 quant-ph cs.AIcs.CC

Srinivasan Arunachalam , Arkopal Dutt , Hari Krovi , Rik Sengupta This is my paper · ORCID

classification quant-phcs.AIcs.CC MSC 68Q1268Q17

keywords quantumadvantageshallowcircuitstransformerlowerboundsdiffusionlanguagemodelsblockparitydistributionchain-of-thoughtsamplingseparationsQNC^0

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves two unconditional separations between very shallow quantum circuits and two formal models of modern large language models. On the functional side, it constructs an iterated multi-index function that can be computed by a quantum circuit of depth $O(\log\log n)$ followed by a single AND gate, yet every constant-depth decoder-only transformer that computes it exactly must have width $n^{2^{-O(L)}}$ (polynomial in the input length for constant depth). On the distributional side, it shows that the uniform distribution over strings made of $M$ blocks of $B$ bits of even parity can be sampled exactly by a depth-four QNC$^0$ circuit, while no constant-round diffusion language model with shallow GC$^0[\log n]$ schedulers and denoisers, $n^{0.9}$ chain-of-thought tokens, and $n^{0.9}$ revision/remasking events can sample it within constant total variation distance. The paper's goal is to initiate the study of provable quantum advantage against the prediction and generation architectures behind current LLMs, rather than against abstract classical circuit classes.

What carries the argument

Two mechanisms carry the arguments. For the functional separation: the iterated multi-index function bundles $t$ copies of an iterated-index instance behind a consistency predicate, so a quantum circuit can verify all candidate computation histories in parallel, checking equality and index lookups with $O(\log n)$-depth Toffoli-based equality subcircuits and a single final AND gate, while the $t$-fold copy structure lets the transformer lower bound reduce to a known iterated-index communication lower bound. For the distributional separation: the poor man's cat state, starting from $|+\rangle^{\otimes B}$, measuring the commuting parity observables $Z_i Z_{i+1}$, and applying Hadamards, samples the uniform even-parity distribution exactly in constant depth; on the classical side, the defining structural axiom that a denoising round samples updated coordinates independently conditioned on the transcript makes each round's output law a small convex mixture of product distributions, and a mixture-of-products lower bound shows that approximating a product of parity cosets requires $2^{\Omega(\sum_b (r_b - 1))}$ components. An entropy-deficit accounting then forces most blocks to be completed one bit at a time, reducing the last-bit completion to a parity prediction that contradicts known GC$^0[\log n]$ parity lower bounds.

What would settle it

Run a masked discrete diffusion model and, at a single denoising round, condition on the current partially generated sequence; record the values of two tokens unmasked in the same round and repeat many times. A statistically significant correlation between those values would show that the paper's within-round conditional-independence axiom is not satisfied by that architecture, marking exactly where the lower bound does not apply. Conversely, any constant-round shallow DLM that satisfies the axiom and yet samples the block-parity distribution within constant total variation distance would directly refute Theorem 4.1.

Watch

Extended reading notes

Core claim

The central discovery is that both canonical LLM capabilities, prediction and generation, meet a hard wall when implemented by bounded-depth classical layers, while shallow quantum circuits clear that wall. Concretely, the iterated multi-index function IterMultInx, which checks that $t$ copies of an iterated-index instance agree and then outputs the iterated index, lies in $\wedge\circ \textsf{QNC}^0[\log\log K]$: a quantum circuit of depth $O(\log\log K)$ whose measurement outcomes are classically ANDed together. Yet any constant-depth decoder-only transformer solving it needs width $Hdp = n^{2^{-O(L)}}$. Separately, the block-parity distribution $D_{\mathrm{blk}} = \bigotimes_{b=1}^{M} U^{\oplus}_B$, uniform over even-parity $B$-bit strings in each of $M$ blocks, is exactly sampleable by a QNC$^0$ circuit that prepares a poor man's cat state per block and measures in the Hadamard basis; no constant-round shallow diffusion language model with GC$^0[\log n]$ schedulers and denoisers, sublinear chain-of-thought, and sublinear revision/remasking can approximate it within constant total variation distance. The lower bound rests on the observation that each denoising round induces only a small mixture of product distributions over fresh coordinates, whereas the target conditional law is a product of affine parity cosets that requires exponentially many product components to approximate.

Load-bearing premise

The distributional separation stands on the modeling axiom that, conditioned on the current transcript, the coordinates updated in one denoising round are sampled independently from coordinate-wise marginals; without that within-round independence, for example if a joint denoiser couples coordinates through shared latent noise, the mixture-of-products entropy argument collapses.

Editorial extensions

If this is right

Any exact constant-depth decoder-only transformer computing IterMultInx must have width polynomial in the input length, so the problem separates all subpolynomial-width transformers from $\wedge\circ \textsf{QNC}^0[\log\log n]$.
The block-parity distribution gives an unconditional sampling separation: QNC$^0$ samples it exactly in constant depth, while constant-round shallow DLM samplers fail even when given $n^{0.9}$ chain-of-thought tokens and $n^{0.9}$ revision/remasking events.
The distributional lower bound is robust to sublinear revision/remasking: since each event touches one coordinate and $R = o(M)$, only $o(M)$ blocks can be affected, and the untouched blocks are governed by the monotone argument.
The functional separation is essentially tight: any function deterministically computed by a $\wedge\circ \textsf{QNC}^0[d]$ circuit with advice and $d \le \log\log n + O(1)$ is already in AC$^0$, so the depth bound cannot be relaxed to a smaller constant multiple.
The DLM lower bound holds against GC$^0[\log n]$ schedulers and denoisers, a strictly stronger class than the AC$^0$ circuits previously analyzed, implying the obstruction is structural rather than an artifact of weak denoisers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's closing remarks imply that linear rather than sublinear chain-of-thought would plausibly make both tasks easy for classical LLMs; if so, the demonstrated advantage is confined to the sublinear-workspace parallel-generation regime, not a blanket statement about real LLM deployments.
A direct test of the distributional claim in practice is to measure within-round statistical independence of simultaneously unmasked tokens in a running diffusion model; any coupling would show the model lives outside the paper's defining axiom, so the lower bound would not describe it.
The same mixture-of-products entropy argument should transfer to any target distribution built from many independent small affine constraints, such as per-block mod-3 or mod-k parity, yielding a family of sampling separations with different block sizes.
The functional separation suggests a concrete hybrid recipe, delegating the consistency check and index lookup to a shallow quantum coprocessor and keeping the transformer for the surrounding language tasks, whose success on IterMultInx-style instances would be a testable consequence of the paper's upper bound.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

What you should know: this is one of the first papers to put QNC^0 directly against transformer and diffusion language models, and it has real technical content. The distributional separation (Theorem 4.1) is probably sound inside the formal model, and the entropy-deficit counting in Section 4.3 is nice. The functional separation (Theorem 3.10) is the headline result, and that's where the trouble is.

The paper does well: the quantum upper bound for the block-parity distribution is clean and self-contained, and the iterated multi-index construction is a legitimate way to remove the copy overhead from earlier index-function upper bounds. The paper is honest in its final remarks, saying the tasks are adversarial and the CoT assumptions are strong. Citation practice is fine; the lower bounds reduce to published work by other groups (CPW25, Kumar), so there is no circularity.

Soft spots, in proportion. The functional lower bound has a formal gap at the black-box step. Lemma 3.9 converts a width-T transformer protocol for IterMultInx into an autoregressive protocol for IterInx with bandwidth Tt, where t = T^{2^{O(L)}} (Lemma 3.8). The proof then calls Theorem 3.5 (CPW25's theorem), which is stated only for protocols with bandwidth B ≤ T. Tt exceeds T by a polynomial factor. The paper does not show the CPW25 bound extends to that regime, and it does not reparameterize the instance. As written, Theorem 3.10 does not follow. This is a load-bearing issue, not a typo. I checked the surrounding text and found no repair.

On the DLM side, the lower bound rests on the "standard DLM" axiom of Section 2.3.2: within a round, coordinates are sampled independently from marginal distributions. The paper is explicit, but that is a strong restriction. Many modern diffusion architectures use a joint denoiser that correlates tokens in one round, so the theorem does not apply to them. That is a modeling caveat, not a proof error, but it limits the "LLM" part of the title.

Also, the revision/remasking extension in Section 4.4.3 is explicitly sketched; the "routine bookkeeping" is not supplied. The plan is plausible, but the formal statement is not proven there.

Who it's for: quantum complexity people and theorists working on LLM expressivity will want to read this. It deserves a serious referee. I'd send it out, with a clear request: fix the CPW25 bandwidth issue or clearly state a proviso; write out the remasking argument; and temper the title's claims about LLMs. If the bandwidth gap is unfixable, the functional section should be substantially rewritten.

Referee Report

3 major / 5 minor

Summary. The paper proves two unconditional separations between low-depth quantum circuits and classical large-language-model architectures. First, it exhibits the block-parity distribution D_blk, uniform over M blocks of B bits with even parity, and shows that it is exactly sampleable by constant-depth QNC^0 circuits (Lemma 4.2), while any constant-round shallow diffusion language model with GC^0[log n] denoisers, s=n^0.9 chain-of-thought/workspace tokens, and R=n^0.9 output-token revision/remasking events fails to sample it within constant total variation distance (Theorem 4.1). Second, it defines the iterated multi-index function IterMultInx, proves a quantum upper bound in ∧∘QNC^0[log log K] (Theorem 3.7), and claims that any constant-depth decoder-only transformer computing it must have width T ≥ n^{2^{-O(L)}} (Theorem 3.10). The transformer lower bound imports the CPW25 autoregressive-protocol lower bound, and the DLM lower bound builds an entropy-based obstruction against mixtures of product distributions, ultimately reducing to Kumar's parity lower bound.

Significance. If the results hold, they would initiate a rigorous complexity-theoretic comparison between shallow quantum circuits and practical LLM architectures, going beyond earlier separations against NC^0/AC^0/GC^0. The quantum upper bounds are self-contained and the distributional lower bound introduces a novel entropy-mixture framework that quantifies the cost of many simultaneous parity constraints. The paper is transparent about its model assumptions and its dependence on prior work. However, the functional separation currently hinges on applying the CPW25 lower bound in a bandwidth regime the quoted theorem does not cover, and the DLM separation is conditional on a strong within-round independence axiom. The revision/remasking extension is sketched rather than fully proved. These issues are load-bearing for the paper's central claims.

major comments (3)

[§3.4.2, Theorem 3.10, Eq. (36)] The proof of Theorem 3.10 applies Lemma 3.9 to obtain an autoregressive protocol Π_orig for IterInx with bandwidth B = Tt, and then invokes Theorem 3.5 to conclude Tt ≥ n_orig^{α_L}. However, Theorem 3.5 is stated only for protocols with bandwidth B ≤ T. By Lemma 3.8, t = C_L T^{c_L} with c_L = 2^{O(L)} (a positive exponent for constant L), so B = Tt exceeds T by a polynomial factor for all sufficiently large T. The hypothesis of Theorem 3.5 is therefore not satisfied, and the inequality in Eq. (36) does not follow from the quoted statement. This is a load-bearing gap: without a valid lower bound for the reduced protocol, the conclusion T ≥ n^{2^{-O(L)}} is unsupported. The authors need to verify whether the CPW25 lower bound actually holds for arbitrary bandwidth (and if so, state that version explicitly), or else provide a modified reduction that respects the B ≤ T regime.
[§4.4.3] The extension of the DLM lower bound to revision/remasking is presented as follows: after the execution, delete all touched blocks, apply Lemma 4.7 to the 'induced monotone execution' on untouched blocks, and assert that the same counting argument goes through with 'only routine bookkeeping.' This is not routine: the set of touched blocks is determined only at the end of the execution, so it is a future event relative to the adaptive DLM process. Conditioning on this post hoc event changes the conditional law of the untouched blocks in a way that the entropy chain rule and the product-mixture argument of Lemmas 4.5 and 4.7 are not designed to handle. A rigorous proof showing that the bounds survive with s,R = o(M) is needed; as written, the advertised robustness to R = n^0.9 revision/remasking events is not established.
[§2.3.2, Theorem 4.1] The distributional separation depends critically on the axiom that, conditioned on the current transcript, the coordinates updated in one denoising round are sampled independently from coordinate-wise marginals. This assumption is essential to the entire lower bound: without it, the mixture-of-products structure in Theorem 4.4 and the entropy accounting in Lemma 4.7 collapse. The paper calls this the defining property of a 'standard DLM,' but the abstract and introduction state the separation for 'no constant-round diffusion language model' without this qualification. Since models with joint denoisers or shared latent noise would fall outside the axiom, the claimed separation is substantially narrower than the unqualified statements suggest. The authors should restrict all statements to their standard model, or extend the lower bound to permit within-round coupling.

minor comments (5)

[§3.4.2, just before Theorem 3.10] The sentence 'Since we prove lower bounds against determiistictransformer models (for which we showed the ∧◦QNC0[log logn] upper bound.' contains typos and an unclosed parenthesis; it should be rewritten for clarity.
[Lemma 4.9] The description of the input x as 'the uniform bits inserted into block b* before completion' is confusing: the completion coordinate's bit is not inserted but generated by the DLM, and the circuit outputs G ⊕ x_J. The proof should clarify that x_J is the input bit at the completion position, which is XORed with the generated bit G.
[Theorems 3.6 and 3.7] The notation 'K O(L8L)' is garbled in several places; it should be typeset as a power such as K^{2^{O(L)}} or K^{O(L·8^L)} so the copy complexity and gate complexity are unambiguous.
[Lemma 2.2 and Theorem 4.4] Lemma 2.2 gives the bound |H(P)-H(W)| ≤ 2ε log|X| + 1, but the proof of Theorem 4.4 uses the stronger inequality |H(P)-H(W)| ≤ η log|X| + h_2(η). The authors should state the stronger form (and cite it) to avoid an apparent mismatch.
[Footnote 17, p. 38] The adaptation of Lemma 2.4 from IterInx to IterMultInx is stated to hold 'with no change in the proof' but this is used as a central step in Theorem 3.10. The adaptation should be stated as an explicit lemma with a proof sketch, since the input structure of IterMultInx differs from that of IterInx.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: upper bounds are self-contained; lower bounds reduce to independent published results (CPW25, Kumar) rather than to the paper's own definitions or fitted parameters.

full rationale

The paper's central quantities are defined independently of the models under attack: D_blk is a product of uniform even-parity blocks, and IterMultInx is a consistent-copy extension of CPW25's IterInx with an explicit quantum circuit in AND∘QNC^0[log log K] (Theorem 3.7). The quantum samplers and circuits are explicit constructions (Lemmas 4.2, Claims 3.1-3.4, Theorems 3.6-3.7), not definitions that presuppose the target separations. The classical lower bounds are imported from external black boxes: the transformer width bound invokes Theorem 3.5 from CPW25, and the DLM sampling bound invokes Kumar's parity correlation theorem (Theorem 4.3); neither theorem is authored by the present authors, and the paper does not prove or assume these theorems by assuming its own conclusions. The mixture-of-product lower bound (Theorem 4.4) is a genuine entropy argument, not a fitted parameter renamed as a prediction: it starts from an explicit parity-coset support and an entropy lower bound, and derives a log K lower bound independent of any fitted value. The distributional result does rely on the within-round conditional independence axiom of the DLM model (Section 2.3.2), but this is an explicitly stated modeling assumption, not a circular definition of the target. A possible correctness gap exists in the functional reduction: Lemma 3.9 produces a protocol of bandwidth Tt while Theorem 3.5 is stated only for bandwidth B≤T, so invoking Theorem 3.5 on that protocol may exceed the stated hypothesis. That issue concerns the soundness of an external-theorem application, not circularity: no step backs the target claim by its own definition or by a self-citation chain. Remasking/revision handling (Section 4.4.3) is likewise a bookkeeping extension, not a circular step. Overall, the derivation chain is self-contained against external benchmarks and exhibits no definitional or statistical circularity.

Assumptions & free parameters 7 free parameters · 5 assumptions · 0 invented entities

No parameters are fitted to data; all numerical settings are asymptotic parameter choices made to satisfy the proof constraints. The main burden rests on external lower bounds from CPW25 and Kumar, and on the DLM conditional-independence modeling assumption. No new physical entities, particles, forces, or dimensions are introduced.

free parameters (7)

B = n^0.01
Block length in D_blk; chosen so B*M=n and each block is large enough for parity lower bounds.
M = n^0.99
Number of parity blocks; chosen so s,R=o(M) and the QNC^0 sampler is parallel.
s = n^0.9
Workspace/chain-of-thought token budget; chosen sublinear in M for the entropy argument.
R = n^0.9
Total revision/remasking event budget; chosen sublinear in M so touched blocks are a vanishing fraction.
K(T,L) = (TL)^8
Parameter governing the IterInx and IterMultInx instance families; tied to transformer width T and layer count L following CPW25.
t = K^{O(L 8^L)}
Copy parameter; chosen so the quantum circuit can compute index from input copies and so the lower bound survives the bandwidth blow-up.
eta = small constant epsilon*(T)
Allowed total variation distance in DLM sampling; chosen small enough for Theorem 4.4 and the parity contradiction to hold.

assumptions (5)

standard math Kumar's GC^0[log m] parity lower bound (Theorem 4.3)
Used as a black box in the distributional lower bound, Section 4.3.
standard math CPW25 iterated index communication lower bound (Theorem 3.5)
Used as a black box for the transformer lower bound in Sections 3.4.1 and 3.4.2.
domain assumption DLM conditional independence: each denoising round samples newly revealed coordinates independently given the current transcript
Core structural model property in Section 2.3.2; without it Theorem 4.4's product-mixture bound does not apply.
domain assumption Decoder-only transformer model with softmax attention, width Hdp, constant depth, and no chain-of-thought
Sets the transformer class in Section 2.2; the lower bound only targets this formal model.
ad hoc to paper Input copies in IterMultInx are part of the input and can be used by the quantum circuit
The quantum upper bound exploits t input copies; this makes the function total and places it in ∧∘QNC^0[log log K].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Separating quantum circuits from classical LLMs." pith.science (2026). https://pith.science/paper/2LH55IH4

@misc{pith2026260803962,
  author       = {Pith},
  title        = {Pith review of: Separating quantum circuits from classical LLMs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2LH55IH4}},
  note         = {Machine review of arXiv:2608.03962}
}

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.

Figures

Figures reproduced from arXiv: 2608.03962 by the authors.

**Figure 2.** An idealized depiction of the core DLM architecture. We now describe the diffusion language model (DLM) framework used in this paper. In abstraction, a DLM is defined as a generative model for text [NZY+25, SZL+25] that starts from a corrupted (masked or noisy) sequence of tokens, and iteratively denoises it. It is used typically to generate samples from a learned distribution over text; more precisely, it learns o… view at source ↗

**Figure 3.** Illustration of circuit Aj for equality check [x = y]. The circuit Aj is applied over n+1 qubits accounting for the size of y and the additional ancilla qubit. The circuit Aj used O(n) many single-qubit gates applied in parallel to each other and one (n + 1)-controlled Toffoli gate. The latter has a one- and two-qubit gate complexity of O(n) and requires depth O(log n) (when given O(n) clean ancillas). This complete… view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Illustration of quantum circuit Aj used for equality check [ij = j] and outputting the corresponding bit xj if true. Let us denote the last qubit as |tj ⟩ for a given j. To compute the index function, we now apply the circuit U composed of the smaller circuits Aj for j…

**Figure 5.** Figure 5: Illustration of the circuit used for outputting [PITH_FULL_IMAGE:figures/full_fig_p024_5.png]

**Figure 6.** Figure 6: Illustration of circuit for preparing the poor man’s cat state and sampling from [PITH_FULL_IMAGE:figures/full_fig_p042_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 35 canonical work pages

[1]

Proceedings of the 40th International Conference on Machine Learning , pages =

Tighter Bounds on the Expressivity of Transformer Encoders , author =. Proceedings of the 40th International Conference on Machine Learning , pages =. 2023 , publisher =

work page 2023
[2]

Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , pages =

Overcoming a Theoretical Limitation of Self-Attention , author =. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , pages =. 2022 , publisher =. doi:10.18653/v1/2022.acl-long.527 , url =

doi:10.18653/v1/2022.acl-long.527 2022
[3]

, booktitle =

Kumar, Vinayak M. , booktitle =. Tight Correlation Bounds for Circuits Between. 2023 , publisher =. doi:10.4230/LIPIcs.CCC.2023.18 , url =

work page doi:10.4230/lipics.ccc.2023.18 2023
[4]

2024 , eprint =

Improved Circuit Lower Bounds and Quantum-Classical Separations , author =. 2024 , eprint =

work page 2024
[5]

Science , volume =

Quantum Advantage with Shallow Circuits , author =. Science , volume =. 2018 , doi =

work page 2018
[6]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages =

Exponential Separation Between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits , author =. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2019 , publisher =. doi:10.1145/3313276.3316404 , url =

work page arXiv 2019
[7]

Nadimpalli, Shivam and Parham, Natalie and Vasconcelos, Francisca and Yuen, Henry , booktitle =. On the. 2024 , publisher =. doi:10.1145/3618260.3649662 , url =

arXiv 2024
[8]

On the Computational Power of

Anshu, Anurag and Dong, Yangjing and Ou, Fengning and Yao, Penghui , booktitle =. On the Computational Power of. 2025 , publisher =. doi:10.1145/3717823.3718189 , url =

arXiv 2025

Show all 53 references

[9]

Advances in Neural Information Processing Systems , volume =

Attention Is All You Need , author =. Advances in Neural Information Processing Systems , volume =. 2017 , publisher =

2017
[10]

Gretta, Lucas and Gupta, Meghal and Joshi, Malvika Raj , booktitle =. Parity. 2026 , publisher =. 2604.02793 , archivePrefix =

2026 arXiv
[11]

Super-Constant Weight

Gretta, Lucas and Gupta, Meghal and Joshi, Malvika Raj , year =. Super-Constant Weight. 2604.15298 , archivePrefix =

arXiv
[12]

Improved Lower Bounds for

Joshi, Malvika Raj and Tal, Avishay and Vasconcelos, Francisca and Wright, John , booktitle =. Improved Lower Bounds for. 2026 , publisher =. doi:10.1145/3798129.3800922 , url =

2026
[13]

Learning Junta Distributions, Quantum Junta States, and

Bao, Jinge and Escudero-Guti. Learning Junta Distributions, Quantum Junta States, and. Proceedings of the 43rd International Conference on Machine Learning , series =. 2026 , publisher =. 2410.15822 , archivePrefix =

2026 arXiv
[14]

and Grier, Daniel and Pad

Fenner, Stephen A. and Grier, Daniel and Pad. Tight Bounds on Depth-2. 2025 , eprint =

2025
[15]

Proceedings of Thirty Eighth Conference on Learning Theory , pages =

Learning Shallow Quantum Circuits with Many-Qubit Gates , author =. Proceedings of Thirty Eighth Conference on Learning Theory , pages =. 2025 , publisher =

2025
[16]

Bounds on the

Rosenthal, Gregory , booktitle =. Bounds on the. 2021 , publisher =. doi:10.4230/LIPIcs.ITCS.2021.32 , url =

2021 doi
[17]

Counting, Fanout, and the Complexity of Quantum

Green, Frederic and Homer, Steven and Moore, Cristopher and Pollett, Christopher , journal =. Counting, Fanout, and the Complexity of Quantum. 2002 , doi =

2002
[18]

1991 , publisher =

Elements of Information Theory , author =. 1991 , publisher =

1991
[19]

17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals , author =. 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =. 2026 , publisher =. doi:10.4230/LIPIcs.ITCS.2026.73 , url =

2026 doi
[20]

Nature Physics , volume =

Quantum Advantage with Noisy Shallow Circuits , author =. Nature Physics , volume =. 2020 , doi =

2020
[21]

Communications in Mathematical Physics , volume =

Trading Locality for Time: Certifiable Randomness from Low-Depth Circuits , author =. Communications in Mathematical Physics , volume =. 2021 , doi =

2021
[22]

34th Computational Complexity Conference (CCC 2019) , pages =

Average-Case Quantum Advantage with Shallow Circuits , author =. 34th Computational Complexity Conference (CCC 2019) , pages =. 2019 , publisher =. doi:10.4230/LIPIcs.CCC.2019.21 , url =

2019 doi
[23]

Transactions of the Association for Computational Linguistics , volume =

Saturated Transformers Are Constant-Depth Threshold Circuits , author =. Transactions of the Association for Computational Linguistics , volume =. 2022 , doi =

2022
[24]

Quantum Generalizations of the Polynomial Hierarchy with Applications to

Gharibian, Sevag and Santha, Miklos and Sikora, Jamie and Sundaram, Aarthi and Yirka, Justin , journal =. Quantum Generalizations of the Polynomial Hierarchy with Applications to. 2022 , doi =

2022
[25]

39th Computational Complexity Conference (CCC 2024) , pages =

The Entangled Quantum Polynomial Hierarchy Collapses , author =. 39th Computational Complexity Conference (CCC 2024) , pages =. 2024 , publisher =. doi:10.4230/LIPIcs.CCC.2024.6 , url =

2024 doi
[26]

17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =

Oracle Separations for the Quantum-Classical Polynomial Hierarchy , author =. 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =. 2026 , publisher =. doi:10.4230/LIPIcs.ITCS.2026.2 , url =

2026 doi
[27]

Proceedings of Thirty Eighth Conference on Learning Theory , pages =

Quantum State and Unitary Learning Implies Circuit Lower Bounds , author =. Proceedings of Thirty Eighth Conference on Learning Theory , pages =. 2025 , publisher =

2025
[28]

2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages =

Quantum Learning Algorithms Imply Circuit Lower Bounds , author =. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2022 , publisher =. doi:10.1109/FOCS52979.2021.00062 , url =

2021
[29]

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , pages =

Quantum Meets the Minimum Circuit Size Problem , author =. 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , pages =. 2022 , publisher =. doi:10.4230/LIPIcs.ITCS.2022.47 , url =

2022 doi
[30]

31st Conference on Computational Complexity (CCC 2016) , pages =

Learning Algorithms from Natural Proofs , author =. 31st Conference on Computational Complexity (CCC 2016) , pages =. 2016 , publisher =. doi:10.4230/LIPIcs.CCC.2016.10 , url =

2016 doi
[31]

The Twelfth International Conference on Learning Representations , year =

The Expressive Power of Transformers with Chain of Thought , author =. The Twelfth International Conference on Learning Representations , year =
[32]

2023 , eprint =

Average-Hard Attention Transformers Are Constant-Depth Uniform Threshold Circuits , author =. 2023 , eprint =

2023
[33]

Advances in Neural Information Processing Systems , volume =

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages , author =. Advances in Neural Information Processing Systems , volume =. 2024 , publisher =. doi:10.52202/079017-0327 , url =

2024 doi
[34]

Proceedings of the 32nd International Conference on Machine Learning , pages =

Deep Unsupervised Learning Using Nonequilibrium Thermodynamics , author =. Proceedings of the 32nd International Conference on Machine Learning , pages =. 2015 , publisher =

2015
[35]

Advances in Neural Information Processing Systems , volume =

Denoising Diffusion Probabilistic Models , author =. Advances in Neural Information Processing Systems , volume =. 2020 , publisher =

2020
[36]

The Twelfth International Conference on Learning Representations , year =

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems , author =. The Twelfth International Conference on Learning Representations , year =
[37]

2026 , publisher =

Grier, Daniel and Morris, Jackson and Wu, Kewen , booktitle =. 2026 , publisher =. 2601.03243 , archivePrefix =

2026
[38]

The Fourteenth International Conference on Learning Representations , year =

Diffusion Language Models Are Provably Optimal Parallel Samplers , author =. The Fourteenth International Conference on Learning Representations , year =
[39]

SIAM Journal on Computing , volume =

On the Correlation of Parity and Small-Depth Circuits , author =. SIAM Journal on Computing , volume =. 2014 , doi =

2014
[40]

Advances in Neural Information Processing Systems , volume =

Chain-of-Thought Prompting Elicits Reasoning in Large Language Models , author =. Advances in Neural Information Processing Systems , volume =. 2022 , publisher =

2022
[41]

First Conference on Language Modeling , year =

On Limitations of the Transformer Architecture , author =. First Conference on Language Modeling , year =
[42]

Advances in Neural Information Processing Systems , volume =

Separations in the Representational Capabilities of Transformers and Recurrent Architectures , author =. Advances in Neural Information Processing Systems , volume =. 2024 , publisher =

2024
[43]

Interactive Shallow

Grier, Daniel and Schaeffer, Luke , booktitle =. Interactive Shallow. 2020 , publisher =. doi:10.1145/3357713.3384332 , url =

2020
[44]

2024 , eprint =

Gemini 1.5: Unlocking Multimodal Understanding Across Millions of Tokens of Context , author =. 2024 , eprint =

2024
[45]

2025 , eprint =

Wavefunction Flows: Efficient Quantum Simulation of Continuous Flow Models , author =. 2025 , eprint =

2025
[46]

2021 , url =

A Mathematical Framework for Transformer Circuits , author =. 2021 , url =

2021
[47]

2024 , url =

Introducing. 2024 , url =

2024
[48]

2019 , url =

Language Models Are Unsupervised Multitask Learners , author =. 2019 , url =

2019
[49]

Advances in Neural Information Processing Systems , volume =

Representational Strengths and Limitations of Transformers , author =. Advances in Neural Information Processing Systems , volume =. 2023 , publisher =

2023
[50]

17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =

Unconditional Quantum Advantage for Sampling with Shallow Circuits , author =. 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =. 2026 , publisher =. doi:10.4230/LIPIcs.ITCS.2026.17 , url =

2026 doi
[51]

2025 , eprint =

Seed Diffusion: A Large-Scale Diffusion Language Model with High-Speed Inference , author =. 2025 , eprint =

2025
[52]

Advances in Neural Information Processing Systems , volume =

Large Language Diffusion Models , author =. Advances in Neural Information Processing Systems , volume =. 2025 , publisher =

2025
[53]

2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

Theoretical Limitations of Multi-Layer Transformer , author =. 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2025 , publisher =. doi:10.1109/FOCS63196.2025.00136 , url =

2025

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Proceedings of the 40th International Conference on Machine Learning , pages =

Tighter Bounds on the Expressivity of Transformer Encoders , author =. Proceedings of the 40th International Conference on Machine Learning , pages =. 2023 , publisher =

work page 2023

[2] [2]

Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , pages =

Overcoming a Theoretical Limitation of Self-Attention , author =. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , pages =. 2022 , publisher =. doi:10.18653/v1/2022.acl-long.527 , url =

doi:10.18653/v1/2022.acl-long.527 2022

[3] [3]

, booktitle =

Kumar, Vinayak M. , booktitle =. Tight Correlation Bounds for Circuits Between. 2023 , publisher =. doi:10.4230/LIPIcs.CCC.2023.18 , url =

work page doi:10.4230/lipics.ccc.2023.18 2023

[4] [4]

2024 , eprint =

Improved Circuit Lower Bounds and Quantum-Classical Separations , author =. 2024 , eprint =

work page 2024

[5] [5]

Science , volume =

Quantum Advantage with Shallow Circuits , author =. Science , volume =. 2018 , doi =

work page 2018

[6] [6]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages =

Exponential Separation Between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits , author =. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2019 , publisher =. doi:10.1145/3313276.3316404 , url =

work page arXiv 2019

[7] [7]

Nadimpalli, Shivam and Parham, Natalie and Vasconcelos, Francisca and Yuen, Henry , booktitle =. On the. 2024 , publisher =. doi:10.1145/3618260.3649662 , url =

arXiv 2024

[8] [8]

On the Computational Power of

Anshu, Anurag and Dong, Yangjing and Ou, Fengning and Yao, Penghui , booktitle =. On the Computational Power of. 2025 , publisher =. doi:10.1145/3717823.3718189 , url =

arXiv 2025