Pith. sign in

REVIEW 2 major objections 6 minor 29 references

State-Based Classical Shadows

T0 review · 2 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Pith's one-line read Classical shadows can be built from random states instead of random unitaries, with a Bell-basis measurement as the only online step.

desk verdict A genuinely new state-based twist on classical shadows with a solid information-theoretic core, but the computational half is a conditional reduction to an uninstantiated pseudo-design and still lacks a workable classical post-processing step. read the letter →

arxiv 2507.10362 v1 pith:YA646CVI submitted 2025-07-14 quant-ph

classification quant-ph MSC 81P6868Q12
keywords classicalshadowsBell-basismeasurementstatet-designspseudo-designsquantumpseudorandomnessshadowtomographyconstant-depthsnapshotgenerationmedianofmeans
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

Classical shadow tomography normally works by applying random unitaries to copies of an unknown state and measuring in the computational basis. This paper shows that the random unitary can be replaced by a random auxiliary state: entangle the unknown state with an independently prepared auxiliary state, measure both in the Bell basis, and record the classical snapshot $\hat{\rho} = (2^n+1)|\zeta_{x,z}^*\rangle\langle\zeta_{x,z}^*| - I$. If the auxiliary distribution is a relative or additive approximate state 3-design, the snapshot estimator approximates the expectation of an arbitrary observable with controlled bias and variance; the additive guarantee requires approximation error $\epsilon \ll 2^{-2n}$ and works for any Hermitian observable. If the distribution is a state 3-pseudo-design, then efficiently implementable observables can still be estimated, so computational classical shadow tomography becomes possible. The online quantum part of the procedure is only a Bell-basis measurement, which is constant depth.

What carries the argument

The central object is the state-based snapshot channel $M_S$, which maps an input state $\rho$ to the expected projection onto the conjugated auxiliary state: $M_S(\rho) = \mathbb{E}_{\zeta\sim S}\sum_{x,z}\Pr[x,z\,|\,\zeta]\,|\zeta_{x,z}^*\rangle\langle\zeta_{x,z}^*|$. The analysis compares the second and third moments of $S$ with the corresponding Haar moments, so both the bias and the variance of $\mathrm{Tr}(O\hat{\rho})$ are controlled by how close $S$ is to a state 3-design. For the pseudo-design result, the paper constructs two small quantum distinguishers (Figure 2) that compute the estimator's expectation and variance using three copies of $\zeta$ and black-box access to the conjugate observable $O^*$; a pseudo-design that fools circuits of size $O(\max(t,n))$ therefore yields valid shadows for all observables of complexity $t$.

What would settle it

Compute the third-moment trace distance $\left\|\mathbb{E}_{k\sim K}[|\psi_k\rangle\langle\psi_k|^{\otimes 3}]-\int|\phi\rangle\langle\phi|^{\otimes 3}d\mu(\phi)\right\|_1$ for the scalable pseudorandom families of [BS20] and [LQS+23]. If any family has distance not far below $2^{-2n}$, or if a distinguisher of size $O(\max(t,n))$ achieves advantage $\epsilon \geq 2^{-2n}$ against it, then Theorem 3.3's error bound cannot be met and the computational claim is vacuous.

Watch

Extended reading notes

Core claim

The paper's central claim is that the building block of classical shadow tomography can be a distribution over states rather than over unitaries. Concretely, sampling $|\zeta\rangle$ from the distribution $S$, measuring $\rho \otimes |\zeta\rangle$ in the Bell basis, and outputting $\hat{\rho}=(2^n+1)|\zeta_{x,z}^*\rangle\langle\zeta_{x,z}^*|-I$ gives an unbiased estimator when $S$ is the Haar state distribution, and the inverse map used is the depolarizing-channel inverse $M^{-1}(A)=(2^n+1)A-\mathrm{Tr}(A)I$. The paper proves that a relative $\epsilon$-approximate state 3-design yields error $\gamma+2\epsilon\,\mathrm{Tr}(O)$ for positive $O$ (Theorem 3.1), an additive $\epsilon$-approximate state 3-design yields error $\gamma+(2^n+1)\epsilon\|O\|_\infty$ for any Hermitian $O$ (Theorem 3.2), and a $(T,\epsilon)$-state 3-pseudo-design with $T=c\,\max(t,n)$ yields error $\gamma+2(2^n+1)\epsilon\|O\|_\infty$ for observables of circuit complexity $t$ (Theorem 3.3). This is, to the authors' knowledge, the first computational treatment of classical shadows, and it also implies that real-valued pseudorandom state constructions cannot achieve the scalable pseudo-design parameter $2^{-2n}$.

