# Tomography lower bounds — research scout report

**Date:** 2026-09-17
**Scout:** subagent ff1c95f5-eb0e-4598-9104-9c7511116ff4 (requested by session f7a77e1d-48f6-4ecf-8af2-5c147ed391a9)
**Question:** What are the proven LOWER BOUNDS on characterising an unknown n-qubit quantum state, and what exactly do they quantify over?
**Status:** COMPLETE — all theorem statements below are quoted from the arXiv primary sources fetched during this session (evidence class: Established, primary-source quote, unless flagged).

<!-- project: github.com/travislockman/agentic_workforce -->

Notation used throughout: `d` = Hilbert-space dimension = 2^n for n qubits; `ρ` rank ≤ r mixed state, `d = 2^n` in all n-qubit translations; trace distance `T(ρ,σ) = ½‖ρ−σ‖₁`, denoted `ε`; infidelity `1−F(ρ,σ)`, denoted `δ` or `γ`. Relation: `1−F ≤ T ≤ √(1−F²)` (HHJ+17 eq. 1). In all these theorems the *state ρ is fixed but unknown*, and a *learner* receives n copies ρ^⊗n and must output an estimate ρ̂. That scope matters — see VERDICT.

---

## 1. Haah–Harrow–Ji–Wu–Yu, "Sample-optimal tomography of quantum states", arXiv:1508.01797 (STOC 2016; IEEE Trans. Inf. Theory 63(9):5628–5641, 2017; journal DOI 10.1109/TIT.2017.2719044)

### Scope — what measurement model the theorem quantifies over (exact quote)

>The main bounds are for **collective/entangled measurements on all n copies**. Exact quote from §II: *"In this paper we will consider optimal measurements (also called "collective" measurements) and will not discuss the extensive literature on independent or adaptive measurements."*

- **Upper bound (Theorem 2 / abstract):** a theoretical POVM on (ℂ^d)^⊗n (joint measurement on all n copies) achieves infidelity δ with
  `n = O((dr/δ)·ln(d/δ))` copies, hence trace distance ε with `n = O((dr/ε²)·ln(d/ε))`.
- **Lower bound (Theorem 3, exact):** Let ε ∈ (0,1), η ∈ (0,1). Suppose a POVM {M_σ dσ} on (ℂ^d)^⊗n satisfies: for **any** rank-≤r state ρ, `∫_{½‖σ−ρ‖₁≤ε/2} dσ tr[M_σ ρ^⊗n] ≥ 1−η`. Then
  `n ≥ C·(dr/ε²)·(1−ε)² / ln(d/rε)`, `C` depending only on η.
  If r = d (full rank): `n ≥ C·(d²/ε²)·(1−ε)²`, `C` depending only on η.
  The infidelity form of this is `n ≥ Ω̃(dr/δ)`.
- **Lower bound, independent (product, hence non-adaptive) measurements (Theorem 4, exact):** an independent measurement = tensor product of n POVMs on ℂ^d. If for any rank-≤r ρ, `∫_{1−F(σ,ρ)≤δ/4} dσ tr[M_σ ρ^⊗n] ≥ 1−η`, then
  `n ≥ C·(dr²/(δ²·ln(2/δ)))·(1−δ)⁴`, `C` depending only on η.
  Full-rank trace-distance version: if the independent measurement achieves `∫_{½‖ρ−σ‖₁≤ε/2} … ≥ 1−η` for any full-rank ρ, then `n ≥ C·(d³/ε²)·(1−ε)²`. Also stated as: infidelity bound implies `n ≥ C·dr²/(ε²·ln(2/ε))`.
- **What the scope means (my inference, flagged):** Theorem 3 quantifies over *every* POVM on the joint n-copy space; since any single-copy strategy (adaptive or not) is a special case of a joint POVM, Theorem 3 binds adaptive single-copy learners too — but only with the *weak* rate d²/ε². The *strong* single-copy rate d³/ε² is proven in Theorem 4 **only for non-adaptive product measurements**; covering *adaptive* single-copy strategies at the d³/ε² rate required new work (Chen–Huang–Li–Liu–Sellke, §4 below). This is exactly the gap those authors later closed.
- **Technique:** ε-packing net of rank-r states of size 2^Ω(dr) → communication protocol → Holevo's theorem + Fano's inequality.
- Also reported (their §II, on Keyl–Werner spectrum estimation): `Ω(d²/ε²) ≤ n ≤ O(d²/ε²·ln(d/ε))`; pure-state prior: `n ≈ Θ(d/δ)`.

