How hard is it to verify a classical shadow?

Dorian Rudolph; Georgios Karaiskos; Jens Eisert; Johannes Jakob Meyer; Sevag Gharibian

REVIEW 3 major objections 4 minor 10 references

How hard is it to verify a classical shadow?

T0 review · 3 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Classical shadow verification is QMA-complete even for the simplest local measurement protocol, while global-measurement shadows are classically checkable when observables have low Frobenius norm.

desk verdict A solid complexity-theoretic framework for shadow verification with a real QMA-completeness result, but the dequantization theorem has a gap at Eq. (11) that needs repair. read the letter →

arxiv 2510.08515 v3 pith:FQMTVL3P submitted 2025-10-09 quant-ph cs.CC

Georgios Karaiskos , Dorian Rudolph , Johannes Jakob Meyer , Jens Eisert , Sevag Gharibian This is my paper

classification quant-phcs.CC MSC 68Q1281P68

keywords classicalshadowsshadowverificationQMA-completenessdequantizationquantumpolynomialhierarchyobservableconsistencysemidefiniteprogramminglocalCliffordmeasurements

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how hard it is to check that a classical shadow—a compact classical record meant to predict measurement outcomes of some quantum state—is genuine. It proves that for the simplest shadow protocol, in which each qubit is measured in a random Pauli basis, the verification problem is QMA-complete: in the worst case it is as hard as any problem with a quantum witness. It also proves the opposite for the global-Clifford version when the observables have polynomially bounded Frobenius norm and sampling access is available: verification can be done in randomized classical polynomial time. Finally, when there are exponentially many observables, verification becomes complete for a quantum-classical level of the polynomial hierarchy, giving the first natural complete problem for that class.

What carries the argument

The paper works with an abstract equivalent problem, observable consistency: given observables and claimed expectation values, decide whether a state matches them. Carrying the hard case is a chain of reductions starting from one-dimensional consistency of local density matrices, solved through a linear program rounded to integer weights and then patched by a dynamic program. The easy case is carried by sampling-based low-rank matrix sketches, which compress observables into a polynomial-dimensional subspace, followed by a semidefinite program on the compressed instance. The exponential-observable case is carried by an equivalence between shadow validity and a super-verifier class that colla

What would settle it

Run a sampling-based low-rank routine on a small explicit observable and compare the operator formed by the approximate vectors with the two-sided projection ΠOΠ; check whether the difference can be made large enough to flip a shadow-validity instance's yes/no answer. Alternatively, exhibit a shadow-validity instance whose minimal consistency error is attained only at a non-normalized operator with trace less than 1.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the complexity of shadow verification is not fixed by the shadow idea itself but by the measurement ensemble and the observables. It defines classical shadow validity as a decision problem—given a shadow, can its predictions be realized by some n-qubit state within tolerance—and shows that for local Clifford measurements, the problem is QMA-complete even with six-local observables arranged on a spatially sparse hypergraph. For global Clifford measurements with observables of polynomially bounded Frobenius norm, it exhibits a randomized classical polynomial-time algorithm. For exponentially many observables, it places shadow validity exactly at qc-Σ2, a q

Load-bearing premise

The dequantization proof relies on the step where approximate low-rank vectors obtained by sampling are used as if they were exact eigenvectors, so that the truncated observable equals the two-sided projection of the original observable onto their span; those vectors are only approximations, and if that equality cannot be justified, the polynomial-time classical algorithm for global-Clifford shadows is not established. A secondary fragile point is optimizing over Tr[ρ] ≤ 1 ra

Editorial extensions

If this is right