Load-bearing premise

The computational guarantee rests on the existence of a state 3-pseudo-design whose quantum distinguishers of size $O(\max(t,n))$ have advantage $\epsilon \ll 2^{-2n}$, and the paper shows no known construction reaches this regime; the classical estimate $\mathrm{Tr}(O\hat{\rho})$ must also be efficiently computable from the seed, a resource the paper does not specify.

Editorial extensions

If this is right

  • The online snapshot-generation circuit is a constant-depth Bell-basis measurement, so the input state is disturbed by only a few layers of elementary gates; the auxiliary state can be prepared offline, potentially with fault tolerance and post-selection.
  • Every guarantee previously obtained with approximate unitary designs is recovered using only approximate state designs, a weaker and potentially cheaper building block.
  • An additive approximate state 3-design with $\epsilon \ll 2^{-2n}$ is enough for shadows of any Hermitian observable, not just positive ones, and the paper maps exactly when the additive analysis beats the relative one.
  • For efficiently computable observables, state pseudo-designs replace information-theoretic designs, opening a computational version of classical shadow tomography.
  • The pseudo-design result rules out real-valued scalable pseudorandom state constructions: their distinguishing advantage cannot reach $2^{-2n}$.

Reading between the lines

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

  • The paper leaves open whether known scalable pseudorandom state families actually achieve the $2^{-2n}$ advantage its theorems need; an explicit construction or a matching lower bound for a concrete candidate would settle whether the computational result is non-vacuous.
  • The resource model for the classical post-processing is under-specified: for a pseudorandom $\zeta$ and an arbitrary efficiently implementable $O$, evaluating $\mathrm{Tr}(O\hat{\rho})$ from the seed may itself be intractable, so the practical speedup may be limited to observables whose overlap with the snapshot matrix is easy to compute.
  • A natural testable extension is to run the Bell-basis snapshot protocol with a small, classically generated approximate state 3-design in a real device and compare the empirical bias and variance with the paper's bounds; this would validate the additive versus relative trade-off in practice.
  • The state-based viewpoint may connect to other settings where state designs already exist for free, such as analog quantum simulators, extending the approach beyond the gate-based digital setting.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

Summary. The paper proposes a state-based framework for classical shadow tomography in which the unknown state ρ is measured in the Bell basis against an auxiliary state ζ sampled from a distribution S. The resulting snapshot is ρ̂ = (2^n+1)|ζ*_{x,z}⟩⟨ζ*_{x,z}| − I, and the estimator Tr(Oρ̂) is used to predict Tr(Oρ). The authors prove bias and variance bounds when S is a relative or additive approximate state 3-design (Theorems 3.1, 3.2, 4.4, 4.6), and a computational variant when S is generated by a state 3-pseudo-design generator (Theorems 3.3, 4.7). The online part of the protocol is a constant-depth Bell measurement, which is the main efficiency innovation. An appendix compares additive and relative approximate state designs.

Significance. If the statistical theorems are correct, the paper introduces a genuinely new design axis for classical shadows: replacing unitary distributions with state distributions and obtaining constant online depth. The analysis in Propositions 4.1–4.3 and Lemma 4.5 is explicit and largely self-contained, and the additive/relative comparison in Appendix A is a useful clarification. The computational contribution, however, is currently conditional in two important ways: it relies on an uninstantiated (T,ε)-state 3-pseudo-design generator with exponentially small ε, and it does not define the classical post-processing model for evaluating Tr(Oρ̂) from the pseudo-design seed. These issues do not affect the information-theoretic theorems, but they substantially weaken the advertised claim that pseudorandom state families suffice for efficiently computable observables.

