{"id":"7e1f89c7-f13c-4087-84db-235aec7a1d8e","arxiv_id":"2608.11151","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A new sample-efficient estimator achieves subquadratic sample complexity for von Neumann entropy, O(d^2(log log d)^2/(epsilon^2 log^2 d) + log^2(d/epsilon)/epsilon^2).","lead":"This paper gives the first estimator for von Neumann entropy that uses fewer than d^2 samples of a d-dimensional quantum state, breaking a long-standing quadratic barrier. Its key new tool is a pinching inequality that controls the entropy lost when the state is cut into large and small eigenvalue parts.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Subquadratic claim is conditional on two unproved primitives imported from [PSTW26]; if Lemma 2.10 or Lemma 2.12 needs more samples or has a different error scaling, Theorem 1.1's bound is not established.","rationale":"I read the paper in good faith. The internal argument is coherent: the pinching inequality (Lemma 4.8), the bias-corrected large-eigenvalue estimator (Proposition 5.2 and Section 5.3), and the bounded-coefficient polynomial approximation (Lemma 6.3) are self-contained and appear mathematically sound. The constants in Algorithm 1 are left implicit, but this is a standard convention in complexity-theoretic papers and is not by itself a correctness defect, since the proof indicates how to choose them consistently (Corollary 6.6 spells out the compatibility conditions). The single load-bearing point is the dependence on two unproved primitives from the companion preprint [PSTW26]: Lemma 2.10 (simultaneous observable tomography) and Lemma 2.12 (projected moment estimation). All of the paper's new estimates are phrased relative to those guarantees. A concrete failure mode is that Lemma 2.12's sample count n = O(d/(B epsilon^2)) might require a power of d in the denominator that is not d^{k/2}; the moment error for k = K would then be much larger than the budget in Corollary 6.6, forcing nmom to be d^2/epsilon^2 or worse. Similarly, if Lemma 2.10's rank dependence is not as stated, the off-diagonal bound in Lemma 4.5 and hence the pinching loss in (29) would not be O(epsilon). These are correctness risks, not circularities or internal inconsistencies. The reader's weakest_assumption identifies exactly the same risk, so I agree. Because the reader already assigned CONDITIONAL, my stress test does not change the verdict; it remains conditional on independent verification of the two imported primitives and on making their constants explicit.","tokens_in":22292,"tokens_out":18000,"duration_ms":154091,"concrete_test":"Verify Lemma 2.12 analytically: re-derive the ProjectedMoments estimator from [PSTW26, Corollary 5.7] for sigma = Pi rho Pi with ||sigma||_inf <= B, using n = C d/(B epsilon^2) copies of rho, and confirm the simultaneous error bound |bp_k - tr(sigma^k)| <= 23^K K^{5K} (B^{k/2} epsilon^k / d^{k/2} + B^k epsilon) for every k <= K <= sqrt(n). Specifically check whether the leading k = 2 term is O(B epsilon^2/d + B^2 epsilon) with the stated sample count; if the derivation instead gives n = Theta(d^2/(B epsilon^2)) or puts d^k rather than d^{k/2} in the denominator, the nmom assignment in Algorithm 1 is too small. A secondary check: confirm Lemma 2.10's bound holds for the specific Hermitian W of Lemma 4.5 with rank(W) <= 2 rank(P), since this is the only use of the full observable version of RelativeTomography.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central sample-complexity claim, O(d^2 log^2(log d) log(1/epsilon)/(epsilon^2 log^2 d) + log^2(d/epsilon)/epsilon^2), is proven in Section 7 only under the two algorithmic guarantees imported without proof in Section 2.3: Lemma 2.10 (RelativeTomography) and Lemma 2.12 (ProjectedMoments) from the preprint [PSTW26]. Every downstream estimate inherits these statements: Lemma 4.5 and Corollary 4.9 use Lemma 2.10 to bound the off-diagonal term t <= C d/(n_tom B); Lemma 5.4 and Corollary 5.5 use the same rank-one bound to get delta^2 <= epsilon/10; Corollary 6.6 uses Lemma 2.12 to bound the small-eigenvalue moment errors, with nmom = Theta(d^2/(epsilon K^2 zeta^2)) matching the n = O(d/(B epsilon^2)) requirement only if B = Theta(epsilon K^2/d). If Lemma 2.12 actually needs n = Omega(d^2/(B epsilon^2)) or has a worse k-dependence (e.g., B^k instead of B^{k/2}/d^{k/2}), the nmom budget and the error budget (28) fail, and the final complexity could become Omega(d^2/epsilon) or worse. If Lemma 2.10 has an extra rank factor or requires n >= C d^2 rank(O), the pinching bound t log(e/t) <= epsilon/2 in (29) does not follow. The paper gives no proof or public-version reference for these lemmas beyond the preprint [PSTW26], so Theorem 1.1 is currently conditional on that manuscript's correctness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an estimator for the von Neumann entropy of an unknown d-dimensional quantum state with sample complexity O(d^2 log^2(log d) log(1/ε)/(ε^2 log^2 d) + log^2(d/ε)/ε^2), which for constant ε is O_ε(d^2 log^2(log d)/log^2 d) = o(d^2). The algorithm thresholding (Algorithm 1) splits the eigenspaces into large and small eigenvalues determined by a relative-tomography output, estimates the large-eigenvalue entropy with a bias-corrected plug-in, and estimates the small-eigenvalue entropy with a polynomial in estimated moments. The proof introduces a pinching inequality (Lemma 4.8) and a bounded-coefficient polynomial approximation (Lemma 6.1). The internal derivations are detailed, but the main theorem is conditional on two imported algorithmic guarantees from the preprint [PSTW26].","tokens_in":22649,"tokens_out":15763,"duration_ms":119758,"significance":"If the result is established, it breaks the long-standing quadratic barrier for von Neumann entropy estimation and is nearly optimal in d and ε in view of the recent lower bound [Wan26]. The pinching inequality and the construction of an entropy polynomial with well-controlled coefficients are interesting and potentially reusable tools. The paper is honest about its methodological debt: the lower bound is cited only for comparison, and the core proofs are not circular. However, the significance is currently tempered because the central claim rests on unproved statements from another preprint, and the universal constants in the algorithm are not made explicit.","major_comments":[{"comment":"Theorem 1.1 is conditional on two imported algorithmic guarantees from the preprint [PSTW26] that are stated without proof. These lemmas are load-bearing: Lemma 2.10 enters through Corollary 4.6 and Corollary 4.9 to produce the pinching-loss bound t ≤ C d/(n_tom B) that ultimately gives (29), and Lemma 2.12 enters through Lemma 6.5 and Corollary 6.6 to bound the moment-estimation error with n_mom = Θ(d^2/(ε K^2 ζ^2)). If Lemma 2.10 carries an extra rank factor or requires n ≳ d^2 rank(O), the inequality t log(e/t) ≤ ε/2 in (29) fails; if Lemma 2.12 requires n = Ω(d^2/(B ε^2)) or has a worse k-dependence, the error budget (28) fails and the sample complexity could become Ω(d^2/ε) or worse. Since the present manuscript does not provide proofs or independent verification of these statements, Theorem 1.1 is not established as a self-contained result. Please either include proofs of the two lemmas (for example, in an appendix) or state Theorem 1.1 as conditional on [PSTW26] and clearly flag the dependence.","section":"Section 2.3, Lemmas 2.10 and 2.12"},{"comment":"The universal constants in the Θ choices for K, B, ζ, n_tom, n_hi, n_mass, and n_mom are never made explicit, yet the proof requires them to satisfy a sequence of inequalities: 3δ^2 ≤ ε/10 in Corollary 5.5, the bias budget dM/K^2 ≤ ε/10 in (27), the higher-moment budget (28), and t log(e/t) ≤ ε/2 in Section 7. Corollary 6.6 gives a partial explicit compatibility check, but it leaves the constant C_K in (26) and the constants in n_tom and n_mom unspecified and relies on 'sufficiently large d' without stating the threshold. Because the subquadratic rate rests on K = Θ(log d/log log d) and B = Θ(ε K^2/d), an explicit instantiation of the constants or a formal proof of their existence is needed for the theorem as stated.","section":"Algorithm 1 and Section 7"}],"minor_comments":[{"comment":"The condition is written as ζ√(M d) ≤ 1/2, but the proof defines z := ζ/√(M d) and uses z ≤ 1/2; the displayed verification 'ζ√(M d) ≤ c_ζ√(2c_B)' is only correct if the intended condition is z = ζ/√(M d) ≤ 1/2. Please correct the typo in Eq. (22) and in the corresponding sentence in Corollary 6.6.","section":"Lemma 6.5, Eq. (22), and Corollary 6.6"},{"comment":"Since Lemmas 2.9–2.12 are taken from an unreviewed preprint [PSTW26], it would be helpful to state explicitly at the start of Section 2.3 which statements are proved in this paper and which are imported from other work.","section":"Section 2.3"},{"comment":"The reference [BMW16] is listed as a private communication; if it is not publicly available, the corresponding row in Table 1 and the text should say so, since readers cannot verify the comparative bound independently.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the dependence on [PSTW26]. If the two imported lemmas are correct, the paper's approach is coherent and likely publishable after the constants are made precise. It may be worth suggesting that the authors obtain permission to include the statements of Lemmas 2.10 and 2.12 (or a summary of their proofs) in an appendix. The citation of the co-author's own lower bound [Wan26] is for comparison only and does not affect the proof, though it may draw scrutiny."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nThe headline: this paper plausibly breaks the quadratic barrier for von Neumann entropy estimation, giving the first o(d^2) sample complexity for constant eps. It's a strong result, but it's conditional on two algorithmic lemmas imported without proof from the preprint [PSTW26]. If those hold, the main theorem is established; if not, the paper collapses.\n\nWhat's genuinely new is the pinching inequality (Lemma 4.8) that controls the entropy loss when you cut the Hilbert space into large- and small-eigenvalue subspaces, plus the hybrid estimator: a bias-corrected plug-in for the large eigenvalues and a bounded-coefficient polynomial moment estimator for the small ones. I worked through the proof chain — thresholding, the off-diagonal bound, pinching, the quadratic relative-entropy error, and the Chebyshev polynomial approximation — and it's internally consistent. The Fourier derivation for the polynomial is clean and the error budgets add up.\n\nThe soft spot is exactly the external dependence. The theorem uses Lemma 2.10 (RelativeTomography) and Lemma 2.12 (ProjectedMoments) from [PSTW26], which are cited as preprints without proof. The stress-test's alternative scalings (e.g., Lemma 2.12 needing d^2/(B eps^2) samples instead of d/(B eps^2)) are speculative, but the point stands: the reader cannot verify the foundation. A referee should ask for proofs of those lemmas or a stable published reference. Also, the constants in Algorithm 1 are left as Theta and only shown to exist via compatibility inequalities; that's minor and normal for this kind of theory paper, though it means the algorithm isn't directly instantiable.\n\nThe comparison to [Wan26] is by one of the authors, but it's used only for context, not as input. No circularity.\n\nBottom line: if the imported primitives check out, this is a breakthrough that nearly matches the lower bound. It deserves a serious referee. I'd bring it to reading group and cite it once the dependency is resolved or verified.\n\nBest","headline":"A credible subquadratic von Neumann entropy estimator whose internal math is solid, but whose headline claim is conditional on two unproved primitives from an unpublished preprint.","tokens_in":23203,"tokens_out":5248,"would_cite":true,"duration_ms":46756,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P45","81P68","94A17"],"pacs":["03.67.-a"],"model":"deepseek-v4-flash","headline":"The paper establishes the first o(d^2)-sample estimator for von Neumann entropy, breaking the quadratic barrier faced by all previous estimators.","keywords":["von Neumann entropy estimation","sample complexity","quantum state tomography","subquadratic estimator","polynomial approximation","pinching inequality","spectrum estimation","quantum information"],"falsifier":"Run the two imported primitives at exactly the sample counts used in Algorithm 1\\u2014$n=\\Theta(d^2\\log(1/\\varepsilon)/(\\varepsilon^2K^2))$ for RelativeTomography and $n=\\Theta(d^2/(\\varepsilon K^2\\zeta^2))$ for ProjectedMoments\\u2014on states whose large-eigenvalue block has rank about $d/K$ and whose small block has eigenvalues just below $2B$; if the simultaneous observable errors or the projected-moment errors exceed the bounds of Lemmas 2.10 and 2.12, the claimed sample complexity of Theorem 1.1 is not achieved.","tokens_in":22072,"feed_emoji":"⚫️","tokens_out":9304,"duration_ms":90832,"temperature":0.7,"pith_summary":"This paper claims the first subquadratic-sample estimator for the von Neumann entropy of an unknown $d$-dimensional quantum state. For additive error $\\varepsilon$, the estimator uses $O(d^2 (\\log\\log d)^2 \\log(1/\\varepsilon)/(\\varepsilon^2 (\\log d)^2) + \\log^2(d/\\varepsilon)/\\varepsilon^2)$ samples, which for constant $\\varepsilon$ is $o(d^2)$ and therefore beats the $d^2$ barrier that all previous estimators, in particular all plug-in estimators, faced. The estimator avoids full tomography: it uses a small amount of mixed-state tomography to separate large and small eigenvalues, estimates each block separately, and corrects the bias of the plug-in estimate. If the claim is right, von Neumann entropy estimation is strictly easier than full quantum state tomography for fixed precision, and the sample count is close to the best known lower bound.","feed_headline":"Von Neumann entropy estimation breaks the d-squared barrier","feed_subtitle":"New split-threshold estimator needs d^2(log log d)^2/log^2 d samples at fixed error, nearly matching lower bounds.","key_machinery":"Algorithm 1 splits the Hilbert space at threshold $B=\\Theta(\\varepsilon K^2/d)$, where $K=\\Theta(\\log d/\\log\\log d)$. The high block is estimated by $S(\\tilde\\rho_{hi})$ plus a linear bias-correction term involving the observable $-\\log \\tilde\\rho_{hi} - P$; the low block is estimated by $\\sum_{k=1}^K a_k \\hat p_k$, where $\\sum_k a_k x^k$ is a polynomial approximating $-x\\log x$ on $[0,2B]$ with coefficient bounds $|a_1|\\le C\\log(eK/M)$ and $|a_k|\\le C_{\\mathrm{poly}}^K M^{1-k}$. The two blocks are tied together by the pinching inequality of Lemma 4.8, which bounds $0\\le S(\\rho_{hi})+S(\\rho_{lo})-S(\\rho)\\le t\\log(e/t)$ with $t=\\operatorname{tr}(X^\\dagger \\rho_{hi}^{-1}X)$, and this $t$ is controlled by the imported RelativeTomography guarantee.","core_discovery":"Theorem 1.1 states that for every $d$-dimensional quantum state $\\rho$, there is an estimator that outputs $\\hat S$ with $|\\hat S - S(\\rho)| \\le \\varepsilon$ and success probability at least $2/3$, using $O(d^2 (\\log\\log d)^2 \\log(1/\\varepsilon)/(\\varepsilon^2 (\\log d)^2) + \\log^2(d/\\varepsilon)/\\varepsilon^2)$ samples. For constant error this is $O_\\varepsilon(d^2(\\log\\log d)^2/(\\log d)^2)=o(d^2)$, the first subquadratic sample complexity for this problem. The estimator is not a plug-in estimator: it applies a bias-corrected plug-in estimate to the large-eigenvalue block of the state and a bounded-coefficient polynomial approximation of $-x\\log x$ to the small-eigenvalue block, and it controls the entropy lost in the split through a new pinching inequality.","pith_inferences":["If the imported RelativeTomography and ProjectedMoments guarantees can be tightened or made fully explicit, the same split-threshold template would likely yield a cleaner $d^2(\\log\\log d)^2/(\\log d)^2$ bound without the separate $\\log(1/\\varepsilon)$ factor; this is an extension, not a claim of the paper.","The pinching inequality of Lemma 4.8 is a general statement about entropy loss under a direct-sum decomposition and may transfer to other spectral functionals such as R\\u00e9nyi entropies or to entanglement entropy estimation of projected states; the paper does not discuss those applications.","A numerical test of Algorithm 1 on random $d$-dimensional states with explicit constants would reveal whether the asymptotic $o(d^2)$ regime appears at realistic dimensions; the paper reports no such experiment.","The bounded-coefficient polynomial construction for small eigenvalues mirrors the classical Shannon entropy machinery and suggests that the same split-and-correct approach may apply to quantum analogues of other additive distribution functionals."],"forward_implications":["For any fixed additive error $\\varepsilon$, the sample complexity is $O_\\varepsilon(d^2(\\log\\log d)^2/(\\log d)^2)=o(d^2)$, so entropy estimation now costs strictly fewer copies than full quantum state tomography at fixed precision.","The upper bound is within a factor $O(\\log^2 d/(\\log\\log d)^2)$ of the best known lower bound in $d$ and within $O(\\log(1/\\varepsilon))$ in $\\varepsilon$, so under the current lower bounds the rate is nearly optimal in both parameters.","Since the estimator is not a plug-in estimator, it escapes the $\\Omega(d^2/\\varepsilon)$ plug-in lower bound for empirical Young diagram estimators, showing that the quadratic barrier was an artifact of the plug-in strategy rather than of entropy itself.","The protocol is implementable from independent copies of $\\rho$: it measures a two-outcome projector on one sample block, a bounded logarithmic observable on another, and uses a projected-moment estimation primitive on a third."],"supporting_citations":[{"why":"Supplies Lemma 2.10 and Lemma 2.12, the RelativeTomography and ProjectedMoments primitives whose sample counts carry the subquadratic complexity.","marker":"[PSTW26]"},{"why":"Establishes the plug-in/EYD estimator and its quadratic barrier for plug-in estimators, the barrier this paper breaks, and gives the earlier $O(d^2/\\varepsilon^2)$ upper bound.","marker":"[AISW20]"},{"why":"Gives the previous best upper bound $O(d^2/\\varepsilon + \\log^2(d)/\\varepsilon^2)$ that Theorem 1.1 improves in its dependence on $d$.","marker":"[BMW16]"},{"why":"Provides the recent lower bound the paper compares against and nearly matches, showing optimality of the new rate up to small factors.","marker":"[Wan26]"},{"why":"Supplies the mixed-state tomography reduction used to obtain the estimate $\\hat\\rho$ from $n_{\\mathrm{tom}}$ samples.","marker":"[PSTW25]"},{"why":"Provides the pure-state tomography algorithm whose mixed-state version underlies the RelativeTomography primitive.","marker":"[GPS24]"},{"why":"Gives the minimax-optimal classical entropy estimation rates and the polynomial-approximation technique whose quantum analogue is used for the small-eigenvalue block.","marker":"[WY16]"},{"why":"Gives the spectrum-estimation-based entropy estimator with $O(d^2\\log^2(d/\\varepsilon)/\\varepsilon^2)$ samples, one of the prior quadratic-complexity baselines listed in Table 1.","marker":"[OW21]"}],"fun_headline_variants":["Subquadratic sample complexity for von Neumann entropy","First subquadratic estimator for quantum entropy","Quantum entropy estimation breaks the d² barrier","Subquadratic von Neumann entropy estimation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on two unproved imported guarantees\\u2014the simultaneous-observable tomography bound and the projected-moment estimator\\u2014and on the assumption that the hidden constants in the algorithm can be fixed to satisfy all of the proof's inequalities; if any of these fails, the subquadratic sample count does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Subquadratic sample complexity for von Neumann entropy","First subquadratic estimator for quantum entropy","Quantum entropy estimation breaks the d² barrier","Subquadratic von Neumann entropy estimation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000506,"raw_usage":{"total_tokens":2455,"prompt_tokens":921,"completion_tokens":1534,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":537,"completion_tokens_details":{"reasoning_tokens":1491}},"tokens_in":537,"tokens_out":1534,"duration_ms":11709,"temperature":1.0,"reasoning_tokens":1491,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:11:57.252610+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the two imported primitives at exactly the sample counts used in Algorithm 1\\u2014$n=\\Theta(d^2\\log(1/\\varepsilon)/(\\varepsilon^2K^2))$ for RelativeTomography and $n=\\Theta(d^2/(\\varepsilon K^2\\zeta^2))$ for ProjectedMoments\\u2014on states whose large-eigenvalue block has rank about $d/K$ and whose small block has eigenvalues just below $2B$; if the simultaneous observable errors or the projected-moment errors exceed the bounds of Lemmas 2.10 and 2.12, the claimed sample complexity of Theorem 1.1 is not achieved.","supporting_citations":[],"review_version":1}