## 2. O'Donnell–Wright, "Efficient quantum tomography" I and II

### I: arXiv:1508.01907 (STOC 2016; v2 Sept 2015)
Collective (entangled) EYD + Keyl measurements on ρ^⊗n. Exact statements:
- **Thm 1.2:** E‖Û·diag(λ̲)·Û† − ρ‖_F² ≤ (4d−3)/n (squared Frobenius error).
- **Cor 1.4:** unknown rank-r mixed ρ estimated to *trace distance* ε with `n = O(rd/ε²)` copies, with high probability (1−δ confidence by × log(1/δ) copies). Full rank: `n = O(d²/ε²)`.
- **Lower bounds (constant-error regime, via Holevo + packing/pairwise-orthogonal ensembles):** `Ω̃(rd)` copies for trace distance ε₀ (constant); `Ω̃(d)` copies for Frobenius error ε₀ even for rank-1; `Ω̃(d²)` for Frobenius error ε = Θ(1/√d) (matches their O(d/ε²) upper bound: n = O(d·d) = O(d²)).
- **Result in network:** with HHJ+ Theorem 3's Ω(d²/ε²), and OW removing the log factor on the upper side, the coherent/collective trace-distance tomography rate is `Θ(d²/ε²)`. (Quote, from 2206.05265 §1: "[HHJ+17] demonstrated n = O(d²log(d/ε)/ε²) … n = Ω(d²/ε²) … are necessary. Concurrently, [OW16] removed the logarithmic factor in the upper bound, thus establishing that the optimal rate for this problem is n = Θ(d²/ε²).") For n qubits: `Θ(4ⁿ/ε²) = 2^Ω(n)` copies — exponential in qubits even with fully coherent measurements.
- Scope note: all OW upper bounds are entangled/collective (Schur–Weyl sampling); their lower bounds are information-theoretic (Holevo-based) and therefore hold against arbitrary measurement strategies, but only give the weak d-rates, not the single-copy-restricted d³/ε².

### II: arXiv:1612.00034 (Nov 2016)
Spectrum/rank-k results, collective measurements:
- Eigenvalues of ρ to ε-accuracy in Hellinger², χ² or KL distance: `n = O(d²/ε)` copies.
- Top-k eigenvalues: `n = O(kd/ε)` (Hellinger²/χ²) or `n = O(k/ε)` (ℓ₂²).
- Optimal rank-k approximation to ε-fidelity (Hellinger²): `n = Õ(kd/ε)` copies.

## 3. Quantum-memory separations — which side is exponential

### Chen–Cotler–Huang–Li, "Exponential separations between learning with and without quantum memory", arXiv:2111.05881 (FOCS 2021; v2 Nov 2021)
**Model definitions (exact quotes):** *"a learning algorithm without quantum memory can only perform measurements on each copy of the quantum state, and learn from the resulting classical measurement data. However, note that the choice of measurement applied to the i-th copy could depend on all previous measurement outcomes."* — i.e. the "no quantum memory" lower bounds are proven against **adaptive single-copy strategies**. With memory: store copies, "perform joint quantum processing … followed by an entangled measurement".

Exact results:
- **Shadow tomography:** for any M>1 there is a set of M observables such that any no-memory algorithm needs `T = Θ̃(min(M, 2ⁿ)/ε²)` samples (Thm 1.1 informal; formal Cor 5.7 / Thm 5.5). Up to logs this matches the no-memory upper bound `O(min(M log M, 2ⁿ log M)/ε²)` [HKP20]; **with quantum memory** the same task needs only `O(n log²(M)/ε⁴)` copies [BO20 – Bubeck–Ozarowski]. So for M = superpolynomial, the without-memory side is exponential and the with-memory side polynomial — the exponential side is the *no-quantum-memory* side.
- **Pauli observables, memory–sample tradeoff (first such tradeoff):** to estimate absolute values of all n-qubit Pauli observables to constant error, any algorithm with k < n qubits of quantum memory needs `Ω(2^{(n−k)/3})` samples, while an algorithm with an n-qubit memory needs only `O(n)` samples. Exponential blowup as k falls below n.
- **Also separated exponentially:** purity testing, distinguishing scrambling vs depolarizing dynamics, discovering symmetry in dynamics. Strengthens/improves [ACQ21].
- **Full tomography** (context quote): "quantum state tomography requires exponentially many copies T = 2^Ω(n) for learning algorithms with and without quantum memory [OW17, HHJ+17]" — i.e. even memory doesn't save you from d²/ε² = 4ⁿ/ε².

