# Online Learning of Quantum States Under Adaptive Adversaries

Date: 2026-09-17. Thread deliverable for Argus. Scope: adversarial/adaptive online quantum-state learning, currencies paid (samples, mistakes, memory, time), tree-size lower bounds, and succinct-description hardness.

## VERDICT

- **[Established]** Yes: Aaronson-Chen-Hazan-Kale-Nayak prove that an agent can answer an adversarially and adaptively chosen sequence of two-outcome measurements while staying consistent with a fixed unknown `n`-qubit state, with `O(n/epsilon^2)` mistakes and `O(L sqrt(T n))` regret; source: arXiv:1802.09025, Theorems 1 and 2, https://arxiv.org/abs/1802.09025.
- **[Established]** The adversary is explicitly adaptive: the paper says the sequence can be "chosen adversarially, and even adaptively" and that `x_t` may depend on previous learner behavior; later it states, "The sequence of measurements E_t can be arbitrary, even adversarial, based on the learner's previous actions." Source: arXiv:1802.09025, introduction and preliminaries.
- **[Established]** The currency in the central theorem is not a succinct classical description: the algorithms maintain hypothesis density matrices `omega_t in C_n`, where `C_n` is the set of `2^n x 2^n` PSD trace-1 matrices; source quote below from arXiv:1802.09025.
- **[Established]** Computationally, the central algorithms are classical but exponential in `n`: the paper states, "Finally, the algorithms have run time exponential in the number of qubits in each iteration, but are entirely classical," and explains that measurements and outputs are `2^n x 2^n` matrices.
- **[Derived]** Memory for the explicit hypothesis is exponential: a dense `2^n x 2^n` density matrix has `4^n` complex entries up to Hermitian/trace constraints, i.e. `Theta(4^n)` real-scale storage for a generic mixed-state hypothesis; provenance: derived from the paper's explicit definition of `C_n`.
- **[Established]** Follow-ups improve regret under additional structure (low-rank/sparse/Frobenius-bounded measurements, small-loss cases, changing states, special squared-loss multi-outcome settings), but I did not find a general unrestricted adversarial online learner with a poly(n)-size classical hypothesis answering arbitrary measurement queries.
- **[Inference]** The honest space-vs-time summary for arbitrary states/measurements is: either store an explicit state/density matrix, paying exponential space and then polynomial-in-dimension linear algebra per query; or store a succinct generator/circuit, paying polynomial space but generally #P/GapP-hard exact query evaluation. This dichotomy is right as a worst-case classical-renderer statement, but incomplete for structured states, restricted observables, quantum hardware, and approximate/statistical query models.

## 1. Central Paper: Online Learning of Quantum States

Source: Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, Ashwin Nayak, "Online Learning of Quantum States," arXiv:1802.09025v3, NeurIPS 2018, J. Stat. Mech. (2019) 124019, DOI 10.1088/1742-5468/ab3988, https://arxiv.org/abs/1802.09025.

### 1.1 The Mistake Bound

- **[Established, inherited-checked]** The paper's abstract states the headline mistake bound as `O(n/epsilon^2)`: "We show that it is possible to do this in a way that guarantees that |Tr(E_i sigma_t) - Tr(E_i rho)|, the error in our prediction for the next measurement, is at least epsilon at most O(n / epsilon^2) times."
- **[Established, verbatim]** Theorem 1 in the arXiv source states:

> "Let `rho` be an `n`-qubit mixed state, and let `E_1,E_2,...` be a sequence of `2`-outcome measurements that are revealed to the learner one by one, each followed by a value `b_t in [0,1]` such that `| Tr(E_t rho) - b_t | <= epsilon / 3`. Then there is an explicit strategy for outputting hypothesis states `omega_1,omega_2,...` such that `| Tr(E_t omega_t) - Tr(E_t rho) | > epsilon` for at most `O( n / epsilon^2 )` values of `t`."

- **[Established]** The proof converts `L_1` regret into mistakes: if the algorithm updates only when `|Tr(E_t omega_t)-b_t| > 2 epsilon/3`, then `T` updates imply `(2 epsilon/3)T <= (epsilon/3)T + O(sqrt(T n))`, hence `T = O(n/epsilon^2)`.
- **[Derived]** For constant `epsilon`, the mistake count is linear in `n`; for fixed `n`, it scales quadratically in `1/epsilon`.

### 1.2 The Regret Bound

