Pith. sign in

REVIEW 3 major objections 6 minor 19 references

Improved Classical Shadow Tomography Using Quantum Computation

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A quantum-to-classical-to-quantum protocol solves shadow tomography with the same copies, exponential space savings, and a quadratic time speedup in dimension.

desk verdict QCQC is a genuine new idea, and the Pauli variant is clever; but the Clifford variant silently requires the exact trace of each observable, which the abstract wrongly claims to avoid. read the letter →

arxiv 2505.14953 v1 pith:U2OMDX53 submitted 2025-05-20 quant-ph cs.ITmath.IT

Zahra Honjani , Mohsen Heidari This is my paper · ORCID
classification quant-phcs.ITmath.IT
keywords classicalshadowtomographyquantum-to-classical-to-quantumCliffordmeasurementsPaulinormmedian-of-meansestimatorsamplecomplexityspace
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 claims that classical shadow tomography can be made faster and much smaller in memory by sending its classical snapshots back into a quantum computer before estimating observables. The protocol, called QCQC, measures copies of $\rho$ as in CST, then prepares quantum states that encode the shadow snapshots and measures them directly with circuits for the observables, bypassing the expensive classical traces of $d\times d$ matrices. For Clifford measurements, the result is an exponential reduction in classical working space and a quadratic speedup in $d$ relative to classical CST; for Pauli measurements, the same idea handles $k$-local observables with similar gains. If the construction is correct, the resource bottleneck of shadow tomography shifts from classical matrix post-processing to the depth and fidelity of the quantum circuits that implement the observables.

What carries the argument

The central object is a classical-to-quantum channel that maps each recorded snapshot $(U_i,b_i)$ into a quantum state that stands in for the inverted shadow channel acting on the pure outcome. For Clifford measurements, the state $U_i^\dagger |b_i\rangle$ is measured and the inverse-channel correction is moved into the estimator scale factor $d+1$ and the subtraction of $\mathrm{tr}(O_j)$. For Pauli measurements, the non-positive operator $3U_{i,l}^\dagger |b_{i,l}\rangle\langle b_{i,l}|U_{i,l}-I$ is replaced by a physical density matrix obtained by flipping each bit with probability $1/3$ and attaching the weight $3(-1)^{e_l}$, which makes the estimator unbiased while keeping the state preparable. This re-quantization is what lets the observable evaluation run as a quantum circuit of $F$ gates rather than as a classical multiplication of $d\times d$ matrices.

What would settle it

Run the Clifford QCQC protocol on a classical simulator for $n=20$ and $n=30$ qubits with $M=10$ fidelity observables while tracking peak memory and total runtime; the exponential space reduction predicts peak memory stays polynomial in $n$, and the quadratic speedup predicts runtime grows like $d$ rather than $d^2$.

Watch

Extended reading notes

Core claim

The paper establishes that a classical shadow snapshot, which CST treats as a $d\times d$ matrix whose trace with each observable must be computed classically, can instead be re-prepared as a quantum state and measured directly by a circuit implementing the observable. For Clifford measurements, the estimator is $Y_{i,j}=(d+1)X_{i,j}-\mathrm{tr}(O_j)$, where $X_{i,j}$ is the empirical average of measuring the re-prepared snapshot with $O_j$; this estimator is unbiased for $\mathrm{tr}(\rho O_j)$ and has variance bounded by $4\,\mathrm{tr}(O_j^2)$. The paper proves this yields a protocol solving Problem 1 with $O(B\log M)$ copies of $\rho$, $\tilde{O}(d B F M)$ quantum and classical time, and $O(\mathrm{polylog}(d,M)+M\log M)$ classical space, where $B=\max_j \mathrm{tr}(O_j^2)$ and $F$ is the maximum number of gates in the circuits for the observables. For Pauli measurements, the snapshot is re-prepared by flipping each recorded bit with probability $1/3$ and weighting the outcome by $3(-1)^{e_l}$, giving a protocol for $k$-local observables with $O(4^k\log M\,B)$ copies and $\tilde{O}(9^k k B F M\log M)$ time. The sample complexity matches the original CST, so the improvement is purely in how the classical data is processed.

Load-bearing premise

The claimed speedups hold only when every observable $O_j$ can be implemented as a quantum circuit with polynomially many gates and its classical trace $\mathrm{tr}(O_j)$ can be computed efficiently; if either condition fails, the protocol loses its advantage.

Editorial extensions

