{"id":"cadf58c7-d6c4-44c2-baed-77ec63e4fa40","arxiv_id":"2608.03962","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"Low-depth quantum circuits can solve functional and sampling tasks that small constant-depth transformer and diffusion language models provably cannot.","lead":"This paper proves two formal separation results: constant-depth quantum circuits can compute a function and sample a distribution that bounded-resource classical transformer and diffusion language models cannot match. It is the first complexity-theoretic bridge between shallow quantum advantage and LLM architectures.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Functional lower bound applies CPW25 outside its stated bandwidth regime: Lemma 3.9 yields protocol bandwidth B=Tt, but Theorem 3.5 requires B≤T.","rationale":"The reader identified the within-round conditional-independence axiom of DLMs as the weakest assumption. That concern is real but is a scope limitation: the paper explicitly defines its DLM model with this product structure (Section 2.3.2), so the distributional theorem is internally valid under that formal model. The functional lower bound, by contrast, appears to apply the CPW25 communication lower bound outside its own stated hypothesis in the paper (Theorem 3.5: B ≤ T; Lemma 3.9 produces B = Tt > T). This is a proof-level gap in one of the two central separations, not merely a mismatch between the formal model and practical LLMs. It is therefore the more load-bearing concern. The reader's conditional verdict remains appropriate, but for a different reason: the functional separation needs either a corrected citation/statement of CPW25 or a reparameterized reduction. I do not recommend rejection, because the gap may be fixable by a stronger version of the CPW25 theorem or by adjusting the parameterization, and the distributional separation appears sound within its stated model.","tokens_in":49388,"tokens_out":33146,"duration_ms":329213,"concrete_test":"Independently verify the exact hypothesis of Theorem 4.1 in [CPW25], and in particular whether its 'bandwidth B ≤ T' condition is essential. Then re-derive Eqs. (36)-(37) of Theorem 3.10 with B = Tt substituted explicitly: if the hypothesis is not satisfied, determine whether the CPW25 proof can be strengthened to all B on the T-parameterized instance. A direct check is to fix L=2, take a concrete T, compute t from Lemma 3.8, and ask whether a bandwidth-Tt protocol for the T-parameterized IterInx can trivially solve it; if such a protocol exists, Eq. (36) is unsound as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The transformer lower bound in Theorem 3.10 depends entirely on the reduction of Lemma 3.9: a width-T transformer solving the T-parameterized IterMultInx yields a protocol for the T-parameterized IterInx with bandwidth B = Tt, where t is the copy parameter. The proof then invokes Theorem 3.5, the CPW25 black box, to conclude B ≥ n_orig^α (Eq. (36)). But Theorem 3.5 as stated applies only to protocols with bandwidth B ≤ T on the T-parameterized IterInx instance. Lemma 3.8 shows t = C_L T^{c_L} with c_L = 2^{O(L)}, so B = Tt is not merely a constant factor larger than T; it exceeds the theorem's stated hypothesis by a polynomial factor. Consequently, the application of Theorem 3.5 is invalid unless the CPW25 lower bound is known to hold for all bandwidths B on the T-parameterized instance, which the stated theorem does not assert. This is not a modeling-preference issue: it is a correctness gap inside the formal proof of the functional separation. If the CPW25 theorem genuinely requires B ≤ T, the reduction produces a protocol that is allowed more bandwidth than the lower bound covers, so no contradiction follows.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":49646,"tokens_out":26284,"duration_ms":210750,"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":[{"comment":"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.","section":"§3.4.2, Theorem 3.10, Eq. (36)"},{"comment":"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.","section":"§4.4.3"},{"comment":"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.","section":"§2.3.2, Theorem 4.1"}],"minor_comments":[{"comment":"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.","section":"§3.4.2, just before Theorem 3.10"},{"comment":"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.","section":"Lemma 4.9"},{"comment":"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.","section":"Theorems 3.6 and 3.7"},{"comment":"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.","section":"Lemma 2.2 and Theorem 4.4"},{"comment":"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.","section":"Footnote 17, p. 38"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the bandwidth-regime mismatch in the functional lower bound; this is a concrete technical gap that needs to be resolved before the claim can be accepted. The authors should also be asked to provide a complete proof for the revision/remasking extension, which is currently only sketched. The paper is otherwise well-motivated and the quantum upper bounds are solid; the distributional framework is interesting even if scoped to the standard DLM model."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nSoft 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.\n\nOn 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.\n\nAlso, 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.\n\nWho 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.","headline":"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.","tokens_in":50170,"tokens_out":4669,"would_cite":true,"duration_ms":44244,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves unconditional separations between shallow quantum circuits and bounded classical LLM architectures, both for function computation and for distribution sampling.","keywords":["quantum advantage","shallow quantum circuits","transformer lower bounds","diffusion language models","block parity distribution","chain-of-thought","sampling separations","QNC^0"],"falsifier":"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.","tokens_in":49179,"feed_emoji":"⚛️","tokens_out":13130,"duration_ms":113163,"temperature":0.7,"pith_summary":"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.","feed_headline":"Shallow quantum circuits beat LLMs on two tasks","feed_subtitle":"A 4-deep quantum circuit samples a parity distribution that shallow diffusion LLMs cannot match with chain-of-thought.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It supplies the iterated-index communication lower bound and the autoregressive model that the functional separation imports to rule out small-width transformers.","marker":"[CPW25]"},{"why":"It defines the diffusion-language-model parallel-sampler framework and the even-parity distribution that the block-parity candidate generalizes.","marker":"[JHC26]"},{"why":"It establishes the parity lower bound for GC$^0[\\log n]$ circuits that the final-bit prediction argument contradicts.","marker":"[Kum23]"},{"why":"It provides the poor man's cat state construction that gives the constant-depth QNC$^0$ sampler for block parity.","marker":"[BWKST19]"},{"why":"It introduces the GC$^0[k]$ circuit class used for scheduling and denoising, and supplies related separations and parity bounds.","marker":"[GK24]"},{"why":"It gives the multi-index trick that lets the quantum upper bound avoid explicitly granted copies of the input.","marker":"[GMW26]"},{"why":"It originates the QNC$^0$-versus-shallow-classical separation framework and the parity-based sampling idea underlying the distributional result.","marker":"[BGK18]"},{"why":"It is the classical parity lower bound for AC$^0$ that the final-step parity prediction contradicts, complementing the GC$^0$ bound.","marker":"[H˚as14]"}],"fun_headline_variants":["Quantum beats LLMs on prediction and generation","Shallow quantum circuits outdo LLMs on two tasks","Diffusion LLMs can't sample this quantum distribution","Chain-of-thought can't rescue diffusion LLMs from quantum sampling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quantum beats LLMs on prediction and generation","Shallow quantum circuits outdo LLMs on two tasks","Diffusion LLMs can't sample this quantum distribution","Chain-of-thought can't rescue diffusion LLMs from quantum sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001557,"raw_usage":{"total_tokens":6302,"prompt_tokens":1105,"completion_tokens":5197,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":721,"completion_tokens_details":{"reasoning_tokens":5132}},"tokens_in":721,"tokens_out":5197,"duration_ms":34211,"temperature":1.0,"reasoning_tokens":5132,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:46:22.831873+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}