- **[Established, verbatim]** Theorem 2 states:

> "Let `E_1,E_2,...` be a sequence of two-outcome measurements on an `n`-qubit state presented to the learner, and `ell_1, ell_2, ...` be the corresponding loss functions revealed in successive iterations in the regret minimization model. Suppose `ell_t` is convex and `L`-Lipschitz; in particular, for every `x in R`, there is a sub-derivative `ell_t'(x)` such that `| ell_t'(x) | <= L`. Then there is an explicit learning strategy that guarantees regret `R_T = O( L sqrt(Tn) )` for all `T`. This is so even assuming the measurement `E_t` and loss function `ell_t` are chosen adaptively, in response to the learner's previous behavior.

> Specifically, the algorithm applies to `L_1` loss and `L_2` loss, and achieves regret `O( sqrt(Tn) )` for both."

- **[Established, measured/source]** The RFTL theorem in the same source gives the constant-form bound: Theorem 3 says, "Setting `eta = sqrt((log 2)n/(2TL^2))`, the regret of Algorithm 1 is bounded by `2L sqrt((2 log 2) T n)`."
- **[Established, measured/source]** The Matrix Multiplicative Weights theorem gives the tighter constant-form bound: Theorem 4 says, "Setting `eta = sqrt((log 2)n/(4T))`, the regret of the algorithm based on the update rule ... is bounded by `2L sqrt((log 2)Tn)`."

### 1.3 Is the Sequence Chosen by an Adaptive Adversary?

- **[Established, verbatim]** The introduction says: "Crucially, there is no assumption whatsoever about the `x_t`'s: the sequence could be chosen adversarially, and even adaptively, which means that the choice of `x_t` might depend on the learner's behavior on `x_1,...,x_{t-1}`."
- **[Established, verbatim]** The formal preliminaries say: "The sequence of measurements `E_t` can be arbitrary, even adversarial, based on the learner's previous actions."
- **[Established, verbatim]** The regret theorem itself says the guarantee holds "even assuming the measurement `E_t` and loss function `ell_t` are chosen adaptively, in response to the learner's previous behavior."
- **[Established]** Therefore the answer to Travis's central adversary question is yes: the measurement/loss sequence may be chosen adaptively after seeing previous learner behavior.

### 1.4 What Object Does the Algorithm Maintain?

- **[Established, verbatim]** The paper defines the state domain as: "An `n`-qubit quantum state `rho` is an element of `C_n`, where `C_n` is the set of all trace-1 positive semi-definite (PSD) complex matrices of dimension `2^n`: `C_n = { M in C^{2^n x 2^n} , M = M^dagger, M >= 0, Tr(M)=1 }`."
- **[Established, verbatim]** Algorithm 1 sets `K := C_n`, initializes `omega_1 := 2^{-n} I`, predicts `omega_t`, and updates `omega_{t+1}` by optimizing over `varphi in K`.
- **[Established, verbatim]** The paper explicitly says: "For the algorithms we present in this article, we assume that a two-outcome measurement is specified via a classical description of its defining matrix `E`."
- **[Established, verbatim]** The computational-cost paragraph says: "Finally, the algorithms have run time exponential in the number of qubits in each iteration, but are entirely classical. Exponential run time is unavoidable, as the measurements are presented explicitly as `2^n x 2^n` matrices, where `n` is the number of qubits. If we were required to output the hypothesis states, the length of the output--also exponential in the number of qubits--would again entail exponential run time."
- **[Derived]** The hypothesis object is a full `2^n x 2^n` density matrix or equivalent matrix-valued iterate; generic storage is `Theta(4^n)` scalar parameters, not `poly(n)`.

### 1.5 Samples, Mistakes, Memory, Time

- **[Established]** Measurement samples: the theorem assumes that after each measurement `E_t` the learner receives a value `b_t` with `|Tr(E_t rho)-b_t| <= epsilon/3`; empirically obtaining each such `b_t` from copies of `rho` costs repeated measurements, not priced in the theorem as a separate sample-complexity bound.
- **[Established]** Mistakes: `O(n/epsilon^2)` in the realizable approximate-feedback setting.
- **[Established]** Regret: `O(L sqrt(T n))` for convex `L`-Lipschitz losses; `O(sqrt(T n))` for `L_1` and `L_2`.
- **[Established]** Time: exponential in `n` per iteration, polynomial in matrix dimension `D=2^n`; RFTL solves a convex program over density matrices and MMW computes matrix exponentials/normalization over `D x D` matrices.
- **[Derived]** Memory: exponential in `n`; at least enough to represent the current hypothesis matrix and accumulated gradient/loss matrix, i.e. `Omega(D^2)=Omega(4^n)` entries for dense generic states.