If this is right

  • For Clifford measurements, the protocol solves Problem 1 with $O(B\log M)$ copies, $\tilde{O}(d B F M)$ quantum and classical time, and $O(\mathrm{polylog}(d,M)+M\log M)$ classical space, compared with the $\Omega(d^2M\log M)$ runtime of classical CST.
  • For bounded-rank observables, Corollary 1 gives $O(d r \lambda^2 M\log M)$ time and $O(r\lambda^2\log M)$ copies, so low-rank cases such as fidelity estimation with $r=1$ scale gracefully in dimension.
  • For $k$-local observables, the Pauli-measurement variant uses $O(4^k\log M\,B)$ copies, $\tilde{O}(9^k k B F M\log M)$ time, and only $O(k+M\log M)$ working classical space.
  • The copy complexity is unchanged from ordinary CST, so the speedups do not come at the cost of extra copies of $\rho$.
  • If the observables have polynomial gate complexity, the classical post-processing no longer scales with the exponential matrix dimension, because traces are replaced by direct quantum measurements.

Reading between the lines

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

  • The same re-quantization idea could transfer to other shadow ensembles, such as shallow shadows or random Gaussian unitaries, whenever the inverse channel maps individual measurement outcomes to mixtures of valid quantum states; the paper analyzes only Clifford and Pauli ensembles.
  • On real hardware the quadratic time advantage may be offset by the large number of additional quantum measurements: each of the $N M$ observable evaluations uses $m=2(d+1)$ or $(9/4)^k$ shots on re-prepared states, so total shot count grows as $N M d$ for the Clifford case, a cost the paper counts as time but not as a separate hardware resource.
  • A natural testable extension is to benchmark peak classical memory and wall-clock time for fidelity estimation on $n=20$ to $30$ qubits; the exponential space reduction should appear as polynomial-in-$n$ classical memory, and the quadratic speedup as time scaling closer to $d$ than to $d^2$.
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.

Referee Report

3 major / 6 minor

Summary. This paper proposes a quantum-to-classical-to-quantum (QCQC) variant of classical shadow tomography (CST). As in standard CST, a random unitary U_i is applied to a copy of an unknown state rho and a computational-basis outcome b_i is recorded; the new second phase prepares the state |b_i>, applies U_i-dagger, and measures each target observable O_j directly on the resulting quantum state, instead of classically materializing the d-by-d shadow matrix and computing traces. For Clifford measurements the estimator is Y_{i,j} = (d+1)X_{i,j} - tr(O_j) (Section III-A), and for Pauli measurements it is formed from bit-flip-weighted measurement outcomes (Section III-B), in both cases followed by a median-of-means step. The main results are Theorem 2 (Clifford case: O(B log M) copies, O-tilde(d B F M) time, and O(polylog(d) + M log M) classical space, with B = max_j tr(O_j^2) and F the gate count of each observable, versus Omega(d^2 M log M) time for classical Clifford CST) and Theorem 3 (Pauli case for k-local observables: O(4^k B log M) copies and O(9^k k B F M log M) time). The paper claims an exponential classical-space reduction and a quadratic (in d) running-time improvement over single-copy CST.

Significance. The QCQC idea--delegating shadow post-processing to quantum circuits so that the observable trace is computed by measurement--is natural, and the mathematical analysis is mostly sound. Lemma 1 proves unbiasedness; Lemma 2 bounds the Clifford estimator's variance by 4 tr(O_j^2) with the shot count m = 2(d+1) balancing the two variance contributions; Lemma 3's bit-flip construction is an elegant and genuinely trace-free implementation of the Pauli shadow channel; and the median-of-means constants in Theorem 2's proof are correct. If the trace-access assumption discussed in Major Comment 1 is added, the claimed exponential space reduction for Clifford shadows and the reduction of the per-observable classical cost from Omega(d^2) to O-tilde(d F) are real, and the Pauli-side separation (classical 16^k versus QCQC 9^k k F, up to B and log factors) is a concrete and falsifiable complexity claim. I found no circularity: the shot counts m = 2(d+1) and m = (9/4)^k and the bit-flip probability 1/3 are fixed by variance analysis rather than fitted to the target results, and the proof steps are short enough to verify by hand, though no machine-checked proofs or code are provided.