If local-Clifford shadow validity is QMA-complete, no classical polynomial-time worst-case verifier can certify such shadows unless QMA collapses to P; practical verification must exploit additional structure or promises.
The dequantization result implies that for global-Clifford shadows with low-Frobenius-norm observables, shadow validity can be checked classically, matching the regime where the shadow protocol itself is efficient.
The qc-Σ2-completeness result for exponentially many observables provides the first natural complete problem for a quantum generalization of the second level of the polynomial hierarchy.
Product-state variants of shadow validity become complete for QMA(2) and for a three-level quantum-classical hierarchy, extending the verification question to unentangled-prover settings.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An inference beyond the paper: the hardness seems to come from stitching local information across the whole system, so any shadow protocol whose snapshots are spatially local along a line may inherit QMA-hardness, while protocols whose snapshots are global may become easier for bounded-norm observables.
A testable extension: the paper does not prove qc-Σ2-completeness for the specific triply efficient shadow protocol that targets all Pauli observables; closing that gap is a concrete open target suggested by the exponential-observable result.
A practical consequence not drawn by the paper: the promise-gap formulation suggests that bounded-error approximate verification is the meaningful regime, and a constant gap β−α may make the exponential-observable case strictly easier than the QMA-complete polynomial-observable case.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know two things up front. First, this paper gives the first formal definition of classical shadow validity and shows that verifying local-Clifford HKP shadows is QMA-complete, even for 6-local observables on a spatially sparse hypergraph. That result looks right and is the main reason to care. Second, the dequantization theorem for global-Clifford shadows (Theorem 4.22) has a genuine flaw: Eq. (11) asserts that O_j times an approximate projector equals the projected version “since O_j is Hermitian.” But the v_{j,t} from the FKV algorithm are approximate singular vectors of a sketched matrix, not eigenvectors of O_j, so that equality does not follow. The proof needs a rederived error bound, e.g. by defining \tilde O_j = Π_j O_j Π_j directly and using FKV's low-rank guarantee to control the projection error. As written, the main dequantization claim is incompletely justified. A second, smaller issue is the SDP allowing Tr[ρ] ≤ 1 instead of Tr[ρ] = 1, which can potentially accept subnormalized states; that is likely fixable with a short argument.

The best parts of the paper are the hardness results. The LP/IP stitching technique in Theorem 4.5 is clever: it encodes 1D-CLDM consistency into a linear program over local snapshot distributions, then rounds with a dynamic program. The QMA-completeness for MYZ qudit shadows is a natural extension. The qc-Σ2 completeness for exponentially many observables is also a solid contribution—the class is new, and the proof via SuperQMA_exp is clean. The paper is generally well-written and the authors are honest about which arguments are sketches.

The soft spots beyond Eq. (11): Theorem 4.4 and parts of Appendix B are proof sketches rather than complete proofs. The combination of Broadbent–Grilo and Hallgren–Nagaj–Narayanaswami is plausible but needs more detail to be verified. Also, the runtime in Proposition 4.6 is polynomial with a gigantic constant (L^{m^2−2} with m^2 on the order of 10^4), which is fine for complexity theory but worth noting for anyone wanting a practical algorithm.

The hardness half of the paper is worth taking seriously; the dequantization half needs repair. I would send this to a serious referee, and I would bring the hardness results up at reading group. The citation should be held until the dequantization gap is patched, but the QMA-completeness result alone is a good reason to keep the paper on your radar.

Referee Report

3 major / 4 minor

Summary. The paper initiates the study of Classical Shadow Validity (CSV): given a classical shadow S, an observable set, and a recovery algorithm, decide whether S's predictions are close to the measurement statistics of some n-qubit state. It introduces a general observable-consistency formulation (ObsCon), shows that general ObsCon with polynomially many observables is QMA-complete, and that the HKP local-Clifford shadow protocol remains QMA-hard even for 6-local observables on a spatially sparse hypergraph. For global-Clifford shadows with low-Frobenius-norm observables, it claims a randomized classical polynomial-time 'dequantization' algorithm via matrix sketches and an SDP. It further proves QMA-completeness for the MYZ qudit local-Clifford protocol and, for exponentially many observables, completeness for a newly introduced class qc-Σ2 (a quantum-classical second level of the polynomial hierarchy), giving the first natural complete problem for such a class. The paper also studies product-state variants connected to QMA(2) and a multiple-shadow consistency problem.