### Huang, Broughton, Cotler, Chen, Li, Mohseni, Neven, Babbush, Kueng, Preskill, McClean, "Quantum advantage in learning from experiments", arXiv:2112.00778 (Science 376, 1182–1186, 2022; DOI 10.1126/science.abn7293)
- Claim (abstract quote): "quantum machines can learn from **exponentially fewer experiments** than those required in conventional experiments … in predicting properties of physical systems, performing quantum principal component analysis on noisy states, and learning approximate models of physical dynamics."
- Key subtlety (quote): "the quantum processing needed to achieve the exponential advantage can be modest; for example, one can simultaneously learn about many noncommuting observables by processing **only two copies** of the system" — the advantage is not contingent on unbounded memory.
- Experimental: up to 40 qubits, 1300 gates. This is the experimental/computational sequel to the information-theoretic CCHL separation. The exponential side is the classical (measure-each-copy) learner.

## 4. Adaptivity for single-copy (incoherent) measurements — does it help?

### Chen (Brice)–Huang–Li–Liu–Sellke, "When does adaptivity help for quantum state learning?", arXiv:2206.05265 (FOCS 2023)
- **Trace distance: adaptivity does NOT help; exact tight bound (formal Thm 3.11, quoted verbatim):** *"There exist absolute constants ε₀>0 and d₀∈ℕ such that for any 0<ε<ε₀ and any integer d≥d₀, the following holds. If n = o(d³/ε²), then for any algorithm for state tomography (𝒯,𝒜) that uses n incoherent, possibly adaptive, measurements, its output ρ̂ upon measuring n copies of ρ satisfies ‖ρ−ρ̂‖_tr > ε with probability 1−o(1)."*
  Matching upper bound: non-adaptive `O(d³/ε²)` [KRT17 — Kueng–Rauhut–Terkia]. So single-copy trace-distance tomography is `Θ(d³/ε²)` even with adaptivity. (For n qubits: 8ⁿ/ε².)
- **Infidelity: adaptivity DOES help.** Adaptive algorithm (Thm 1.2 informal / Thm 6.1 formal): `Õ(d³/γ)` copies to reach infidelity γ. Non-adaptive lower bound: `Ω(d³/γ²)` [HHJ+17 Thm 4]. Trace-distance lower bound forces `Ω(d³/γ)`, so `Õ(d³/γ)` is optimal up to polylog. This is, per the authors, "arguably the first natural instance of a separation between the power of adaptive versus nonadaptive measurements" for a quantum learning problem.
- Prior open-problem status (quoted): "understanding the power of adaptive but incoherent measurements for quantum tomography has been posed as an open question by multiple papers [HHJ+17, BCL20]"; before this paper "nothing nontrivial is known in the adaptive setting."

### Chen–Cotler–Huang–Li, arXiv:2111.05881 — the shadow-tomography Θ̃(min(M,2ⁿ)/ε²) lower bound is proven against **adaptive, no-memory** algorithms (model quote in §3). Exponential for M or 2ⁿ exponential.

### Chen–Li–Huang(Brice)–Liu, "Tight bounds for quantum state certification with incoherent measurements", arXiv:2204.07155 (FOCS 2022)
- Mixedness testing: folklore non-adaptive algorithm uses `O(d^{3/2}/ε²)` copies, optimal for non-adaptive; the paper proves `Ω(d^{3/2}/ε²)` **even for arbitrary incoherent (adaptive) measurements**, settling the gap from BCL20's Ω(d^{4/3}/ε²). "Qualitatively, our results say that adaptivity does not help at all for these problems." Also: instance-optimal certification bounds of Chen–Li–O'Donnell hold against arbitrary incoherent measurements. (n-qubit: 2^{3n/2}/ε².)

