{"id":"b6cc8948-1d12-46c1-b7f4-28d5784d8589","arxiv_id":"2505.16715","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Estimating k powers of a quantum state against one observable simultaneously costs Θ~(k) samples, matching the cost of the single hardest term.","lead":"This paper shows that all quantities tr(Oρ), tr(Oρ²), ..., tr(Oρ^k) can be estimated simultaneously from about k log k copies of ρ, only a log factor more than estimating the hardest single one. This settles a basic resource count in quantum estimation and cuts the sample cost of entanglement spectroscopy and virtual cooling by a quadratic factor.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; central Theorem 1.1 is sound, with a fixable proof gap in Corollary 3.2.","rationale":"After reviewing the full proof, I could not identify a load-bearing error in Theorem 1.1. The delicate step the reader flagged, Lemma 2.11, is valid: for total weight <= 2, the weighted cycle type is preserved under the involution, because a directed cycle with one weight-2 edge or two weight-1 edges is mapped to an isomorphic weighted directed cycle under reversal; this implies (s_k e1)† is in the same orbit as s_k e1, giving Hermiticity, and every term in O_i O_j has total weight 2, making the coefficient argument in Proposition 2.16 go through. The variance bound and the lower bound are consistent: Kadison-Schwarz is applicable to the completely positive unital symmetrization map, and the hard-instance infidelity scales as epsilon^2/k, yielding Omega(k/epsilon^2). The one genuine defect is Corollary 3.2's m <= k case: the proof omits the median-trick step needed to reach failure probability 1/(3m) per polynomial with only O(log m) overhead. This is fixable and does not affect the central claim, so I do not change the reader's CONDITIONAL verdict; the condition should be the completion of the Corollary 3.2 proof.","tokens_in":19089,"tokens_out":42393,"duration_ms":350041,"concrete_test":"Independently verify Proposition 2.16 by brute force: for n=3 and n=4 with a random Hermitian O (e.g., a random 2x2 or 3x3 matrix), construct O_i = mu(Phi(s_i e1)) for i=1..n and symbolically compute [O_i,O_j] for all i<j; if any commutator is nonzero, the sample-reuse argument in Theorem 1.1 collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"We find no load-bearing flaw in the central simultaneous-estimation claim. The commutativity of {O_i} rests on Lemma 2.11, and the weighted-cycle-type argument checks out: for total weight <= 2, a directed cycle has at most one weight-2 edge or two weight-1 edges, and reversal of edge directions leaves the weighted cycle type invariant; the orbit/type correspondence then makes the coefficient argument in Proposition 2.16 valid. The variance bound via Kadison-Schwarz and the Helstrom/Holevo lower bound are internally consistent. The only concrete defect is in Corollary 3.2: its m <= k case asserts an O(log(min{k,m})) overhead, but the proof does not show how each of m polynomial estimates is boosted to failure probability 1/(3m) within O(log m) total runs. The natural fix (median of the m linear-combination estimators over O(log m) independent runs) mirrors Theorem 3.1 and does not affect Theorem 1.1.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the simultaneous estimation of the nonlinear functionals tr(Oρ), tr(Oρ²), ..., tr(Oρ^k) from copies of an unknown state ρ with a known observable O. The main contribution is a construction of pairwise commuting, permutation-symmetrized observables O_k whose joint measurement yields unbiased estimators with variance O(k||O||²/n), leading to an O(k log(k)||O||²/ε²) sample upper bound for simultaneous estimation of all k values. This is complemented by a lower bound Ω(k||O||²/ε²) for the single term tr(Oρ^k), obtained by a two-state discrimination hard instance together with the Helstrom-Holevo bound. The paper also extends the method to polynomial functionals of ρ via linear combinations of the simultaneous estimators, and discusses applications to entanglement spectroscopy and quantum virtual cooling.","tokens_in":19227,"tokens_out":19043,"duration_ms":149459,"significance":"If correct, the main theorem is significant: it removes a factor of k from the naive O(k² log k) sample bound and shows that simultaneous estimation of all k power functionals is essentially as hard as estimating the single hardest term. The construction is elegant and largely self-contained: the weighted-permutation formalism, the commutativity proof via weighted cycle types, and the variance comparison via the Kadison-Schwarz inequality are clearly presented. The lower bound is a clean application of standard quantum state discrimination, with a concrete hard instance and no fitted parameters. The extensions to polynomial functionals and the applications to entanglement spectroscopy and virtual cooling give the results practical relevance. The proofs are direct and appear internally consistent, with no circularity.","major_comments":[{"comment":"The m ≤ k branch of the proof does not establish the claimed O(k log m max_i ||f_i||₁² ||O||²/ε²) sample bound. The preceding single-polynomial argument only guarantees failure probability at most 1/3 per run, and the text asserts without proof that each of the m estimates can be boosted to failure probability 1/(3m) with only an O(log m) overhead. As written, a naive application would either incur an extra factor of m by estimating each f_i separately or fail the union bound if one only boosts the underlying p_j's. The natural fix is to repeat the whole k-value measurement O(log m) times, compute all m linear combinations in every run, and take the coordinatewise median; since each run already produces all m estimates, the total sample count is O(k max_i ||f_i||₁² ||O||² log m / ε²), matching the corollary. This repair does not affect Theorem 1.1.","section":"Corollary 3.2, proof (m ≤ k case)"},{"comment":"The statements of Theorems 4.3 and 4.4 quantify over all finite-dimensional observables O, but the proof constructs a two-dimensional hard instance, and the lower bound is false for d = 1: when the Hilbert space is one-dimensional, tr(Oρ^k) = tr(O) is a known constant, so zero samples suffice. Please add an explicit assumption that the Hilbert space has dimension at least 2, or otherwise exclude the trivial one-dimensional case, in both theorem statements.","section":"Theorems 4.3 and 4.4"}],"minor_comments":[{"comment":"The notation 'π0 ∈ Mn' appears to be a typo: it should read 'π0 ∈ Wn'.","section":"Section 2.2"},{"comment":"The inequality |tr(Oρ_+^k) - tr(Oρ_-^k)| ≥ tr(ρ_+^k) - tr(ρ_-^k) is not immediate for a ∈ [-1,1]; it follows because the term a((1/k - ε/k)^k - (1/k + ε/k)^k) is at least -((1/k + ε/k)^k - (1/k - ε/k)^k). Adding this one-line justification would improve readability.","section":"Proof of Theorem 4.4"},{"comment":"The reduction to ⟨0|O|0⟩ = 1 should mention the sign flip O → -O when the eigenvalue of largest magnitude is -1; this keeps ||O|| unchanged and preserves the estimation problem up to a known sign.","section":"Proof of Theorem 4.4"},{"comment":"The phrase 'standard variation' should be 'standard deviation'.","section":"Corollary 3.2, proof"},{"comment":"When ε is large relative to ||O||, the expression 6k||O||²/ε² can be smaller than k; the proof implicitly relies on the trivial zero estimator in that regime, or one should set n = max(k, ⌈6k||O||²/ε²⌉).","section":"Theorem 3.1, proof"}],"recommendation":"major_revision","confidential_remarks":"The central simultaneous-estimation result (Theorem 1.1) is sound, and the lower bound is correct for non-trivial dimension. The two substantive issues are the proof gap in Corollary 3.2 and the missing dimension assumption in the lower-bound statements; both are easily repairable within the scope of a revision. I would be happy to see a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Zhi, quick take on 2505.16715. The headline result is real: you can estimate tr(Oρ), …, tr(Oρ^k) to additive error ε with O(k log k ||O||^2/ε^2) samples, and estimating the single hardest term tr(Oρ^k) requires Ω(k||O||^2/ε^2). So simultaneous estimation is essentially as hard as the single-term problem, up to a log factor. The previous simultaneous approach via repeated SWAP tests was O(k^2 log k), so this is a quadratic improvement and effectively closes the question up to the log.\n\nWhat the paper does well: the estimator construction is genuinely clever. The weighted-permutation formalism with symmetrized observables O_k is new; showing they pairwise commute is the crux, and the proof via Lemma 2.11 (weighted cycle type is preserved under involution when total weight ≤ 2) checks out. I went through the weight-2 case carefully; the argument holds. The variance bound is clean: symmetrize a block estimator, then Kadison–Schwarz gives Var[O_k] ≤ Var[T_k] ≤ 2k||O||^2/n. The lower bound is a standard state-discrimination reduction, but the two-level hard instance is neat and gives the Θ(k) scaling.\n\nSoft spots: Corollary 3.2 (multiple polynomials) has a real but fixable gap. In the m ≤ k branch, the proof asserts an O(log m) overhead for the union bound but never shows the amplification. The natural fix is the same median trick as in Theorem 3.1, applied to the m linear-combination estimators; it does not affect Theorem 1.1 but should be written out. Section 2 is notation-heavy, and the proof of Lemma 2.11 is terse to the point of being easy to misread—that deserves more exposition. The applications (entanglement spectroscopy, virtual cooling) are straightforward substitutions and add little on their own, but they are not wrong.\n\nThe citation pattern is fine. The companion paper [CW25] is their own concurrent work on trace powers, but the simultaneous-estimation result stands on its own. No fitted parameters, no circularity.\n\nBottom line: this deserves a serious referee. I would accept it into peer review and expect a minor revision, mainly fixing Corollary 3.2's proof and expanding the terse parts. The main theorem is sound and the contribution is significant for quantum estimation theory.","headline":"Resolves the sample complexity of simultaneous nonlinear functional estimation up to a log factor; the main theorem is sound, with a fixable gap in a corollary.","tokens_in":19802,"tokens_out":7912,"would_cite":true,"duration_ms":60857,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12"],"pacs":["03.67.-a"],"model":"deepseek-v4-flash","headline":"For any known observable $O$, one batch of $n$ copies of a quantum state can simultaneously estimate all moments $\\operatorname{tr}(O\\rho),\\dots,\\operatorname{tr}(O\\rho^k)$ with $\\widetilde O(k)$ samples, and this is optimal up to a log…","keywords":["quantum state estimation","nonlinear functionals","trace of state powers","simultaneous estimation","sample complexity","weighted permutations","entanglement spectroscopy","virtual cooling"],"falsifier":"Take a small case such as $n=4$, $O$ a generic $2\\times2$ observable, and symbolically compute $[O_2,O_3]=O_2O_3-O_3O_2$ in the monoid ring $\\mathbb{C}W_4$ using Definitions 2.13 and 2.14. If any coefficient is nonzero, Proposition 2.16 is false and the claimed simultaneous measurement cannot be performed; the paper's proof predicts all coefficients are zero.","tokens_in":18867,"feed_emoji":"⚛️","tokens_out":8107,"duration_ms":62412,"temperature":0.7,"pith_summary":"This paper claims that a single batch of $n$ copies of a quantum state $\\rho$ can supply unbiased, low-variance estimates of $\\operatorname{tr}(O\\rho), \\operatorname{tr}(O\\rho^2), \\dots, \\operatorname{tr}(O\\rho^k)$ simultaneously for any known observable $O$, using $O(k\\log k\\,\\|O\\|^2/\\varepsilon^2)$ copies to reach additive error $\\varepsilon$. It proves a matching lower bound: even estimating the single hardest term $\\operatorname{tr}(O\\rho^k)$ needs $\\Omega(k\\|O\\|^2/\\varepsilon^2)$ copies. If correct, estimating all $k$ moments costs almost the same as estimating the hardest one, replacing the $O(k^2\\log k)$ cost of estimating the values one by one. The improvement transfers directly to entanglement spectroscopy and to quantum virtual cooling of many-body thermal states, where samples were previously wasted on separate estimates.","feed_headline":"All k quantum-state moments estimated from one sample batch","feed_subtitle":"The same copies yield every trace value, cutting sample cost from k² to k log k.","key_machinery":"The argument runs through the monoid of weighted permutations $W_n \\simeq S_n \\ltimes \\mathbb{Z}_{\\ge0}^n$, where $\\mu(\\pi^w)=U_\\pi(O^{w_1}\\otimes\\cdots\\otimes O^{w_n})$. Each orbit under conjugation by $S_n$ is encoded by a weighted cycle type, a directed cycle graph with integer weights on edges. The load-bearing structural fact is Lemma 2.11: the involution $(\\pi^w)^\\dagger = (\\pi^{-1})^{w_{\\pi^{-1}}}$ preserves weighted cycle type whenever total weight $|w|_1\\le2$. Since each estimator has total weight 1 and each product $O_iO_j$ has total weight 2, this preservation yields Hermiticity of $O_k$ and then, by comparing coefficients on each orbit, the pairwise commutativity $O_iO_j=O_jO_i$. Variance control uses the fact that $O_k$ is the symmetrization of a block-local estimator $T_k$, so the Kadison-Schwarz inequality gives $\\operatorname{Var}[O_k]\\le\\operatorname{Var}[T_k]\\le2k\\|O\\|^2/n$.","core_discovery":"The central discovery is a family of Hermitian, pairwise-commuting observables $O_1,\\dots,O_n$ on the $n$-copy Hilbert space, each supported on the symmetrized orbit of a weighted cyclic shift: $O_k = \\mu(\\Phi(s_k e_1))$. Measuring all of them on the same $n$ copies returns variables $p_k$ with $\\mathbb{E}[p_k]=\\operatorname{tr}(O\\rho^k)$ and $\\operatorname{Var}[p_k]\\le 2k\\|O\\|^2/n$. Because the observables commute, one round of measurements yields every moment estimate, and Chebyshev plus median boosting gives the $\\widetilde O(k)$ bound. The matching lower bound comes from a two-level pair of states whose $k$-th power traces differ by $\\Theta(\\varepsilon)$ while their fidelity gap is $O(\\varepsilon^2/k)$, forcing $\\Omega(k/\\varepsilon^2)$ samples by state-discrimination.","pith_inferences":["The hard instance in the lower bound is a two-level state, so the $k$-dependence is not an artifact of high dimension; the same $\\Omega(k/\\varepsilon^2)$ barrier should apply to any protocol that must output $\\operatorname{tr}(O\\rho^k)$ with additive error.","Because the commuting family contains estimators for every $k\\le n$, the same $n$-copy data could be reused for any polynomial approximation of a target function; the paper's Corollary 3.2 makes this explicit only for degree-$k$ polynomials.","The weighted-cycle-type argument is specialized to total weight $\\le2$; if it can be extended to weight 3 or more, the same sample-reuse trick might apply to products like $\\operatorname{tr}((\\rho\\sigma)^k)$ or to simultaneous estimation of Rényi entropies at several orders."],"forward_implications":["Simultaneously estimating the $k$ values costs $\\widetilde O(k\\|O\\|^2/\\varepsilon^2)$ copies, versus $O(k^2\\log k)$ by estimating each term separately, and the matching lower bound makes this optimal up to the log factor.","Entanglement spectroscopy can extract $\\operatorname{tr}(\\rho^2),\\dots,\\operatorname{tr}(\\rho^{k_{\\max}})$ with $O(k_{\\max}\\log k_{\\max}/\\varepsilon^2)$ copies, improving the prior $O(k_{\\max}^2\\log k_{\\max}/\\varepsilon^2)$.","Quantum virtual cooling can obtain observables at fractional temperatures $T/2,\\dots,T/n$ from $O(n\\log n)$ copies of the thermal state, a quadratic reduction over the direct approach.","Estimating $\\operatorname{tr}(Of(\\rho))$ for any degree-$k$ polynomial $f$ costs $O(k\\|f\\|_1^2\\|O\\|^2/\\varepsilon^2)$ copies, which is optimal up to constants by the hard instance $f(x)=x^k$."],"supporting_citations":[{"why":"Supplies the generalized SWAP test via cyclic shifts, the baseline estimator for individual terms $\\operatorname{tr}(O\\rho^k)$ that the simultaneous construction generalizes.","marker":"[EAO+02]"},{"why":"Provides the variance-comparison lemma used to show that symmetrization does not increase the variance of the estimator.","marker":"[BOW19]"},{"why":"States the Kadison-Schwarz inequality used to bound $\\operatorname{Var}[O_k]$ through the symmetrized estimator.","marker":"[Kad52]"},{"why":"Supplies the Helstrom bound for quantum state discrimination, a load-bearing ingredient in the matching lower bound.","marker":"[Hel67]"},{"why":"Supplies the Holevo form of the discrimination lower bound used in the sample-complexity argument.","marker":"[Hol73]"},{"why":"Provides the fidelity-based sample lower bound for distinguishing the hard pair of states, converting the fidelity gap into a samples lower bound.","marker":"[Hay16]"},{"why":"Prior work with quadratic $O(k^2\\|f\\|_1^2/\\varepsilon^2)$ sample complexity for polynomial functionals, which Corollary 3.2 improves.","marker":"[QKW24]"},{"why":"Prior simultaneous estimator for the power traces with $O(k^2\\|O\\|^2/\\varepsilon^2)$ cost, the direct comparison for Theorem 3.1.","marker":"[SLLJ24]"},{"why":"Hoeffding's inequality is used in the median trick that turns constant success probability into probability at least $2/3$ across all $k$ estimates.","marker":"[Hoe63]"}],"fun_headline_variants":["All k quantum moments from a single batch","One measurement round, every trace value","k moment estimates for the price of one","Simultaneous quantum moment estimation at ~k samples","Commuting observables cut moment estimation cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 2.11: for weighted permutations, the involution preserves the weighted cycle type whenever the total weight is at most 2; if this failed, the estimators $O_i$ and $O_j$ would not be simultaneously measurable and the entire sample-reuse argument would fall apart.","fun_headline_variants_meta":{"raw":{"variants":["All k quantum moments from a single batch","One measurement round, every trace value","k moment estimates for the price of one","Simultaneous quantum moment estimation at ~k samples","Commuting observables cut moment estimation cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000588,"raw_usage":{"total_tokens":2716,"prompt_tokens":858,"completion_tokens":1858,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":474,"completion_tokens_details":{"reasoning_tokens":1791}},"tokens_in":474,"tokens_out":1858,"duration_ms":13743,"temperature":1.0,"reasoning_tokens":1791,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:56:27.611790+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small case such as $n=4$, $O$ a generic $2\\times2$ observable, and symbolically compute $[O_2,O_3]=O_2O_3-O_3O_2$ in the monoid ring $\\mathbb{C}W_4$ using Definitions 2.13 and 2.14. If any coefficient is nonzero, Proposition 2.16 is false and the claimed simultaneous measurement cannot be performed; the paper's proof predicts all coefficients are zero.","supporting_citations":[],"review_version":1}