Significance. If the main results hold, this is a valuable contribution: it gives the first systematic complexity-theoretic treatment of verification of classical shadows, shows that verifying even the simplest local-Clifford shadows is intractable in the worst case, and identifies a new quantum-classical hierarchy level with a natural complete problem. The general ObsCon/QMA-completeness route and the qc-Σ2 = SuperQMAexp equivalence are clean and reduce from independent QMA-complete problems, which is a strength. The QMA-hardness constructions for HKP and MYZ are elaborate and plausible, and the connection to 1D-CLDM and the HNN 8-state line is a sensible use of known hardness. The main caveat is the dequantization proof, which currently contains a load-bearing unjustified equality; until that is repaired, the polynomial-time claim for global-Clifford CSV is not established.

major comments (3)

[§4.5, Eq. (11)] The equality \tilde O_j := O_j Σ_t v_{j,t}v_{j,t}^† = Π_j O_j Π_j is asserted 'since O_j is Hermitian'. The vectors v_{j,t} produced by the FKV algorithm are approximate singular vectors of a sketched matrix, not exact eigenvectors of O_j; Hermiticity only identifies left and right singular vectors for exact singular vectors and does not imply that Π_j commutes with O_j. Theorem 4.18 bounds ∥O_j − D*∥_F for a rank-r D*, not ∥O_j − Π_jO_jΠ_j∥_F. Since Eq. (15) and the compressed SDP are formulated in terms of Π_jO_jΠ_j, the proof of Theorem 4.22 is incomplete. Please either work directly with the FKV approximation D* and show how to evaluate Tr(D*_j ρ) from the sketch, or derive a projected Frobenius bound relating Π_jO_jΠ_j to the FKV output.
[§4.5, SDP (16)–(18)] The semidefinite program uses the constraint Tr[ρ] ≤ 1 instead of Tr[ρ] = 1. This allows subnormalized states, whose expectation values can be scaled down; a NO instance could then be accepted if the targets y_j are small. This is likely patchable by enforcing Tr[ρ] = 1, but as written the soundness of the final SDP step is not justified.
[§4.2, Theorem 4.9] The proof of QMA-hardness for CSVMYZ is only a sketch. The central claim needs the qudit analogue of the LP/IP in Eqs. (4)–(5) written out explicitly, including the Weyl-operator basis, the qudit snapshot alphabet, and the exact embedding of the 8-level 1D-CLDM instance into odd prime dimension d ≥ 11 with promise gaps preserved. As it stands, the reduction rests on an analogy rather than a checkable construction, which is especially important because it is one of the main hardness results.

minor comments (4)

[§4.5, Eq. (15)] In the displayed formula for v†_{k,l} \tilde O_l v_{j,t}, the numerator contains u†_{j,t} S_k while the denominators use W†_k u_{k,l} and W†_j u_{j,t}. The first vector should presumably be u†_{k,l} S_k. Please fix the index notation.
[Abstract / §4.3] The abstract says 'low-rank observables' while the formal theorem and Definition 4.12 are stated for observables with polynomially bounded Frobenius norm. These are not equivalent in general; align the terminology.
[§4.1, Theorem 4.5] After solving the LP in Eq. (4), the transition to the integer program in Eq. (5) introduces a trace-norm error ε. The proof should state explicitly how ε is chosen relative to α and β in Definition 4.1; otherwise the completeness/soundness gap of the constructed CSVHKP instance is not quantified.
[§6, Lemma 6.4] The randomized reduction from SampleCSV to CSV is only sketched. Since this lemma is used to justify the equivalence of the sampled and explicit shadow models, the full proof should be included or moved to an appendix with all promises checked.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; main results reduce from independent QMA-complete problems.

full rationale