major comments (2)
  1. [Definition 2.7; Theorems 3.3 and 4.7] The main computational theorems are conditional on a (T,ε)-state 3-pseudo-design generator whose advantage ε must be exponentially small in n for the bounds to be meaningful: the variance term in Theorem 3.3 contains ε(2^n+1)^2, so useful sample complexity requires ε ≪ 2^{-2n}. The manuscript cites [BS20,LQS+23] as candidate instantiations, but Section 1 ('The Computational Setting') explicitly states that the authors are 'unable to ascertain advantageous properties of using these specific constructions,' and no theorem or proof shows that any known construction satisfies Definition 2.7 at this quantitative advantage against the stated non-uniform quantum distinguishers. As written, Theorem 3.3 is therefore a reduction from shadow estimation to a new, uninstantiated primitive rather than a demonstrated algorithmic result. The paper should either provide a construction or a formal reduction from a known primitive at the required parameters, or restate the computational contribution as a conditional reduction and carefully explain the status of the assumption.
  2. [Section 3 (snapshot definition, footnote 8) and Remark 2] The estimator in the computational setting requires the classical evaluation of Tr(Oρ̂) = (2^n+1)⟨ζ*_{x,z}|O|ζ*_{x,z}⟩ − Tr(O) from the classical seed k and the measurement outcomes x,z. Footnote 8 says this can be done analytically 'given a classical description of the matrix ρ̂,' but for a pseudo-design the description of |ζ*_{x,z}⟩ is the key k together with the StateGen circuit, not an explicit matrix. For a general polynomial-size observable O, computing the inner product ⟨ζ*_{x,z}|O|ζ*_{x,z}⟩ is not shown to be classically efficient and can in general be #P-hard. The paper never defines the resource model for this post-processing step. To support the claim that pseudorandom state families suffice for efficiently computable observables, the authors must either exhibit an efficient classical algorithm for this step for a specified class of observables, or explicitly state the sense in which the snapshot is classical and allow for possibly exponential classical post-processing.
minor comments (6)
  1. [Theorem 4.6 and Lemma 4.5] Lemma 4.5 and Theorem 4.6 are stated for 'any positive observable,' while Theorem 3.2 claims the same result for any Hermitian observable; the proofs appear to work for Hermitian observables, so the statements should be aligned.
  2. [Section 1, 'The Computational Setting'] The assertion that real-valued states cannot be used for classical shadows, and the claimed implication that real-valued PRS constructions cannot achieve the 'scalability' property at advantage 2^{-2n}, are stated without proof. Since this is presented as a new limitation result, the authors should include the straightforward argument or an explicit citation to a proof.
  3. [Theorem 3.3] The condition 'if T = c·max(t,n)' should be 'if T ≥ c·max(t,n)', since larger T makes the pseudorandomness assumption stronger and the distinguishers in Theorem 4.7 have size O(max(t,n)).
  4. [Proof of Theorem 4.4] The sentence 'for all x,z, {|ψ*_{k,x,z}|}_{k∼K} is also an approximate 2-design' is terse; a one-line justification using unitary invariance of the Haar measure and invariance under complex conjugation would improve readability.
  5. [Figure 2] The gate label 'Zz Xx' in Figure 2 is used inconsistently with the text's X^xZ^z notation; please disambiguate the order of the Pauli corrections.
  6. [Throughout] There are several typographical issues, including the stray 's' at the start of Theorem 4.4 and malformed formatting in some displayed equations; a careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the shadow-estimation guarantees are derived from explicit state-design and pseudo-design assumptions via a distinguisher reduction.

full rationale

The paper's central derivation is self-contained. The snapshot estimator rho_hat = (2^n+1)|zeta*_{x,z}><zeta*_{x,z}| - I is the inverse of the depolarizing channel that arises when the auxiliary distribution is the Haar measure (Eq. 8), and the error bounds in Theorems 3.1-3.3 follow from explicit bias/variance decompositions (Propositions 4.1 and 4.2) that compare the auxiliary distribution S with the Haar measure. The approximation parameter epsilon is an input assumption, and the bias/variance bounds are derived consequences, not re-statements of the assumption. For the computational theorem, the proof constructs explicit distinguishers (Figure 2) and shows that any distinguishing advantage bound epsilon for a (T,epsilon)-state 3-pseudo-design translates into a shadow-estimation error bound; this is a standard conditional reduction, not a definitional identity. Self-citations (BS20, BS19, JMW23) are used only as possible instantiations or examples, and the paper explicitly disclaims being able to ascertain advantageous properties of the cited scalable pseudorandom-state constructions, so they are not load-bearing. No uniqueness theorem is imported from the authors' prior work, and no fitted parameter is renamed as a prediction. The main genuine limitations are correctness/instantiation risks rather than circularity: the paper does not prove that any known pseudorandom-state construction satisfies Definition 2.7 with epsilon much smaller than 2^{-2n}, and Remark 2 notes that computing the inverse map for general distributions may be hard, with the classical post-processing resource model for evaluating Tr(O rho_hat) left unspecified. These gaps do not make the derivation circular.

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

No numerical constants are fitted to data; the epsilon parameters are inputs to the theorems and the constant c in Theorem 4.7 is a universal constant. No new physical entities, forces, particles, or dimensions are introduced. The new objects, state-based shadows and state pseudo-designs, are formal definitions rather than postulated physical entities.