## 2. Follow-Ups and Improvements

### 2.1 Chen and Wang: Low-Rank Measurements and Small-Loss Bounds

Source: Yifang Chen and Xin Wang, "More Practical and Adaptive Algorithms for Online Quantum State Learning," arXiv:2006.01013, https://arxiv.org/abs/2006.01013.

- **[Established, verbatim]** The abstract says RFTL with Tsallis-2 entropy achieves "`O(sqrt(MT))` total loss with perfect hindsight on the first `T` measurements with maximum rank `M`. This regret bound depends only on the maximum rank `M` of measurements rather than the number of qubits."
- **[Established, verbatim]** The paper says it also gets a small-loss bound: "When the loss is `L_2`-norm, we provide a parameter-free learning rate adjusting strategy ... to achieve a so-called 'small loss' bound `O~(sqrt(n L*) + n)`, where `L*` is the loss of the best quantum state in hindsight."
- **[Established, verbatim]** It says, "When `L_T^* = 0`, which is the realizable case, the regret becomes `O(n log T)`."
- **[Established]** This improves currencies under extra assumptions, but does not replace the general full-density-matrix hypothesis with a general classical `poly(n)` data structure.
- **[Established]** The paper explicitly keeps density matrices as the state model: "The pure states and mixed states can be unitedly described by a mathematical tool called density matrix... The set of `d`-dimensional quantum states is denoted by `S_d`."
- **[Established]** It adds a near-term quantum implementation angle: "our RFTL with Tallis-2 entropy algorithm can be implemented efficiently on near-term quantum computing devices," which is a different currency than succinct classical storage.

### 2.2 Adaptive Online Learning of Changing States

Source: Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang, Rui Yang, "Adaptive Online Learning of Quantum States," arXiv:2206.00220v2, Quantum 8, 1471 (2024), https://arxiv.org/abs/2206.00220.

- **[Established, verbatim]** The abstract says they consider mutable states and present "adaptive and dynamic regret bounds for online shadow tomography, which are polynomial in the number of qubits and sublinear in the number of measurements."
- **[Established, verbatim]** The dynamic-regret theorem says: if the comparator path length `P` is at least 1 and losses are convex, `L`-Lipschitz, and map to `[0,1]`, "the dynamic regret ... is bounded by `O(L sqrt(T(n+log(T)) P))`."
- **[Established, verbatim]** The adaptive-regret theorem says the algorithm guarantees strongly adaptive regret `O(L sqrt(n tau log(T)))` for all `T`.
- **[Established, verbatim]** For `k` shifts, the mistake bound is `O((kn/epsilon^2) log(kn/epsilon^2))`.
- **[Established]** This addresses changing target states, not a general succinct classical hypothesis for arbitrary adaptive measurement queries.

### 2.3 Bansal and Liu: Structured Measurements and Logarithmic Regret

Source: Akshay Bansal and Jiahui Liu, "Improved regret bounds for structured online learning of quantum states," arXiv:2608.05740v1, https://arxiv.org/abs/2608.05740.

- **[Established, verbatim]** The abstract says: "under the assumption that the adversarial measurements have bounded Frobenius norm, we analyze Projected Online Gradient Descent and derive regret bounds that depend on intrinsic structural properties, such as rank or sparsity, rather than the ambient Hilbert space dimension."
- **[Established, verbatim]** Their informal OGD theorem states: if `||E_t||_F <= B`, then `R_T <= O(LB sqrt(T))`.
- **[Established, verbatim]** Their formal theorem states: if losses are convex and `L`-Lipschitz and `||E_t||_F <= B`, then `R_T <= D L B sqrt(T)`, where `D` is the Frobenius diameter of the density-matrix domain.
- **[Established, verbatim]** The low-rank corollary gives `R_T <= O(L sqrt(min{r,n} T))`; the sparse corollary gives `R_T <= O(L sqrt(min{kappa,n} T))`.
- **[Established, verbatim]** Their logarithmic-regret result is special: "Under the squared `L_2` loss in the `K`-outcome measurement setting, the averaging (Follow-the-Leader) algorithm achieves regret `R_T = O(log(T))`. In particular, the regret grows only logarithmically with the time horizon and is independent of the number of qubits and the number of measurement outcomes."
- **[Established, verbatim]** Their online interaction says the learner reveals a quantum state by "providing its full classical description," and the adversary responds with a measurement and loss.
- **[Established]** This is an improvement in regret under structural/loss assumptions, not an unrestricted poly-size state representation.