The paper's central results are genuine reductions. QMA-hardness of CSVHKP is obtained by reducing from 1D-CLDM, which is shown QMA-hard by combining the independent external results of Broadbent–Grilo and Hallgren–Nagaj–Narayanaswami; the LP/IP/dynamic-programming construction is explicit and does not assume the target result. The dequantization theorem uses the external FKV and CGL+ sampling/low-rank frameworks; the questionable Eq. (11) step (treating approximate FKV vectors as exact eigenvectors) is a correctness or rigor concern, not a circularity, since it does not presuppose the theorem's conclusion. The qc-Σ2 completeness result is also not circular: SuperQMAexp and qc-Σ2 are defined independently and proved equivalent via nontrivial Hoeffding/Markov arguments, with no load-bearing self-citation or fitted-input-called-prediction step. Self-citations in the paper are contextual and not load-bearing. No circular step could be exhibited, so the score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No numerical parameters are fitted to data. The thresholds α, β, ε and the FKV cutoff are problem inputs or tunable algorithm parameters, not free parameters used to make the result true. No new physical entities are posited; the new complexity classes are formal constructs with no independent falsifiable physical handle outside the definitions.

assumptions (7)

standard math QMA = SuperQMApoly (Aharonov–Regev [AR03])
Used in Corollary 3.6 to lift ObsConpoly completeness to QMA-completeness; taken as a theorem from the literature.
domain assumption 1D-CLDM on 8-level qudits is QMA-complete (Theorem 4.4, proven by combining [BG22] and [HNN13])
Central hardness anchor for CSVHKP; the proof in Appendix B instantiates BG22's simulatable-history-state machinery on HNN's 1D 8-state architecture. If this theorem fails, the HKP hardness result collapses.
standard math CLDM is QMA-complete under Karp reductions (Broadbent–Grilo [BG22])
Background theorem used directly in Appendix A and indirectly in Theorem 4.4.
standard math 1D Local Hamiltonian with 8-level qudits is QMA-complete (Hallgren–Nagaj–Narayanaswami [HNN13])
Used to provide the spatially local model in Theorem 4.4.
standard math FKV low-rank approximation theorem (Theorem 4.18) and CGL+22 sampling/query lemmas (Lemmas 4.19, 4.20)
Basis of the dequantization algorithm; assumes the SQ access model from [CGL+22].
standard math Product test / SymQMA(k) equivalence (Harrow–Montanaro [HM10])
Used in Lemma 5.3 to show SuperQMA(2)poly = QMA(2).
standard math Sion's minimax theorem (Lemma 5.12)
Used to swap quantifiers in proving qc-\Sigma_2(2) = qcq-\Sigma_3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of How hard is it to verify a classical shadow?." pith.science (2026). https://pith.science/paper/FQMTVL3P

@misc{pith2026251008515,
  author       = {Pith},
  title        = {Pith review of: How hard is it to verify a classical shadow?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FQMTVL3P}},
  note         = {Machine review of arXiv:2510.08515}
}

read the original abstract

Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state rho, while only requiring measurements on logarithmically many copies of rho in the size of P. In this work, we initiate the study of verification of classical shadows, denoted classical shadow validity (CSV), from the perspective of computational complexity, which asks: Given a classical shadow S, how hard is it to verify that S predicts the measurement statistics of a quantum state? We first show that even for the elegantly simple classical shadow protocol of [Huang, Kueng, Preskill, Nature Physics 2020] utilizing local Clifford measurements, CSV is QMA-complete. This hardness continues to hold for the high-dimensional extension of said protocol due to [Mao, Yi, and Zhu, PRL 2025]. In contrast, we show that for the HKP and MYZ protocols utilizing global Clifford measurements, CSV can be "dequantized" for low-Frobenius norm observables, i.e., solved in randomized poly-time with standard sampling assumptions. Among other results, we also show that CSV for exponentially many observables is complete for a quantum generalization of the second level of the polynomial hierarchy, yielding the first natural complete problem for such a class.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

10 extracted references · 1 linked inside Pith

[1]

If x ∈ Ayes, then for any good witness eψ(s) that makes eV (s) x accept with probability 1 − negl(|x|), we have that ρ(x, t, S) − TrS∩work eUt · · ·eU1 eψ(s) ⊗ |0⟩ ⟨0|⊗q eU † 1 · · ·eU † t Tr ≤ negl(|x|)
[2]

At t = 0, for any ancilla qubit j ∈ S we have Tr{j}(ρ(x, 0, S)) = |0⟩ ⟨0|
[3]