assumptions (5)
  • standard math Haar measure moment identities from Proposition 2.1 of [GKK15].
    Used in Proposition 4.1 and the variance analysis to evaluate Haar integrals over two and three copies of a random state.
  • standard math Median-of-means concentration bound [NY83, JVV86].
    Used in the proof of Theorems 3.1, 3.2, and 3.3 to convert single-snapshot bias and variance bounds into an aggregated estimation guarantee.
  • domain assumption Existence and security of (T,epsilon)-state t-pseudo-design generators with exponentially small epsilon.
    Theorem 3.3 and Theorem 4.7 are conditional on such a generator. The paper cites BS20 and LQS+23 but does not construct or verify the required 2^{-2n}-scale advantage.
  • domain assumption The gate set is closed under complex conjugation, and an observable and its conjugate have the same circuit complexity.
    Needed in Theorem 4.7 so that the conjugate observable O* can be used inside the distinguishers with no additional asymptotic overhead.
  • domain assumption Efficient sampleability of state designs.
    Used in Section 1 to argue that the total complexity of preparing the auxiliary state is no worse than that of applying a unitary design; this relies on prior constructions from the unitary-design literature.

how reviews work

0 comments
Cite this review

Pith. "Pith review of State-Based Classical Shadows." pith.science (2026). https://pith.science/paper/YA646CVI

@misc{pith2026250710362,
  author       = {Pith},
  title        = {Pith review of: State-Based Classical Shadows},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YA646CVI}},
  note         = {Machine review of arXiv:2507.10362}
}
read the original abstract

Classical Shadow Tomography (Huang, Kueng and Preskill, Nature Physics 2020) is a method for creating a classical snapshot of an unknown quantum state, which can later be used to predict the value of an a-priori unknown observable on that state. In the short time since their introduction, classical shadows received a lot of attention from the physics, quantum information, and quantum computing (including cryptography) communities. In particular there has been a major effort focused on improving the efficiency, and in particular depth, of generating the classical snapshot. Existing constructions rely on a distribution of unitaries as a central building block, and research is devoted to simplifying this family as much as possible. We diverge from this paradigm and show that suitable distributions over \emph{states} can be used as the building block instead. Concretely, we create the snapshot by entangling the unknown input state with an independently prepared auxiliary state, and measuring the resulting entangled state. This state-based approach allows us to consider a building block with arguably weaker properties that has not been studied so far in the context of classical shadows. Notably, our cryptographically-inspired analysis shows that for \emph{efficiently computable} observables, it suffices to use \emph{pseudorandom} families of states. To the best of our knowledge, \emph{computational} classical shadow tomography was not considered in the literature prior to our work. Finally, in terms of efficiency, the online part of our method (i.e.\ the part that depends on the input) is simply performing a measurement in the Bell basis, which can be done in constant depth using elementary gates.

Figures

Figures reproduced from arXiv: 2507.10362 by the authors.

