- 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 -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 but hard to approximate by constant-round DLMs with 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
-
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.
-
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
- Important proof gaps affect both main results.
For the functional result, Theorem B.5 requires bandwidth on the -parameterized IterInx instance. Lemma B.9 produces an IterInx protocol with bandwidth , 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 where the product-bias identity requires ; this local error appears repairable.
- 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 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 circuit: take independent uniform , set , and output . 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
-
What lower bound justifies applying Theorem B.5 to the bandwidth- protocol obtained in Lemma B.9, on the same -parameterized instance?
-
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 with the stated resources.
-
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.
-
Which precise lemma provides the advance beyond [2] and [3]? Given the simple classical sampler for block parity, what additional theoretical insight is established by the quantum comparison?
Thank you very much for the careful technical assessment. Here are specific responses.
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 t, where t=TOL(1) for every fixed L (Lemma B.8). We agree that applying Theorem B.5 directly with bandwidth Tt 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 t replicated tables can equivalently be viewed as a single vector-valued function Zℓ:[Nℓ−1]→[Nℓ−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 t 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 R 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 R 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 R revision events. Since 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εb.