We have that TrE(ρ(x, t, S)) = TrE eUt · · ·eUtd+1 Enc(|1⟩ ⟨1|) eU † td+1 · · ·eU † t

Let td be the step just before the decoding and assume t ≥ td and E ⊆ S be the set of qubits of the encoding of the output qubit in S. We have that TrE(ρ(x, t, S)) = TrE eUt · · ·eUtd+1 Enc(|1⟩ ⟨1|) eU † td+1 · · ·eU † t . Proof. Write the time-t snapshot as |Ψt⟩ = |m(t)⟩markers ⊗ |w(t)⟩work. For an edge e = (i, i+ 1) the reduced snapshot factors: X(x, t,...
[6]

+ 1, . . . ,2nk} and, for each edge e = ( i, i+ 1), define its location type L(e) ∈ {A, B, C, D, E} from the block index and the in block position (interior odd/even and the two block-end / between-block cases (see Table 5 in Ref. [HNN13])). For each location L ∈ {A, B, C, D, E}, let LL ⊆ Σ2 be the set of legal adjacent marker pairs that occur at edges of...
[7]

If x ∈ Ayes, then there exists a good witness eψ(s) that makes eV (s) x accept with probability at least 1 − negl(|x|) such that: bX(x, S) − TrS ΦHNN Tr ≤ negl(|x|), ΦHNN := 1 T + 1 TX t,t′=0 |m(t)⟩ ⟨m(t′)|⊗|w(t)⟩ ⟨w(t′)|
[8]

Then for every x ∈ A, Tr(Hi bX(x, Si)) = 0

Let Hi be one term from HNN circuit-to-Hamiltonian construction from eV (s) x and Si be the set of qudits on which Hi acts non-trivially. Then for every x ∈ A, Tr(Hi bX(x, Si)) = 0. Proof sketch. Construction of SimHNN eV (s) (x, S). Trace out all marker registers on S. For any t, t′ the marker factor reduces as TrS |m(t)⟩ ⟨m(t′)| = O j∈S |mj(t)⟩ ⟨mj(t′)|...
[9]

The power of unentan- glement

DOI: 10.1145/3188745.3188802. [ABD+09] S. Aaronson, S. Beigi, A. Drucker, B. Fefferman, and P. Shor. “The power of unentan- glement”. In: Theory of Computing 5.1 (2009), pp. 1–42. DOI: 10.4086/toc.2009. v005a001. [AGKR24] A. Agarwal, S. Gharibian, V . Koppula, and D. Rudolph. “Quantum Polynomial Hierar- chies: Karp-Lipton, Error Reduction, and Lower Bound...

arXiv 2009
[10]

37 Proof of Theorem 4.4 Since the containment is straightforward we only show hardness explicitly

Hence Tr Hi bX(x, Si) = X I∈I(Si) |I| T + 1 Tr Hi bX(x, I, Si) = 0. 37 Proof of Theorem 4.4 Since the containment is straightforward we only show hardness explicitly. Let x ∈ A (where A is a promise problem in QMA), the reduction uses SimHNN eV (s) to compute the 1D-CLDM instance on an 8-level qudit chain: {(S, bX(x, S)) : S ∈ {i, (i, i+ 1)}} If x ∈ Ayes,...

Show all 10 references

[11]

normalized Hi so ∥Hi∥∞ ≤ 1

Hence Tr(H(x)τ ) = X i Tr Hi TrSi(τ ) = X i Tr Hi TrSi(τ ) − bX(x, Si) ≤ X i ∥Hi∥∞ TrSi(τ ) − bX(x, Si) Tr ≤ L α, where the first inequality uses the H ¨older inequality for Schatten norms ( | Tr(AB)| ≤ ∥A∥∞∥B∥Tr), and we also assumed w.l.o.g. normalized Hi so ∥Hi∥∞ ≤ 1. Here,...
[2008]

Triply Efficient Shadow Tomography

