{"id":"683e59d5-5135-4757-bc8f-7865dd6bf2a4","arxiv_id":"2501.09574","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A depth-adaptive fermionic classical shadow protocol achieves polynomial sample complexity at depth max{d_int^2/log n, d_int}, where d_int is the observable's interaction distance.","lead":"The authors propose an adaptive-depth fermionic classical shadow protocol that picks the random matchgate circuit depth from the observable's interaction distance, reducing circuit depth while keeping sample complexity polynomial. The result could make fermionic shadow tomography more practical on near-term quantum devices if the depth-to-accuracy trade-off holds.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central depth formula is conditional: Theorem 1 relies on an unproven sign assumption for the random-walk remainder, and the k-local extension is a numerical ansatz, so αS,d is not established to be Ω(1/poly(n)) at the claimed depth.","rationale":"The reader's verdict is CONDITIONAL, and my read supports that rather than moving to ACCEPT or REJECT. The paper is transparent that the 2-local lower bound is conditional on a numerical sign assumption, and its numerical experiments are consistent with the claimed behavior. However, the central claim in the abstract and Section III.D is stronger: it presents the depth formula as established for general k-local observables. The load-bearing gap is the unproven lower bound on αS,d itself; without it, the depth scaling has no consequence for sample complexity. The average-state issue identified by the reader is real but secondary: it limits the scope of the sample-complexity guarantee, whereas the αS,d gap threatens the core derivation. I therefore partially agree with the reader: the same family of unproven assumptions is noted in the rationale, but the weakest_assumption field highlights the state-averaging issue rather than the αS,d bound. No independent verification, machine-checked proof, or parameter-free derivation is provided at the critical step. The concrete test of exact enumeration for small n and d would either find a counterexample or substantially raise confidence in the assumption; absent such a test, CONDITIONAL is the appropriate verdict.","tokens_in":27452,"tokens_out":7235,"duration_ms":83626,"concrete_test":"Compute αS,d exactly by tensor-network contraction (Eqs. 14–16) for all 2-local Majorana strings S on n = 4, 6, ..., 16 qubits and for all depths d up to the claimed d*(n). For each tuple, verify the sign pattern (G30) by exact enumeration rather than random sampling, and record the minimum ratio αS,d/αL_S,d. If any sign violation or ratio below the constant 47/72 appears, Theorem 1's proof fails. If no violation appears, repeat the exact comparison for k = 4 and k = 6 against the ansatz α'_S,d (Eq. 22) to test whether the k-local extension is reliable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"All sample-complexity statements depend on Var[v] ≤ 1/αS,d (Eq. 11), so the central issue is whether αS,d is Ω(1/poly(n)) at d* = Θ(max{dint²/log n, dint}). The paper does not prove this. Appendix G's Theorem 1 states the 2-local lower bound only 'under the following assumption': R_{i,j}(μ,μ,t) ≤ 0 and R_{i,j}(μ,ν,t) ≥ 0 for μ ≠ ν (Eq. G30), i.e. the true walk is less diagonal and more off-diagonal than the SLRW. Lemma 7, which turns this into αS,d ≥ (47/72) max_{d'≤d} αL_S,d', is derived under that assumption. The only evidence is the random numerical sign plot in Fig. 8. If the assumption fails for some S,d in the target regime, αS,d can be much smaller than αL and the depth formula no longer implies efficient estimation. For k-local observables, Section III.D claims d = Θ(log n) suffices when dint = O(log n), but the supporting Appendix H is only a sketch that discards branches and multiplies per-step constants without a rigorous accounting, and the key approximation α'_S,d (Eq. 22) is validated only numerically for d > 2 log n. Thus the abstract's 'we establish' is stronger than what is proven: a conditional 2-local theorem plus k-local numerics. This concern is logically prior to the average-over-ρ caveat in Appendix C: even for average states, the αS,d lower bound must hold, and it is not proven.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces an adaptive-depth fermionic classical shadow (ADFCS) protocol. The protocol uses d-depth brickwork random matchgate circuits and adapts the depth to the observable H via its interaction distance d_int(H). The central claim is that, for k-local Majorana observables with d_int(H)=O(log n), depth d* = Θ(max{d_int(H)^2/log n, d_int(H)}) suffices to keep the key parameter α_{S,d} at order Ω(1/poly(n)), while maintaining the same order of sample complexity as the full matchgate FCS protocol. The analysis maps the tensor-network contraction for α_{S,d} to a random walk on a polynomial space, derives an analytical Poisson-summation formula for the 2-local case, and proposes a factorization ansatz for the k-local case. Numerical experiments on random states and on the Kitaev chain Hamiltonian support the depth-vs-accuracy tradeoff.","tokens_in":27872,"tokens_out":3941,"duration_ms":36840,"significance":"If the main claim holds, the paper addresses a concrete open question: whether a shallow-depth FCS protocol can match the sample complexity of the full-depth FCS protocol for a meaningful class of fermionic observables. The tensor-network-to-random-walk mapping and the closed-form Poisson approximation for α_{S,d} are valuable technical contributions, and the Kitaev-chain demonstration is a nice practical illustration. However, the central result is conditional: the 2-local lower bound rests on an unproven sign assumption, the k-local extension rests on a numerically validated ansatz rather than a proof, and the sample-complexity statement is derived for Haar-averaged states. These gaps limit the strength of the conclusions that can be drawn from the paper in its current form.","major_comments":[{"comment":"The 2-local lower bound α_{S,d} ≥ (47/72) max_{d'≤d} α^L_{S,d'} is derived under the sign-definiteness assumption R_{ij}(μ,μ,t) ≤ 0 and R_{ij}(μ,ν,t) ≥ 0 for μ≠ν, which is only supported by the numerical sign plot in Fig. 8. If this assumption fails for some S,d in the target regime, Lemma 7 no longer applies and the depth formula d* = Θ(max{d_int²/log n, d_int}) does not imply the claimed polynomial sample complexity. Since Theorem 1 is the main theoretical basis for the 2-local depth scaling, this conditional nature is load-bearing.","section":"Appendix G, Theorem 1 and Eq. (G30)"},{"comment":"The k-local extension relies on the factorization ansatz α'_{S,d} = 1/(k-1)!! (3n/2)^{k/2} ... ∏ α^L_{{i,j},d}, which is validated only numerically for d > 2 log n. The proof sketch in Appendix H preserves branches with non-increasing d_near and discards the others, asserting that the remaining coefficients sum to at least 1/36^{k d_int/2}, but it does not show that the discarded branches cannot contribute to the contraction with ⟨⟨0,0|. Consequently, the statement that d = Θ(log n) suffices for d_int = O(log n) and constant k is not established; a rigorous bound on |α_{S,d} - α'_{S,d}| is needed.","section":"Section III.D and Appendix H, Eq. (22)"},{"comment":"The variance bound Var[v] ≤ 1/α_{S,d} is derived by averaging the state ρ over the Haar distribution, i.e., E_ρ[ρ] = I/2^n. For a fixed, adversarially chosen ρ, the variance can be larger, yet the abstract and conclusion present the O(1/(α_{S,d} ε²)) sample complexity as a general statement. The numerics in Section IV use only random states and therefore do not test worst-case behavior. This is load-bearing because the depth scaling alone does not imply efficient estimation for arbitrary input states.","section":"Appendix C, Eq. (11)"},{"comment":"The definitions of the parameters in Eq. (19) disagree with those in Lemma 4: Eq. (19) uses a = |⌊(i-1)/4⌋ - ⌊(j-1)/4⌋| and b = ⌊(i-1)/4⌋ + ⌊(j-1)/4⌋ + 1, whereas Lemma 4 uses a = |i-j| and b = i+j-1. The subsequent Lemma 5, which connects the order of α^L_{S,d} to d_int = |i-j|, is based on the Lemma 4 definitions. The main text does not reconcile these two expressions, so it is unclear which formula is being used to derive the depth bound d* = Θ(max{d_int²/log n, d_int}).","section":"Section III.C, Eq. (19) and Appendix F, Lemma 4"}],"minor_comments":[{"comment":"Typo: 'bouned' should be 'bounded'.","section":"Section III.A"},{"comment":"The Hamiltonian is misspelled 'Kiteav' in several places; it should be 'Kitaev'.","section":"Section IV and Fig. 4"},{"comment":"The word 'production' should be 'product', and the notation for the product over pairs (i,j) ∈ Λ should be defined explicitly.","section":"Eq. (22)"},{"comment":"The figure is hard to read: the edge probabilities are not clearly associated with the graph, and the printed numbers appear garbled. Please redraw with explicit labels.","section":"Fig. 7"},{"comment":"The error term in Eq. (19) is written O(e^{-π² d}), while Lemma 4 obtains O(e^{-π² t/2}) with d = 2t+1; the translation between these expressions and the relevant regime of t should be stated explicitly.","section":"Appendix F, Lemma 4"}],"recommendation":"major_revision","confidential_remarks":"The paper contains a useful new technique and promising numerics, but the abstract's 'we establish' overstates the strength of the results: the 2-local theorem is conditional on a numerically observed sign assumption, the k-local formula is an ansatz, and the sample-complexity statement is average-state rather than worst-case. These gaps are fixable in principle but require additional proof or careful restatement of the claims. I recommend major revision with an emphasis on making the conditional nature of the central results explicit and on providing numerical or analytical evidence for the sign assumption in the actual parameter regime."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nYou should know two things about arXiv:2501.09574. First, the core idea is genuinely new: Bian and Wu propose an adaptive-depth fermionic classical shadow protocol where the brickwork matchgate circuit depth is chosen from the observable's interaction distance, and they give a random-walk analysis of the shallow matchgate shadow channel that leads to a predicted depth scaling max{d_int^2/log n, d_int}. That directly targets the open question raised by Zhao et al. and King et al. about whether shallow FCS can match the sample complexity of full FCS for structured observables. The tensor-network-to-random-walk mapping and the numerical evidence for the depth-variance tradeoff are useful contributions.\n\nSecond, the headline sample-complexity claim is not actually established. The variance bound in Eq. (11) is derived in Appendix C by averaging the unknown state rho over the Haar distribution. That gives an average-case variance, not a guarantee for a fixed adversarial rho. Theorem 1 is honest enough to say \"in the average of rho,\" but the abstract and introduction present the depth-scaling result as if it holds for the state at hand. Since the protocol may be used in VQE on a specific state, this is load-bearing.\n\nThere are two further gaps. The 2-local depth bound is conditional on a sign-definiteness assumption on the remainder terms R_{i,j} (Appendix G, Eq. G30) that is only supported by a numerical sign plot. The theorem states the assumption, but the abstract's \"we establish\" is stronger than what is proven. For general k-local observables, the paper relies on a factorization ansatz (Eq. 22) validated only numerically for d > 2 log n, and Appendix H is a sketch that discards branches without a rigorous accounting. So the k-local scaling is plausible but unproven. Minor slips in the appendix (e.g., a bound written as Ω(n) where it must be Ω(1/poly(n))) add to the impression of haste.\n\nIf the authors can either prove the sign assumption and give a worst-case variance bound, or explicitly restrict all claims to average-case and to the factorization regime, the paper would be solid. As it stands, it is a promising conditional result with honest theorem statements and overreaching front matter. I would send it to peer review—the open problem and the technique justify referee time—but I would not accept the current claims at face value.\n\nFor you: it is a good reading-group paper precisely because it exposes the average-case/worst-case and proven/numerically-assumed boundary in shadow tomography.","headline":"Good new idea about adaptive-depth fermionic shadows, but the sample-complexity guarantee is average-case and rests on unproven sign and factorization assumptions; the abstract overclaims.","tokens_in":28314,"tokens_out":9257,"would_cite":true,"duration_ms":97535,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces an adaptive-depth fermionic classical shadow protocol and claims that the required depth for approximating a fermionic observable $H$ scales as $\\max\\{d_{\\mathrm{int}}(H)^2/\\log n,\\ d_{\\mathrm{int}}(H)\\}$ while…","keywords":["fermionic classical shadows","adaptive-depth circuits","matchgate circuits","Majorana observables","interaction distance","classical shadow estimation","tensor network contraction","symmetry lazy random walk"],"falsifier":"Prepare a fixed computational-basis state or an adversarially chosen state and run ADFCS at depth $d^*$, measuring the empirical variance of $\\mathrm{Tr}(\\hat\\rho\\gamma_S)$; if the variance exceeds $1/\\alpha_{S,d}$ by more than a constant factor, the sample-complexity claim as stated fails. A second check is to compute the remainder coefficients $R_{i,j}(\\mu,\\nu,t)$ for an adjacent Majorana pair at shallow depth: a positive diagonal remainder or a negative off-diagonal remainder violates the assumption behind the proof of the depth rule.","tokens_in":27227,"feed_emoji":"⚛️","tokens_out":10091,"duration_ms":93875,"temperature":0.7,"pith_summary":"Fermionic classical shadows estimate expectation values of fermionic observables by applying random matchgate circuits, but the standard protocol needs polynomial-depth circuits. This paper proposes an adaptive-depth version (ADFCS) in which the depth of the brickwork matchgate circuit is chosen from the observable itself, and claims that a fermionic observable $H$ can be approximated with depth $\\Theta(\\max\\{d_{\\mathrm{int}}(H)^2/\\log n,\\ d_{\\mathrm{int}}(H)\\})$, where $d_{\\mathrm{int}}(H)$ is the interaction distance of $H$, while keeping the same order of sample complexity as the full fermionic classical shadow protocol. The practical point is that local and short-ranged fermionic Hamiltonians, such as the Kitaev chain treated in the paper, can then be measured with constant or logarithmic-depth circuits rather than polynomial-depth ones.","feed_headline":"Fermionic shadow depth set by interaction distance, not system size","feed_subtitle":"Adaptive matchgate circuits keep fermionic-shadow accuracy at much lower depth.","key_machinery":"The load-bearing object is the tensor-network representation of the $d$-depth matchgate shadow channel. Each independent two-qubit matchgate is replaced by a fixed fourth-order tensor obtained from the second-moment twirl of the matchgate group, and connecting these tensors in the brickwork architecture produces a tensor network whose contraction gives $\\alpha_{S,d} = \\langle\\langle 0,0|\\mathcal{C}|\\gamma_S,\\gamma_S\\rangle\\rangle$. For two-local Majorana strings the contraction is then shown to evolve as a symmetry lazy random walk on a polynomial space; the walk's transition probabilities yield a closed-form Poisson-sum expression for the dominant part $\\alpha^L_{S,d}$, and an auxiliary remainder bound relates $\\alpha^L_{S,d}$ to $\\alpha_{S,d}$. The adaptive depth rule follows from requiring $\\alpha^L_{S,d}=\\Omega(1/\\mathrm{poly}(n))$.","core_discovery":"The paper's central claim is that the depth needed for a random matchgate measurement is set by the observable's interaction distance, not by the system size. For a $k$-local Majorana string $\\gamma_S$ with constant $k$ and interaction distance $d_{\\mathrm{int}}(S)=O(\\log n)$, a random circuit of depth $d=\\Theta(\\log n)$ already makes the shadow eigenvalue $\\alpha_{S,d}$ polynomially large, i.e. $\\alpha_{S,d}=\\Omega(1/\\mathrm{poly}(n))$; more generally the required depth is $d^*=\\Theta(\\max\\{d_{\\mathrm{int}}(S)^2/\\log n,\\ d_{\\mathrm{int}}(S)\\})$. Because the variance of the estimation is bounded by $1/\\alpha_{S,d}$, this gives the same order of sample complexity as the original FCS protocol while using far shallower circuits.","pith_inferences":["The same tensor-network-to-random-walk reduction could be re-derived for other circuit geometries, such as non-brickwork or open-boundary matchgate layouts, changing only the kernel of the walk and hence the constants in the depth rule.","A state-dependent version of the variance bound would be needed before using ADFCS for adversarial or worst-case inputs; the current protocol's practical guarantee is tied to the Haar-averaged variance.","The per-term depth selection suggests a practical variational-quantum-eigensolver-style measurement strategy: choose a different measurement depth for each Hamiltonian term according to its own $d_{\\mathrm{int}}$, rather than one global depth.","The closed-form Poisson-sum formula could be turned into a lookup table or analytic depth selector, removing the numerical-fitting step and giving a fully deterministic protocol."],"forward_implications":["A fermionic Hamiltonian whose terms have logarithmic interaction distance can be measured with $O(\\log n)$-depth random matchgate circuits and polynomial sample complexity.","Shallow-depth estimation preserves the unbiasedness of the classical-shadow estimator whenever $\\alpha_{S,d}\\neq 0$.","For a 10-qubit Kitaev chain, depth $d=3$ already suffices to reach estimation errors comparable with the full FCS protocol.","For observables with interaction distance $d_{\\mathrm{int}}=\\omega(\\log n)$, the required depth interpolates between logarithmic and polynomial scaling as the observable becomes more nonlocal.","The sample-complexity bound retains the form $O(1/(\\alpha_{S,d}\\epsilon^2))$, matching the original FCS order when $\\alpha_{S,d}$ is polynomially large."],"supporting_citations":[{"why":"Establishes the classical shadow channel and shadow-norm framework that the FCS protocol builds on.","marker":"[11]"},{"why":"Proves that no subgroup of Clifford and matchgate elements gives a better fermionic shadow norm, motivating the search for shallow-depth variants.","marker":"[13]"},{"why":"Supplies the first three moments of the uniform matchgate distribution used to construct the tensor T and diagonalize the shadow channel.","marker":"[15]"},{"why":"Introduces the shallow-shadow tensor-network and matrix-product-operator technique that makes the contraction for $\\alpha_{S,d}$ efficient at shallow depth.","marker":"[24]"},{"why":"Shows that Haar-random brickwork matchgate circuits require $\\Omega(n^2)$ depth, the baseline that ADFCS improves on.","marker":"[29]"},{"why":"Provides the exact spatiotemporal propagation solution for the symmetry lazy random walk used to evaluate $\\alpha^L_{S,d}$.","marker":"[34]"},{"why":"Defines the Kitaev chain Hamiltonian used as the numerical application.","marker":"[36]"}],"fun_headline_variants":["Interaction distance, not system size, sets fermionic shadow depth","Fermionic shadow depth adapts to interaction distance","Shorter matchgate circuits for fermionic shadows via adaptive depth","Adaptive depth yields fermionic shadows with less circuit depth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The depth guarantee and the matching sample complexity rest on the variance bound $\\mathrm{Var}[v]\\le 1/\\alpha_{S,d}$, which is derived by averaging the unknown state over the uniform (Haar) distribution; a fixed adversarial state could require more samples than the stated order.","fun_headline_variants_meta":{"raw":{"variants":["Interaction distance, not system size, sets fermionic shadow depth","Fermionic shadow depth adapts to interaction distance","Shorter matchgate circuits for fermionic shadows via adaptive depth","Adaptive depth yields fermionic shadows with less circuit depth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000931,"raw_usage":{"total_tokens":4000,"prompt_tokens":971,"completion_tokens":3029,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":587,"completion_tokens_details":{"reasoning_tokens":2961}},"tokens_in":587,"tokens_out":3029,"duration_ms":20341,"temperature":1.0,"reasoning_tokens":2961,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:54:29.748491+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Prepare a fixed computational-basis state or an adversarially chosen state and run ADFCS at depth $d^*$, measuring the empirical variance of $\\mathrm{Tr}(\\hat\\rho\\gamma_S)$; if the variance exceeds $1/\\alpha_{S,d}$ by more than a constant factor, the sample-complexity claim as stated fails. A second check is to compute the remainder coefficients $R_{i,j}(\\mu,\\nu,t)$ for an adjacent Majorana pair at shallow depth: a positive diagonal remainder or a negative off-diagonal remainder violates the assumption behind the proof of the depth rule.","supporting_citations":[{"cited_title":"Rubin, and Akimasa Miyake","cited_arxiv_id":null,"evidence_quote":"Proves that no subgroup of Clifford and matchgate elements gives a better fermionic shadow norm, motivating the search for shallow-depth variants."},{"cited_title":"Huggins, Joonho Lee, and Ryan Babbush","cited_arxiv_id":null,"evidence_quote":"Supplies the first three moments of the uniform matchgate distribution used to construct the tensor T and diagonalize the shadow channel."},{"cited_title":"Shallow shadows: Expectation estimation using low-depth random clifford circuits","cited_arxiv_id":null,"evidence_quote":"Introduces the shallow-shadow tensor-network and matrix-product-operator technique that makes the contraction for $\\alpha_{S,d}$ efficient at shallow depth."},{"cited_title":"Sung, Kostyantyn Kechedzhi, Vadim N","cited_arxiv_id":null,"evidence_quote":"Shows that Haar-random brickwork matchgate circuits require $\\Omega(n^2)$ depth, the baseline that ADFCS improves on."},{"cited_title":"Exact spatiotemporal dynamics of confined lattice random walks in arbitrary dimensions: a century after smoluchowski and p´ olya.Physical Review X, 10(2):021045, 2020","cited_arxiv_id":null,"evidence_quote":"Provides the exact spatiotemporal propagation solution for the symmetry lazy random walk used to evaluate $\\alpha^L_{S,d}$."},{"cited_title":"Unpaired majorana fermions in quantum wires","cited_arxiv_id":null,"evidence_quote":"Defines the Kitaev chain Hamiltonian used as the numerical application."}],"review_version":1}