Paper deep dive
Separating quantum circuits from classical LLMs
Srinivasan Arunachalam, Arkopal Dutt, Hari Krovi, Rik Sengupta
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.03962v1
- Canonical: https://arxiv.org/abs/2608.03962v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
165,787 characters extracted from source content.
Expand or collapse full text
Separating quantum circuits from classical LLMs Srinivasan Arunachalam ∗ Arkopal Dutt ∗ Hari Krovi ∗ Rik Sengupta ∗ 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 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 (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 DLMs rely on. 2. Functional separation. We exhibit a function computable in ∧◦ QNC 0 [log logn] (i.e., a family of O(log logn)-depth QNC 0 circuits, where n is the input length, followed by a single classical AND gate) such that any constant-depth decoder-only transformer computing the function must be large: it would have to have width n Ω(1) . Together, our work initiates the study of quantum advantage in the era of large language models. Contents 1 Introduction2 1.1 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 1.2 Functional separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 1.3 Distributional separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 1.4 Outlook and further directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Preliminaries and Background12 2.1 Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Transformer models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Diffusion models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3 Functional separation: quantum versus transformer models22 3.1 Motivation for our candidate problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 Final candidate function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Quantum upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4 Classical lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.5 Obstructions in further improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4 Distributional separation: quantum circuits versus DLMs39 4.1 Main result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 Quantum upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 Lower bound: important lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.4 Proof of the classical lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 ∗ IBM Research. srinivasan.arunachalam@ibm.com, arkopal@ibm.com, hari.krovi@ibm.com, rik@ibm.com. 1 arXiv:2608.03962v1 [quant-ph] 4 Aug 2026 1 Introduction A central task in quantum computing is finding problems solvable by quantum computers but not solvable by their classical counterparts. At its strongest, this asks for an unconditional complexity- theoretic separation between quantum and classical computing. In the oracular model, exponential separations are well-known, but in the non-oracular model such separations are far beyond current techniques for general polynomial-time computation. More recently, a fruitful line of work has focused on restricted models and asking if one can show unconditional separations between quantum and classical computation. One such direction that has received a lot of traction recently is understanding the power of shallow circuits, i.e., constant-depth quantum circuits in contrast to their classical counterparts. Shallow quantum circuits are well motivated from a practical point of view, since they are potentially implementable on near-term fault-tolerant quantum computers. Understanding the power of these circuits was spurred by the groundbreaking work of Bravyi, Gosset, and K ̈onig [BGK18], who gave an unconditional relational separation between quantum and classical shallow circuits. Concretely, they considered the class of classical circuits of polynomial size, constant depth, unbounded fan-out, and bounded fan-in gates (which is often referred to as NC 0 ) and the class of quantum circuits of polynomial size and constant depth with single- or two-qubit gates (which is referred to as quantum NC 0 , denoted QNC 0 ). In [BGK18], they exhibited a relational problem 1 solvable by a QNC 0 circuit but not by any NC 0 circuit. Subsequent works strengthened this result in several directions, showing that the classical lower bound holds in the average case [CSV21, LG19], that the quantum upper bound is robust to noise [BGKT20], that stronger separations can be obtained between QNC 0 vs AC 0 [BWKST19], QNC 0 vs GC 0 [GK24] (we will formally define these classes later), as well as in interactive settings [GS20] and sampling separations between QNC 0 and classical classes [BWP26, GKM + 26]. These results suggest that, in general, shallow quantum circuits can generate and utilize correlations that are inaccessible to several “standard” shallow classical circuit classes. A natural next question is whether such separations can be shown for more “contemporary” classical computational models. In this direction, given the remarkable success of large language models (LLMs) in practice, a rapidly growing body of work has sought to understand the expressive power and computational limitations of various models of LLMs. In this regime, transformer mod- els [VSP + 17] have been the dominant architecture for prediction-based language modeling, while diffusion language models [SDWMG15, HJA20] (DLMs) have provided an alternative paradigm for content generation. Although these models can seem superficially different from the traditional circuit complexity classes studied in complexity theory (such as NC 0 , AC 0 , and TC 0 ), their the- oretical abstractions often retain a key shallow-classical feature: every layer of token updates is generated by bounded-depth classical computation with limited bandwidth. This suggests a new form of quantum-classical comparison: rather than only asking whether one can separate QNC 0 from the “theoretically-motivated” circuit classes NC 0 , AC 0 , or GC 0 , we can now also ask whether shallow quantum circuits can solve computational or sampling tasks that are hard for transformers or DLMs, resulting in a new realm of separation results. Given the recent surge of interest in understanding large language models and the role of quantum computing in machine learning, a particularly timely question is the following: Is there a task solvable by shallow quantum circuits but not by classical LLMs? 1 Unlike a functional problem which has a unique output for every input, a relational problem can have several outputs for an input; the goal is to produce one such valid output for a given input. 2 1.1 Main results We show two results that separate quantum shallow circuits from transformers and DLMs for functional and distributional tasks respectively. In particular, we exhibit the following: 1. a function that is computable by a O(log logn)-depth QNC 0 circuit followed by a single classical AND gate, but hard to compute by a shallow-depth transformer unless it is “large”; 2 2. a distribution that is sampleable in QNC 0 , but hard to approximately sample from a DLM which uses GC 0 denoisers, 3 has sublinear chain-of-thought/workspace, and a sublinear number of output-token revision/remasking events (which are the features modern DLMs rely on). A key distinction from earlier shallow-circuit separations is that our lower bounds are not only against classical circuit classes such as NC 0 , AC 0 , GC 0 , but against basic transformer and diffusion language models used in recent theoretical studies of modern language models [CPW25, JHC26] to understand the strengths and weaknesses of these models. Although our tasks are deliberately complexity-theoretic, the separating models are among the closest formal proxies currently available for the prediction and generation mechanisms used in practice. To formulate our main results formally, we need a high-level definition of transformers and DLMs, which we provide in the next sections (Sections 1.2 and 1.3). For each of these models, we give an overview of some prior classical works in the related area, which serve as a starting point for our results; after that, we state our main theorem for that model, and give a detailed proof sketch of the separation in question. 1.2 Functional separation 1.2.1 Transformer models (a high level overview) In this section, we give a high-level overview of transformers, sufficient to understand the proof overview that follows subsequently. In Section 2.2 we give a detailed overview of the model. Transformers form the backbone of most modern LLMs. The core transformer architecture is specified by a number of parameters: the input length n (the “context size”), the number L of layers (the “depth”), the number H of attention heads, the embedding dimension d, and a precision parameter p. A transformer can be viewed as a sequence of length-preserving functions on d-dimensional real vectors across a sequence of layers, once the input text has been embedded into one such sequence. The transition between every pair of adjacent layers in the transformer architecture is determined by parameterized query, key, and value vectors. At a high level, the so-called attention mechanism takes as input a vector x ∈ R n , and then takes a position-wise weighted average of value vectors (where the weights are a function of the key and query vectors), followed by a position-wise piecewise affine transformation. In this work, we exclusively consider decoder-only transformers, where each position attends only to positions preceding it, reflecting the causal structure of autoregressive generation. We emphasize that almost every prominent modern LLM, such as GPT [RWC + 19], Claude [ENO + 21], Gemini [G + 24] and LlaMa [Met24], use variants of the decoder-only transformer architecture, due to their superiority in next-token prediction. From the perspective of complexity, the key resource for transformers is not merely the total number of parameters, but the total amount of information communicated through the attention mechanism at each layer. Following recent work, this notion of “useful” information transmitted through the layers is captured by the so-called width Hdp, which is simply the product of the number 2 We formally define the notion of small and large transformers in Section 3. 3 The circuit class GC 0 [k] consists of unbounded fan-in and fanout AND, OR, NOT gates along with the G[k] gate, which on input x∈0, 1 n , can compute an arbitrary function of x if|x|≤ k and evaluates to 0 otherwise. Throughout this work, we will restrict to k ≤ O(logn). 3 of heads, the embedding dimension, and the precision used to represent each numeric coordinate. Following the convention of [CPW25, SHT23] we say a transformer is small if Hdp = n o(1) , and large otherwise. In particular, a computational task can be thought of as requiring large width if every constant-depth decoder-only transformer solving the problem requires large internal communication in between the layers. We note that the assumption of constant depth is reasonable in practice. 1.2.2 Prior works and context We now provide some context and prior works in understanding the complexity of transformers, which will set up the main motivation for our results. (i) There have been several recent complexity theoretic works characterizing the power of trans- former models in terms of circuits [C22, CCP23, YCA24, LLZM24]. Depending on the assumptions on the parameters of the transformers in question (i.e., H,d,p defined earlier), their expressive power can be shown to lie somewhere roughly between AC 0 (e.g., for constant- precision transformers using unique hard attention) and TC 0 (log-precision transformers using softmax attention). Hence, it is conceivable that the results in [BWKST19, GK24] imply that QNC 0 can solve (relational) tasks that the small class of constant-precision transformers can- not solve. 4 (i) Chen, Peng, and Wu [CPW25] were the first to show unconditional limitations of decoder- only transformer models (in the regime of non-constant precision, i.e., in the TC 0 regime). Although their main candidate problem certifying hardness is not quite phrased in these terms, it can actually be viewed as a variant of the well-known index function. Their lower bound was obtained via a reduction to a novel communication complexity model. (i) Finally, a recent result of Grier et al. [GMW26] shows how to compute arbitrary TC 0 functions in QAC 0 , when the quantum circuit is provided with O(n 2 ) copies of the input (where n is the length of the input), 5 and further shows that computing the index function essentially requires these many copies. The starting point for our work is the observation that we can avoid the O(n 2 ) copies for a certain class of problems which are also hard to compute by transformers (which computationally form a subclass of TC 0 ). In particular, we generalize the candidate function of [CPW25], and show that this generalized function requires large width for constant-depth transformers computing it, but is computable by the “simplest” non-trivial class∧◦ QNC 0 [log logn], i.e., an O(log logn)-depth QNC 0 circuit followed by a single classical AND gate. 6 1.2.3 Proof sketch of the functional separation Why not a relational separation? We first explain why the well-known relational separations used in [BGK18, BWKST19, GK24] do not imply separations between QNC 0 and transformers of the form that we want. To the best of our knowledge, almost all known existing techniques for proving lower bounds on transformer width are primarily via proving communication complexity 4 We believe making this rigorous might be fruitful and leave it for future work. 5 Note that in classical complexity we often assume that the bits and gates have fanout, i.e., x 1 ,...,x n can be fed to several gates, and so we can get polynomially many copies of the bits x 1 ,...,x n for free. However, quantum gates do not have fanout, hence this is not a free operation for quantum circuits. Hence, one needs to account for “copying” the input x and using t copies of the input increases the depth of the circuit by O(logt); so, creating poly(n) many copies of the input adds O(logn) depth to the quantum circuit. 6 We call this the simplest class here since we show in addition that, if a function is exactly computed by ∧◦ QNC 0 [log logn], then this function is actually computable by AC 0 . 4 lower bounds [SHT23, PNP24, CPW25]. In this communication model, the relevant resource is not the total number of bits of communication, but rather the per-player bandwidth, which is typically measured proportional to the size of that player’s input. This creates a basic obstacle for relational problems: the player’s output needs to be similar to the input (in order to have a well-formed problem), and if each player is allowed bandwidth proportional to their input length, then enough information can be communicated to solve the corresponding relational communication task in a straightforward way. Thus, the bandwidth regime in which we can hope for a nontrivial lower bound essentially disappears. In contrast, for functional problems, there are meaningful intermediate bandwidth regimes: the output is a single fixed bit, so it makes sense to ask for a bound on the amount of local information that must be transmitted in order to compute this target bit. This is the reason we focus on a functional separation instead of a relational one. Our candidate and lower bound. In light of the above discussion, we turn towards functional problems, and in particular to the one considered by [CPW25], essentially a variant of the iterated index function. Before discussing the iterated version, we first define the index function: on input (i, x) ∈ [n]×0, 1 n , the goal is to output x i . It is a well-known fact that the index function can be computed in AC 0 ; our goal was to express this circuit in terms of quantum gates, and in particular through weak QAC 0 circuits, which are the same as QNC 0 except that we also allow many-qubit gates (potentially acting on n qubits) on top of the usual one- and two-qubit gates. There have been several recent works aimed at understanding the power of multi-qubit gates in computing well-known Boolean functions [GHMP02, Ros21, VH25, FGPT25, GGJ26a, GGJ26b, JTVW26, ADOY25, BEG26, NPVY24]; however, a common concern acknowledged in these works is that it is undesirable to allow multi-qubit gates in quantum circuits, since they require coherent interaction between arbitrary qubits, which is incompatible with locality and noise constraints in physical architectures of current quantum devices. At this point, the following sequence of results yields our separation: 1. Index with copies. We first observe that the index function can be computed in QAC 0 assuming we have copies of the input. This is undesirable for two reasons: (i) we require copies and (i) QAC 0 circuits can be trivially simulated by QNC 0 circuits of depth O(logn). At this point, we observe that one can overcome this trivial simulation as follows. We observe that the index function can be written as a QNC 0 [log logn] circuit followed by a (large) AND gate at the end, however we still need copies of the input i in order to compute x i . 2. Generalizing to iterated index, still with copies. Next, consider the iterated index function (as defined by Chen et al. [CPW25]) as follows: IterInx : [m]× [N 1 ] m × [N 2 ] logN 1 ×·× [N ℓ ] log(N ℓ−1 ) → [N ℓ ], defined as IterInx(i,x 1 ,...,x ℓ ) = x ℓ (x ℓ−1 (x ℓ−2 (·x 1 (i))·)),(1) for a pre-defined choice of parameters m,N 1 ,N 2 ,...,N ℓ−1 . In other words, we iteratively compute index on (i,x), look at x i ∈ [N 1 ], then evaluate x 2 on x 1 (where we view x 1 as a (logN 1 )-bit string) and repeat this iteratively for ℓ many functions. Using the previous bullet point wherein one can compute index using copies, we show that one can actually even compute IterInx also in ∧◦ QNC 0 [log logn] given copies of the input. 3. Removing the multiple copies. The next natural step is to remove the assumption of many copies of the input being given. Using a standard trick also used in [GMW26], we first 5 define the multi-index function as: MultInx : (i 1 ,...,i N ,x) = x i · [i 1 =· = i N ],(2) which is now a total function. Note that by definition, if i 1 = · = i N , then we effectively have access to copies of the input. However, the issue is that one needs to check the condition [i 1 = · = i N ]. For this, we show that this indicator can be checked in ∧◦ QNC 0 [log logn] as well. Furthermore, the same circuit used for checking the index can in fact also compute x i without increasing the complexity (our construction is subtle in that we ensure that the eventual circuit is not in ∧◦∨◦ QNC 0 [log logn], but just a single AND gate at the end of the QNC 0 [log logn] circuit). 4. Generalizing to a hard problem for transformers. Now that we have a total function MultInx, the goal is to prove a lower bound against transformers. As we observed earlier, this problem is a priori easy for decoder-only transformers. To make it hard for the transformer model, we define our final candidate function to be the iterated multi-index function, denoted IterMultInx (putting together the functional computation Eq. (1) along with the predicate of Eq. (2)). Here, we have copies of truth tables x 1 i ,...,x ℓ i i∈[t] (the t = 1 case is precisely the IterInx function) and with these copies of the truth table and index position, we show that IterMultInx can be computed in our desired quantum circuit class. A description of this final candidate is quite dense and technical, and so we refer the reader to Section 3.2.2 for the details. 5. Putting everything together. The main challenge in putting together everything is keep- ing track of several parameters which need to be carefully chosen to witness our separation. Furthermore, the current outline is simplified slightly for ease of readability, but the eventual IterMultInx candidate is actually chosen with a slightly more contrived base index function which is also defined over a larger alphabet. With these technicalities in place, we concretely show that (i) the IterMultInx can be computed still in ∧◦ QNC 0 [log logn]; (i) the IterMultInx problem can be reduced to the IterInx problem, and the hardness for transformers can be therefore imported via the lower bound by Chen et al. [CPW25]. We note here that our lower bound is polynomially weaker than the one in [CPW25], since our problem is more general. Finally, we remark that our separation above is essentially tight. In particular, we show that for deterministic protocols, any function f that is computed by a ∧◦ QNC 0 [log logn] circuit whose depth is at most log logn (i.e., when the implicit constant in the O(log logn) depth is at most 1) can also be computed in AC 0 , a circuit class that essentially corresponds to transformers with constant precision (which is a strong assumption when it comes to transformer computations). Since our goal is to prove lower bounds against non-constant precision transformers, our quantum upper bound of∧◦ QNC 0 [log logn] (where the implicit constant in the O(log logn) depth is strictly greater than 1) allows us to obtain a function that is in QNC 0 but not computable by transformers unless their width is large, i.e., Hdp = n Ω(1) . 1.3 Distributional separation 1.3.1 Diffusion models (a high level overview) In this section, we give a high-level overview of DLMs, sufficient to understand the proof overview that follows. As with transformers in Section 1.2, we first give a detailed overview of the model. Diffusion language models (DLMs) are a central generative paradigm for tasks such as image and text generation. In this work, we will exclusively consider discrete diffusion models. 6 DLMs are organized differently from transformers, and are tailor-made to generate samples from distributions. At a high level, DLMs generate samples by training models via the following process: they introduce random noise to training data, and then train the model to systematically remove the noise, so that the eventual model can generate new noiseless samples from the distribution. More formally, instead of generating tokens strictly from left to right (as in transformers), a DLM starts with the so-called masked sequence mask ⋆ (which one can think of as maximally random) and iteratively reveals/unmasks tokens to produce elements from the alphabet Σ (for simplicity in this paper we let Σ = 0, 1). So, at any point in the process, the DLM maintains a partially revealed sequence whose coordinates are of the form Σ∪mask, where Σ is the fixed token alphabet and mask is an auxiliary token. The sequence contains input coordinates and output coordinates, together with possible auxiliary workspace or chain-of-thought (CoT) coordinates. The computation itself begins with several masked coordinates, and proceeds through a number of denoising rounds which consists of two phases: In the first phase, a scheduler decides on the set of currently masked coordinates to be revealed, a decision that can adaptively depend on all the (non-mask) tokens generated so far, including workspace tokens; and in the second phase, a denoiser circuit is applied to each newly revealed coordinate, and a value is sampled. The defining structural feature of a standard DLM is within-round conditional independence. Once the current partially generated sequence is fixed, the coordinates updated in that round are sampled independently (but potentially dependent on the sequence at the beginning of the round), using the corresponding coordinate-wise denoising marginals. Thus, after conditioning on the visible transcript and the current workspace/CoT coordinates, a single denoising step induces a product distribution over the coordinates it updates. Global correlations can still arise, but only through the iterative interaction of scheduling, workspace, and future denoising rounds. This makes DLMs powerful enough to build correlations adaptively, while still imposing a strong structural constraint on what can be generated in one round. 1.3.2 Prior works and context The starting point for our result is the work by Jiang, Haghtalab, and Chen [JHC26], which studies DLMs as parallel samplers and analyzes the strengths and weakness of revision/remasking/chain- of-thought in DLM models. In particular, there is one striking feature in their work: they consider the distribution: U ⊕ B = unifx∈0, 1 B :|x|≡ 0 (mod 2). They show that standard DLMs, without remasking or revision, cannot sample from this distribution in O(1) steps when the predictor and scheduler are implemented by AC 0 circuits. However, their work cannot handle the scenario where the DLMs are augmented with a (bounded) number of chain-of-thought tokens, and a (bounded) number of token revision/remasking events. Note that both of these are features that modern DLMs crucially rely on. Although incomparable, the best known distribution sampling quantum-classical separation we know of is due to Bene Watts and Parham [BWP26] separating QNC 0 from NC 0 ; so it is natural to try and prove sampling lower bounds using the candidate problem from [JHC26] against DLMs with AC 0 denoisers. Furthermore, several quantum/classical circuit separations [BGK18, BWKST19, BWP26] are in essence based on the observation that one can sample parity-based relations and distributions in QNC 0 . With this in mind, our main contributions are as follows: (i) we generalize the candidate problem of [JHC26] and define a block-parity function, which still admits an efficient QNC 0 protocol, but is provably hard for DLMs; (i) using the generalized candidate, we are able to prove lower bounds even when we allow 7 revision/remasking and chain-of-thought (with the caveat that we only allow at most sublinear number of tokens for these augmented features); (i) our lower bounds allow GC 0 denoisers 7 , which are significantly stronger than AC 0 denoisers; (iv) we show hardness even to approximately sample from the newly constructed distribution. Indeed, along the way, we show several structural properties of DLMs that we hope might be of independent interest. The main technical contribution of our work is the classical lower bound, which combines several ideas from theoretical computer science. First, we use a direct-product style amplification to turn many local parity constraints into a global obstruction. Second, we view a DLM execution as a query-like process whose visible behavior, after hiding the workspace/CoT coordinates, can be expressed as a convex combination of simple decision-tree-like distributions. Finally, we prove that block-parity functions cannot be approximated by such small convex combinations. We make this candidate problem and proof structure clear in the next section. 1.3.3 Proof sketch of the distributional separation We now give a proof sketch of our DLM lower bound. The task that we consider here is to sample from the distribution: D blk = M O b=1 U ⊕ B =(x 1 ,...,x M ) : x i ∈0, 1 B ,|x i |≡ 0 (mod 2) for all i within total variation distance η for some fixed constant η > 0. The quantum algorithm to sample from this is easy, and the main ideas have appeared before [BGK18, BWKST19, GK24]. We now sketch the classical lower bound. Assume towards a contradiction that there exists a constant- round standard DLM which samples from D blk , with workspace length s, fully adaptive scheduling, bounded revision/remasking, and polynomial-size constant depth GC 0 [logn] scheduling and denois- ing circuits. For each block b∈ [M ], define its completion round to be the first round after which all B output coordinates in that block have been generated. Let r b be the number of previously ungenerated coordinates of block b that are generated in this round. Each block is completed in one of two ways. • r b ≥ 2, i.e., the DLM completes the block by unmasking many fresh coordinates at once; • r b = 1, i.e., the DLM completes the block by generating a single final coordinate, with the remaining B− 1 coordinates having already been fixed in previous rounds. The proof is a win–win argument over these two completion modes. Suppose first that many blocks are completed with r b ≥ 2. For such a block, conditioned on the coordinates revealed earlier in the block, the r b fresh coordinates are not freely distributed: under the target distribution, they must satisfy one affine parity constraint. Thus a round that completes many such blocks must simultaneously realize many independent within-block parity constraints. We prove a structural theorem below showing that this is impossible for the conditional laws produced by a bounded- workspace DLM. Hence, it follows that only few blocks can be completed in the multi-bit way and for most blocks, we must have r b = 1. But then the DLM is forced into a “last-bit prediction” regime: when it completes such a block, the final coordinate has to be the parity of the previous B− 1 coordinates. This can be used to show that a shallow AC 0 or GC 0 circuit predicts parity with constant bias, contradicting the usual parity lower bound of Hastad [H ̊as14] or Kumar [Kum23]. 7 We do not define the class GC 0 here and refer the reader to Section 2.1; we simply note that it is a classical circuit complexity class that is strictly more powerful than AC 0 . 8 Formally, the argument proceeds in four main steps. 1. Mixtures of product distributions induced by DLMs. Fix a round t, and condition on the revealed output history τ out , i.e., the revealed output coordinates for the final sample together with their values, the scheduling history up to round t, and the previously generated workspace/chain-of-thought tokens. Let w denote the revealed current workspace so far. Now, using the independence properties of DLMs, we have that the output distribution of the t-th round conditioned on τ out and w is given by: P (output of the t-th round| τ out ,w) = Q τ out ,w , where Q τ out ,w is a product distribution over the coordinates revealed in round t. Hence, averaging over the possible current workspaces gives: P (output of the t-th round| τ out ) = X w Pr[w | τ out ]· Q τ out ,w .(3) Since the token alphabet has constant size, the current workspace contains at most s tokens, and so there are at most 2 O(s) possible values of w. Consequently, conditioned on any visible transcript, a denoising round induces only a small latent mixture of product distributions. 2. Multi-bit block completions. Now, fix a transcript branch and consider a block b com- pleted in some round with r b ≥ 2. Under the target distribution U ⊕ B , the full block satisfies L B i=1 x b,i = 0. Once some coordinates of the block have already been revealed, the remaining unrevealed coordinates are still uniform subject only to the residual parity constraint deter- mined by the revealed prefix. Therefore, if the DLM completes the block by generating r b fresh coordinates simultaneously, the correct conditional law for these fresh coordinates is: U a b r b := unif ( x∈0, 1 r b : M i x i = a b ) , where a b depends on the previously revealed coordinates and the parity of their respective coordinates. Importantly, these distributions are not products over coordinates: the fresh co- ordinates inside the block must jointly satisfy a parity condition. Since D blk is product across blocks, if many blocks are completed simultaneously, then the target conditional law becomes: V = O b U a b r b ,(4) namely, a product across blocks of internally parity-constrained factors. 3. Inapproximability of Eq. (4). Now, our main structural result is that a distribution of the form given in Eq. (4) cannot be approximated by a small mixture of coordinate-wise product distributions. Quantitatively, if Eq. (3), written abstractly as: P = K X h=1 λ h Q h is a mixture of product distributions satisfying TV(P,V )≤ η, then we necessarily have: logK ≥ Ω X b (r b − 1) ! . 9 Intuitively, each block completed with r b ≥ 2 contributes an independent intra-block parity constraint: the r b fresh coordinates must lie in an affine parity coset, i.e., satisfy ⊕ i x i = a b , rather than in a product distribution. A small latent mixture cannot realize many such constraints simultaneously. Quantitatively, if a round completes a collection of blocks with completion sizesr b , then approximating the corresponding conditional law requires at least 2 Ω ( P b (r b −1) ) product components. On the other hand, after conditioning on the visible tran- script, the only hidden information is the workspace/CoT coordinates, which gives at most K = 2 O(s) mixture components. Hence, we have P b (r b − 1) = O(s) in any typical denois- ing round. In particular, since every block with r b ≥ 2 contributes at least 1 to this sum, only O(s) blocks can be completed by simultaneous multi-bit generation over all (constantly many) rounds. Therefore, when s = o(M ), almost every block must fall in the category where r b = 1. Hence, we have reduced the task of DLM approximating D blk to the task of predicting a parity bit, which will be the basis for our lower bound. 4. Reduction of final-bit completion to parity prediction. Suppose now that a block satisfies r b = 1. At its completion round, the DLM has already generated B− 1 coordinates and must generate the last one. Under U ⊕ B , this last coordinate is forced: X b,j = M i̸=j X b,i . Thus, a successful DLM must predict a parity bit. Technically, if the previous B − 1 bits generated by the DLM were uniformly random, then we are done since we can use known lower bounds of GC 0 , AC 0 computing parity. However, the first B− 1 bits were generated by the DLM itself, while the parity lower bound is for uniform external inputs. This is the most subtle part of the proof, and showing this requires us to account for the entropy of various blocks along the DLM process and show that there exists at least one block among the M blocks in which the pre-completion B− 1 bits have large entropy. In this block b ⋆ , we can use the probabilistic method to show that the pre-completion bits are already close to uniform, which means that we can replace these bits by a set of independent uniform bits, This changes the execution distribution by only o(1) in total variation, while leaving the final completion round unchanged. After this replacement, the final generated bit predicts the parity of a uniform B-bit input with constant advantage. Since the planted execution can be simulated by a shallow GC 0 [logn] circuit, we obtain a shallow circuit that computes parity on B− 1 bits with constant advantage, contradicting the known parity lower bounds for GC 0 [logn] circuits [Kum23, GK24]. 5. Handling Remasking/Revision. Finally, we extend the argument to bounded remask- ing/revision. We observe that this case requires a small modification of the entropy argu- ments. We cannot unfortunately simply restrict our attention to untouched blocks, since the set of touched blocks may be correlated with the generated values. Instead, we account for the entropy argument by adjusting the probability that it is revised after completion. Since there are at most R revision/remasking events, this adds only an o(M ) correction for our pa- rameters. In fact, the same win-win and planting argument as before goes through now. Each output-token remasking/revision event touches exactly one coordinate, and hence belongs to one block. Therefore, at most R distinct blocks can be touched by all such events. On the re- maining blocks, the execution is equivalent to one without output-token remasking/revision, and the previous argument applies. Restricting to the untouched blocks eliminates revision entirely, and the previous argument applies verbatim. Thus the lower bound survives as long as s + R = o(M ), which indeed motivates our main choice of parameters. 10 1.4 Outlook and further directions We see this work as initiating the task of separating quantum computation and classical LLMs. Naturally, there are several questions arising from this work that are worth further investigating. We hope that this serves as a launching pad for substantial future work from the community. 1. Strengthening the separations. Is there a candidate problem for which we can also show DLM-hardness, even in the presence of linear chain-of-thought, and remasking and/or revision? In the case of transformers, we provide one reason why a more typical relational separation (where the input and output length are the same) seems essentially impossible to obtain, but this does not preclude more contrived search-based or relational separations between QNC 0 and decoder-only transformers. Finally, since transformers (without chain-of- thought) are known to be inside TC 0 , it is conceivable that one can obtain a width-Ω(n) lower bound without that implying a complexity-theoretic breakthrough. 2. Randomized separation. This work is only concerned with deterministic functions. If we move to randomized problems (where the output needs to be correct with probability ≥ 2/3, say), can we also show separations, between, e.g., ∧◦ QNC 0 and transformers? 3. Quantum-augmented DLMs. In the model we consider here, recall that new bits are gen- erated using AC 0 or GC 0 denoisers. What if we used quantum circuits to generate new bits? Could such quantum-augmented DLMs be more powerful than using DLMs with classical- circuit based denoisers? More generally, is there a deeper connection between quantum dy- namics and DLMs? 8 4. Copy complexity of transformers. As mentioned earlier, a recent work of Grier et al. [GMW26] shows how to compute TC 0 functions using QAC 0 , with the caveat that one needs O(n 2 ) copies of the input (assumed to be on n bits). Since transformers can be shown to roughly interpolate between AC 0 and TC 0 (depending on the precision parameter and the type of attention used), it is not inconceivable that computing these functions would require fewer copies for the QAC 0 circuit. Could this be formalized? 5. Architecture-independent separations. Our functional and distributional separations rely on different structural limitations of transformers and diffusion language models. Is there a single task solvable by shallow quantum circuits for which every bounded-resource classical language model—whether autoregressive, diffusion-based, or a hybrid of the two—must incur a polynomial cost in at least one of width, chain-of-thought/workspace, sequential generation rounds, or token revision? Final remarks. Finally, we make a couple of important remarks on our results to contextualize our work fairly. The separations that we exhibit here are entirely theoretical. Our motivation is to understand how quantum algorithms could be better than classical LLMs at certain ad hoc tasks that are specifically designed to show these separations. Secondly, state-of-the-art AI models rely on significant amounts of chain-of-thought [WWS + 22], which is empirically known to improve the ability to reason by forcing the LLM to perform step-by-step “scratchpad”-style reasoning, which has been shown to yield better accuracy and more expressivity in practice. Our transformer and DLM lower bounds are proven under the assumption of no chain-of-thought and sublinear chain- of-thought respectively, which are very strong assumptions; the lower bounds do not hold without these restrictions in place, and indeed it is entirely conceivable that our problems are easy for classical LLMs with a reasonable amount of chain-of-thought. The goal of this work, rather, is to 8 A recent work of Layden et al. [LSH + 25] showed that the dynamics of continuous-model DLMs can be efficiently simulated on a quantum computer. 11 initiate the study of the interplay between quantum circuits and classical machine learning models, which we view as being timely and important in the era of large language models. Acknowledgments. SA thanks Yunchao Liu for pointing the work of [CPW25] and thanks Hongxun Wu for clarifications about their work [CPW25]. SA thanks ChatGPT 5.5 for help in proving Theorem 4.4 and the subsequent corollary. RS thanks ChatGPT for some minor corrections in the parameterization of the transformer lower bound, which were since then strengthened by hand. The presentation here has been rewritten and checked by us (any further mistakes are our own). 2 Preliminaries and Background Notation. We use base-2 logarithms throughout. We also define [n] :=1,...,n for any natural number n∈ N and [n] 0 :=0∪ [n]. Information theory. We will need some well-known results in information theory, such as Pinsker’s inequality, which can all be found in [CT91]. For a distribution P on a finite set Ω, its Shannon entropy is defined as: H(P ) := X x∈Ω P (x) log 1 P (x) . It is a fact that H(·)≤ log|Ω|. For a random variable X, we write H(X) for the entropy of its law. For random variables X,Y , the conditional entropy is defined as: H(X | Y ) := E y∼Y [H(X | Y = y)]. We will use the standard facts that: H(X | Y )≤ H(X), H(X 1 ,...,X m | Y )≤ m X i=1 H(X i | Y ). For two distributions P,Q on the same finite set Ω, their total variation distance is defined as: TV(P,Q) := 1 2 X x∈Ω |P (x)− Q(x)|= sup A⊆Ω |P (A)− Q(A)|. We will also use the data processing inequality for total variation: if f : Ω→ Ω ′ is any map, then: TV(f (P ),f (Q))≤ TV(P,Q). Equivalently, taking marginals cannot increase the total variation distance. We will need a couple of additional lemmas, as follows. Lemma 2.1. Let P and Q be distributions on a finite product space T ×Y . Then, we have: E t∼Q T [TV P Y|T =t ,Q Y|T =t ]≤ 2· TV(P,Q), where Q T is the marginal distribution. The same bound also holds when the expectation is taken with respect to P T in place of Q T . 12 Lemma 2.2. Let P and W be distributions on a set X with TV(P,W ) = ε≤ 1/4. Then, we have |H(P )− H(W )|≤ 2ε log|X|+1. Proof. For ∥P − W∥ 1 = 2ε≤ 1/2, we have: |H(P )− H(W )|≤∥P − W∥ 1 log |X| ∥P − W∥ 1 = 2ε log|X|+2ε log 1 2ε , and u log(1/u)≤ (loge)/e < 1 for u∈ (0, 1]. Lemma 2.3. If μ is a distribution on 0, 1 r then TV(μ, unif(0, 1 r ))≤ p r− H(μ). Proof. First we observe that for distributions μ,ν on a finite set, the total variation distance is related to the KL divergence as TV(μ,ν)≤ p KL(μ∥ν). In particular, Pinsker’s inequality together with KL(μ∥ unif) = r− H(μ) gives the statement of the lemma. 2.1 Circuits Classical circuit classes. The classes NC 0 , AC 0 , and TC 0 are well-known in complexity theory. NC 0 is the class of all Boolean functions computable in a circuit family containing circuits with bounded fan-in (i.e., the number of inputs to every gate is O(1) independent of n), constant depth (i.e., every circuit in the family has depth O(1) independent of n, the number of inputs to the circuit itself), and basis ∧,∨,¬. AC 0 is the class of all Boolean functions defined the same way as NC 0 , except that we allow the circuits to have unbounded fan-in. TC 0 is the class of all Boolean functions defined the same way as AC 0 , except that we allow the circuits to have majority gates (gates that output 1 if and only if a strict majority of their input bits are 1). In addition, we are also interested in GC 0 (k), a classical circuit class defined recently [Kum23, GK24], with a special type of gate allowed in addition to AC 0 . For k ∈ N, a G k gate takes in an unbounded number of bits as input: on input x, if |x|≤ k, then G k (x) can be an arbitrary function on the input x and if |x|> k, then G k (x) is some constant in 0, 1. These are useful as a soft generalization of threshold gates. Quantum circuit classes. Parallel (and in some cases comparable) to the classical circuit hi- erarchy is the hierarchy of quantum circuits. The two classes of importance for us are QNC 0 and QAC 0 . A QNC 0 circuit basis consists of all possible one- and two-qubit gates. For the sake of succinctness, we allow the following in particular: Clifford gates, i.e.: H = 1 √ 2 11 1 −1 , S = 1 0 0 i ,CNOT = 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 , and S,T -gates, i.e.: S = 1 0 0 i , T = 10 0 e iπ/4 and Pauli matrices, i.e.: I = 1 0 0 1 , X = 0 1 1 0 , Y = 0 −i i0 , Z = 10 0 −1 . 13 We write these gates as above because all Pauli gates and Clifford gates are simulable, and the T gate makes quantum computation universal. In order to describe QAC 0 , we first observe what the CNOT gate does. It performs the following operation: CNOT :|a,b⟩7→|a,a⊕ b⟩ for all a,b∈0, 1. This is a 2-qubit gate. If a = 1 it flips the second bit, whereas if a = 0, it keeps the second qubit as it is. Consider a CCNOT gate (also referred to as Toffoli gate), defined as: CCNOT :|a 1 ,a 2 ,b⟩→|a 1 ,a 2 ,b⊕ a 1 · a 2 ⟩ for all a 1 ,a 2 ,b∈0, 1, i.e., the gate flips the last bit if and only if the first 2 qubits are both 1. In order to describe QAC 0 , we allow the circuits to have generalized CNOT (referred to as Toffoli gates) acting on t∈ [n] qubits: Toffoli :|a 1 ,...,a t ,b⟩7→|a 1 ,...,a t ,b⊕ a 1 ·a t ⟩ for all a 1 ,...,a t ,b∈0, 1, i.e., the gate flips the last bit if and only if the first t qubits are all 1. We can now describe the two quantum circuit classes of interest to us. 1. QNC 0 , the set of circuits acting on: n input bits and poly(n) auxilliary qubits, constant depth, consisting of Paulis, Cliffords, S, and T gates. 2. QAC 0 , the set of circuits acting on: n input bits and poly(n) auxilliary qubits, constant depth, consisting of Paulis, Cliffords, T , and Toffoli gates. The only difference between QNC 0 and QAC 0 is that the latter contains Toffoli gates, which are not present in the former. Notation for superconstant depths. Suppose we have a circuit family C from a circuit class (or quantum circuit class)C, such that C has depth O(f (n)) (i.e., the depth of each circuit in the family is allowed to be a function of the input length, instead of being a universal constant). In that case, we write C belongs toC[f (n)]. In other words,C[f (n)] is the class of circuit families or quantum circuit families whose depth grows as O(f (n)), but whose other parameters are defined by the classC. Now, when f (n) = Ω(logn), typically the superscript of the circuit class goes up according to the degree of the polylogarithmic factor; for instance, NC 0 [logn] = NC 1 , QAC 0 [logn] = QAC 1 , AC 0 [log 2 n] = AC 2 , and so on. However, we will mainly be concerned with the case when f (n) = o(logn); in that case, we will simply designate the resulting class as C[f (n)]. In particular, QAC 0 [log logn] will be the class of quantum circuits that are exactly QAC 0 circuits, except that their depth can go up to O(log logn). 2.2 Transformer models We first describe in the figure below the structure of a transformer model. In the remaining part of this section, we define various aspects of this transformer architecture and discuss how one goes from the input to the output. 2.2.1 Definitions and Architecture We now give a brief introduction to the basic transformer architecture. Apart from the choice of the attention mechanism itself (which is typically taken to be a variant of softmax ), there are a few other parameters that define a transformer: 1. L: the number of layers 14 Figure 1: An idealized depiction of the core transformer architecture. 2. H: the number of attention heads in each layer 3. d: the embedding dimension 4. p: the bit precision of entries in the internal computations. The context length n, which corresponds to the length of the input measured in tokens, is not a parameter of the transformer; this is what enables a transformer to carry out its computations on unbounded-length inputs. We often refer to L as the depth of the transformer, and to the product Hdp as its width or size. Recent works [SHT23, CPW25] have adopted the convention of designating a transformer as “small” if Hdp = n o(1) and “large” if Hdp = n Ω(1) . A transformer with H heads and L layers computes a length-preserving sequence-to-sequence function. It starts by breaking up some input text (the prompt ) into a length-n sequence w = w 1 ...w n of tokens, and then embeds each token w i into a (dH)-dimensional real vector x (0) i , creating the n-sequence: x (0) = x (0) 1 ,...,x (0) n ∈ R dH n where each entry is represented using at most p bits. Subsequently, over the course of a sequence of length-preserving internal computations through L layers in its architecture, the transformer converts the original sequence into the sequence: x (L) = x (L) 1 ,...,x (L) n ∈ R dH n . Each transformer layer contains H attention heads. The computation in the ℓ-th layer is determined by query, key and value matrices indexed by their corresponding attention head, explicitly given by Q ℓ,h ,K ℓ,h ,V ℓ,h ∈ R d×dH for ℓ ∈ [L],h ∈ [H]. These matrices are all determined (i.e., learned) during training time, and are subsequently considered a complete specification to the transformer architecture (which, in this model, carries out a deterministic computation on each given input). We now describe the transition in between the layers of the transformer: if the input to the ℓ-th layer is x (ℓ−1) , then the output x (ℓ) is determined as follows: for every position i∈ [n], and attention 15 head h∈ [H], define: α (ℓ,h) i,j := 1 Z i · exp(⟨Q (ℓ,h) x (ℓ−1) i ,K (ℓ,h) x (ℓ−1) j ⟩), where Z i := P j exp(⟨x (ℓ) i Q (ℓ,h) ,K (ℓ,h) x ℓ j ⟩). Note that this is where we have used the currently- used softmax attention, instead of other variants such as unique hard attention and average hard attention that have been theoretically considered as well. Then, set: y (ℓ,h) i := X j α (ℓ,h) i,j V (ℓ,h) x (ℓ) j ∈ R d .(5) Now, we can concatenate the vectors y (ℓ) i := (y (ℓ,1) i ,...,y (ℓ,H) i )∈ R dH , and then set: y (ℓ) := y (ℓ) 1 ,...,y (ℓ) n ∈ R dH n . Finally, the output x (ℓ) of the ℓ-th layer is obtained via applying an arbitrary (learnable) function g ℓ : R dH → R dH coordinate-wise to y (ℓ) , i.e.: x ℓ := g ℓ (y (ℓ) 1 ),...,g ℓ (y (ℓ) n ) . Usually, the transformer takes the vector x (L) n ∈ R dH , applies a linear transformation to it along with a sigmoid function to obtain a probability p out ∈ [0, 1], and then rounds this probability p out to a value in 0, 1. In this sense, a transformer can be seen as a language recognizer over its input alphabet, and this is what enables us to place transformers inside or outside standard complexity classes. Decoder transformers. The definition above is for a general transformer. We say a transformer is a decoder-only transformer if the sums in Eq. (5) and the definition of Z i are only over all j with j < i. In other words, the values of y (ℓ,h) i and Z i only depend on all the coordinates of x until coordinate i, i.e., only on x (ℓ) 1 ,...,x (ℓ) i−1 . This requirement for each position to only attend to positions before it is known as future masking, and it is what enables the autoregressive capabilities of modern LLMs. Chain-of-thought. In autoregressive decoder models, the architecture is equipped with the abil- ity to output intermediate tokens during its computation process, which are then fed back to the architecture by appending them to the (increasingly growing) input. This process is called chain- of-thought (CoT); it is well known that CoT-equipped transformers are strictly more powerful in terms of expressivity than transformers without CoT. Indeed, most modern LLMs use CoT-style intermediate reasoning. 2.2.2 Complexity Class Relations As we saw, viewing transformers as language recognizers enables us to compare their capabilities with standard complexity classes. In this section, we provide a brief summary of the capabilities of decoder-only transformers. Note that encoder-only transformers are theoretically strictly more powerful than decoder-only ones, but recent LLMs focus almost exclusively on decoder-only models, and so we will restrict ourselves to that model. We note that modern architectures allow intermedi- ate tokens generated during the computation by a process called chain-of-thought (CoT). Allowing 16 ℓ intermediate tokens on an input of length n, where ℓ∈0,..., logn does not increase the com- plexity class, but increasing ℓ further can certainly improve the expressivity of these transformers (in fact, in the limit, arbitrary amount of chain-of-thought lets transformers Turing-complete). So, the same table below applies even for chain-of-thought length up to ℓ = O(logn) [LLZM24]. PrecisionModel dimensionComplexity class O(1)O(logn)⊆ AC 0 O(1)poly(n)= AC 0 O(logn)O(logn)⊆ TC 0 O(logn)poly(n)= TC 0 Table 1: Summary of main results of [LLZM24] which simulates the transformer class with the corresponding precision and model dimension in terms of standard circuit complexity classes. 2.2.3 Lower Bound via Communication Complexity In a recent work, Chen et al. [CPW25] introduced an autoregressive communication model, and showed that any unconditional lower bound on the communication complexity of a particular problem in this model yields lower bounds on the width Hdp of any constant-depth transformer designed to solve the same problem. The communication model is defined formally as follows. There are L + 2 players (denoted players −1, 0, 1,...,L). For −1 ≤ i ≤ L, the input z i for player i is describable using m i tokens. There is a (directional and restricted) communication protocol for these players, which takes place over a certain number of epochs and a fixed bandwidth B, as follows. Let X (0) ℓ := z ℓ , for ℓ ∈ −1,...,L, for ℓ ≥ 1, they proceed as follows. Every player i∈−1,...,L runs the following: 1. For j > i, player i sends a message Γ (ℓ) ij to player j, depending solely on its current state X (ℓ) i . 2. Player j replies back to player i with a message Π (ℓ) ij that satisfies two constraints: (i) the message Π (ℓ) ji depends solely on Γ (ℓ) ij and player j’s current state X (ℓ) j ; (i) the size of the message satisfies |Π (ℓ) ji |≤ B· m i . 3. Upon receiving the messagesΠ (ℓ) ji j>i , player i updates its state to X (ℓ+1) := X (ℓ) i ∪ S j>i Γ (ℓ) ij . After L rounds, player −1 should output the first bit of X (L) in order for the protocol to be deemed successful. We now point out two nuances about this protocol. • Memorylessness. Suppose during epoch ℓ, players i,j interacted by exchanging the mes- sages Γ (ℓ) ij , Π (ℓ) ji , and so player i updated its current state X (ℓ+1) by including the transcript message Π (ℓ) ji . For a subsequent epoch, say ℓ + 1, by the protocol requirements, player j is forced to forget the previous exchange altogether. Since player j did not update its local state X (ℓ) → X (ℓ+1) using Γ (ℓ) ij , Π (ℓ) ji and all messages solely depend on their local state, players are therefore forced to forget some information between epochs. • Local one-way-ness. Observe that in each epoch, when player i talked to player j, by the protocol requirements, player j cannot reply back to player i based on its interaction with the players−1,...,j− 1. In any given epoch, player j cannot respond to any of the players 17 by “mixing” the input messages it received. Instead, it can only reply based on its current state X (ℓ) j and Π (ℓ) ij . The main result proven by Chen et al. [CPW25] is the following: they define the iterated index function, called IterInx (which we formally define later in Section 3.2.1), and show how to give lower bounds on the width of constant-depth decoder-only transformers computing IterInx, using the communication protocol defined above. In particular, they show the following result. Lemma 2.4. If there is an L-layer decoder-only transformer with width Hdp that solves IterInx for all instances of the problem, then there is a deterministic autoregressive protocol on L + 2 players that solves IterInx in L epochs with bandwidth 2Hdp. 2.3 Diffusion models We first describe in the figure below the structure of a diffusion language model (DLM). In the remaining part of this section, we define various aspects of this DLM architecture and discuss how one samples a distribution using this model. Figure 2: An idealized depiction of the core DLM architecture. We now describe the diffusion language model (DLM) framework used in this paper. In ab- straction, 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 one distribution within a parameterized class of distributions that approximates the data. Informally, the goal is as follows. Let: D u :0, 1 n → [0, 1] u be a family of target distributions. The goal of the DLM is the following task: on input u, generate a sampled output string y ∼ D u . We also study approximate generation, where the DLM is allowed to output a sample from a distribution e D u satisfying: TV( e D u ,D u )≤ ε. More formally, we present the usual convention of DLMs in literature (similar to the formalization given in [JHC26]). Let V be a finite token vocabulary (for simplicity we let it be 0, 1 here) and 18 let mask denote the so-called mask token. A state in a DLM algorithm is a sequence: x∈ (V ∪mask) L . A coordinate equal to mask is called masked or unresolved, while a coordinate in Σ has already been assigned a token and is called resolved. A noiseless sequence is an element of V L . A predictor is a map which, for every partially masked sequence x∈ (V ∪mask) L , specifies a distribution: p(·| x)∈ ∆(V L ), i.e., the coordinate-wise conditional distribution of z ∼ p(·| x) is given by: p(z | x) = L Y i=1 p i (z i | x). In the standard model, already unmasked coordinates are kept fixed, i.e., p i (z i = x i | x) = 1 whenever x i ∈ V . 2.3.1 Masked states The structure of a usual DLM algorithm is as follows: it begins from a partially masked state: x |z input , mask m−n | z workspace/CoT , mask n |z output , and progressively resolves masked coordinates over several denoising rounds (which we define be- low). After a fixed number of rounds, it outputs the final n coordinates, which are designated as output coordinates. The goal is for the distribution of the final n coordinates to be “close” to the target distribution D x . The remaining coordinates are auxiliary workspace coordinates that may be used during the computation and discarded at the end. We use the term workspace token for any auxiliary coordinate generated during the DLM com- putation but discarded before the final output is read. In the DLM literature, such coordinates are often interpreted as chain-of-thought (CoT) tokens when they serve as intermediate reasoning or scratchwork. Since our lower bounds only use the formal role of these coordinates as auxil- iary generated tokens available to later rounds, we use the terms workspace and chain-of-thought interchangeably when no distinction is needed. 2.3.2 Denoising process We now describe the denoising process. This process is a iterative procedure through which masked coordinates are progressively resolved. Suppose the current state of the DLM at round t is: X (t) ∈ (Σ∪mask) m . A single denoising round consists of two conceptually distinct operations: 1. scheduling/unmasking, where the model decides which masked coordinates will be updated in the current round; 2. token generation, where the model generates values for the selected coordinates. We describe both operations below in detail. 19 Scheduling/unmasking. At round t, the model selects a subset R t (X (t) ) ⊆ [m] of currently masked coordinates to reveal. Equivalently, one may think of the scheduler as outputting revealed bits S t,i (X (t) )∈0, 1, where S t,i (X (t) ) = 1 indicates that the coordinate i will be updated during round t. The revealed set is therefore: R t (X (t) ) =i : S t,i (X (t) ) = 1. The model then samples, independently for all i∈ S t : X (t+1) i ∼ p i t (·| X (t) ), and leaves all other coordinates unchanged. A key feature of DLMs is that the reveal schedule may depend adaptively on the partially generated sequence so far. Thus, the model does not need to decide the entire reveal order in advance; instead, future reveal decisions may depend on tokens generated in earlier rounds, including both workspace/CoT coordinates and output coordinates. An important aspect to consider here is how complex the scheduling is. As is common in the DLM literature, we require that the scheduling rule itself be computationally shallow. Concretely, for each coordinate i and round t, the reveal decision S t,i (X (t) ) is computed by a constant-depth polynomial-size circuit. Token generation. Once the reveal set R t (X (t) ) has been selected, the model generates token values at those coordinates. The crucial and defining structural property of a standard DLM is the following notion of conditional independence: Conditioned on the current state, newly revealed coordinates are sampled independently. More precisely, conditioned on the current partially generated state X (t) , the model specifies marginal distributions p t,i (·| X (t) ) for all i∈ R t (X (t) ), and samples: X (t+1) i ∼ p t,i ·| X (t) independently across coordinates. Thus, the conditional law of the newly generated coordinates factorizes as: L (X (t+1) i ) i∈R t X (t) = O i∈R t p t,i ·| X (t) . Intuitively, conditioned on the current partially generated sequence, a standard DLM generates fresh coordinates in parallel using coordinate-wise denoising rules. Execution as a branching process. It is useful to view a DLM execution as a branching process over partially generated states. Each possible state τ = X (t) at the beginning of round t defines a transcript branch of the computation. Conditioned on reaching a fixed partially generated state τ : • the reveal set R t (τ ) is fixed, • the next batch of generated coordinates has the product law: L (X (t+1) i ) i∈R t (τ ) X (t) = τ = O i∈R t (τ ) p t,i (·| τ ). We write p i t (· | τ ) for the i-th marginal of the DLM predictor p t (· | τ ). Although the predictor specifies a full product distribution on V L , only the coordinates selected by R t (x) are actually 20 updated in the current denoising round. Thus, conditioned on a fixed partially generated state, the next round of generation is a product distribution over the newly revealed coordinates. Globally, however, the overall output distribution may still exhibit highly nontrivial correlations because future rounds depend adaptively on previously generated tokens. Consequently, correlations may accumulate across rounds through the interaction of adaptive scheduling and iterative denoising. 2.3.3 Constant-round shallow DLMs As discussed before, a natural question in this set-up is how complex is the sample generation? In particular, one must also account for the circuits implementing the scheduling and token-generation steps. As is standard in the DLM literature, these steps are required to be computationally shallow. Concretely, we assume that the number of denoising rounds is constant, i.e., T = O(1), and that for every round t and coordinate i, both the scheduling rule S t,i (X (t) ) and the denoising marginal p t,i (· | X (t) ) are computable by constant-depth polynomial-size circuits. The work by Jiang et al. [JHC26] studies this model with AC 0 circuits, proving both positive and negative results. Since our focus is on hardness, we prove our results even when these shallow circuits are allowed to be GC 0 circuits, effectively strengthening the lower bounds. Because the number of rounds is constant, the entire generation process can be viewed as a constant-depth adaptive computation built from repeated applications of shallow scheduling and coordinate-wise denoising steps. 2.3.4 Remasking and revision. The basic denoising model described above only allows masked coordinates to be resolved over time. Modern diffusion-style language models often consider stronger variants in which previously generated coordinates may later be modified or revisited. Two common mechanisms are revision [SZL + 25] and remasking [NZY + 25]. Intuitively speaking, in a remasking step, previously gener- ated coordinates may be returned to the masked state and regenerated in later rounds, whereas in a revision step, the model is allowed to overwrite or update tokens that were generated in ear- lier rounds. Formally, in a remasking step, after the denoising update, the model applies a (possibly randomized) remasking policy: G t : (V ∪M) L → 2 [L] . For T t = G t (x), the coordinates i ∈ T t are reset to mask. In the revision model, we relax the standard condition that an unmasked coordinate must remain unmasked during the algorithm. Thus, R t (x) may include coordinates i with x i ∈ V , and the predictor marginal p i t (·| x) may assign some probability less than 1 to the current token x i . The coordinate-wise conditional independence condition is still maintained: p t (z | x) = L Y i=1 p i t (z i | x). These mechanisms allow the model to iteratively refine earlier generations rather than commit- ting permanently to the first generated value. Conceptually, remasking and revision substantially strengthen the expressive power of the model: the generation process is no longer monotone in the set of revealed coordinates, and tokens generated early in the computation may later be “corrected” based on information obtained in subsequent rounds. We will prove our main lower bound in the presence of both remasking and revision, making it explicit in our lower bounds. 9 9 We remark that [JHC26] accounts for the cost of remasking/revision differently from ours: they allow arbitrarily many tokens to be remasked or revised in any particular round, and only bound the total number of rounds of revision. Here, we account for the total number of revision/remasking steps throughout the entire DLM computation. 21 3 Functional separation: quantum versus transformer models 3.1 Motivation for our candidate problem In this section, we first give some motivation for our candidate problem that we use to separate quantum shallow circuits from transformer models. The quantum circuits that we use for these motivating functions will be eventually used when discussing our separation. 3.1.1 Index function Our first observation is that the index function, denoted by Inx and defined below, is computable with a shallow quantum circuit with minimal classical post-processing without requiring the full power of QAC 0 circuits, albeit the caveat that it requires copies of the input: Inx :0, 1 n ×0, 1 N →0, 1, such that Inx(i,x) = x i for x∈0, 1 N , where N = 2 n . Formally, we have the following result. Claim 3.1. Let n,N ∈ N such that N = 2 n . Given N copies of the address i ∈ 0, 1 n and one copy of x ∈ 0, 1 N , the index function Inx(i,x) can be computed by a quantum circuit with gate complexity O(N logN ) followed by an OR gate. Moreover, the problem is in ∨◦ QNC 0 [log logN ]. Before we prove the result above, we introduce some simple quantum circuits that will be used for the claim, as well as several subsequent arguments. Quantum circuits for equality checks. We will often require a quantum subroutine for com- puting an equality check of two strings y,z ∈0, 1 n , which we defined as [y = z]. We first present a very simple circuit to compute the equality check. Claim 3.2. Let n∈ N. Given one copy of y,z ∈0, 1 n , the equality check [y = z] can be computed by a quantum circuit over (3n + 1) qubits with gate complexity O(n) and depth O(logn). Proof. We define a quantum circuit A j with the following action: |y⟩|z⟩|0⟩ n |0⟩ A j −→|y⟩|z⟩ ⊗ ℓ∈[n] |[y ℓ = z ℓ ]⟩ |[y = z]⟩.(6) This is implemented as followed. Let the n-ancilla qubit register be denoted by s, and the ℓ-th qubit by s ℓ . Let the last ancilla qubit be denoted by t. For each ℓ∈ [n], we apply a 3-qubit Toffoli gate with controls over |y ℓ ⟩, |z ℓ ⟩, with the target being the qubit s ℓ . This sets the state of the n-ancilla register to ⊗ ℓ∈[n] |[y ℓ = z ℓ ]⟩. We then apply an (n + 1)-qubit Toffoli gate with controls over all of s, with the target being qubit t. The final state is then as given in Eq. (6). The circuit A j is over 3n + 1 qubits. All the 3-qubit Toffoli gates can implemented in parallel and with gate complexity of O(1) each (using O(1) additional ancilla qubits for each). The (n + 1)- qubit Toffoli gate can be implemented with O(n) one- and two-qubit gate complexity, and depth O(logn) (using O(n) additional ancillas). Overall, the gate complexity is O(n) and the depth is O(logn). This completes the proof. The construction above can be modified to give a circuit requiring fewer qubits as input, and which we will primarily use. 22 Claim 3.3. Let n ∈ N. Given one copy each of y,z ∈ 0, 1 n , the equality check [y = z] can be computed by a quantum circuit over (n + 1) qubits with gate complexity O(n) and depth O(logn). Proof. We first note that for a fixed z ∈0, 1 n , we have [y = z] = V ℓ∈[n] [y ℓ = z ℓ ]. For all ℓ∈ [n], the indicator function [y ℓ = z ℓ ] can be written as: [y ℓ = z ℓ ] = ( y ℓ , z ℓ = 1, y ℓ , z ℓ = 0. (7) Define the (smaller) quantum circuit A j as having the following action: 10 |y⟩|0⟩ A j −→|y⟩|[y = z]⟩. This is implemented as follows. We apply a single-qubit X gate on the qubits of |y⟩ for which z ℓ = 0. This is in order to implement [y ℓ = z ℓ ] using Eq. (7). We then implement an (n + 1)-qubit Toffoli gate with controls over the qubits of |y⟩ with the target being the last qubit. We then reset the qubits of |y⟩ by applying a single-qubit X gate on those qubits of |y⟩ for which z ℓ = 0 again. Let us denote this last qubit as |t⟩. The circuit is then summarized below in Figure 3. A j |y⟩ ⊗ ℓ∈[n] X ℓ [z ℓ = 0] • ⊗ ℓ∈[n] X ℓ [z ℓ = 0] |y⟩ |0⟩ |t⟩ =|[y = z]⟩ Figure 3: Illustration of circuit A j for equality check [x = y]. The circuitA j is applied over n + 1 qubits accounting for the size of y and the additional ancilla qubit. The circuit A j 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(logn) (when given O(n) clean ancillas). This completes the proof. Quantum circuit (with copies) for computing index. We are now ready for the proof of Claim 3.1. Proof of Claim 3.1. We first observe that the index function can be written as a depth-3 DNF circuit as follows: Inx(i,x) = _ j∈0,1 n [i = j]∧ x j = _ j∈0,1 n x j ∧ ℓ∈[n] [i ℓ = j ℓ ] . We now describe a quantum circuit to compute the index function. Suppose we have N copies of i, i.e., we are given N copies of the input (i,i,i,...,i). For one copy of i and a fixed j ∈ 0, 1 n , we will consider the quantum circuit A j from Claim 3.3 (with instantiations of y as i, z as j there) and slightly modify it to output x j ∧ [i j = j] (see Figure 4), which has the following action: |i⟩|x j ⟩|0⟩ A j −→|i⟩|x j ⟩|x j ∧ [i = j]⟩. 23 A j |i⟩ ⊗ ℓ∈[n] X ℓ [j ℓ = 0] • ⊗ ℓ∈[n] X ℓ [j ℓ = 0] |i⟩ |x j ⟩ • |x j ⟩ |0⟩ |t j ⟩ =|x j ∧ [i j = j]⟩ Figure 4: Illustration of quantum circuit A j used for equality check [i j = j] and outputting the corresponding bit x j if true. Let us denote the last qubit as |t j ⟩ for a given j. To compute the index function, we now apply the circuit U composed of the smaller circuits A j for j ∈0, 1 n in parallel as follows: (|i⟩|x 0 ⟩|0⟩)... (|i⟩|x 2 n −1 ⟩|0⟩) A 0 ⊗...⊗A 2 n −1 −→ (|i⟩|x 0 ⟩|t 0 ⟩)... (|i⟩|x 2 n −1 ⟩|t 2 n −1 ⟩), where we have used the equivalent integer representation of the index j when denoting x j and A j . We now note that each |t j ⟩ is either |0⟩ or |1⟩. We simply measure the qubits over all |t j ⟩ in the computational basis, and obtain the measurement outcome t j = x j ∧ [i = j]. Applying an OR gate over all j ∈0, 1 n then gives us: _ j∈0,1 n t j = _ j∈0,1 n [i = j]∧ x j , which is the desired index function computation. For each A j , we used O(n) many single-qubit Figure 5: Illustration of the circuit used for outputting Inx(i,x) using copies of |i⟩ and the circuit of A j ,∀j ∈ [N − 1] 0 from Figure 4. gates applied in parallel to each other and one (n +1)-controlled Toffoli gate (Claim 3.3). The latter 10 Note that we do not use a copy of z as a quantum input, unlike in Claim 3.2. 24 has a one- and two-qubit gate complexity of O(n) and requires depth O(logn) (when given O(n) clean ancillas). Summing over all j ∈0, 1 n gives us a gate complexity of O(N logN ). Noting that all A j are applied in parallel, the depth of the circuit is O(logn) = O(log logN ). This completes the proof. 3.1.2 Multi-index function The natural next question for us is: can we remove the need for n copies in the QAC 0 upper bound? For this purpose, we can adopt a simple trick used in [GMW26]. Consider the index function Inx :0, 1 n ×0, 1 N →0, 1, defined as Inx(i,x) = x i . It is shown in [GMW26] that one can consider the multi-index function MultInx : (0, 1 n ) N ×0, 1 N →0, 1 defined as follows: MultInx(i 1 ,...,i N ,x) = [i 1 =· = i N ]· x i 1 , i.e., it first checks if all the n-bit length strings i 1 ,...,i N are equal (say equal to i∈0, 1 n ) and, based on that, outputs x i . The idea is now to say that the players in our protocol are each given N copies of their input, and instead of solving single instances of Inx, they solve MultInx as above. Checking if i 1 =· = i n is doable in QAC 0 , so this does not add any significant complexity to the circuit. Since we also have these many copies “for free” by definition, one can also compute x i . Claim 3.4. Let n,N ∈ N such that N = 2 n . Giveni k k∈[N ] and one copy of x∈0, 1 N , the func- tion MultInx(i 1 ,...,i N ,x) can be computed by a quantum circuit with gate complexity O(N logN ) followed by an AND gate 11 . Moreover, the problem is in ∧◦ QNC 0 [log logN ]. Proof. Recall that the multi-index function is: MultInx(i 1 ,...,i N ,x) = [i 1 =· = i N ]· x i 1 . We now describe a quantum circuit used to compute the multi-index function. We are given the input (i 1 ,i 2 ,...,i N ) and x. We first define a quantum circuit U 1 to check the indicator [i 1 =· = i N ]. Let us introduce Nn ancilla qubits o k,ℓ k∈[N ],ℓ∈[n] with each initialized to |0⟩ and an ancilla qubit s initialized to |0⟩. We first apply a layer of Nn CNOTs in parallel with a CNOT gate from each i k,ℓ to o k,ℓ for all k ∈ [N ],ℓ∈ [n]. This has the effect of setting the state of o k,ℓ to that of i k,ℓ . We then apply another layer of CNOTs in parallel with a CNOT gate from each i k+1,ℓ to o k,ℓ , for all k ∈ [N ],ℓ∈ [n] 12 At this point, the state of each |o k,ℓ ⟩ is |i k,ℓ ⊕ i k+1,ℓ ⟩. Applying a single-qubit X gate on each o k,ℓ then sets the state to be the indicator [i k,ℓ = i k+1,ℓ ], i.e., |o k,ℓ ⟩ =|[i k,ℓ = i k+1,ℓ ]⟩. We could now measure all the qubits overo k,ℓ in the computational basis and apply an AND gate over the measurement outcomes to obtain the value of [i 1 = ... = i N ]. However, we will postpone this step after describing how to obtain x i 1 in case [i 1 =· = i N ] = 1. To obtain x i 1 , we proceed similarly as we had in Claim 3.1. For each j ∈0, 1 n , we consider the quantum circuit A j from Claim 3.3 (with instantiations of y as i j , z as j, x as x and j as the integer corresponding to the given binary representation here) taking as input |i j ⟩, |x j ⟩, and an additional ancilla qubit initialized to 0, which has the following action: |i j ⟩|x j ⟩|0⟩ A j −→|i⟩|x j ⟩|x j ∧ [i j = j]⟩. 11 Throughout this paper, we assume without loss of generality that NOT gates are free, simply by increasing the size of the circuits by at most a constant factor (using De Morgan’s laws) 12 We actually mean from i (k+1) modN,ℓ to o k,ℓ so that the bits of i 1 are chosen for k = N . 25 Let us denote that last qubit as |t j ⟩ for a given j. To compute the multi-index function, we now apply the circuit U composed of the smaller circuits A j for j ∈0, 1 n in parallel as follows: (|i 1 ⟩|x 0 ⟩|0⟩)... (|i N ⟩|x N−1 ⟩|0⟩)|0⟩ Nn (A 0 ⊗...⊗A N−1 )U 1 −→ (|i 1 ⟩|x 0 ⟩|t 0 ⟩)... (|i N ⟩|x N−1 ⟩|t N−1 ⟩) ⊗ k∈[N ],ℓ∈[n] |o k,ℓ ⟩ , where we have used the equivalent integer representation of the index j when denoting x j and A j . We note that|t j ⟩ =|x j ∧ [i j = j]⟩ for each j. We now simply measure the qubits over all|t j ⟩ in the computational basis and obtain the measurement outcome t j = x j ∧ [i = j]. We also measure the qubits over all|o k,ℓ ⟩ in the computational basis to obtain the measurement outcomes o k,ℓ . Applying an AND gate over all the measurement outcomes o k,ℓ k∈[N ],ℓ∈[n] gives us s, which has the value: s = Y k∈[N ],ℓ∈[n] [i k,ℓ = i k+1,ℓ ] = [i 1 =· = i N ]. Applying an OR gate over all t j measurement outcomes gives us t, which has the value: t = _ j∈0,1 n t j = _ j∈0,1 n x j ∧ [i j = j]. Applying a two-bit AND gate on s and t gives us: st = [i 1 =· = i N ]· _ j∈0,1 n x j ∧ [i j = j] = [i 1 =· = i N ]· _ j∈0,1 n x j ∧ [i 1 = j] , where we noted in the second equality that st takes a non-zero value only if [i 1 = · = i N ] = 1, in which case, we can replace i j with i 1 in the second term. This would then compute the MultInx function. We note that we can replace the above classical processing with just one AND gate over the measurement outcomes of t j and o k,ℓ with interleaved NOT gates by using DeMorgan’s laws. The circuit U 1 uses O(N logN ) many CNOT gates and has depth 2. For each A j , we 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(logn) (when given O(n) clean ancillas). Summing over the gates in A j for all j ∈ 0, 1 n and U 1 gives us a gate complexity of O(N logN ). Noting that all A j are applied in parallel, the depth of the overall circuit U is O(logn) = O(log logN ). This completes the proof. 3.2 Final candidate function 3.2.1 Iterated index function Parameter choices. Fix the transformer parameters H,d,p,L, i.e., the number of heads, model dimension, precision and number of layers. We use the same parameter setting as in [CPW25]: we will first define T = Hdp, which is the bandwidth of the players. With this, the remaining parameters are defined as follows: K(T,L) = (TL) 8 , m(T,L) = K P L−1 ℓ=0 8 ℓ +1 , n ℓ (T,L) = K 4·8 L−ℓ−1 for ℓ∈ [L− 1], N ℓ (T,L) = m· ℓ Y j=1 n j for ℓ∈0,...,L− 1. We will sometimes drop the (T,L) dependence when it is clear from the context. 26 Iterated index function. For the iterated index function as defined by [CPW25], the input is a tuple (w,z 0 ,z 1 ,...,z L ), where: 1. w = (w 1 ,...,w L−1 ) has L− 1 components, with w ℓ ∈ [n ℓ ]; 2. the first argument z 0 ∈ [m] is referred to as the seed ; 3. each z ℓ ℓ∈[L] is a function satisfying z ℓ : [N ℓ−1 ]→ [N ℓ−1 ]. We identity the input [N ℓ−1 ] with [n ℓ−1 ]× [N ℓ−2 ] since N ℓ−1 = n ℓ−1 · N ℓ−2 (so we may write z ℓ (w ℓ−1 ,i ℓ−1 ) for ℓ≥ 2). With this notation, the input to player ℓ has size: A −1 = L−1 Y ℓ=1 [n ℓ ], A 0 = [m], A ℓ := [N ℓ−1 ] N ℓ−1 . The goal of the iterated index problem is to simply compute the following function: on input (w,z 0 ,z 1 ,...,z L )∈ A −1 × A 0 × A 1 ×·× A L , output IterInx(w,z 0 ,...,z L ) := i L , where: i 0 = z 0 , i 1 = z 1 (i 0 ), i 2 = z 2 (w 1 ,i 1 ), · ,i ℓ+1 = z ℓ+1 (w ℓ ,i ℓ )for ℓ∈ [L− 1]. Intuition. For some intuition, the reason we think of the expression above as an iterated index is as follows. Consider player 1, who receives the truth table of z 1 : [N 0 ]→ [N 0 ] (i.e., a message with (N 0 ) logN 0 bits), and needs to produce the i 0 -th index in the truth table of z 1 , which we denote i 1 . Now, similarly, player 2 receives the truth table of z 2 : [N 1 ] → [N 1 ] and needs to output the (w 1 ,i 1 )-th index of this truth table z 2 (which we denote as z 2 (w 1 ,i 1 )). This procedure iteratively continues for L− 1 rounds before player L player outputs z L (w L−1 ,i L−1 ) and passes this index to the final player, player (L + 1). This final player (L + 1) outputs z L+1 (w L ,i L ), which is the intended value of the function. Theorem 3.5 ([CPW25, Theorem 4.1]). There exists α L = 2 −O(L) with the following property. Every deterministic autoregressive protocol for IterInx on the parameters (K,m,n ℓ ,N ℓ ), with L epochs and bandwidth B ≤ T satisfies: B ≥ n orig (T,L) α L , where n orig (T,L) := 1 + 1 + P ℓ∈[L] N ℓ−1 ∼ K 2 O(L) is the total token length of the input. 13 3.2.2 Iterated multi-index function Parameter choices. We retain all parameter choices from the iterated index problem above (K,m,n ℓ ,N ℓ as functions of T = Hdp and L), and introduce one additional parameter, the copy parameter : t(T,L) := L Y ℓ=1 N ℓ−1 = L−1 Y ℓ=0 N ℓ .(8) As before, we drop the (T,L) dependence when the context is clear. Iterated multi-index function. The iterated multi-index function is the t-copy extension of the iterated index function. The input is a tuple w (s) s∈[t] ,z (s) 0 s∈[t] ,z (s) 1 s∈[t] ,...,z (s) L s∈[t] , where, for each s∈ [t]: 13 We will prove this final upper bound expression on n orig (T,L) shortly. 27 1. w (s) = (w (s) 1 ,...,w (s) L−1 )∈ A −1 , i.e., w (s) ℓ ∈ [n ℓ ] for ℓ∈ [L− 1]; 2. the seed z (s) 0 ∈ A 0 = [m]; 3. each table z (s) ℓ ∈ A ℓ is a function z (s) ℓ : [N ℓ−1 ]→ [N ℓ−1 ], with the same identification of [N ℓ−1 ] with [n ℓ−1 ]× [N ℓ−2 ] as in the iterated index problem. The per-role input domain in the iterated multi-index problem is the t-fold product: A t −1 = L−1 Y ℓ=1 [n ℓ ] ! t , A t 0 = [m] t , A t ℓ = [N ℓ−1 ] N ℓ−1 t for ℓ∈ [L]. Define the consistency predicate as: E w (s) ,z (s) ℓ := s∈[t] w (s) = w (1) ∧ z (s) 0 = z (1) 0 ∧ ℓ∈[L] z (s) ℓ = z (1) ℓ ∈0, 1, i.e., E = 1 iff all t copies of each input component agree. The goal of the iterated multi-index problem is to compute the following function: on input w (s) ,z (s) 0 ,...,z (s) L , output: IterMultInx w (s) ,z (s) ℓ := E w (s) ,z (s) ℓ · IterInx w (1) ,z (1) 0 ,z (1) 1 ,...,z (1) L . In other words: if every component is internally consistent across the t copies, output the iterated index value on those (common) inputs; otherwise output 0. Intuition. We again provide some intuition for this candidate problem, and why we call it iterated multi-index. First, observe that if: w s i = w 1 ,z (s) 0 = z (1) 0 ,z (s) ℓ = z (1) ℓ for all s∈ [t],ℓ∈ [L],(9) that means that the players are just get the same input string several times. Once that is the case, the players can just treat their input as w (1) ,z (1) i for i ∈ 0,...,L and just run the usual index protocol. But recall that in order to compute even a single instance of the index problem, the QNC 0 circuit requires copies of the index, which is not available for free. Having t copies of the individual input has the effect of providing these copies “for free”, and part of the input for the QNC 0 circuit we will construct. It is clear that having just one copy would be equivalent to the iterated index problem. Indeed, the “diagonal” version of the problem above is exactly the iterated index problem (whose lower bound will be crucial in proving our lower bound). For the off-diagonal elements, we simply enforce the condition that if any of the equalities in Eq. (9) are not met, then the overall function just evaluates to 0. 3.3 Quantum upper bound Iterated index function. We have the following main result regarding the computation of the iterated index function. Theorem 3.6. Let L ∈ N,L ≥ 2, n ℓ ,N ℓ ∈ N for all ℓ ∈ [L − 1] such that N ℓ = 2 n ℓ , for all ℓ ∈ [L − 1]. Given K O(L8 L ) copies of each of w ℓ ℓ∈[L−1] , i 0 , and z ℓ ℓ∈[L] , the iterated-index function IterInx can be computed by a quantum circuit with gate complexity O(K L8 L logK) followed by an AND gate. Moreover, the problem is in ∧◦ QNC 0 [log logK]. 28 Proof. Denote the input to the algorithm as: X = (w,z 0 ,z 1 ,...,z L ), where w = (w 1 ,...,w L−1 ). Recall that the iterated-index computation is then the following sequence of computations starting from the initial seed z 0 : i 0 = z 0 , i 1 = z 1 (i 0 ), i ℓ+1 = z ℓ+1 (w ℓ ,i ℓ )for every ℓ∈ [L− 1]. Explicitly, the intermediate computations are: i 2 = z 2 (w 1 ,i 1 ), i 3 = z 3 (w 2 ,i 2 ), ..., i L = z L (w L−1 ,i L−1 ). One approach would of course be to sequentially and recursively prepare the intermediate indices i 1 ,i 2 ,...,i L−1 on quantum registers, which are the inputs to the truth tables z 2 ,z 3 ,...,z L . How- ever, this might increase depth. So, instead, we verify all possible computation histories in parallel. Note that the input to the final truth table z L is of size N L−1 . A candidate computation history up to z L is a tuple: τ = (r 1 ,...,r L−1 ,a 0 ,a 1 ,...,a L−1 ),(10) where: a 0 ∈ [N 0 ], a ℓ ∈ [N ℓ−1 ], r ℓ ∈ [n ℓ ]for1≤ ℓ≤ L− 1. For a fixed τ , let Const τ (X) denote the predicate that all of the following conditions hold: z 0 = a 0 ,(11) w ℓ = r ℓ for every 1≤ ℓ≤ L− 1,(12) z 1 (a 0 ) = a 1 ,(13) z ℓ+1 (r ℓ ,a ℓ ) = a ℓ+1 for every 1≤ ℓ≤ L− 2.(14) In particular, for every τ , Const τ (X) checks if X is a valid iterated index transcript. Note that exactly one τ ∗ satisfies Const τ ∗ (X) = 1. For this τ ∗ and hence when Const τ (X) = 1, we need to compute the output of z L (w L−1 ,a L−1 ). To this end, for every b∈ [log(N L−1 )], define: C τ,b (X) :=¬ (Const τ (X)∧¬z L (r L−1 ,a L−1 ) b ),(15) where the subscript b indicates the bit position of z L (r L−1 ,a L−1 ) (which is viewed as a vector in 0, 1 logN L−1 ). For every invalid history τ ̸= τ ∗ , we have Const τ (X) = 0, and hence C τ,b (X) = 1. For the unique valid history τ ∗ , we have Const τ ∗ (X) = 1, and hence: C τ ∗ ,b (X) =¬ 1∧¬z L (r ∗ L−1 ,a ∗ L−1 ) b = z L (w L−1 ,i L−1 ) b , where we have used the fact that Const τ ∗ (X) = 1 indicates r ∗ L−1 = w L−1 ,a ∗ L−1 = i L−1 in the second equality. Taking an AND over all histories then gives us: τ C τ,b (X) = τ̸=τ ∗ 1 ∧ C τ ∗ ,b (X) = C τ ∗ ,b (X) = z L (w L−1 ,i L−1 ) b .(16) Doing this over all b∈ [log(N L−1 )] in parallel would then yield the desired result of z L (w L−1 ,i L−1 ). 29 We now describe the corresponding circuit and analyze the corresponding copy complexity, gate complexity and depth. Let T denote the set of all candidate histories. There are: |T|= N 0 L−1 Y ℓ=1 N ℓ−1 ! L−1 Y ℓ=1 n ℓ ! = L−1 Y ℓ=0 N ℓ (17) choices for τ and hence the size of T , where we used the definition of N L−1 = N 0 Q L−1 ℓ=1 n ℓ . Thus, the entire construction will use |T| many copies of the input X with one copy for each candidate history τ ∈T . For a fixed τ ∈ T , we now describe a circuit to compute C τ,b (X), ∀b ∈ [logN L−1 ] (Eq. (15)). Let us define |X (τ ) ⟩ as a portion of the copy of the input X assigned to the computation history τ = (r 1 ,...,r L ,a 0 ,a 1 ,...,a L−1 ) (Eq. (10)): X (τ ) := (w,z 0 ,z 1 (a 0 ),z 2 (r 1 ,a 1 ),...,z ℓ (r ℓ ,a ℓ ),...,z L−1 (r L−2 ,a L−2 ))(18) Once τ is fixed, all the involved addresses in z ℓ+1 (r ℓ ,a ℓ ),∀ℓ∈ [L− 2] are fixed. We will now describe a circuit U τ with the following action on inputs of |X (τ ) ⟩, |z L (r L−1 ,a L−1 )⟩ along with 2 logN L−1 ancilla qubits: |X (τ ) ⟩|0⟩ ⊗ log N L−1 |z L (r L−1 (r L−1 ,a L−1 )⟩|0⟩ ⊗ log N L−1 U τ −→|X (τ ) ⟩|Const τ (X)⟩ ⊗ log N L−1 |z L (r L−1 (r L−1 ,a L−1 )⟩ ⊗ b∈[logN L−1 ] |C τ,b ⟩ .(19) For the equality check of Const τ (X) := [X τ = τ ], we use the quantum circuit from Claim 3.3 (with instantiations of y as X (τ ) , z as τ ) which we denote by A τ and has the following action on input |X (τ ) ⟩ and an additional ancilla qubit initialized to |0⟩: |X (τ ) ⟩|0⟩ A τ −→|X (τ ) ⟩|Const τ (X)⟩.(20) Thus, A τ checks whether the involved truth tables are equal to the fixed strings specified by τ . Adding (log(N L−1 )− 1) additional ancilla qubits initialized to |0⟩, we can copy over the value of Const τ (X) to these ancilla qubits using a CNOT-tree of depth O(log logN L−1 ) and gate complexity O(logN L−1 ). We denote this subcircuit by CNOT tree . We have the following so far: |X (τ ) ⟩|0⟩ logN L−1 A τ −→|X (τ ) ⟩|Const τ (X)⟩|0⟩ logN L−1 −1 CNOT tree −→|X (τ ) ⟩|Const τ (X)⟩ logN L−1 . Recalling the definition of C τ,b from Eq. (15), we now proceed as follows. Consider the input of the state |z L (r L−1 ,a L−1 )⟩ and logN L−1 many additional ancilla qubits initialized to |0⟩ with each one corresponding to b∈ [logN L−1 ] and denoted by t τ,b . Let us also denote the qubit corresponding to z L (r L−1 ,a L−1 ) b as s b for all b ∈ [logN L−1] ]. For each b ∈ [logN L−1 ], we then apply an X gate on qubit s b followed by a 3-qubit Toffoli gate with controls on s b and b-th copy of |Const τ (X)⟩ with the target being t τ,b . We then apply another X gate on the target qubit t τ,b and an X gate on qubit s b to reset it. We will denote the above sequence of gates as B τ,b for each b ∈ [logN L−1 ]. Noting that we can apply all the subcircuits B τ,b in parallel, we can define the overall circuit as B τ := ⊗ b∈[logN L−1 ] B τ,b since each of the qubits s b for b ∈ [logN L−1 ] is unique and can be individually addressed, and we have a copy of |Const τ (X)⟩ for each such b. The circuit B τ then has the following action: |X (τ ) ⟩|Const τ (X)⟩ logN L−1 |z L (r L−1 (r L−1 ,a L−1 )⟩|0⟩ ⊗ logN L−1 B τ −→|X (τ ) ⟩|Const τ (X)⟩ ⊗ logN L−1 |z L (r L−1 (r L−1 ,a L−1 )⟩ ⊗ b∈[logN L−1 ] |¬ (Const τ (X)∧¬z L (r L−1 ,a L−1 ) b ) | z :=C τ,b (X) ⟩ . 30 The desired circuit U τ in Eq. (19) is then U τ := B τ (CNOT tree ⊗ I)(A τ ⊗ I) applied to the input states as described in Eq. (19). Applying the circuits U τ in parallel for all τ ∈T would then simply produce: ⊗ τ∈T |X (τ ) ⟩|0⟩ ⊗ logN L−1 |z L (r L−1 ,a L−1 )⟩|0⟩ ⊗ logN L−1 ⊗ τ∈T U τ −→⊗ τ∈T h |X (τ ) ⟩|Const τ (X)⟩ ⊗ logN L−1 |z L (r L−1 ,a L−1 )⟩ ⊗ b∈[logN L−1 ] |C τ,b (X)⟩ i . Measuring the qubits t τ,b which hold the state |C τ,b ⟩ in the computational basis for all τ ∈ T ,b ∈ [logN L−1 ] and then applying the AND logical gate over the outcomes corresponding to τ ∈ T for each b∈ [logN L−1 ] then gives us the desired result of Eq. (16). 14 We now analyze the number of qubits required and the gate complexity of the overall cir- cuit. For each τ ∈ T , the total number of input qubits involved in defining |X (τ ) ⟩ (Eq. (18)), |z L (r L−1 ,a L−1 )⟩, and the ancilla qubits is: Q τ = O logN 0 + L−1 X ℓ=1 logn ℓ + L−1 X ℓ=0 logN ℓ ! = O L−1 X ℓ=0 logN ℓ ! , where we have noted that the size of the input and output to each z ℓ requires ⌈logN ℓ−1 ⌉ bits to specify. Using the fact that N ℓ = m· Q ℓ j=1 n j , n ℓ (T,L) = K 4·8 L−ℓ−1 , m = K 8 L and that L is constant from the parameter choices described in Section 3.2.1, we then have that: Q τ = O L2 3L logK . Taking into account the size ofT from Eq. (17) and our choice of the parameters, the total number of qubits used is: |T|Q τ = K O(L8 L ) . Moreover, the total number of copies of the input X used to define |X (τ ) ⟩ and |z L (r L−1 ,a L−1 ⟩ for each τ ∈T goes as |T| and hence is K O(L8 L ) . For each τ ∈T , the contribution to gate complexity of U τ is due to A τ , which requires: O L−1 X ℓ=0 logN ℓ ! = O(L2 3L logK) one- and two-qubit gates (Claim 3.3) (i.e., Q τ ) due to the size of X (τ ) , CNOT tree which has gate complexity O(logN L−1 ), and B τ which has gate complexity O(logN L−1 ). Overall, the gate com- plexity is then: |T|O(L2 3L logK) = O L2 3L K L8 L logK . Since all the U τ s are applied in parallel, the depth of the quantum circuit before the application of the AND gate is the same as the depth of any particular U τ . The contribution to the depth of U τ is O(L + logL + log logK) from A τ or O(logQ τ ) (Claim 3.3), an additional O(log logN L−1 ) due to CNOT tree , and finally an additional O(1) depth due to B τ . Overall, the depth of the quantum circuit is then: O (L + logL + log logK). This places IterInx in ∧◦ QNC 0 [log logK]. This completes the proof. 14 Note for a specified bit b, we only require one AND gate at the end. Alternately if the goal is to output [β = z L (w L−1 ,i L−1 )], we can add β on to logN L−1 qubits, measure these in the computational basis and then perform a large AND gate over all the measurement outcomes from before along with these. 31 Iterated multi-index function. We have the following main result regarding the computation of the iterated multi-index function. Theorem 3.7. Let L ∈ N,L ≥ 2, n ℓ ,N ℓ ∈ N for all ℓ ∈ [L − 1] such that N ℓ = 2 n ℓ , for all ℓ ∈ [L− 1], and fix β ∈ [N L−1 ]. Set t = K O(L8 L ) . Given w (s) ℓ ℓ∈[L−1] , i (s) 0 , and z (s) ℓ ℓ∈[L] for all s∈ [t], the output of [β = IterMultInx(w (s) ℓ ℓ ,i (s) 0 ,z (s) ℓ ℓ )] can be computed in ∧◦ QNC 0 [log logK] with total gate complexity O(K L8 L logK). Proof. The proof proceeds similarly to that of Theorem 3.6. For every s∈ [t], denote the s-th input as: X (s) = (w (s) ,z (s) 0 ,z (s) 1 ,...,z (s) L ),where w (s) = (w (s) 1 ,...,w (s) L−1 ).(21) Let X =X (s) s∈[t] denote the entire input and define: E(X) := t s=1 [X (s) = X (1) ](22) as the consistency predicate across all Xs. By definition, we have: IterMultInx X (s) s∈[t] = E(X)IterInx(X (1) ).(23) As in Theorem 3.6, we will proceed by comparing the input against all possible candidate compu- tation histories up to computation of z (1) L (w (1) L−1 ,i (1) L−1 ). We will adopt the notation from there by letting T denote the set of candidate computation histories: τ = (a 0 ,a 1 ,...,a L−1 ,r 1 ,...,r L−1 ), where: a 0 ∈ [N 0 ], a ℓ ∈ [N ℓ−1 ] for 1≤ ℓ≤ L− 1, and r ℓ ∈ [n ℓ ] for 1≤ ℓ≤ L− 1. The number of such histories is: |T|= N 0 L−1 Y ℓ=1 N ℓ−1 ! L−1 Y ℓ=1 n ℓ ! L−1 Y ℓ=0 N ℓ = t, which is precisely the copy parameter from before. Let us order the candidate histories and let τ (s) denote the sth computation history in T where s∈ [t]. We can then denote the components of τ (s) as τ (s) = (a (s) 0 ,a (s) 1 ,...,a (s) L−1 ,r (s) 1 ,...,r (s) L−1 ). For a fixed history τ (s) ∈T and hence fixed s∈ [t], define Const τ (s) (X (s) ) as the predicate that all of the following conditions hold: z (s) 0 = a (s) 0 , w (s) ℓ = r (s) ℓ for every 1≤ ℓ≤ L− 1, z (s) 1 (a (s) 0 ) = a (s) 1 , z (s) ℓ+1 (r (s) ℓ ,a (s) ℓ ) = a (s) ℓ+1 for every 1≤ ℓ≤ L− 2.(24) 32 Thus Const τ (s) (X (s) ) checks whether the copy X (s) is consistent with the history τ (s) up to the computation of z (s) L ,∀s∈ [t]. Exactly as in the proof of Theorem 3.6, note that exactly one τ ∗ ∈T satisfies Const τ ∗ (X (s) ) = 1. For this τ ∗ (and hence when Const τ ∗ (X (s) ) = 1), we need to compute the output of z (s) L (w ∗ L−1 ,a ∗ L−1 ) (where we have decorated the components of τ ∗ with superscript∗). To this end, for every b∈ [log(N L−1 )], define: C τ (s) ,b (X (s) ) :=¬ Const τ (s) (X (s) )∧¬z (s) L (r (s) L−1 ,a (s) L−1 ) b ,(25) where the subscript b indicates the bit position of z (s) L (r (s) L−1 ,a (s) L−1 ) (which is viewed as a vector in 0, 1 logN L−1 ). For every invalid history τ (s) ̸= τ ∗ , we have Const τ (s) (X (s) ) = 0, and hence C τ (s) ,b (X (s) ) = 1. For the unique valid history τ ∗ , we have Const τ ∗ (X (s) ) = 1, and hence: C τ ∗ ,b (X) =¬ 1∧¬z (s) L (r ∗ L−1 ,a ∗ L−1 ) b = z (s) L (w (s) L−1 ,i (s) L−1 ) b ,(26) where we have used the fact that Const τ ∗ (X (s) ) = 1 indicates r ∗ L−1 = w (s) L−1 ,a ∗ L−1 = i (s) L−1 in the second equality. We next define our approach to evaluate E(X) (Eq. (22)). First, let R denote the number of bits used to encode one copy X (s) . For every s∈ [t− 1] and bit position j ∈ [R], define: D s,j (X) := [X (s) j = X (s+1) j ]. It is then immediate that: t−1 s=1 R j=1 D s,j (X) = E(X),(27) which evaluates to 1 if and only if all copies X (s) , ∀s ∈ [t] are identical. For the b-th output bit, define: F b (X) := t−1 s=1 R j=1 D s,j ∧ s∈[t] C τ (s) ,b (X (s) ) .(28) We claim that: F b (X) = IterMultInx X (s) s∈[t] b .(29) To see this, suppose first that the t input copies are not all identical. Then, there exist s∈ [t−1] and j ∈ [R] such that D s,j = 0 and consequently F b (X) = 0, which is consistent with the evaluation of IterMultInx on inconsistent copies. Now, suppose that all copies are identical i.e., X (s) = X (1) , ∀s∈ [t]. The first factor in F b (X) (Eq. (28)), which is nothing but E(X), is then 1. Moreover, there is also a unique computation history τ ⋆ for which Const τ ∗ (X (1) ) = 1, as observed earlier. We then have: s∈[t] C τ (s) ,b (X (s) ) = s∈[t] C τ (s) ,b (X (1) ) = z (1) L (w (1) L−1 ,i (1) L−1 ) b , where the second equality follows from the fact that all the input copies are equal (indeed, they are all X (1) ), and the final equality follows as in Eq. (16) in the proof of Theorem 3.6. This proves the claimed identity of Eq. (29). We now describe a quantum circuit to compute F b (X). We first introduce a circuit to evaluate D s,j (X) and hence the expression in Eq. (27). We will describe U 1 that has the following action on 33 the inputs X (s) s∈[t] along with (t− 1)R many ancilla qubits initialized as |0⟩: ⊗ s∈[t] |X (s) ⟩ |0⟩ (t−1)R U 1 −→ ⊗ s∈[t] |X (s) ⟩ O s∈[t−1] O j∈[R] |D s,j ⟩ (30) For this, we will re-use the circuit introduced in the proof of Claim 3.4 for checking equality of different copies of indices. Let us denote the (t − 1)R ancilla qubits as o s,j s∈[t−1],j∈[R] . We first apply a layer of (t− 1)R CNOTs in parallel with a CNOT gate from each |X (s) b ⟩ to o s,j for all s ∈ [t − 1],j ∈ [R]. This has the effect of setting the state of o s,j to that of X (s) j . We then apply another layer of CNOTs in parallel with a CNOT gate from each X (s+1) j to o s,j for all s ∈ [t− 1],j ∈ [R]. At this point, the state of each qubit o s,j is |X (s) j ⊕ X (s+1) j ⟩. Applying a single-qubit X gate on each o s,j then sets of the state to be the indicator [X (s) j = X (s+1) j ] i.e., |o s,j ⟩ = |[X (s) j = X (s+1) j ]⟩ = |D s,j (X)⟩, ∀s ∈ [t− 1],j ∈ [R]. At this point, we could measure all the qubits over o s,j in the computational basis and apply an AND gate over the measurement outcomes to obtain the value of E(X) (Eq. (27)). However, we will postpone this step until after describing how to obtain z (1) L (w (1) L−1 ,i (1) L−1 ) in the case E(X) = 1. For a fixed s∈ [t] and hence a fixed τ (s) ∈T , we now describe a circuit to compute C τ (s) ,b (X) for all b ∈ [logN L−1 ] (Eq. (25)). Define |Y (s) ⟩ as a portion of the copy of the input X (s) assigned to the computation history τ (s) = (r (s) 1 ,...,r (s) L ,a (s) 0 ,a (s) 1 ,...,a (s) L−1 ): Y (s) := (w (s) ,z (s) 0 ,z (s) 1 (a (s) 0 ),z (s) 2 (r (s) 1 ,a (s) 1 ),...,z (s) ℓ (r (s) ℓ ,a (s) ℓ ),...,z (s) L−1 (r (s) L−2 ,a (s) L−2 )).(31) Once τ (s) is fixed, all the addresses involved in z (s) ℓ+1 (r (s) ℓ ,a (s) ℓ ) for all ℓ∈ [L− 2] are fixed. We can then use the circuit U τ from the proof of Theorem 3.6, denoted here as U τ (s) , to clarify which copy of the input we work with, and which has the following action inputs of |Y (s) ⟩, |z (s) L (r (s) L−1 ,a (s) L−1 )⟩ along with 2 logN L−1 ancilla qubits: |Y (s) ⟩|0⟩ ⊗ log N L−1 |z (s) L (r (s) L−1 ,a (s) L−1 )⟩|0⟩ ⊗ log N L−1 U τ (s) −→|Y (s) ⟩|Const τ (s) (X (s) )⟩ ⊗ log N L−1 |z (s) L (r (s) L−1 ,a (s) L−1 )⟩ ⊗ b∈[logN L−1 ] |C τ (s) ,b (X (s) ⟩ .(32) Applying the circuits U τ s in parallel for all s∈ [t] (and hence all τ (s) ∈T ) would then simply produce: ⊗ s∈[t] |Y (s) ⟩|0⟩ ⊗ logN L−1 |z (s) L (r (s) L−1 ,a (s) L−1 )⟩|0⟩ ⊗ logN L−1 ⊗ s∈[t] U τ (s) −→⊗ s∈[t] h |Y (s) ⟩|Const τ (s) (X (s) )⟩ ⊗ logN L−1 |z (s) L (r (s) L−1 ,a (s) L−1 )⟩ ⊗ b∈[logN L−1 ] |C τ (s) ,b (X (s) )⟩ i . Denote the overall circuit as U := (⊗ s∈[t] U τ (s) )U 1 , which then has the following action: ⊗ s∈[t] |X (s) ⟩ |0⟩ (t−1)R |0⟩ 2 logN L−1 U −→ ⊗ s∈[t] |X (s) ⟩ O s∈[t−1] O j∈[R] |D s,j ⟩ |Const τ (s) (X (s) )⟩ ⊗ logN L−1 ⊗ b∈[logN L−1 ] |C τ (s) ,b (X (s) )⟩ , (33) 34 where we have noted that |Y (s) ⟩, |z (s) L (r (s) L−1 ,a (s) L−1 ⟩ are a part of the input |X (s) ⟩, and collected all the ancilla qubits required for U 1 and U τ (s) in the first line. For a specified b ∈ [logN L−1 ], measuring the qubits which hold the state |D s,j ⟩,∀s ∈ [t− 1],j ∈ [R] and |C τ (s) ,b ⟩,∀s ∈ [t] in the computational basis and then applying the AND logical gate over the outcomes then gives us the desired result of Eq. (29). 15 We can now once again analyze the qubit count, depth, and gate complexity of U . For each s∈ [t], the total number of input qubits involved in defining |X (s) ⟩ is: R = O logN 0 + L−1 X ℓ=1 logn ℓ + L−1 X ℓ=0 logN ℓ ! = O L−1 X ℓ=0 logN ℓ ! , where we have used the fact that the size of the input and output to z ℓ require⌈logN ℓ−1 ⌉ bits each to specify. Using the fact that N ℓ = m· Q ℓ j=1 n j , n ℓ (T,L) = K 4·8 L−ℓ−1 , m = K 8 L and that L is assumed to be a constant, we then have that: R = O L2 3L logK . Taking into account the size of t and our choices for the parameters, the total number of qubits used is: tR = K O(L8 L ) . The contribution to the gate complexity of U is due to U 1 , which has gate complexity O(tR) = K O(L8 L ) , and U τ (s) for all s∈ [t], each requiring: O L−1 X ℓ=0 logN ℓ ! = O(L2 3L logK) one- and two-qubit gates (from the proof of Theorem 3.6). Overall, the gate complexity of U is therefore: O(tL2 3L logK + K L8 L ) = O L2 3L K L8 L logK . Since all the U s ’s are applied in parallel, the depth of U before application of the AND gate is same as depth of any particular U s , which is O (L + logL + log logK), in addition to the depth of U 1 which is O(1). Overall, the depth of U is therefore: O (L + logL + log logK). This places IterMultInx in ∧◦ QNC 0 [log logK], and completes the proof. 3.4 Classical lower bound 3.4.1 Communication problem and token count We use the autoregressive model used in [CPW25] to show unconditional lower bounds on trans- former architectures, but adapt it to apply to the IterMultInx function. Our autoregressive model consists of L + 2 macro-players, who are indexed −1, 0, 1,...,L. The protocol takes place over L communication epochs, which are inherently directional. For each index i, macro-player i receives as input the concatenation of t sub-player copies. In particular: 15 Alternately, if given a β ∈ [N L−1 ], we can also output [β = IterMultInx(X)] by adding β on logN L−1 ancilla qubits, measuring these in the computational basis and performing a classical AND gate on these along with all the measurement outcomes for each b∈ [logN L−1 ] from before. 35 1. the input of macro-player −1 is (w (1) ,...,w (t) )∈ A t −1 ; 2. the input of macro-player 0 is (z (1) 0 ,...,z (t) 0 )∈ A t 0 ; 3. for ℓ∈ [L], the input of macro-player ℓ is (z (1) ℓ ,...,z (t) ℓ )∈ A t ℓ . At the end of the protocol, i.e., at the end of epoch L, macro-player −1 must output the value of IterMultInx on the given instance. Token counts. We now estimate the total number of tokens taken up by each player in the communication protocol. For this, it will be helpful to use the parameters as counted in the original protocol used in [CPW25], which used the iterated index problem. Let m (i) orig denote the token count of player i in the original iterated index problem, i.e.: m (i) orig = ( N i−1 i∈ [L], 1 i∈−1, 0. In our problem, i.e., the iterated multi-index problem, on the other hand, macro-player i holds t concatenated copies of the same set of tokens. So now, his token count becomes m (i) new := t· m (i) orig , which means the total input length (i.e., number of tokens) becomes: n(T,L) := L X i=−1 m (i) new = t· n orig (T,L),(34) where n orig (T,L) := P L i=−1 m (i) orig is the total (token) length of the original iterated index instance. Now, recall that the autoregressive communication model relies on a bandwidth parameter B ∈ N (which relates it to the width of the transformer in Lemma 2.4). By definition, no response that player i receives from player j can exceed the bandwidth bit-count. Specifically, we must have, for each ℓ∈ [L], and any pair of players i and j: Π (ℓ) j,i ≤ 2B· m (i) .(35) As we stated earlier, for the protocol to succeed, at the end of epoch L, player −1 must output a value that depends only on X (L) −1 . We are now ready to prove our lower bound, after a couple of lemmas we state first. Lemma 3.8. The copy complexity t = t(T,L), as defined in Section 3.2.2, satisfies the follow- ing bound: t≤ C L · T c L , where c L = 2 O(L) , C L = 2 2 O(L) . In particular, for every constant L, we have that t is a fixed polynomial in T . Proof. We first bound each N ℓ in terms of K. By definition, N ℓ = m· Q ℓ j=1 n j , so the exponent of K in N ℓ is: L−1 X j=0 8 j+1 + ℓ X j=1 4· 8 L−j−1 . Observe that this is a sum of two geometric series, each with ratio 8. Clearly, both sums are 2 O(L) , and so, for all ℓ, we have N ℓ = K 2 O(L) . Therefore, we have: t = L−1 Y ℓ=0 N ℓ = K 2 O(L) L = K L·2 O(L) = K 2 O(L) . 36 Substituting K = (TL) 8 , we obtain: t = (TL) 8 2 O(L) = T 8·2 O(L) · L 8·2 O(L) = C L · T c L , where we have set C L := L 8·2 O(L) and c L := 8· 2 O(L) and absorbed all other implicit constants independent of L into them appropriately. Note that both C L and c L only depend on L. 3.4.2 Transformer lower bound Lemma 3.9. Fix T ≥ 1. Suppose that there is a deterministic autoregressive protocol Π multi that solves IterMultInx on bandwidth T in L epochs for every instance. Then, there is a deterministic autoregressive protocol Π orig that solves IterInx on bandwidth T ′ := Tt in L epochs for every instance. Proof. Consider an arbitrary instance (w,z 0 ,z 1 ,...,z L ) of IterInx, where the tuple is distributed across players −1, 0, 1,...,L in the usual way (i.e., player i holds the i-th component of the vec- tor). Now, we can have the players in the protocol Π orig simulate Π multi on the diagonal instance w (s) s∈[t] ,z (s) 0 s∈[t] ,z (s) 1 s∈[t] ,...,z (s) L s∈[t] of IterMultInx: w (s) := w, z (s) 0 := z 0 , z (s) ℓ := z ℓ for all s∈ [t],ℓ∈ [L]. Concretely: 1. For all i ∈ −1, 0, 1,...,L, player i locally constructs the t-fold concatenation of its input, and treats the resulting string as the input to macro-player i in Π multi . Note that this is purely local; no communication between players is needed. 2. The players now run Π multi verbatim, acting as the macro-players in that protocol. In par- ticular, whenever a message Γ (ℓ) i,j or response Π (ℓ) j,i is sent in Π multi between the macro-players, the same bits are passed in Π orig between the same players. 3. At the end of epoch L, player −1 in Π orig outputs the output of macro-player −1 in Π multi . Note that the resulting protocol is correct: on the diagonal instance the consistency predicate E = 1 (i.e., all the xs given to individual players are the same), and so the output of Π multi equals IterInx(w,z 0 ,z 1 ,...,z L ), as required. Let us examine the bandwidth used by Π orig . Suppose player i in Π orig has m (i) orig tokens; he locally concatenates t copies of this, creating m (i) new = t·m (i) orig tokens, and therefore each of his communicated strings is blown up by a factor of t. By the bandwidth constraint of the autoregressive model applied to Π multi , we have: Π (ℓ) j,i ≤ 2T · m (i) new = 2(Tt)· m (i) orig , which is precisely within the bandwidth-(Tt) budget of Π orig . The number of epochs remains unchanged at L. We are now ready to state and prove the lower bound. The instance family is parameterized by the transformer’s bandwidth itself: the parameters K,m,n ℓ ,N ℓ ,t,n are defined exactly as above (as functions of T = Hdp and L). This is the standard parameterization of [CPW25], in which the hard instance is tailored to the candidate model size. To prove the theorem, we first observe that on top of the parameters involved in T -parameterized IterMultInx, our quantum upper bound also had an extra parameter β ∈ [N ℓ−1 ] specified in the problem and the goal was to check if β equals the output of the T -parameterized IterMultInx. Since we prove lower bounds 37 against determiistic transformer models (for which we showed the∧◦ QNC 0 [log logn] upper bound. However, note that checking this equality amounts to computing the output of T -parameterized IterMultInx, and hence below we prove lower bounds on transformers computing this function. 16 Theorem 3.10. Let L ≥ 2 be constant. LetT be any L-layer decoder-only transformer (with H heads, embedding dimension d, and precision p, with width T := Hdp) which solves every instance of the T -parameterized IterMultInx family. Then, the width T ofT satisfies: T ≥ n(T,L) 2 −O(L) , where n(T,L) is the number of tokens (i.e., context length) needed to specify the instance family. Proof. SinceT solves the T -parameterized IterMultInx family on every instance, by Lemma 2.4, there is an L-epoch autoregressive protocol Π multi of bandwidth T solving the same task. 17 By Lemma 3.9 (applied with bandwidth T and copy parameter t), there is an L-epoch autoregressive protocol Π orig of bandwidth Tt solving IterInx on the same parameter T . Applying Theorem 3.5 to Π orig , we get: Tt≥ n α L orig , where α L = 2 −O(L) .(36) By Lemma 3.8, t = C L T c L with c L = 2 O(L) , and C L = 2 2 O(L) . Substituting into (36), we get: C L · T c L +1 ≥ n α L orig (37) By definition of n and Eq. (34), we have n = t· n orig = C L T c L · n orig . Hence, we get: n orig ≥ n C L T c L . Substituting this into (37) yields: T c L +1 ≥ 1 C L · n C L T c L α L = n α L C 1+α L L · T c L α L =⇒ T c L +1+c L α L ≥ n α L C 1+α L L . The exponent on the left-hand side is c L (1 + α L ) + 1 ≤ 2c L + 1 = 2 O(L) (since α L ≤ 1). For constant L, C 1+α L L is a constant independent of n. Taking roots and absorbing the constant into the asymptotic, we get: T ≥ n α L /(c L +1+c L α L ) = n 2 −O(L) . Since T = Hdp by definition, the claimed bound is immediate. 3.5 Obstructions in further improvement In this section, we show that if a function f is deterministically computable by QNC 0 circuit of depth log logn (given an advice state) and followed by an AND gate, then this f is already in AC 0 . Note that AC 0 functions roughly capture constant-precision transformers (which are quite weak from an expressivity point of view); indeed, we wish to have lower bounds against at least log-precision transformers. However, since our main result already says that an O(log logn)-depth 16 Concretely, we remark that when reducing the transformer lower bound to the communication lower bound, we will provide this β parameter to the L + 2-th player, who needs to check if β equals the output of T -parameterized IterMultInx which depends on parameters defined for the previous L− 1 players. 17 Actually, Lemma 2.4 is about IterInx rather than IterMultInx, but we can adapt the same result for IterMultInx as well with no change in the proof. 38 QNC 0 circuit with a single AND gate computes functions outside of such log-precision transformers, this shows that even increasing the depth of our (log logn)-circuit by a constant multiple has an effect on its computational power. This implies that our separation is essentially optimal. 18 Indeed, if we increase the depth from log logn to c· log logn for some constant c > 1, then we break past AC 0 to a function that is hard for transformers, i.e., needs width n Ω(1) . Theorem 3.11. Let n≥ 1 and d≤ log logn+O(1). Every function f :0, 1 n →0, 1 computable by ∧◦ QNC 0 [d]/qpoly can be computed in AC 0 . Proof. Let U be the depth-d QNC 0 circuit, let |ψ n ⟩ be the advice state, and let the input state be |x⟩|0⟩|ψ n ⟩. Let q 1 ,...,q m be the designated output qubits, where m = poly(n). For each j, let Q j denote the projector onto the event that output qubit q j is measured as 1, and define: P j := U † Q j U. The projectors P j commute, since the corresponding output measurements commute. The final AND gate accepts with probability: ⟨x, 0,ψ n | m Y j=1 P j |x, 0,ψ n ⟩. Because the computation is exact, this acceptance probability is either 0 or 1, and it equals f n (x). Since Q j P j is a projector, the acceptance probability is 1 if and only if: m Y j=1 P j |x, 0,ψ n ⟩ =|x, 0,ψ n ⟩. For commuting projectors, this is equivalent to: P j |x, 0,ψ n ⟩ =|x, 0,ψ n ⟩for every j ∈ [m]. Thus f n (x) = 1 if and only if V m j=1 g j (x) = 1. The light cone of the output qubit q j contains at most 2 d input qubits, since the circuit has bounded fan-in and depth d. Hence P j acts nontrivially only on those at most 2 d input qubits, together with some ancilla and advice qubits. The ancilla and advice states are fixed independently of x. Therefore the truth value of g j (x) depends only on the input bits in this light cone. Thus each g j is a Boolean function of at most 2 d input bits. Since any Boolean function on k bits can be written as a DNF of size at most k2 k , applying this fact with k ≤ 2 d yields the fact that each g j has a depth-2 AC 0 circuit of size 2 O(2 d ) . Taking the AND over all m = poly(n) such circuits gives an AC 0 circuit for f n of size poly(n, 2 2 d ). So, if d ≤ log logn, then f n ∈ AC 0 , as desired. 4 Distributional separation: quantum circuits versus DLMs In this section, we begin by describing our candidate problem for the distributional separation, and then prove our upper and lower bounds, with the latter being the bulk of the technical content. 18 As we mentioned in the introduction, our result crucially uses that f is exactly computed by ∧◦ QNC 0 /qpoly. If f was only approximated by these circuits, then such a result is unclear. 39 4.1 Main result Candidate problem. We first define our candidate problem. For B ∈ N, consider the set of length-B strings which have even parity, and define the uniform distribution on this set as follows: U ⊕ B := unifx∈0, 1 B :|x|= 0. For n = MB, define the block-parity distribution: D blk := M O b=1 U ⊕ B , i.e., D blk is uniform on the set of strings x 1 ,...,x M ⊆ 0, 1 B such that L i∈[B] x j i = 0 for all j ∈ [M ]. Our proof will require us to keep careful track of these parameters, and we will use the following settings: B = n 0.01 , M = n 0.99 , s,R = n 0.9 ,(38) where s is the number of CoT/workspace tokens, and R is the total number of output-token revision/remasking events. Note that by this definition, D blk is defined on n bits and all the other parameters such as CoT, remasking, revision will be o(n). These parameter choices will become clear when discussing our lower bounds. 19 With these definitions we prove our main result. Theorem 4.1. The distribution D blk satisfies the following: 1. D blk can be sampled exactly by a QNC 0 circuit. 2. No constant-round shallow DLM(GC 0 , logn) with s = n 0.9 CoT tokens and R = n 0.9 output- token remasking/revision events can sample D blk within constant total variation distance. We now make a few remarks about our candidate problem and the lower bound. The DLM samplers we consider have no input; on any (vacuous) input, their goal is just to produce an output that is a uniform sample from the distribution D blk . The DLM that we consider here is the same one described in Section 1, wherein each token generated within the same round is generated in a conditionally independent manner, given the current full transcript. The constraints on this DLM are as follows: (i) We allow only s = n 0.9 hidden transcript bits. (i) The output schedule may be fully adaptive and may depend on hidden token values. (i) For each transcript cell τ , the corresponding token is computed by a polynomial-size GC 0 (k) circuit with depth O(1), where k = O(logn) (i.e., consists of GC k gates for k = O(logn)). 4.2 Quantum upper bound We first show that the block-parity distribution is easy for shallow quantum circuits. The key ingredient is the poor man’s cat state construction of Watts-Kothari-Schaeffer-Tal [BWKST19], which can be prepared in QNC 0 . 19 We remark that one could have also chosen B,M such that B· M = n and s,R = o(M ), so we could have also handled s,R = n 1−ε for arbitrarily small constant ε. We chose the parameters above for the sake of simplicity in presentation. 40 Lemma 4.2. For every B, the distribution U ⊕ B can be sampled exactly by a QNC 0 circuit. Conse- quently, D blk can be sampled exactly by a QNC 0 circuit. Proof. We first describe how to prepare the poor man’s cat state in QNC 0 . We start with B qubits initialized to |0⟩ ⊗B . Applying Hadamard to all qubits gives |+⟩ ⊗B = 1 √ 2 B P x∈0,1 B |x⟩. Next, we measure the commuting parity observables Z i Z i+1 , for i = 1,...,B − 1. 20 Let the measurement outcomes be s i ∈0, 1, where s i = 0 corresponds to eigenvalue +1 (i.e., x i ⊕x i+1 = 0), and s i = 1 corresponds to eigenvalue −1 (i.e., x i ⊕ x i+1 = 1). These B− 1 parity constraints determine the string uniquely up to its bitwise complement. More precisely, there is some string z ∈ 0, 1 B , such that z and ̄z are the only two solutions to all constraints (in fact, they would be of the form z 1 = 0,z 2 = s 1 ,z 3 = s 1 +s 2 ,... and z 1 = 1,z 2 = 1+s 1 ,z 3 = 1+s 1 +s 2 ,... where all the additions are modulo 2). Therefore, after applying these B− 1 projective measurements, the post-measurement state is: |z⟩ +| ̄z⟩ √ 2 ,(39) which is referred to as the poor man’s cat state. The value of z depends on the measurement outcomes (s 1 ,...,s B−1 ), but this will not matter for the sampling task. Now, finally, we apply Hadamard to all B qubits, and measure in the computational basis. For any outcome y ∈0, 1 B , the amplitude equals: y Had ⊗B |z⟩ +| ̄z⟩ √ 2 ∝ (−1) y·z + (−1) y· ̄z . Since y· ̄z = y· z + P B i=1 y i (mod 2), we obtain: (−1) y·z + (−1) y· ̄z = (−1) y·z 1 + (−1) |y| . Therefore, the amplitude vanishes whenever |y| is odd, and has equal magnitude for every even- parity string y. Hence, the measurement outcome is distributed exactly as y ∼ U ⊕ B . Let us quickly describe the corresponding quantum circuit. Consider the input of|+⟩ B on the B system qubits, which we will denote by q i . Let us add B−1 many ancilla qubits, which we denote by a i ,∀i∈ [B− 1], each initialized to|0⟩. To carry out the measurement corresponding to Z i Z i+1 ,∀i∈ [B− 1], we will first apply a layer of CNOTs with control over q i to the target a i for all i∈ [B− 1] followed by another layer of CNOTs with control over q i+1 to the target a i for all i∈ [B− 1]. At this point, the state over the system and ancilla qubits is 1 √ 2 B P x |x⟩ ⊗ i∈[B−1] |x i ⊕ x i+1 ⟩ . Measuring the qubits a i ,∀i ∈ [B− 1] in the computational basis then results in the post-measurement state of Eq. (39) over qubits q i ,∀i ∈ [B]. Finally, applying Hadamards to the qubits q i and then measuring all q i in the computational basis yields outcomes y ∼ U ⊕ B as shown above. This circuit is illustrated in Figure 6. We observe that the poor man’s cat state (Eq. (39)) can be prepared in depth 4, and overall this gives an exact QNC 0 sampler for U ⊕ B . Running this sampler independently and in parallel on all M blocks gives an exact QNC 0 sampler for D blk , proving the lemma statement. The overall circuit has depth 4, gate complexity O(BM ), and is over O(MB) qubits. 4.3 Lower bound: important lemmas For the lower bound, we will use as a black box the following theorem of Kumar [Kum23], that shows that GC 0 [logm] circuits cannot approximate the parity function with constant bias, extend- 20 By this we mean, apply the two-qubit operator Π s i = |00⟩⟨00|+|11⟩⟨11| and Π 1+s i = |01⟩⟨01|+|10⟩⟨10| onto qubits i,i + 1. 41 q 1 :|0⟩ H • H y 1 a 1 :|0⟩ s 1 q 2 :|0⟩ H • H y 2 a 2 :|0⟩ s 2 q 3 :|0⟩ H • H y 3 a 3 :|0⟩ s 3 q 4 :|0⟩ H • H y 4 a 4 :|0⟩ s 4 q 5 :|0⟩ H • H y 5 Figure 6: Illustration of circuit for preparing the poor man’s cat state and sampling from U ⊕ 5 . ing the well-known result of Hastad [H ̊as14] that AC 0 functions cannot approximate parity with constant bias. Theorem 4.3 ([Kum23]). If C:0, 1 m → 0, 1 is a polynomial-size constant depth GC 0 [logm] circuit, then: Pr x∼0,1 m [C(x) = x 1 ⊕·⊕ x m ]≤ 1 2 + 2 −Ω(m/poly log(m)) . 4.3.1DLM run as a combination of distributions We now show the core structural fact underlying the lower bound. Recall that, by the model definition, a DLM follows a sequence of denoising steps before the n output tokens (which we will view as M blocks of B bits) need to produce a string distributed according to D blk . Consider a DLM round t, and consider the parity blocks that are completed for the first time in this round. For such a block b∈ [M ], let r b denote the number of coordinates in block b that are newly generated in the t-th round; equivalently, r b is the number of block-b coordinates that were still masked in each of the first t− 1 rounds. Now, observe that since D blk is uniform on every block b∈ [M ], the newly generated coordinates in the completion round should closely emulate the uniform distribution over an affine parity coset. In particular, the target conditional law for the block b is the distribution: 21 U r b a b := unif n x∈0, 1 r b : r b M i=1 x i = a b o , where a b ∈0, 1 is set according to the parity value of the previously revealed coordinates of the block in the first t− 1 rounds. Now, suppose there are q ≤ M such blocks completed in the t-th 21 Throughout this section, we interchangeably use ⊕x i and |x|= P i x i but emphasize that we using the latter, the summation is modulo 2. 42 round. Then, the overall target conditional law is the product distribution: V = q O b=1 U r b a b .(40) In other words, V is a product distribution across the simultaneously completed blocks, but each of the factors U r b a b contains an internal parity constraint among the coordinates of that block (de- termined by a b ). Let D := P q b=1 (r b − 1) be the total dimension of the parity-coset distribution V . Consequently, we have: |supp(V )|= q Y b=1 2 r b −1 = 2 D . Let N := P q b=1 r b denote the total number of generated coordinates. The following theorem precisely quantifies the obstruction created by these “inter-block” constraints; roughly speaking, even though the q blocks in V are independent of one another, a distribution with many parity- constrained factors cannot be approximated by a small mixture of fully coordinate-wise product distributions. 22 Theorem 4.4. Let q ≤ M ∈ N be the number of blocks completed in the t-th round. For r b ≥ 2,a b ∈0, 1, define: U r b a b = unifx∈0, 1 r b :|x|= a b (mod 2). Define V be as in Eq. (40), N = P q b=1 r b , and D = N−q. Suppose W is a distribution on 0, 1 N with supp(W )⊆ supp(V ) and H(W )≥ D−κ for some κ≥ 0. 23 Then, there exists a constant η > 0 such that whenever P is a mixture of K product distributions (i.e., P = P K h=1 λ h Q h for product distributions Q h ) satisfying TV(P,W )≤ η, then there exist constants c 1 ,c 2 satisfying: logK ≥ c 1 D− κ − c 2 . Proof. Let Π b denote the set of fresh coordinates of block b revealed in the current round, so |Π b |= r b . In Eq. (40), the b-th tensor factor U r b a b is indexed by these coordinates, after choosing an arbitrary ordering of Π b . Thus, identifying 0, 1 r b with 0, 1 Π b , we have: supp(V ) = x∈0, 1 Π : M i∈Π b x i = a b for every b ,Π := q [ b=1 Π b . Then V is uniform on S, and |S|= Q b 2 r b −1 = 2 D (since each linear constraint on x ∈ 0, 1 r b is satisfied by exactly half the variables). Since V is supported on S, we have V (S) = 1 and V (S c ) = 0. Since supp(W )⊆ S, we also have W (S) = 1 and W (S c ) = 0. Therefore, we have: P (S c ) =|P (S c )− W (S c )|≤ TV(P,W )≤ η.(41) Next, since P and W are distributions on 0, 1 N , Lemma 2.2 implies: |H(P )− H(W )|≤ η· log(2 N − 1) + h 2 (η) < ηN + h 2 (η), 22 Although this does not seem a priori related to DLMs as stated, every round of a DLM in fact generates product distributions, which is the connection that we will utilize later. 23 Note that the choice W = V corresponds to κ = 0. 43 where h 2 (·) denotes the binary entropy function. Therefore, we have: H(P )≥ H(W )− O(ηN )− O(1)≥ D− κ− O(ηN )− O(1)≥ (1− c 1 η)D−κ− O(1),(42) where the second inequality uses the fact that H(W )≥ D−κ (an equality when W = V , since V is uniform on a set S of size 2 D ), and the last inequality uses the fact that N = P b r b ≤ 2 P b (r b −1) = 2D. On the other hand, we can sample from P by first choosing h ∈ [K] and then sampling Q h ; therefore, we have: H(P )≤ logK + E h H(Q h ).(43) Let α h := Q h (S c ), so that α h is the probability that the product distribution Q h violates at least one of the parity constraints defining S. Since P = P K h=1 λ h Q h , we have: η ≥ P (S c ) = X h λ h α h = E h [α h ],(44) where the first inequality used Eq. (41). Hence E h [α h ] ≤ η. Fix parameters τ = 10 −3 and η = 1/20(c 1 + 2· 10 3 ), where c 1 is the constant that appears in Eq. (42). We now split the mixture components into “good” and “bad” components according to whether α h ≤ τ or α h ≥ τ . Bad components.By Markov’s inequality on Eq. (44), first observe that: Pr h [α h > τ ]≤ E h [α h ]/τ ≤ η/τ. So, the total weight over all possible h on the bad components is at most η/τ . Now every distribution on 0, 1 N has entropy at most N . Hence, the entropy contributed by each of the bad components to the overall average entropy E h [H(Q h )] is at most (η/τ )· N ≤ 2η/τ · D (where we have used the fact that N ≤ 2D, established earlier). Good components.It remains to bound the entropy of the good components, namely, those satisfying Q(S c )≤ τ. Fix such a product distribution Q = Q i Q i , and for each block b, let ε b denote the probability that Q violates the parity constraint in block b. Equivalently: 1− ε b = Q M i∈Π b x i = a b . Since Q is a product across the coordinates, and the blocks Π b are disjoint, this implies the parity events across different blocks are actually independent. Therefore, we have: Q(S) = Y b (1− ε b ). Since Q(S c )≤ τ , we have Q(S)≥ 1− τ , i.e., Q b (1− ε b )≥ 1− τ . Again, by taking logarithms and using the identity − log(1− u)≥ u for u∈ [0, 1), we get that: X b ε b ≤− log(1− τ )≤ 2τ, 44 using the fact that τ is a sufficiently small constant (e.g., our choice of 10 −3 ). We now analyze a single block Π b . Write p i := Q i (1), and t i := minp i , 1−p i . Recall that for independent Bernoulli variables, X i ∼ Bernoulli(p i ), we have: Pr M i∈Π b X i = a b = 1 2 1 + (−1) a b Y i∈Π b (1− 2p i ) . which follows from the fact that: E h (−1) ⊕ i∈Π b X i i = Y i∈Π b E[(−1) X i ] = Y i∈Π b (1− 2p i ). Since the left hand side is precisely 1− ε b , we have that 1− ε b = Y i∈Π b (1− 2t i )≥ 1− 2 X i∈Π b t i , where the second inequality uses the identity Q i (1−a i )≥ 1− P i a i for a i ∈ [0, 1]. Taking logarithms on both sides and using the identity − log(1− u)≥ u for u∈ [0, 1) again as before, we obtain X i∈Π b t i ≤ Cε b for some absolute constant C provided ε b ≤ 1/10. Hence, the entropy of the block equals: X b H(Q Π b ) = X b X i∈Π b h 2 (p i ) = X b X i∈Π b h 2 (t i )≤ X b X i∈Π b t i log e t i ≤ C X b ε b log er b ε b ≤ C·τ logeN/τ, using h 2 (u) = h 2 (1 − u) (by definition of binary entropy), and also the concavity of the map u 7→ u log(e/u), and then finally the fact that P b e b ≤ τ . Therefore, every good component satisfies H(Q h )≤ Cτ log eN τ . Combining the good and bad components, we obtain: E h [H(Q h )]≤ Cτ log(eN/τ ) + 2ηD/τ. Finally, using Eq. (43) and Eq. (42), we get: (1− cη)D−κ− O(1)≤ H(P )≤ logK + E h [H(Q h )]≤ logK + Cτ log eN τ + 2η τ D, which lets us conclude that: logK ≥ (1− c 1 η− 2η/τ )D−κ− Cτ log(eN/τ )− O(1)(45) ≥ (1− c 1 η− 2η/τ )D−κ− Cτ log(2eD/τ )− O(1)(46) ≥ c 3 D− κ− c 4 ,(47) using the fact that η and τ were chosen to be constants, c 3 and c 4 are new constants, and D is sufficiently large. The theorem follows by relabeling the constants c 3 ,c 4 as c 1 ,c 2 respectively. 45 4.3.2DLMs for D blk induce high entropy distributions Notation. We first define some necessary and convenient notation. Let η := TV(P Y ,D blk ). • P Y is the output distribution of the DLM: the law of the final n-bit string, ignoring the workspace. By assumption, TV(P Y ,D blk )≤ η. • P is the distribution of the entire run: every revealed token (workspace and output), in order. • Let b D = D blk (· | A) for A = supp(P Y ), i.e., the induced distribution of D blk conditioned on the bits in A having been revealed by P Y already. • Let Y denote the final output string of the DLM. Define a distribution Q over executions 24 by first sampling y ∼ b D, then sampling an execution from the original law P conditioned on Y = y: Q(·) := X y b D(y) P(·| Y = y).(48) Furthermore, suppose the final n coordinates of the DLM run were a and the remaining tokens were y (i.e., including the revealed output coordinates and their assignments). Then, we have: P(output=a,rest=y) = P Y (a)· P(rest = y|output = a)(49) Q(output=a,rest=y) = b D(a)· P(rest = y|output = a)(50) by the definitions above. Observe that Q≤ P. 25 We work under the reweighted law Q rather than with P directly, specifically in order to make the target constraints exact. Namely, Q preserves the DLM’s conditional execution law given the final output, while replacing the output marginal by b D, so that each completed block has the exact parity structure of D blk . An execution E = (V 1 ,...,V t ) is the ordered record of token values revealed during the run (workspace and output). Since the schedule is a deterministic function of the current state, the positions of these values are determined by the values themselves, and so E determines the run completely. Furthermore, we define the history of the run to be F t := (V 1 ,...,V t−1 ) as the DLM configuration at the start of round t. Throughout this section, we define a realizable history F as one wherein Q(F t = F ) > 0. Given F t = F (note that F will often be suppressed when it is unambiguous from the context), we define the following: 1. We write Π t (F ) ⊆ [n] for the output coordinates revealed in round t; sometimes we also write Π b t to denote the output coordinates of block b revealed in round t; furthermore, define r b :=|Π b t |. 2. We write C t (F ) for the blocks completed in round t (i.e., coordinates revealed during round t that had not been revealed at the end of round t− 1). 3. Let c t :=|C t (F )| be the number of blocks b completed during round t. 4. We write O t ∈ 0, 1 Π t (F ) for the vector of output bits generated on these coordinates in round t. Thus, O t consists of the output components of the entire round record V t . 5. We write a b (F )∈0, 1 for the parity of its values revealed already; and define: S F := n z ∈0, 1 Π t : M i∈Π b z i = a b (F ) for every b∈ C t o ,log|S F |=|Π t |−c t . 24 We remark that this distribution is not physically motivated but will be useful for our calculations. 25 By this we mean every event of P-probability zero also has Q-probability zero: Q never produces a trajectory the DLM could not. 46 In the basic model (Steps 1–3) every output coordinate is revealed exactly once (we will discuss the remasking/revision later, in Section 4.4.3). Entropy counting in DLMs. The following observation is the basic entropy accounting behind the proof. Fix a round t and condition on a realized history F before this round. Then, the schedule fixes the set Π t (F ) of output coordinates generated before round t (since it was deterministic by definition). Thus, the only remaining randomness in this round is the vector O t ∈ 0, 1 Π t (F ) of newly generated output bits during round t. Now consider a block b that is completed in this round, e.g., b∈ C t (F ). All coordinates of block b outside Π b t (F ) have already been revealed in the history F . Since the output marginal of Q is b D (by Eq. (48)), and b D is supported on valid D blk outputs, the final block must satisfy the corresponding parity constraint. Therefore, the newly generated bits in Π b t (F ) cannot be arbitrary: they must satisfy an affine parity constraint determined by the bits of block b already present in F . For each completed block b∈ C t (F ), the parity condition in block b imposes one affine constraint on the newly generated coordinates Π b t (F ): M i∈Π b t (F ) Y t,i = M i∈B b \Π b t (F ) y i , where the right-hand side is fixed by the history F . Since distinct blocks involve disjoint sets of coordinates, these constraints are independent. Thus, the possible values of O t are contained in an affine subspace: S F ⊆0, 1 Π t (F ) of codimension c t (F ) =|C t (F )|, and therefore: |S F |= 2 |Π t (F )|−c t (F ) . It follows that since O t ∈ S F , we have: H Q (O t |F t = F )≤ log|S F |=|Π t (F )|−c t (F ), where H Q (O t |F t = F ) denotes the Shannon entropy of the newly revealed coordinates in round t under the conditional distribution Q(·|F t = F ). We therefore define the entropy deficit in round t on history F as: δ t (F ) := (|Π t (F )|−c t (F ))− H Q (O t |F t = F ).(51) The preceding discussion shows that δ t (F ) ≥ 0. Intuitively, δ t (F ) measures exactly how much entropy the actual conditional law of the newly generated bits loses beyond the entropy loss forced by the parity constraints of the blocks completed in this round. We now formally state a lemma about this entropy deficit. We use calligraphic letters for random objects and plain lowercase letters for their realizations. For notational convenience, we use F t to denote the random history before round t, while F denotes a fixed realized value of this history. Similarly,E is the random execution, while e is a realized execution. Lemma 4.5. Suppose that TV(P Y ,D blk )≤ η ≤ 1/2. Then, we have: (a) TV(P, Q)≤ 2η; (b) T X t=1 E Q [δ t (F t )] ≤ s + 2η. 47 Proof. (a) Since A = supp(P Y ), we have P Y (A c ) = 0, and therefore: α := D blk (A c ) =|D blk (A c )− P Y (A c )|≤ TV(P Y ,D blk )≤ η. Next, b D(y) = D blk (y)/(1− α) for y ∈ A and b D(y) = 0 otherwise, so: TV( b D,D blk ) = 1 2 X y∈A D blk (y) 1 1− α − 1 + 1 2 X y/∈A D blk (y) = 1 2 h (1− α)· α 1− α + α i = α. We now claim that, in fact, TV(P, Q) = TV(P Y , b D). Every execution e with P(e) > 0 satisfies Y (e)∈ A, and for each such e, we may factorize as follows: P(e) = P Y (Y (e))· P(e| Y = Y (e)),Q(e) = b D(Y (e))· P(e| Y = Y (e)), i.e., the two laws share the same conditional distribution of the execution given the output, and differ only in the distribution of the output itself. Noting that both laws vanish on executions with Y (e) /∈ A, we can now grouping executions according to their output: 2 TV(P, Q) = X e |P(e)− Q(e)| = X y∈A |P Y (y)− b D(y)| X e:Y (e)=y P(e| Y = y) = X y∈A |P Y (y)− b D(y)| = 2 TV(P Y , b D), using P e:Y (e)=y P(e| Y = y) = 1 for each y ∈ A. By the triangle inequality, we now get: TV(P, Q) = TV(P Y , b D)≤ TV(P Y ,D blk ) + TV(D blk , b D)≤ η + α≤ 2η. (b) Recall that an execution is the tuple E = (V 1 ,...,V T ), where V t records all values generated in round t. Since the execution is specified by the round records (V 1 ,...,V T ), applying the chain rule gives us: H Q (V 1 ,...,V T ) = T X t=1 H Q (V t | V <t ) = T X t=1 H Q (V t |F t ), since the pre-round history F t is precisely the transcript determined by V <t . We first lower bound this entropy. Suppose the final output of the DLM after T rounds is Y , which is a deterministic function of the execution E . By the definition of the reweighted execution distribution Q, ifE ∼ Q, then Y follows distribution b D. Since the final output Y is a deterministic function of the execution, the full execution must contain at least as much randomness as Y does. Indeed, under Q, the output distribution is b D, and since entropy cannot increase under a deterministic function, we get: H Q (V 1 ,...,V T )≥ H Q (Y ) = H( b D).(52) Writing α := D blk (A c ), every atom of b D = D blk (·| A) has mass: b D(y) = D blk (y) 1− α ≤ 2 −(n−M ) 1− α . 48 Thus, we get our desired lower bound: H( b D)≥ (n− M )− log 1 1− α ≥ (n− M )− log 1 1− η ≥ (n− M )− 2η,(53) where we used α≤ η ≤ 1/2. We now upper bound the entropy. Fix a round t and a realizable history F . The scheduling rule fixes the coordinates revealed in this round. Let W t be the workspace part of V t , and let O t be the output part, supported on the coordinate set Π t (F ). If w t (F ) workspace coordinates are generated in this round, then we have: H Q (W t |F t = F )≤ w t (F ). On the other hand, by the definition of the round-t deficit (Eq. 51), we also have: H Q (O t |F t = F ) =|Π t (F )|−c t (F )− δ t (F ). By subadditivity, we have: H Q (V t |F t = F ) = H Q ((W t ,O t )|F t = F )≤ w t (F ) +|Π t (F )|−c t (F )− δ t (F ). Taking expectations and summing over the rounds, the chain rule gives us: H Q (V 1 ,...,V T ) = T X t=1 H Q (V t |F t ). For a fixed history F , the round-t record consists of the workspace update, using at most w t (F ) bits of entropy, together with the newly revealed output values O t . Hence: H Q (V t |F t = F )≤ w t (F ) + H Q (O t |F t = F ). By the definition of the round deficit, summing Eq. (51) over the rounds, we therefore have: H Q (V 1 ,...,V T )≤ E Q T X t=1 w t (F t ) + E Q T X t=1 (|Π t (F t )|−c t (F t ))− T X t=1 E Q δ t (F t ). On the other hand, by Eq. (52), we have: H Q (V 1 ,...,V T )≥ H( b D). Combining the two displays and using the lower bound on H( b D) gives us: T X t=1 E Q [δ t (F t )]≤ E Q [ T X t=1 w t (F t )] + 2η. Finally, since the workspace has at most|Σ| s = 2 s possible states, we also have E Q P T t=1 w t (F t )≤ s, and hence: T X t=1 E Q [δ t (F t )]≤ s + 2η, as claimed. 49 Overall, the lemma above gives us a global upper bound of s on the entropy deficit. The next goal is to show a similar statement for some individual block as well, which we wish to eventually use to embed our hard parity function computation. To this end, for a block b, define the quantity def b to measure how much entropy block b loses over the whole run, beyond the one bit of entropy that must be lost when the block is completed because of its parity constraint. Using the lemma above, we will show that the extra entropy loss beyond the unavoidable parity constraints is small on average across blocks; this will be used later to show the existence of a block on which the DLM performed a last-bit parity computation. Corollary 4.6. Fix b∈ [M ]. For a round t and a realized pre-round history F , let n b,t (F ) denote the number of block-b output coordinates revealed in round t, let Y b t denote their values, and define: d b,t (F ) := n b,t (F )− 1[b∈ C t (F )] | z entropy block b is entitled to this round −H Q (Y b t |F t = F ) |z entropy it delivers ≥ 0. Writing: def b := T X t=1 E Q [d b,t (F t )] for the total deficit of block b over the run, we have P M b=1 def b ≤ s + 2η. Proof. Fix a round t and a history F = F t . We first prove nonnegativity. If b /∈ C t (F ), then the newly revealed coordinates of block b in round t form an n b,t (F )-bit string. Hence: H Q (O b t |F t = F )≤ n b,t (F ), and so, d b,t (F ) ≥ 0 by definition. On the other hand, if b ∈ C t (F ), then round t completes block b. The previously revealed coordinates of block b are already fixed by the history F , and the final block must satisfy its parity constraint. Thus: H Q (O b t |F t = F )≤ n b,t (F )− 1, and therefore d b,t (F ) ≥ 1, with equality whenever the newly revealed coordinates are uniformly distributed over the corresponding affine parity coset. For fixed F , we have: X b (n b,t (F )− 1[b∈ C t (F )]) =|Π t (F )|−c t (F ). Additionally, since O t is the collection of the blockwise strings (O b t ) b , subadditivity yields: X b d b,t (F ) =|Π t (F )|−c t (F )− X b H Q (O b t |F t = F )≤|Π t (F )|−c t (F )− H Q (O t |F t = F ) = δ t (F ). Taking expectations over F =F t , summing over t, and applying Lemma 4.5 gives us: X b def b = T X t=1 E Q X b d b,t (F t )≤ T X t=1 E Q δ t (F t )≤ s + 2η. This concludes the proof. 50 4.4 Proof of the classical lower bound 4.4.1 Step 1: Setting up the basic model. In this section, our goal is to prove the following lemma: Lemma 4.7. We have: E P [#b : r b ≥ 2]≤ O(s) + O(ηM ). Proof. We first work under Q. Fix a round t and an output-and-schedule transcript τ . Let: B (2) t (τ ) :=b∈ C t (τ ) :|Π b t (τ )|≥ 2, D t (τ ) := X b∈B (2) t (τ ) (|Π b t (τ )|−1). For a transcript τ , let μ τ denote the conditional law under Q of the newly revealed coordinates in the multi-bit completed blocks, namely S b∈B (2) t (τ ) Π b t (τ ). Let ν τ denote the corresponding conditional law under P on the same coordinates. We call τ good if: TV(μ τ ,ν τ )≤ η 0 , and bad otherwise. Let Bad t be the event that the round-t transcript is not good. Under P, conditioned on τ and on a workspace state w, the round-t denoising law is a coordinate-wise product. Averaging over the possible workspace states, ν τ is therefore a mixture of at most K ≤|Σ| s product distributions. On every good transcript τ , this mixture is η 0 -close to μ τ , which is supported on a product of affine parity cosets of total dimension D t (τ ) and has entropy H(μ τ ) which can be written as: H(μ τ ) = D t (τ )− δ t , where δ t is the total entropy deficit in round t. By Theorem 4.4, we have: logK ≥ c 3 D t (τ )− δ t − C 0 . Since logK ≤ s, every good transcript therefore satisfies: D t (τ )≤ s + δ t + C 0 c 3 .(54) By Lemma 2.1 and Lemma 4.5(a), the average value of TV(μ τ ,ν τ ) over the round-t transcript τ is at most 4η. Hence Markov’s inequality gives us: Pr Q [Bad t ] = Pr Q [TV(μ τ ,ν τ ) > η 0 ]≤ 4η η 0 . The key observation is that for the final counting bound, we only need the number of multi-bit completions in round t, not their total dimension. Let N t (τ ) :=|B (2) t (τ )|. Now, on a good transcript, we have N t (τ )≤ D t (τ ), and hence, by Eq. (54): N t (τ )≤ s + δ t + C 0 c 3 . On a bad transcript, we can use the trivial bound N t (τ )≤ M . Since Pr Q [Bad t ]≤ 4η/η 0 , we obtain: E Q [N t ]≤ s + C 0 c 3 + E Q [δ t ] c 3 + 4η η 0 · M. 51 Summing over the constant number of rounds and using Lemma 4.5(b) yields: E Q T X t=1 N t ≤ T · s + C 0 c 3 + 1 c 3 T X t=1 E Q [δ τ t ] + 4Tη η 0 · M ≤ T · s + C 0 c 3 + s + 2η c 3 + 4Tη η 0 · M. Finally, observe that every block with r b ≥ 2 is counted exactly once in P t N t : in its completion round. Therefore, |b : r b ≥ 2|= P T t=1 N t , and hence: E Q [|b : r b ≥ 2|]≤ T · s + C 0 c 3 + s + 2η c 3 + 4Tη η 0 · M. Since |b : r b ≥ 2|∈ [0,M ] and TV(P, Q)≤ 2η, we obtain: E P [|b : r b ≥ 2|]≤ E Q [|b : r b ≥ 2|] + 2ηM, which proves the claim (using the fact that |Σ|= 2 as assumed in our DLM definition). 4.4.2 Step 2: Final-bit prediction yields parity computation. Selecting a block. For a block b, let E b :=x∈0, 1 B : L B i=1 x i = 0. If r b = 1, let J b be the final revealed coordinate and G b the bit generated there. Define: S b :=r b = 1 and G b = M i̸=J b X b,i . Let P b be the marginal distribution of the final output on block b. Since TV(P Y ,D blk ) ≤ η, data processing under the projection to block b yields: TV(P b ,U ⊕ B )≤ η. In particular, since U ⊕ B is supported on E b , we have Pr[X b /∈ E b ]≤ η. If r b = 1 and the final parity of block b is correct, then the unique bit generated in the completion round must equal the parity of the other B− 1 bits. Thus, there are only two ways for S b to fail: either b was not completed in the last-bit regime, or the final block has odd parity. Therefore, we get: S c b ⊆r b ≥ 2∪ B M i=1 X b,i = 1, and hence: Pr[S c b ]≤ Pr[r b ≥ 2] + η. By Lemma 4.7, we have: 1 M X b∈[M ] Pr[r b ≥ 2] = E[#b : r b ≥ 2] M ≤ O s M + O( √ η) ≤ 1 100 , say, for η bounded below by some constant depending only on T and n (recall that s = n 0.9 = o(M )). Hence, with ∆ := s + 2η, we have: 1 M X b Pr[S c b ] ≤ 1 100 + η ≤ 1 40 , 1 M X b def b ≤ ∆ M (Corollary 4.6). 52 Hence it follows that at most M/4 blocks have Pr[S c b ] > 1/10, and at most M/4 blocks have def b > 4∆/M ; hence there exists b ⋆ satisfying: Pr P [S b ⋆ ] ≥ 9 10 anddef b ⋆ ≤ 4∆ M . This b ⋆ behaves essentially like an almost-ideal last-bit block. With high probability, the DLM leaves one coordinate until the end and fills it in as a function of the parity of all the other coordinates. Furthermore, the def b ⋆ bound says that those earlier coordinates still have nearly full entropy, so this can be viewed as a parity-prediction task on nearly random bits. Replacing the pre-completion bits by uniform bits. The block b ⋆ almost always behaves like a last-bit parity block. The only remaining issue is that the first B − 1 bits of this block were generated by the DLM itself, whereas the parity lower bound is stated for uniform external inputs. To address this, we compare the original execution law P with a modified execution law B: whenever an output coordinate of block b ⋆ is revealed before the completion round of b ⋆ , its value is replaced by an independent uniform bit. All other tokens, and in particular the one during the completion round of b ⋆ , are generated exactly as in the original DLM. The bound for b ⋆ implies that this replacement does not change the execution law by much, which we formalize in the following lemma. Lemma 4.8. For the block b ⋆ chosen above, we have: Pr B [S b ⋆ ]≥ Pr P [S b ⋆ ]− 6Tη− p T · def b ⋆ . Proof. For a round t and a realizable history F , define: e t (F ) := TV(P(V t |F t = F ), B(V t |F t = F )). We compare the two executions round-by-round. As long as the two executions have the same historyF t = F (upto round t− 1), the probability of a disagreement in round t is exactly e t (F ). In- deed, if the two executions never disagree, then the event S b ⋆ has the same value in both executions. Hence: Pr B [S b ⋆ ]≥ Pr P [S b ⋆ ]− T X t=1 E P [e t (F t )].(55) For the given t and F , the two conditional round laws agree unless some output coordinate of block b ⋆ is revealed during some round t, that occurs before the completion round of b ⋆ . Therefore, if either b ⋆ ∈ C t (F ) or Π b ⋆ t (F ) =∅, then e t (F ) = 0. Otherwise, conditioned on F , it must be the case that O b ⋆ t is independent of all other tokens generated in round t. Conditioned on F t = F , observe that within each round the DLM has a product structure implies that O b ⋆ t is independent of the other tokens generated in round t. Since B changes only the marginal of O b ⋆ t , tensorization of total variation gives us: e t (F ) = TV P(O b ⋆ t |F t = F ), Unif(0, 1 Π b ⋆ t (F ) ) . Now, define: β t (F ) := TV(P(O t |F t = F ), Q(O t |F t = F )). By data processing, we get: TV P(O b ⋆ t |F t = F ), Q(O b ⋆ t |F t = F ) ≤ β t (F ). 53 Moreover, in the non-completing case b ⋆ /∈ C t (F ), the blockwise deficit is precisely: d b ⋆ ,t (F ) =|Π b ⋆ t (F )|−H Q (O b ⋆ t |F t = F ). Applying Pinsker’s inequality now gives us: TV Q(O b ⋆ t |F t = F ), Unif(0, 1 Π b ⋆ t (F ) ) ≤ q d b ⋆ ,t (F ). Therefore, for all F , we have: e t (F )≤ β t (F ) + min q d b ⋆ ,t (F ), 1 . We now take expectations in the bound on e t (F ). For the first summand on the right hand side, the conditional-TV lemma implies that E P [β t (F t )] ≤ 4η. For the second summand, since min √ x, 1∈ [0, 1] and TV(P, Q)≤ 2η, changing the measure from P to Q costs at most 2η; then, Jensen’s inequality gives: E P [e t (F t )]≤ 6η + q E Q [d b ⋆ ,t (F t )]. Summing this quantity over t, and applying Cauchy-Schwarz now gives: T X t=1 E P [e t (F t )]≤ 6Tη + T X t=1 q E Q [d b ⋆ ,t (F t )]≤ 6Tη + v u u t T T X t=1 E Q [d b ⋆ ,t (F t )] = 6Tη + p T · def b ⋆ . Finally, combining this with Eq. (55) yields: Pr B [S b ⋆ ]≥ Pr P [S b ⋆ ]− 6Tη− p T · def b ⋆ . This concludes the proof. Lemma 4.9. There is a randomized polynomial-size constant depth GC 0 [logn] circuit C such that: Pr x∼0,1 B [C(x) =|x| (mod 2)]≥ Pr B [S b ⋆ ]. Proof. The circuit that is being constructed in the lemma is obtained via the process B, using its input x = (x 1 ,...,x B ) as the uniform bits inserted into block b ⋆ before completion. All other randomness comes from the hard-wired coin flips baked into the circuit, and all scheduling and denoising steps are implemented by the given DLM circuits. If b ⋆ is completed by a single final coordinate J , and the generated final bit is G, the circuit outputs G⊕ x J ; otherwise it outputs an arbitrary bit. On the event S b ⋆ , we have: G = M i̸=J x i , and hence, G⊕x J = L B i=1 x i . Therefore, C computes parity with probability at least Pr B [S b ⋆ ]. Now, by the DLM definition, observe that the circuit that computes G is via a constant-depth GC 0 [logn] circuit. Since n = B 100 , its size is polynomial in B, and its gate arity is O(logn) = O(logB). 54 Putting everything together. By Lemma 4.8 and our choice of b ⋆ , we have: Pr B [S b ⋆ ]≥ Pr P [S b ⋆ ]− 6Tη− p T · def b ⋆ ≥ 9 10 − 6Tη− r T · 4∆ M . Now, recall our parameters, wherein we chose ∆ = O(s) = O(n 0.9 ) and M = n 0.99 . Therefore, q T · 4∆ M = o(1) for constant T . Taking η ≤ ε ⋆ (T ) to be sufficiently small, the right-hand side becomes at least 4/5 for all sufficiently large n. Then, Lemma 4.9 gives us a randomized polynomial- size depth-O d,T (1) GC 0 [logB] circuit that computes B-bit parity with success probability at least 4/5. Fixing the internal coins gives a deterministic circuit with the same success probability, contradicting Theorem 4.3. This proves the lower bound in the basic model. 4.4.3 Step 3. Allowing revision and remasking We now explain how the our argument extends to DLMs that allow a (bounded) number of re- masking or revision operations. Suppose the DLM allows for at most R = n 0.9 output-token remasking/revision events during the entire execution, and suppose each such operation acts on a single output coordinate. We say a block b∈ [M ] is touched if some output coordinate in block b is ever remasked or revised over the course of the computation. Let Touch b denote this event. Since each remasking/revision event touches only one output coordinate, we have the pathwise bound: M X b=1 1[Touch b ]≤ R. Thus, the fraction of touched blocks is at most R, which by assumption satisfies R/M = o(1). We will simply discard all touched blocks (since there are not too many of them). We remark that it is important to discard these blocks, because revision/remasking events destroy the monotonicity property that is used crucially in the proof for the basic model above: if any coordinate is later revised or remasked, then the value written at the first completion time need not be its final value (note that in our structural result, we used the fact that once a token is unmasked it is never masked or revised again). For untouched blocks, however, monotonicity is completely preserved. Once an output coor- dinate in an untouched block is written, it is never subsequently changed or remasked. Hence, when such a block is first completed, the coordinates unmasked in that round are final output coordinates, and so the same residual affine parity constraint as in the basic model applies. Let: N unt t := #b :¬Touch b , b is completed in round t with r b ≥ 2. For every realization of the DLM execution, after deleting all touched blocks, the remaining com- pleted blocks evolve exactly as in the monotone model (i.e., the model where there is no remask- ing/revision). Applying Lemma 4.7 to this induced monotone execution therefore gives E Q [N unt t ]≤ O(s) + O(ηM ), where we used that the total number of DLM rounds is a constant. Indeed, Lemma 4.7 applies to the induced monotone execution on the untouched blocks, so on good transcripts the same product- mixture argument bounds the corresponding dimension, while on bad transcripts we again use the 55 trivial bound N unt t ≤ M . 26 Summing over the constant number of rounds, we get: E Q [#b :¬Touch b , r b ≥ 2]≤ O(s) + O(ηM ). Adding back touched blocks costs at most R pathwise, and therefore: E Q [#b : r b ≥ 2]≤ O(s) + O(ηM ) + R. Next, define the last-bit success event with the extra requirement that the block is untouched: S rev b := ¬Touch b , r b = 1, G b = M i̸=J b X b,i . If S rev b fails, then either block b was touched, or it was completed by at least two coordinates, or its final parity is incorrect. Thus: (S rev b ) c ⊆ Touch b ∪r b ≥ 2∪ ( B M i=1 X b,i = 1 ) . Averaging over b gives us: 1 M M X b=1 Pr[(S rev b ) c ]≤ R M + E [#b : r b ≥ 2] M + η = o(1) nearly uniform pre-completion bits. Namely, Corollary 4.6 gives us: 1 M M X b=1 def b ≤ s + 2η M . Combining this with the preceding bound and applying Markov’s inequality, it follows that there exists a block b ⋆ such that: Pr[S rev b ⋆ ]≥ 9 10 anddef b ⋆ ≤ 4(s + 2η) M . In the event S rev b ⋆ , the block b ⋆ is never remasked or revised, and it is completed in the last-bit regime. Therefore the replacement-by-uniform-bits argument applies to this block exactly as in the basic model. The modified simulation now simulates the full DLM, including any revision/remasking op- erations on other blocks, while using external uniform input bits for the pre-completion coordinates of block b ⋆ . If the DLM ever touches block b ⋆ , the simulation may fail, but this is already accounted for in the complement of S rev b ⋆ . Thus, the same parity-prediction reduction goes through with an ad- ditional additive loss of at most R/M = o(1), which vanishes. Consequently, our tolerated amount of remasking/revision does not affect the constant-distance lower bound. 27 26 We remark that the property that a block is untouched is determined only after the full execution of the DLM, so one should not interpret the argument as saying that conditioned on a future event, the DLM execution induces a product distribution. Rather, the proof is more naturally viewed as deleting the touched blocks after the execution and applying the same counting argument to the induced monotone execution on the remaining blocks. Making this viewpoint completely formal requires only routine bookkeeping, without affecting any of the quantitative bounds; overall producing the same bounds as we show below as long as s,R = o(n). 27 We emphasize that [CPW25] accounts for revision/remasking as the number of rounds where these revisions occur; we offer a significantly more fine-grained measure, wherein each token which undergoes revision/remasking is included in the complexity. 56 References [ADOY25]Anurag Anshu, Yangjing Dong, Fengning Ou, and Penghui Yao. On the computa- tional power of QAC 0 with barely superlinear ancillae. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1476–1487. Association for Computing Machinery, 2025. 5 [BEG26]Jinge Bao and Francisco Escudero-Guti ́errez. Learning junta distributions, quantum junta states, and QAC 0 circuits. In Proceedings of the 43rd International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 2026. To appear. 5 [BGK18]Sergey Bravyi, David Gosset, and Robert K ̈onig. Quantum advantage with shallow circuits. Science, 362(6412):308–311, 2018. 2, 4, 7, 8 [BGKT20]Sergey Bravyi, David Gosset, Robert K ̈onig, and Marco Tomamichel. Quantum advantage with noisy shallow circuits. Nature Physics, 16(10):1040–1045, 2020. 2 [BWKST19] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 515–526. Association for Computing Machinery, 2019. 2, 4, 7, 8, 40 [BWP26]Adam Bene Watts and Natalie Parham. Unconditional quantum advantage for sam- pling with shallow circuits. In Shubhangi Saraf, editor, 17th Innovations in Theoret- ical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:12. Schloss Dagstuhl – Leibniz- Zentrum f ̈ur Informatik, 2026. 2, 7 [C22]David Chiang and Peter Cholak. Overcoming a theoretical limitation of self-attention. In Proceedings of the 60th Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pages 7654–7664. Association for Computational Linguistics, May 2022. 4 [CCP23]David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 5544–5562. PMLR, 2023. 4 [CPW25]Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical limitations of multi-layer transformer. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2631–2653. IEEE, 2025. 3, 4, 5, 6, 12, 15, 17, 18, 26, 27, 35, 36, 37, 56 [CSV21]Matthew Coudron, Jalex Stark, and Thomas Vidick. Trading locality for time: Certi- fiable randomness from low-depth circuits. Communications in Mathematical Physics, 382(1):49–86, 2021. 2 [CT91]Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, New York, 1991. Chapter 2, “Entropy, Relative Entropy and Mutual Information,” p. 12–49. 12 [ENO + 21]Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, 57 Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. A mathematical framework for transformer circuits. Transformer Circuits Thread, December 2021. 3 [FGPT25]Stephen A. Fenner, Daniel Grier, Daniel Pad ́e, and Thomas Thierauf. Tight bounds on depth-2 QAC-circuits computing parity, 2025. 5 [G + 24]Gemini Team et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context, 2024. 3 [GGJ26a]Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi. Parity /∈ QAC 0 iff QAC 0 is Fourier-concentrated. In 2026 IEEE 67th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2026. 5 [GGJ26b]Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi. Super-constant weight Dicke states in constant depth without fanout, 2026. 5 [GHMP02]Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. Counting, fanout, and the complexity of quantum ACC. Quantum Information & Computation, 2(1):35–65, 2002. 5 [GK24]Sabee Grewal and Vinayak M. Kumar. Improved circuit lower bounds and quantum- classical separations, 2024. ECCC: TR24-130. 2, 4, 8, 10, 13 [GKM + 26]Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu. Quantum advantage from sampling shallow circuits: Beyond hardness of marginals. In Shubhangi Saraf, editor, 17th Innovations in Theoretical Computer Science Con- ference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 73:1–73:14. Schloss Dagstuhl – Leibniz-Zentrum f ̈ur Informatik, 2026. 2 [GMW26]Daniel Grier, Jackson Morris, and Kewen Wu. QAC 0 contains TC 0 (with many copies of the input). In 2026 IEEE 67th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2026. To appear. 4, 5, 11, 25 [GS20]Daniel Grier and Luke Schaeffer. Interactive shallow Clifford circuits: Quantum ad- vantage against NC 1 and beyond. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 875–888. Association for Computing Ma- chinery, 2020. 2 [H ̊as14]Johan H ̊astad. On the correlation of parity and small-depth circuits. SIAM Journal on Computing, 43(5):1699–1708, 2014. 8, 42 [HJA20]Jonathan Ho, Ajay N. Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, volume 33, pages 6840–6851. Curran Associates, Inc., 2020. 2 [JHC26]Haozhe Jiang, Nika Haghtalab, and Lijie Chen. Diffusion language models are prov- ably optimal parallel samplers. In The Fourteenth International Conference on Learn- ing Representations, 2026. 3, 7, 18, 21 [JTVW26]Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright. Improved lower bounds for QAC 0 . In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 2199–2209. Association for Computing Machinery, 2026. 5 58 [Kum23]Vinayak M. Kumar. Tight correlation bounds for circuits between AC 0 and TC 0 . In Amnon Ta-Shma, editor, 38th Computational Complexity Conference (C 2023), volume 264 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1– 18:40. Schloss Dagstuhl – Leibniz-Zentrum f ̈ur Informatik, 2023. 8, 10, 13, 41, 42 [LG19]Fran ̧cois Le Gall. Average-case quantum advantage with shallow circuits. In Amir Shpilka, editor, 34th Computational Complexity Conference (C 2019), volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:20. Schloss Dagstuhl – Leibniz-Zentrum f ̈ur Informatik, 2019. 2 [LLZM24]Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empow- ers transformers to solve inherently serial problems. In The Twelfth International Conference on Learning Representations, 2024. 4, 17 [LSH + 25]David Layden, Ryan Sweke, Vojtˇech Havl ́ıˇcek, Anirban Chowdhury, and Kirill Nek- lyudov. Wavefunction flows: Efficient quantum simulation of continuous flow models, 2025. 11 [Met24]Meta AI. Introducing Meta Llama 3: The most capable openly available LLM to date. Meta AI Blog, April 2024. 3 [NPVY24]Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. On the Pauli spectrum of QAC 0 . In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1498–1506. Association for Computing Machinery, 2024. 5 [NZY + 25]Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, Jun Zhou, Yankai Lin, Ji-Rong Wen, and Chongxuan Li. Large language diffusion models. In Advances in Neural Information Processing Systems, volume 38, pages 50608–50646. Curran Associates, Inc., 2025. 18, 21 [PNP24]Binghui Peng, Srini Narayanan, and Christos Papadimitriou. On limitations of the transformer architecture. In First Conference on Language Modeling, 2024. 5 [Ros21]Gregory Rosenthal. Bounds on the QAC 0 complexity of approximating parity. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Confer- ence (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:20. Schloss Dagstuhl – Leibniz-Zentrum f ̈ur Informatik, 2021. 5 [RWC + 19]Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. Technical report, OpenAI, 2019. 3 [SDWMG15] Jascha Sohl-Dickstein, Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 2256–2265. PMLR, 2015. 2 [SHT23]Clayton Sanford, Daniel J. Hsu, and Matus J. Telgarsky. Representational strengths and limitations of transformers. In Advances in Neural Information Processing Sys- tems, volume 36, pages 36677–36707. Curran Associates, Inc., 2023. 4, 5, 15 [SZL + 25]Yuxuan Song, Zheng Zhang, Cheng Luo, Pengyang Gao, Fan Xia, Hao Luo, Zheng Li, Yuehang Yang, Hongli Yu, Xingwei Qu, Yuwei Fu, Jing Su, Ge Zhang, Wenhao 59 Huang, Mingxuan Wang, Lin Yan, Xiaoying Jia, Jingjing Liu, Wei-Ying Ma, Ya-Qin Zhang, Yonghui Wu, and Hao Zhou. Seed diffusion: A large-scale diffusion language model with high-speed inference, 2025. 18, 21 [VH25]Francisca Vasconcelos and Hsin-Yuan Huang. Learning shallow quantum circuits with many-qubit gates. In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 5553–5604. PMLR, 2025. 5 [VSP + 17]Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30, pages 5998–6008. Curran As- sociates, Inc., 2017. 2 [WWS + 22]Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reason- ing in large language models. In Advances in Neural Information Processing Systems, volume 35, pages 24824–24837. Curran Associates, Inc., 2022. 11 [YCA24]Andy Yang, David Chiang, and Dana Angluin. Masked hard-attention transform- ers recognize exactly the star-free languages. In Advances in Neural Information Processing Systems, volume 37, pages 10202–10235. Curran Associates, Inc., 2024. 4 60