major comments (3)
  1. [Section III-A (Lemma 1, Theorem 2) and Abstract] The Clifford estimator Y_{i,j} = (d+1)X_{i,j} - tr(O_j) requires the exact classical number tr(O_j), but Theorem 2's input model states only that each O_j is 'implemented with at most F quantum gates'; it does not say that tr(O_j) is known, supplied as an oracle, or computable within the stated complexity budget. For observables given as circuits this matters: with O_j = |0><0| tensor ((U+U-dagger)/2) + |1><1| tensor I for a polynomial-size unitary U, tr(O_j) = Re tr(U) + 2^n, and computing Re tr(U) exactly is #P-hard, while estimating tr(O_j) to the additive error epsilon required by Problem 1 is not included in the copy count N or the O-tilde(d B F M) runtime (|tr(O_j)| can be as large as d). Without an exact or epsilon-accurate tr(O_j), the estimator is biased, and the abstract's claim that 'calculating large matrix traces is avoided' is not justified for the Clifford protocol; only the Pauli protocol of Section III-B avoids tr(O_j) entirely. Note that the classical CST baseline absorbs the -tr(O_j) I part of the shadow matrix in its d-by-d matrix arithmetic, whereas QCQC must subtract it explicitly, so this is a genuine gap in the input model. The theorem should add the explicit assumption that tr(O_j) is available classically or computable in poly(n) time (or restrict the statement to classes such as projectors or Pauli operators with known traces), and the abstract should be qualified accordingly.
  2. [Abstract and Section IV] The abstract and conclusion state an exponential space reduction and a quadratic running-time improvement 'of CST with single-copy measurements' without the conditions under which these hold. The exponential space reduction applies to Clifford-measurement CST, whose classical shadows are d-by-d matrices; for Pauli measurements the classical shadow is a product of n single-qubit matrices and already fits in O(n) space, so there is no exponential space problem there. The quadratic speedup is in the dimension d and requires F = polylog(d) (the gate count of each observable) together with bounded Hilbert-Schmidt norm; for observables with exponential gate count the claimed runtime advantage disappears, and the comparison is against the standard classical implementation of [4] that materializes the shadow matrices. For Pauli measurements the comparison is different: classical k-local CST costs O(16^k M log M), whereas Theorem 3 gives O(9^k k B F M log M), an exponential-in-k separation rather than a quadratic one. These scope conditions should be stated in the abstract and conclusion so that the claims are checkable as written.
  3. [Theorem 2; Theorem 3; Corollary 1] The theorem statements omit the accuracy parameters that are part of Problem 1. Theorem 2 claims 'O(B log M) copies' and 'O-tilde(d B F M)' time with no epsilon or delta, yet Problem 1 requires error at most epsilon with probability at least 1-delta, and no procedure can meet that requirement with a cost independent of epsilon and delta. The proof of Theorem 2 contains the correct dependencies (N = 8 log(M/delta) Var(Y_{1,j})/epsilon^2, K = 2 log(M/delta)), and Theorem 3 explicitly says it is 'ignoring epsilon, delta'; Corollary 1 likewise drops them. All three statements should carry the (1/epsilon^2) log(M/delta) factors so that the theorems are checkable against Problem 1 as stated.
minor comments (6)
  1. [Section III-A (proof of Theorem 2)] The proof says the sample requires storing 'the description of U_j', but the unitary sampled in the first phase is U_i; this is a typo.
  2. [Section III-B (Lemma 4)] The displayed derivation of E[Y^2_{i,j}|U_i, b_i] is typeset in a garbled way, and the step that replaces X^2_{i,j} with a trace involving O_j^2 uses the identity X^2 = tr(U-dagger |c><c| U O_j^2) for a projective measurement of O_j; it should be written out explicitly, and the operator norm ||O_j|| should be defined at first use.
  3. [References] Reference [19] is cited for the claim that one can sample uniformly from the Clifford group on n qubits in O(n^8) classical time with O(n^2)-gate circuit descriptions; the standard reference for this task is Koenig and Smolin, J. Math. Phys. 55, 122202 (2014), and the authors should verify that [19] indeed proves what is claimed.
  4. [Theorem 2 (input model)] The input model 'each implemented with at most F quantum gates' should be defined precisely, in particular how a non-unitary Hermitian observable O_j is measured (e.g., via a block-encoding or ancilla-assisted circuit) and whether F counts the gates of that measurement circuit; otherwise the per-shot cost m F in the proof of Theorem 2 is not well defined.
  5. [Corollary 1] Corollary 1 states a time bound O(d r lambda^2 M log M) with no dependence on the gate complexity F that appears in Theorem 2, and also drops epsilon and delta; it should be restated with those dependencies, or with the assumption F = O(polylog(d)) made explicit.
  6. [Section IV] The paper does not discuss the resource trade-off that QCQC replaces classical post-processing with additional quantum circuit executions (about m times M shots per shadow snapshot, m = 2(d+1) for Clifford and (9/4)^k for Pauli, on top of the N initial measurements); a sentence acknowledging this added quantum hardware usage would contextualize the space and time gains against the appeal of minimal quantum hardware in CST.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: QCQC estimator is the standard CST inverse-channel estimator with traces moved to quantum measurements; remaining self-citations are not load-bearing.

