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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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)
- [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.
- [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.
- [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)).
- [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.
- [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.
- [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
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
assumptions (5)
- standard math Haar measure moment identities from Proposition 2.1 of [GKK15].
- standard math Median-of-means concentration bound [NY83, JVV86].
- domain assumption Existence and security of (T,epsilon)-state t-pseudo-design generators with exponentially small epsilon.
- domain assumption The gate set is closed under complex conjugation, and an observable and its conjugate have the same circuit complexity.
- domain assumption Efficient sampleability of state designs.
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
Reference graph
Works this paper leans on
-
[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
work page 2024
-
[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
work page 2018
-
[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
work page 2023
-
[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
work page 2016
-
[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
work page 2024
-
[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
work page 2005
-
[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
work page 2019
-
[8]
Scalable pseudorandom quantum states
Zvika Brakerski and Omri Shmueli. Scalable pseudorandom quantum states. In Annual International Cryptology Conference , pages 417--440. Springer, 2020
work page 2020
Show all 29 references
-
[9]
Pseudorandomness from subset states
Tudor Giurgica - Tiron and Adam Bouland. Pseudorandomness from subset states. CoRR , abs/2312.09206, 2023
2023 arXiv
-
[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
2015
-
[11]
Aram W. Harrow. The church of the symmetric subspace, 2013
2013
-
[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
2023
-
[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
2024
-
[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
2017
-
[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
2020
-
[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
1973
-
[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 ...
2018
-
[18]
Subset states and pseudorandom states
Fernando Granha Jeronimo, Nir Magrafta, and Pei Wu. Subset states and pseudorandom states. CoRR , abs/2312.15285, 2023
2023 arXiv
-
[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
1986
-
[20]
Commitments from quantum one-wayness
Dakshita Khurana and Kabir Tomer. Commitments from quantum one-wayness. Cryptology ePrint Archive, Paper 2023/1620, 2023
2023
-
[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
2023
-
[22]
Quantum pseudorandom scramblers
Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. Quantum pseudorandom scramblers. arXiv preprint arXiv:2309.08941 , 2023
2023 arXiv
-
[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
2023
-
[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
1983
-
[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
2017
-
[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
2016
-
[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
2024 arXiv
-
[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...
2017
-
[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
2021
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.