### Interpolation reference: Chen–Li–Liu, "An optimal tradeoff between entanglement and copy complexity for state tomography", arXiv:2402.16353 (STOC 2024)
- Measuring t copies at a time (t ≤ d²): `Θ̃(d³/(√t·ε²))` copies necessary and sufficient for trace distance ε. Sanity check: t=1 gives d³/ε² (single-copy), t=d² gives d²/ε² (fully coherent). First smooth entanglement–copy tradeoff for any quantum learning task.

---

## Summary: what each bound quantifies over

| Result | Measurement model | Quantity bounded | Worst case over | Status |
|---|---|---|---|---|
| HHJ+17 Thm 3 (1508.01797) | ANY POVM on ρ^⊗n (incl. adaptive) | n ≥ C(dr/ε²)(1−ε)²/ln(d/rε) copies | rank-≤r states, fail prob ≤ η | tight up to logs (coherent) |
| HHJ+17 Thm 4 | independent (product, non-adaptive) | n ≥ C(dr²/δ²ln(2/δ))(1−δ)⁴; full-rank trace: C(d³/ε²)(1−ε)² | fixed-ρ worst case | first d³/ε² rate, non-adaptive only |
| OW16 Cor 1.4 (1508.01907) | coherent (collective) | n = O(rd/ε²) trace, w.h.p. | rank-r states | matches Ω(dr/ε²)/log |
| OW16/OW17 coherent net | coherent | Θ(d²/ε²) = 4ⁿ/ε² = 2^Ω(n) copies | all states | tight (with HHJ+ Thm 3, r=d) |
| CCHL21 (2111.05881) | no quantum memory = **adaptive** single-copy | shadow tomography T = Θ̃(min(M,2ⁿ)/ε²); Pauli: k<n mem ⇒ Ω(2^{(n−k)/3}) | worst-case observable set | tight up to logs; exponential vs O(n)-copies-with-memory |
| CHLLS23 (2206.05265) | incoherent (single-copy), **adaptive** | trace: n = Ω(d³/ε²); infidelity: n = Õ(d³/γ) adaptive vs Ω(d³/γ²) non-adaptive | all states, constants ε₀,d₀ absolute | trace tight; infidelity: first adaptivity separation |
| CHLL22 (2204.07155) | incoherent, adaptive | mixedness Ω(d^{3/2}/ε²) | worst case | tight |

---

## VERDICT

**Question:** does a tomography lower bound bind an agent that must be consistent with an n-qubit state against an observer who chooses measurements *adaptively*, when the agent *is* the state or may choose the state lazily as queries arrive?

**Answer, straight: NO — these bounds do not bind that agent; and the specific question is not addressed in this literature.**

1. **Every theorem above is a statement about a LEARNER, not about a state-holder.** Each fixes an *unknown* ρ, gives the learner n i.i.d. copies ρ^⊗n, and lower-bounds how many copies the learner needs to output ρ̂ within distance ε. The minimax quantifier is over the state (rank ≤ r, or unrestricted); the bound is on the learner's copy budget. The adversarial structure is: *nature picks ρ first, learner never sees ρ, only copies*. Nothing in any of these papers models an entity whose state *is* ρ and who must answer queries about it.

2. **An agent that IS the state is trivially consistent with zero copies.** It can answer any measurement question truthfully from ρ with no sampling cost; classical query cost is a computation question, not a sample-complexity question. The exponential bounds (Θ(4ⁿ/ε²) coherent, Θ(8ⁿ/ε²) single-copy, 2^Ω(n) shadow without memory) all describe how many *copies of a fixed unknown ρ* a learner must consume — an in-state agent consumes none. The bounds only bite an agent if the agent's internal representation is itself an *estimate* of ρ (an agent-as-learner model, which is a different and legitimate reading — flag this as my inference, not a literature result: none of the target papers discuss an agent whose state is its own object of knowledge and whether tomographic lower bounds govern its ability to act as a source of ρ).