full rationale

The derivation of Lemmas 1-4 and Theorems 2-3 does not fit parameters to data and does not use any output to define its inputs. The estimator Y_{i,j}=(d+1)X_{i,j}-tr(O_j) is unbiased because E[X]=tr(E[U†|b><b|U]O)=tr(D_{1/(d+1)}(rho)O), and the inverse channel M^{-1} is exactly the external CST construction of Huang et al. [4]. Variance bounds use the shadow-norm bounds (3) and (5) and the depolarizing-channel identity D_{1/(d+1)} from [4], all external published results; no step is justified solely by the authors' own prior work. The only self-citations are [8] (Quantum data sketches, Zhang-Heidari) and [10] (Heidari-Szpankowski) in the related-work paragraph, and neither is used to prove Theorem 2 or Theorem 3. The choice m=2(d+1) or m=(9/4)^k is set by closing the variance proof, not fitted to the target observable values. A separate correctness concern, not circularity, is that the Clifford protocol requires the classical number tr(O_j) to form Y_{i,j}; for observable circuits this is not guaranteed to be efficiently computable, but this is an unsupported input assumption rather than a reduction of the claim to its own output.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The protocol introduces no new physical entities. The resource improvements come from moving trace evaluation onto a quantum computer. The hand-chosen shot counts m and the 1/3 bit-flip probability are the main adjustable parameters; they are set by variance analysis, not empirical fit.

free parameters (3)
  • m_Clifford_shots = 2(d+1)
    Set analytically in Lemma 2 to balance the first variance term against the shadow norm; the time complexity scales linearly with this m.
  • m_Pauli_shots = (9/4)^k
    Set analytically in Theorem 3 for k-local observables to bound the variance by 2*4^k B; not fitted to data, but a design choice in the algorithm.
  • bit_flip_probability = 1/3
    Chosen in Section III-B so that the expectation of the randomized projector yields 3|b><b| - I, matching the Pauli shadow snapshot.
assumptions (4)
  • domain assumption The Clifford shadow channel is the depolarizing channel D_{1/(d+1)}(rho).
    Used in Lemma 2 and Lemma 1; taken from [4].
  • domain assumption The shadow norm bounds ||O||_shadow <= 2^k ||O||_infinity (Pauli) and ||O||_shadow <= sqrt(3 tr(O^2)) (Clifford) from [4].
    Used in Lemma 2 and Lemma 4 to bound the second variance term.
  • domain assumption Random n-qubit Clifford circuits can be sampled in O(n^8) time and implemented with O(n^2) gates, per [19].
    Basis for the polylog(d) factors in the runtime of Theorem 2.
  • ad hoc to paper Observables O_j are provided as quantum circuits with F gates and with classically computable traces tr(O_j).
    Needed to form Y and to keep runtime linear in F; not stated as an explicit theorem condition.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Classical Shadow Tomography Using Quantum Computation." pith.science (2026). https://pith.science/paper/U2OMDX53

@misc{pith2026250514953,
  author       = {Pith},
  title        = {Pith review of: Improved Classical Shadow Tomography Using Quantum Computation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U2OMDX53}},
  note         = {Machine review of arXiv:2505.14953}
}
read the original abstract