### 2.4 Efficiently Generatable Pure States

Source: Taiga Hiroka and Min-Hsiu Hsieh, "Computational Complexity of Learning Efficiently Generatable Pure States," arXiv:2410.04373, https://arxiv.org/abs/2410.04373.

- **[Established, verbatim]** The abstract says prior work shows polynomial copies suffice for efficiently generatable states, but "their algorithms are inefficient, and the computational complexity of this learning problem remains unresolved."
- **[Established, verbatim]** Their positive result is oracle-heavy: "if unknown quantum states are promised to be pure states and efficiently generateable, then there exists a quantum polynomial time algorithm `A` and a language `L in PP` such that `A^L` can learn its classical description."
- **[Established]** This is relevant to succinct generators but not a plain poly-time classical data structure for arbitrary adaptive measurement answering.

### 2.5 Not Found: General Succinct Classical Hypothesis

- **[Established]** I searched arXiv/API/web for `online learning of quantum states`, `logarithmic regret`, `succinct representation quantum state measurement queries`, `efficiently generatable pure states`, `Hsieh`, `Chen Wang`, and the cited online-learning follow-up chain.
- **[Established]** Found improvements: arXiv:2006.01013, arXiv:2206.00220, arXiv:2608.05740, arXiv:2410.04373, arXiv:2311.04237, arXiv:2202.02765.
- **[Established]** Not found: a theorem giving the same unrestricted adaptive adversarial guarantees as Aaronson-Chen-Hazan-Kale-Nayak while maintaining a `poly(n)`-size classical hypothesis that can answer arbitrary two-outcome measurement queries in `poly(n)` time.
- **[Inference]** This absence is expected: a general hypothesis that answers arbitrary two-outcome measurements to small error is essentially a full predictive representation of a `D=2^n` dimensional density matrix.

## 3. Aaronson 2004: Multilinear Formulas and Tree Size

Source: Scott Aaronson, "Multilinear Formulas and Skepticism of Quantum Computing," quant-ph/0311039, STOC 2004 / SIAM J. Comput. 34(4), 2005, https://arxiv.org/abs/quant-ph/0311039.

### 3.1 What Tree Size Measures

- **[Established, verbatim]** The abstract says the paper investigates "the set of states expressible by a polynomial number of additions and tensor products."
- **[Established, verbatim]** Definition: "A quantum state tree over `H_2^{otimes n}` is a rooted tree where each leaf vertex is labeled with `alpha|0> + beta|1>` ... and each non-leaf vertex ... is labeled with either `+` or `otimes`."
- **[Established, verbatim]** Size definition: "For reasons of convenience, we define the size `|T|` of a tree `T` to be the number of leaf vertices. Then given a state `|psi> in H_2^{otimes n}`, the tree size `TS(|psi>)` is the minimum size of a tree that represents `|psi>`."
- **[Established, verbatim]** Approximate tree size: `TS_epsilon(|psi>)` is the minimum tree size of a state `|varphi>` with `|<psi|varphi>|^2 >= 1-epsilon`.

### 3.2 Unconditional Lower Bounds

- **[Established, verbatim]** The abstract says: "Using a recent lower bound on multilinear formula size due to Raz, we then show that states arising in quantum error-correction require `n^{Omega(log n)}` additions and tensor products even to approximate."
- **[Established, verbatim]** Theorem 12 (`ecclb`) states: "If `S` is drawn from `E`, then `MFS(f_S) = n^{Omega(log n)}` (and hence `TS(|S>) = n^{Omega(log n)}`), with probability `Omega(1)` over `S`."
- **[Established, verbatim]** Theorem 15 (`ecclbapprox`) states: "For all constants `epsilon in [0,1)`, if `S` is drawn from `E`, then `MFS_epsilon(fhat_S) = n^{Omega(log n)}` with probability `Omega(1)` over `S`."
- **[Established, verbatim]** The corollary after Theorem 15 says `TS_epsilon(|S>) = n^{Omega(log n)}` with probability `Omega(1)` over `S`, for all `epsilon < 1`.
- **[Established, verbatim]** The explicit derandomized construction: after Reed-Solomon/Hadamard coding, Theorem 17 states `MFS(f) = n^{Omega(log n)}`, and the text says a corollary is `TS(|S>) = n^{Omega(log n)}` and also `TS_epsilon(|S>) = n^{Omega(log n)}` for all `epsilon < 1`.
- **[Established]** These are unconditional superpolynomial lower bounds for tree/multilinear-formula descriptions of some stabilizer/codeword/subgroup states.
- **[Established]** They are not exponential lower bounds for ordinary tree size; Aaronson explicitly says Raz's technique "is only able to show lower bounds of the form `n^{Omega(log n)}`" and conjectures `2^{Omega(n)}`.