arXiv: 0808.2775 [quant-ph]. [KGKB25] R. King, D. Gosset, R. Kothari, and R. Babbush. “Triply Efficient Shadow Tomography”. In: PRX Quantum 6.1 (2025), p. 010336. DOI: 10.1103/PRXQuantum.6.010336. [KMY03] H. Kobayashi, K. Matsumoto, and T. Yamakami. “Quantum Merlin-Arthur Proo...

2025 arXiv

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

If x ∈ Ayes, then for any good witness eψ(s) that makes eV (s) x accept with probability 1 − negl(|x|), we have that ρ(x, t, S) − TrS∩work eUt · · ·eU1 eψ(s) ⊗ |0⟩ ⟨0|⊗q eU † 1 · · ·eU † t Tr ≤ negl(|x|)

[2] [2]

At t = 0, for any ancilla qubit j ∈ S we have Tr{j}(ρ(x, 0, S)) = |0⟩ ⟨0|

[3] [3]

We have that TrE(ρ(x, t, S)) = TrE eUt · · ·eUtd+1 Enc(|1⟩ ⟨1|) eU † td+1 · · ·eU † t

Let td be the step just before the decoding and assume t ≥ td and E ⊆ S be the set of qubits of the encoding of the output qubit in S. We have that TrE(ρ(x, t, S)) = TrE eUt · · ·eUtd+1 Enc(|1⟩ ⟨1|) eU † td+1 · · ·eU † t . Proof. Write the time-t snapshot as |Ψt⟩ = |m(t)⟩markers ⊗ |w(t)⟩work. For an edge e = (i, i+ 1) the reduced snapshot factors: X(x, t,...

[4] [6]

+ 1, . . . ,2nk} and, for each edge e = ( i, i+ 1), define its location type L(e) ∈ {A, B, C, D, E} from the block index and the in block position (interior odd/even and the two block-end / between-block cases (see Table 5 in Ref. [HNN13])). For each location L ∈ {A, B, C, D, E}, let LL ⊆ Σ2 be the set of legal adjacent marker pairs that occur at edges of...

[5] [7]

If x ∈ Ayes, then there exists a good witness eψ(s) that makes eV (s) x accept with probability at least 1 − negl(|x|) such that: bX(x, S) − TrS ΦHNN Tr ≤ negl(|x|), ΦHNN := 1 T + 1 TX t,t′=0 |m(t)⟩ ⟨m(t′)|⊗|w(t)⟩ ⟨w(t′)|

[6] [8]

Then for every x ∈ A, Tr(Hi bX(x, Si)) = 0

Let Hi be one term from HNN circuit-to-Hamiltonian construction from eV (s) x and Si be the set of qudits on which Hi acts non-trivially. Then for every x ∈ A, Tr(Hi bX(x, Si)) = 0. Proof sketch. Construction of SimHNN eV (s) (x, S). Trace out all marker registers on S. For any t, t′ the marker factor reduces as TrS |m(t)⟩ ⟨m(t′)| = O j∈S |mj(t)⟩ ⟨mj(t′)|...

[7] [9]

The power of unentan- glement

DOI: 10.1145/3188745.3188802. [ABD+09] S. Aaronson, S. Beigi, A. Drucker, B. Fefferman, and P. Shor. “The power of unentan- glement”. In: Theory of Computing 5.1 (2009), pp. 1–42. DOI: 10.4086/toc.2009. v005a001. [AGKR24] A. Agarwal, S. Gharibian, V . Koppula, and D. Rudolph. “Quantum Polynomial Hierar- chies: Karp-Lipton, Error Reduction, and Lower Bound...

arXiv 2009

[8] [10]

37 Proof of Theorem 4.4 Since the containment is straightforward we only show hardness explicitly

Hence Tr Hi bX(x, Si) = X I∈I(Si) |I| T + 1 Tr Hi bX(x, I, Si) = 0. 37 Proof of Theorem 4.4 Since the containment is straightforward we only show hardness explicitly. Let x ∈ A (where A is a promise problem in QMA), the reduction uses SimHNN eV (s) to compute the 1D-CLDM instance on an 8-level qudit chain: {(S, bX(x, S)) : S ∈ {i, (i, i+ 1)}} If x ∈ Ayes,...