3. **A lazy agent (state chosen/updated as queries arrive) is outside the model entirely.** The i.i.d.-copies assumption (ρ^⊗n for one fixed ρ) is the load-bearing assumption of every i.i.d bound here; certification bounds and the whole HHJ+/OW framework collapse if the source may present *different* states. The only related model the literature addresses is the opposite direction — the *observer's* power against a hidden fixed state (state discrimination/certification: e.g. 2204.07155, and the general Holevo-based discrimination bounds). If the agent is committed to one fixed ρ and the observer knows a candidate σ, the certification literature bounds how many copies the *observer* needs to detect a deviation (instance-optimal rates, Chen–Li–O'Donnell 2021, CHLL 2204.07155). That is an upper bound on the observer's detection power at a cost in copies — it is not a constraint on the agent, and it does not cover an agent that may choose ρ after seeing which measurements are offered.

4. **Specific sub-questions the literature DOES answer, for completeness:**
   - Adaptivity of the *observer* does not buy the observer anything for trace-distance tomography (CHLLS23: Ω(d³/ε²) even adaptive) — relevant only if the agent is a learner.
   - Worst-case bounds do not bind any particular easy instance: all results are minimax. Even a learner constrained to single-copy measurements can beat d³/ε² on structured families (e.g. stabilizer/stabilizer-mixture states via classical shadows, Huang–Kueng–Preskill, 2002.08953; that paper is cited inside 2111.05881's discussion) — instance-optimality is an active line (Chen–Li–O'Donnell, arXiv:2202.05268, "Toward instance-optimal state certification").

**Verdict on the direct question: not addressed.** The tomography-lower-bound literature constrains learners who do not know the state and receive i.i.d. copies; whether an agent that *is* or *lazily chooses* the state can be held consistent against an adaptive observer is a different (game-theoretic) question that these papers neither pose nor answer. I will not guess. If Argus needs an answer there, it is an open modeling question — and the nearest provable fragments are (a) observer-side detection bounds (certification/discrimination), which set the *observer's* copy cost to catch deviation, and (b) the observation that a committed fixed state makes the i.i.d. assumption hold, so an observer with ~d²/ε² (coherent) copies can falsify any alternative at trace distance ε — again an observer-side, not agent-side, constraint.

---

## Not found / where I looked

- **Not found:** any reference in the five target papers (or their cited related work: BCL20, ACQ21, HKP20, HKP21, KRT17, BO20, CLO21, CHLL22) to an "agent that is the state" or "lazily chosen state" model. Searched: 2111.05881 v2 full HTML (intro + §4.4 learning models + Table 1), 2206.05265 v2 HTML, 2112.00778 abstract/HTML, 1508.01797 v2 HTML, 1508.01907 v2 HTML, 1612.00034 v1 HTML. Search queries run: "exponential separations learning quantum memory", "adaptivity help quantum state learning", "tight bounds quantum state certification incoherent", "optimal tradeoff entanglement copy complexity", each returning the papers above; a query for a "Chen–Huang–Li–Liu–Sellke" paper distinct from 2206.05265 returned only 2206.05265 (and 2502.00823, an unrelated shadow-estimation work by Chen, Brice Huang, Li, Liu, Sellke — noted, not a tomography lower bound paper).
- **Not fetched:** full PDF bodies of HHJ+ (only HTML was available — Theorem 3/4 statements were extracted from the HTML of v2, which is the STOC/ITIT version; the v1 lower bound for independent measurements was weaker, per the v2 comment), and OW II's later sections (only needed its abstract + intro theorem list, which I captured). The Science paper (2112.00778) main text beyond the abstract was not fetched (paywalled structure; abstract + report number suffice for its exact claim).
- **Constants:** HHJ+ Theorem 3/4 state constants "C depending only on η" without numerical values — the papers do not give explicit numeric constants, so none are reported here (numbers are in the (1−ε)²/(1−δ)⁴ factors, as quoted). CHLLS23 Theorem 3.11 gives absolute constants ε₀, d₀ without values. This is inherent to the sources, not a gap in extraction.
- **Cross-checked via:** arXiv abs pages for all seven arXiv IDs; HTML full texts for 1508.01797v2, 1508.01907v2, 1612.00034v1, 2206.05265v2, 2111.05881v2, 2112.00778 (abstract), 2204.07155 (abstract), 2402.16353 (abstract).