### 3.3 Which States Need Superpolynomial Descriptions?

- **[Established]** Random subgroup states over `Z_2^n` drawn from the paper's distribution require `n^{Omega(log n)}` tree size with constant probability.
- **[Established]** Explicit subgroup/codeword states built from concatenated Reed-Solomon and Hadamard codes require `n^{Omega(log n)}` tree size.
- **[Established]** The paper ties subgroup states to stabilizer codes: "Coset states arise as codewords in the class of quantum error-correcting codes known as stabilizer codes."
- **[Established]** The Shor-state lower bound is conditional, not unconditional: Theorem 20 says Conjecture 19 implies `MFS(f_{n,p}) = n^{Omega(log n)}` and hence `TS(|pZ>) = n^{Omega(log n)}`.
- **[Established, verbatim]** The paper says, "Unfortunately, we are only able to answer this question assuming a number-theoretic conjecture," for Shor states.

### 3.4 Relevance to Space

- **[Established]** Tree size is a classical description-size measure built from additions and tensor products; it is weaker/different than full amplitude-table storage.
- **[Established]** The lower bound is unconditional for some natural QEC/stabilizer-code states, but only `n^{Omega(log n)}`, not `2^n`.
- **[Inference]** This supports the claim that some physically meaningful `n`-qubit states evade a broad polynomial-size classical expression language, but it does not by itself prove that every classical data structure answering arbitrary measurements needs exponential bits.

## 4. Data Structures, Succinct Circuits, and Query Hardness

### 4.1 Full Arbitrary Query Answering Implies Exponential Information in the Worst Case

- **[Established]** Full tomography of arbitrary `n`-qubit states requires exponential resources; Aaronson et al. state that reconstructing the full `2^n x 2^n` density matrix to trace distance `epsilon` requires exponentially many measurements, citing O'Donnell-Wright and Haah-Harrow-Ji-Wu-Yu.
- **[Established]** Haah-Harrow-Ji-Wu-Yu, "Sample-optimal tomography of quantum states," arXiv:1508.01797, proves sample-optimal tomography lower bounds for full state reconstruction; O'Donnell-Wright, arXiv:1508.01907 / STOC 2016, gives tomography lower bounds.
- **[Inference]** A classical data structure that answers all two-outcome measurements to sufficiently small additive error would determine the density matrix operationally, because effects separate quantum states; hence a generic exact/all-query representation cannot have only `poly(n)` bits for all states.
- **[Inference]** A metric-entropy version gives the same conclusion: the set of `D x D` density matrices has real dimension `D^2-1` with `D=2^n`, so a uniform epsilon-net/full predictive encoding needs exponential-in-`n` bits for constant precision.
- **[Not found]** I did not find, in this pass, a named theorem phrased exactly as "any classical data structure of size `S` answering arbitrary adaptive quantum measurement queries must have `S=2^{Omega(n)}`"; the closest established results are tomography/sample lower bounds and standard dimension/epsilon-net arguments.

### 4.2 Succinct Circuit Description: Polynomial Space, Hard Query Evaluation

