{"id":"ef4787ca-2f2d-4848-ab00-9d97873a1621","arxiv_id":"2507.10362","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Replacing random unitaries with random auxiliary states in a Bell-basis measurement gives classical shadows whose guarantees hold for approximate state designs and even for pseudorandom state families.","lead":"This paper proposes a new way to make classical shadows of quantum states: entangle the unknown state with a pre-prepared random auxiliary state and measure in the Bell basis, instead of applying a random unitary to the state. For efficiently computable observables, the authors show that pseudorandom state families are enough, opening a computational angle on shadow tomography.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The computational claim rests on an uninstantiated (T,ε)-state 3-pseudo-design with ε≪2^{-2n}; if no known PRS achieves this, Theorem 3.3 is vacuous, and even with such a generator the classical evaluation of Tr(O ρ̂) is not shown to be efficient.","rationale":"The information-theoretic results for relative and additive approximate state 3-designs appear internally consistent: the bias/variance proofs in Section 4 follow from the stated moment conditions, and the sample-complexity statements in Theorems 3.1 and 3.2 are plausible. The main risk is concentrated entirely in the computational extension, exactly where the reader placed it. Theorem 3.3 depends on a very strong primitive: a state 3-pseudo-design with exponentially small distinguishing advantage, against non-uniform quantum distinguishers of essentially the same size as the observable. The paper supports this only by an informal reference to scalable PRS constructions and an admitted inability to ascertain their properties; no proof of instantiation is supplied. This makes the headline computational claim potentially vacuous. A second, related gap is the classical usability of the snapshot: the paper stores (k,x,z) and defines ρ̂ through the exponentially large state |ζ*_{x,z}⟩, but no efficient classical procedure is given to compute Tr(Oρ̂) for general efficiently implementable O. In the standard classical-shadows paradigm, the snapshot must support classical post-processing; if the estimator must instead be evaluated by a quantum computer that regenerates |ζ*_{x,z}⟩, the paper should say so explicitly and adjust its claims. Both gaps are addressable in principle — by proving that a suitable pseudo-design exists and by specifying a coherent post-processing model — so I would not reject the paper outright, but the current formulation justifies conditional acceptance. My view is therefore close to the reader's, with a slight shift: the classical-evaluation gap is at least as load-bearing as the pseudo-design existence assumption, so I mark agreement as partial rather than full.","tokens_in":20773,"tokens_out":14726,"duration_ms":193824,"concrete_test":"Re-derive the security proof of the scalable pseudorandom-state construction [BS20] (or [LQS+23]) for the specific t=3, non-uniform, quantum-advice distinguishers AE and AVar from Figure 2, with circuit size T = c·max(t,n). If the proven distinguishing advantage is not ≤ 2^{-2n}/poly(n), then the hypothesis of Theorem 3.3 is not met by any available construction and the computational claim has no instantiation. Separately, check whether any cited or implicit algorithm computes ⟨ζ*_{x,z}|O|ζ*_{x,z}⟩ in poly(n,t) classical time from (k,x,z); if none is identified, the protocol does not yet constitute a classical shadow in the HKP sense.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorems 3.3 and 4.7 are conditional on a (T,ε)-state 3-pseudo-design generator with ε much smaller than 2^{-2n}, secure against non-uniform quantum distinguishers of size T = c·max(t,n). The paper cites [BS20,LQS+23] for scalable pseudorandom states but does not prove, or even state as a formal theorem, that any known construction satisfies Definition 2.7 at this exponentially small advantage; the introduction explicitly disclaims the ability to ascertain useful properties of those constructions. If no such generator exists, the computational contribution is vacuous. Independently, even granting such a generator, the snapshot estimator requires evaluating Tr(O ρ̂) = (2^n+1)⟨ζ*_{x,z}|O|ζ*_{x,z}⟩ - Tr(O) from the classical seed k and outcomes x,z. For an arbitrary polynomial-size observable O and a pseudorandom state |ζ_k⟩, no classical polynomial-time algorithm for this evaluation is provided; Remark 2 notes the inverse map is hard for general distributions, and the resource model for post-processing is left undefined. Thus the computational claim is either unsupported in its existence assumption or does not clearly yield a classical shadow.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21009,"tokens_out":24153,"duration_ms":275470,"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":[{"comment":"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":"Definition 2.7; Theorems 3.3 and 4.7"},{"comment":"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.","section":"Section 3 (snapshot definition, footnote 8) and Remark 2"}],"minor_comments":[{"comment":"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":"Theorem 4.6 and Lemma 4.5"},{"comment":"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.","section":"Section 1, 'The Computational Setting'"},{"comment":"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)).","section":"Theorem 3.3"},{"comment":"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.","section":"Proof of Theorem 4.4"},{"comment":"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.","section":"Figure 2"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The information-theoretic results appear sound and are a solid contribution. The computational section is the main point of contention: the paper's own disclaimer about not being able to ascertain properties of known PRS constructions, combined with the undefined classical post-processing step, means the advertised 'computational classical shadows' result is not yet established at the level claimed. If the journal is willing to accept a conditional reduction with an open instantiation, the authors should reframe the contribution accordingly and address the post-processing issue; otherwise the computational claims need substantial additional work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a paper I'd send to a referee, but the computational half needs major revision. The core idea—replace the random unitary with a random state, entangle and measure in the Bell basis, and build the snapshot as (2^n+1)|zeta*_{x,z}><zeta*_{x,z}| - I—is fresh and worth taking seriously. The information-theoretic part is the strongest: the distinguisher-based proof that additive approximate 3-designs suffice (Lemma 4.5) is clean, the bias/variance bounds are explicit, and the constant-depth online step is a genuine practical advantage. The appendix on additive vs. relative approximations is correct and useful. Credit also where it's due: the authors are honest about not being able to verify properties of known pseudorandom-state constructions.\n\nThe soft spots are real. First, Theorem 3.3 is conditional on a (T,epsilon)-state 3-pseudo-design with epsilon much smaller than 2^{-2n}. The paper cites [BS20, LQS+23] but gives no theorem that any known PRS satisfies Definition 2.7 at that advantage, and the introduction explicitly disclaims being able to tell. That makes the computational claim a reduction to an unnamed open problem, not a result. Second and more serious, the paper never defines the classical post-processing model for the pseudo-design case. To estimate Tr(O rho_hat) from the seed k and outcomes (x,z), you need to compute <zeta*_{x,z}|O|zeta*_{x,z}> classically. For a pseudorandom state, there is no known compact classical description, and the paper just says \"calculate when needed\" without saying how. Without a classical algorithm for this evaluation, the method is not evidently a classical shadow in the computational setting. Third, the real-valued impossibility claim in the introduction is asserted without proof; that's minor, but it should be proved or labeled a conjecture.\n\nOverall: the statistical framework is a legitimate contribution and should be published. The computational section is a research agenda, not a finished theorem. A serious referee should engage with the paper, but the authors need to either supply a working pseudo-design construction or state the exact assumption they need, and they must resolve the classical-evaluation question. I'd accept this for peer review with major-revision expectations, and I'd cite the information-theoretic part.","headline":"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.","tokens_in":664,"tokens_out":1055,"would_cite":true,"duration_ms":71176,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12"],"pacs":[],"model":"deepseek-v4-flash","headline":"Classical shadows can be built from random states instead of random unitaries, with a Bell-basis measurement as the only online step.","keywords":["classical shadows","Bell-basis measurement","state t-designs","state pseudo-designs","quantum pseudorandomness","shadow tomography","constant-depth snapshot generation","median of means"],"falsifier":"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.","tokens_in":20571,"feed_emoji":"⚛️","tokens_out":8277,"duration_ms":81703,"temperature":0.7,"pith_summary":"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.","feed_headline":"State-based shadows cut online work to a Bell measurement","feed_subtitle":"A random auxiliary state stands in for random unitaries, so one Bell-basis measurement suffices to snapshot an unknown state.","key_machinery":"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$.","core_discovery":"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}$.","pith_inferences":["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."],"forward_implications":["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}$."],"supporting_citations":[{"why":"Defines classical shadow tomography and supplies the unitary-design baseline and the median-of-means estimation framework this work generalizes.","marker":"[HKP20]"},{"why":"Introduces relative-approximate low-depth unitary designs, whose relative-approximation analysis is recovered here in the state-design setting.","marker":"[SHH24]"},{"why":"Cited as a scalable pseudorandom state construction that could instantiate the state 3-pseudo-design with the required tiny advantage.","marker":"[BS20]"},{"why":"Another scalable pseudorandom construction, cited alongside [BS20] as a candidate for the pseudo-design generator.","marker":"[LQS+23]"},{"why":"Introduces pseudorandom quantum states, the cryptographic notion that motivates the computational setting.","marker":"[JLS18]"},{"why":"Related prior work generating classical shadows by entangling the input with an ancilla register, which the present state-based framework simplifies.","marker":"[MF23]"},{"why":"Supplies the symmetric-subspace moment identities used to compute Haar moments and to convert additive approximation to relative approximation.","marker":"[Har13]"},{"why":"Supplies the two-copy Haar moment formula used in Propositions 2.1 and 4.1.","marker":"[GKK15]"},{"why":"Provides the median-of-means concentration bound used to aggregate snapshots.","marker":"[NY83]"}],"fun_headline_variants":["State-based shadows: one Bell measurement replaces unitary sampling","First computational classical shadows via pseudorandom states","Bell measurement only: classical shadows from random states","Replacing unitaries with states: constant-depth classical shadows"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["State-based shadows: one Bell measurement replaces unitary sampling","First computational classical shadows via pseudorandom states","Bell measurement only: classical shadows from random states","Replacing unitaries with states: constant-depth classical shadows"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000766,"raw_usage":{"total_tokens":3505,"prompt_tokens":1161,"completion_tokens":2344,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":777,"completion_tokens_details":{"reasoning_tokens":2282}},"tokens_in":777,"tokens_out":2344,"duration_ms":18463,"temperature":1.0,"reasoning_tokens":2282,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:35:05.339347+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}