Figure 1
Figure 1. Description of a single experiment in the shadow tomography procedure. [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Description of the distinguishers. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 23 canonical work pages

  1. [1]

    A survey on the complexity of learning quantum states

    Anurag Anshu and Srinivasan Arunachalam. A survey on the complexity of learning quantum states. Nature Reviews Physics , 6(1):59--69, 2024

  2. [2]

    Shadow tomography of quantum states

    Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2018, page 325–338, New York, NY, USA, 2018. Association for Computing Machinery

  3. [3]

    Scalable and flexible classical shadow tomography with tensor networks

    Ahmed A Akhtar, Hong-Ye Hu, and Yi-Zhuang You. Scalable and flexible classical shadow tomography with tensor networks. Quantum , 7:1026, 2023

  4. [4]

    Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. Local random quantum circuits are approximate polynomial-designs. Communications in Mathematical Physics , 346(2):397–434, August 2016

  5. [5]

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

    Christian Bertoni, Jonas Haferkamp, Marcel Hinsche, Marios Ioannou, Jens Eisert, and Hakop Pashayan. Shallow shadows: Expectation estimation using low-depth random clifford circuits. Physical Review Letters , 133(2):020602, 2024

  6. [6]

    Universal quantum computation with ideal clifford gates and noisy ancillas

    Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Physical Review A—Atomic, Molecular, and Optical Physics , 71(2):022316, 2005

  7. [7]

    (pseudo) random quantum states with binary phase

    Zvika Brakerski and Omri Shmueli. (pseudo) random quantum states with binary phase. In Theory of Cryptography - 17th International Conference, TCC 2019 , LNCS, pages 229--250. Springer, 2019

  8. [8]

    Scalable pseudorandom quantum states

    Zvika Brakerski and Omri Shmueli. Scalable pseudorandom quantum states. In Annual International Cryptology Conference , pages 417--440. Springer, 2020

Show all 29 references
  1. [9]

    Pseudorandomness from subset states

    Tudor Giurgica - Tiron and Adam Bouland. Pseudorandomness from subset states. CoRR , abs/2312.09206, 2023

  2. [10]

    A partial derandomization of phaselift using spherical designs

    David Gross, Felix Krahmer, and Richard Kueng. A partial derandomization of phaselift using spherical designs. Journal of Fourier Analysis and Applications , 21(2):229--266, 2015

  3. [11]

    Aram W. Harrow. The church of the symmetric subspace, 2013

  4. [12]

    Classical shadow tomography with locally scrambled quantum dynamics

    Hong-Ye Hu, Soonwon Choi, and Yi-Zhuang You. Classical shadow tomography with locally scrambled quantum dynamics. Physical Review Research , 5(2):023027, 2023

  5. [13]

    Efficient local classical shadow tomography with number conservation

    Sumner N Hearth, Michael O Flynn, Anushya Chandran, and Chris R Laumann. Efficient local classical shadow tomography with number conservation. Physical Review Letters , 133(6):060802, 2024

  6. [14]

    Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu

    Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory , 63(9):5628--5641, 2017

  7. [15]

    Predicting many properties of a quantum system from very few measurements

    Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics , 16(10):1050--1057, 2020

  8. [16]

    Bounds for the quantity of information transmitted by a quantum communication channel

    Alexander Semenovich Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii , 9(3):3--11, 1973

  9. [17]

    Pseudorandom quantum states

    Zhengfeng Ji, Yi - Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III ...

  10. [18]

    Subset states and pseudorandom states

    Fernando Granha Jeronimo, Nir Magrafta, and Pei Wu. Subset states and pseudorandom states. CoRR , abs/2312.15285, 2023

  11. [19]

    Jerrum, Leslie G

    Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science , 43:169--188, 1986

  12. [20]

    Commitments from quantum one-wayness

    Dakshita Khurana and Kabir Tomer. Commitments from quantum one-wayness. Cryptology ePrint Archive, Paper 2023/1620, 2023

  13. [21]

    Shadow process tomography of quantum channels

    Jonathan Kunjummen, Minh C Tran, Daniel Carney, and Jacob M Taylor. Shadow process tomography of quantum channels. Physical Review A , 107(4):042403, 2023

  14. [22]

    Quantum pseudorandom scramblers

    Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. Quantum pseudorandom scramblers. arXiv preprint arXiv:2309.08941 , 2023

  15. [23]

    Shadow tomography from emergent state designs in analog quantum simulators

    Max McGinley and Michele Fava. Shadow tomography from emergent state designs in analog quantum simulators. Physical Review Letters , 131(16):160601, 2023

  16. [24]

    A. S. Nemirovsky and D. B. Yudin. Problem complexity and method efficiency in optimization . A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, Translated from the Russian and with a preface by E. R. Dawson, Wiley-Interscience Series in Discrete Mathematics, 1983

  17. [25]

    Quantum computation with realistic magic-state factories

    Joe O'Gorman and Earl T Campbell. Quantum computation with realistic magic-state factories. Physical Review A , 95(3):032338, 2017

  18. [26]

    Efficient quantum tomography

    Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing , STOC '16, page 899–912, New York, NY, USA, 2016. Association for Computing Machinery

  19. [27]

    Random unitaries in extremely low depth

    Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. Random unitaries in extremely low depth. arXiv preprint arXiv:2407.07754 , 2024

  20. [28]

    Wang, Y.-A

    Chao Song, Kai Xu, Wuxin Liu, Chuiping Yang, Shi-Biao Zheng, Hui Deng, Qiwei Xie, Keqiang Huang, Qiujiang Guo, Libo Zhang, Pengfei Zhang, Da Xu, Dongning Zheng, Xiaobo Zhu, H. Wang, Y.-A. Chen, C.-Y. Lu, Siyuan Han, and Jian-Wei Pan. 10-qubit entanglement and parallel logic op...

  21. [29]

    Experimental quantum state measurement with classical shadows

    Ting Zhang, Jinzhao Sun, Xiao-Xu Fang, Xiao-Ming Zhang, Xiao Yuan, and He Lu. Experimental quantum state measurement with classical shadows. Physical Review Letters , 127(20):200501, 2021

Pith tools

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