- **[Established]** A quantum circuit of polynomial size is a polynomial-size classical description of the state it prepares.
- **[Established]** Aaronson 2004 notes that the subgroup states with large tree size can nevertheless be prepared by small quantum circuits: "Aaronson and Gottesman show how to prepare any `n`-qubit subgroup state using a quantum circuit of size `O(n^2/log n)`."
- **[Established]** Fortnow and Rogers, "Complexity limitations on quantum computation," cs/9811023, prove a GapP representation for quantum acceptance probability: Lemma 3.1 says, "For any quantum Turing machine `M` running in time bounded by a polynomial `t(n)`, there is a `GapP` function `f` such that for all inputs `x`, `Pr(M(x) accepts)=f(x)/5^{2t(|x|)}`." Source: https://arxiv.org/abs/cs/9811023.
- **[Established]** Fenner, Green, Homer, and Pruim, "Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy," quant-ph/9812056, show nonzero quantum acceptance/amplitude questions are PH-hard: abstract quote, "determining whether a quantum computation has a non-zero probability of accepting is at least as hard as the polynomial time hierarchy," and the result also applies to whether "a given quantum basis state appears with nonzero amplitude in a superposition." Source: https://arxiv.org/abs/quant-ph/9812056.
- **[Derived]** Exact output-probability evaluation from a circuit is #P-hard: a quantum circuit can reversibly simulate a classical nondeterministic computation with uniform branching, so an exact output-probability oracle gives `#accept/2^m`, and multiplying by `2^m` recovers the #P count.
- **[Inference]** Therefore a poly-size circuit is a compact generative description, but it does not give a poly-time classical query oracle for arbitrary measurement probabilities unless standard counting-hardness barriers collapse.

## 5. Currency Table

| Setting | Space | Time per query/update | Guarantee | Evidence |
|---|---:|---:|---|---|
| Full density matrix | `Theta(4^n)` entries | polynomial in `D=2^n` matrix dimension; exponential in `n` | answers arbitrary explicit two-outcome measurements by `Tr(E rho)` | Established/derived from arXiv:1802.09025 definitions |
| Aaronson et al. online learner | exponential hypothesis/output length | exponential in `n` per iteration | `O(n/epsilon^2)` mistakes; `O(L sqrt(Tn))` regret against adaptive adversary | Established, Theorems 1-4 |
| Low-rank/structured online improvements | still density-matrix/domain based; sometimes quantum-device implementation | improved regret when `rank`, sparsity, Frobenius norm, or loss structure is favorable | `O(sqrt(MT))`, `O~(sqrt(nL*)+n)`, `O(LB sqrt(T))`, `O(log T)` in special settings | Established, arXiv:2006.01013, 2206.00220, 2608.05740 |
| Polynomial-size quantum circuit | `poly(n)` description | exact classical query evaluation generally #P/GapP-hard; quantum execution samples natively | succinct generation, not free classical prediction | Established/derived, Fortnow-Rogers; Fenner-Green-Homer-Pruim |
| Tree/multilinear formulas | formula size | evaluation depends on formula size | some QEC/subgroup states require `n^{Omega(log n)}` even approximately | Established, Aaronson quant-ph/0311039 |

## 6. What I Could Not Find

- **[Not found]** A general unrestricted adversarial online-learning algorithm for arbitrary `n`-qubit states and arbitrary adaptively chosen two-outcome measurements that maintains a `poly(n)`-bit classical hypothesis and answers each query in `poly(n)` time.
- **[Not found]** A theorem phrased exactly as a classical data-structure lower bound for arbitrary measurement-query answering; found tomography lower bounds and dimension arguments instead.
- **[Not found]** An unconditional exponential lower bound for ordinary tree size in Aaronson 2004; the proven ordinary tree-size lower bounds are `n^{Omega(log n)}`, while exponential lower bounds are conjectured or for different/weaker measures such as manifestly orthogonal tree size.
- **[Not found]** An unconditional superpolynomial ordinary-tree-size lower bound for Shor states in Aaronson 2004; that result is conditional on the paper's number-theoretic conjecture.

## 7. Bottom Line for Argus

- **[Established]** Adaptive adversarial consistency is possible in mistake/regret currency polynomial in `n`.
- **[Established]** That result does not make the simulator's classical memory polynomial: the known algorithms keep full density-matrix hypotheses and run in time exponential in `n`.
- **[Established]** Succinct generators/circuits are polynomial-space descriptions, but arbitrary exact prediction from them is counting-hard.
- **[Inference]** For a classical renderer facing arbitrary future quantum measurement queries, the durable dichotomy is: store the explicit state and pay exponential space, or store a succinct generator and pay exponential/#P-hard time to answer general queries.
- **[Inference]** The dichotomy is not a theorem against all renderers, because structured states, restricted measurements, approximate/statistical guarantees, quantum hosts, and observer-limited policies can move cost between currencies.