Classical shadow tomography (CST) involves obtaining enough classical descriptions of an unknown state via quantum measurements to predict the outcome of a set of quantum observables. CST has numerous applications, particularly in algorithms that utilize quantum data for tasks such as learning, detection, and optimization. This paper introduces a new CST procedure that exponentially reduces the space complexity and quadratically improves the running time of CST with single-copy measurements. The approach utilizes a quantum-to-classical-to-quantum process to prepare quantum states that represent shadow snapshots, which can then be directly measured by the observables of interest. With that, calculating large matrix traces is avoided, resulting in improvements in running time and space complexity. The paper presents analyses of the proposed methods for CST, with Pauli measurements and Clifford circuits.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 17 canonical work pages

  1. [4]

    Predicting many properties of a quantum system from very few measurements,

    H.-Y . Huang, R. Kueng, and J. Preskill, “Predicting many properties of a quantum system from very few measurements,”Nature Physics 16, 1050–1057 (2020), Feb. 2020. 10

    work page 2020

  2. [1]

    Sample-optimal tomography of quantum states,

    J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, “Sample-optimal tomography of quantum states,” inProceedings of the forty-eighth annual ACM symposium on Theory of Computing. ACM, jun 2016

    work page 2016

  3. [2]

    Some estimates of the information transmitted by quantum communication channels,

    A. S. Holevo, “Some estimates of the information transmitted by quantum communication channels,”Problems of Information Transmission, vol. 9, no. 3, pp. 177–183, 1973

    work page 1973

  4. [3]

    Shadow tomography of quantum states,

    S. Aaronson, “Shadow tomography of quantum states,” inProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ser. STOC 2018. New York, NY , USA: Association for Computing Machinery, 2018, p. 325–338

    work page 2018

  5. [5]

    Adaptive pauli shadows for energy estimation,

    C. Hadfield, “Adaptive pauli shadows for energy estimation,” 2021, arXiv:2105.12207 [quant-ph]

    arXiv 2021

  6. [6]

    Measurements of quantum hamiltonians with locally-biased classical shadows,

    C. Hadfield, S. Bravyi, R. Raymond, and A. Mezzacapo, “Measurements of quantum hamiltonians with locally-biased classical shadows,” 2020, arXiv:2006.15788 [quant-ph]

    arXiv 2020

  7. [7]

    Information-theoretic bounds on quantum advantage for learning,

    H.-Y . Huang, R. Kueng, and J. Preskill, “Information-theoretic bounds on quantum advantage for learning,”Physical Review Letters, vol. 127, p. 030503, 2021

    work page 2021

  8. [8]

    Quantum Data Sketches

    Q. Zhang and M. Heidari, “Quantum data sketches,” inInternational Conference on Database Theory (ICDT), arXiv:2501.06705, 2025

    work page Pith review arXiv 2025

Show all 19 references
  1. [9]

    Learning quantum states from their classical shadows,

    H.-Y . Huang, “Learning quantum states from their classical shadows,”Nature Reviews Physics, vol. 4, no. 2, p. 81, 2022

    2022

  2. [10]

    New bounds on quantum sample complexity of measurement classes,

    M. Heidari and W. Szpankowski, “New bounds on quantum sample complexity of measurement classes,” in2024 IEEE International Symposium on Information Theory (ISIT). IEEE, Jul. 2024, pp. 1515–1520

    2024

  3. [11]

    Quantum versus classical proofs and advice,

    S. Aaronson and G. Kuperberg, “Quantum versus classical proofs and advice,” inProceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07). IEEE, 2007, pp. 115–128

    2007

  4. [12]

    Optimal tradeoffs for estimating pauli observables,

    S. Chen, W. Gong, and Q. Ye, “Optimal tradeoffs for estimating pauli observables,” in2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), 2024, pp. 1086–1105

    2024

  5. [13]

    R. King, D. Gosset, R. Kothari, and R. Babbush,Triply efficient shadow tomography, pp. 914–946

  6. [14]

    Shadow tomography based on informationally complete positive operator-valued measure,

    A. Acharya, S. Saha, and A. M. Sengupta, “Shadow tomography based on informationally complete positive operator-valued measure,” Phys. Rev. A, vol. 104, p. 052418, Nov 2021

    2021

  7. [15]

    Shallow shadows: Expectation estimation using low-depth random clifford circuits,

    C. Bertoni, J. Haferkamp, M. Hinsche, M. Ioannou, J. Eisert, and H. Pashayan, “Shallow shadows: Expectation estimation using low-depth random clifford circuits,” 2024

    2024

  8. [16]

    Classical shadow tomography for continuous variables quantum systems,

    S. Becker, N. Datta, L. Lami, and C. Rouze, “Classical shadow tomography for continuous variables quantum systems,”IEEE Transactions on Information Theory, vol. 70, no. 5, pp. 3427–3452, 2024

    2024

  9. [17]

    Classical shadows with noise,

    D. E. Koh and S. Grewal, “Classical shadows with noise,”Quantum, vol. 6, p. 830, 2022

    2022

  10. [18]

    Y .-C. Chen. A short note on the median-of-means estimator

  11. [19]

    Quantum data hiding,

    D. DiVincenzo, D. Leung, and B. Terhal, “Quantum data hiding,”IEEE Transactions on Information Theory, vol. 48, no. 3, pp. 580–598, Mar. 2002. 11

    2002

Pith tools

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