Nearly tight lower bounds for estimating quantum functionals: Uhlmann fidelity, trace distance, and von Neumann entropy

Qisheng Wang

REVIEW 3 major objections 4 minor 16 references

Nearly tight lower bounds for estimating quantum functionals: Uhlmann fidelity, trace distance, and von Neumann entropy

T0 review · 3 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Estimating Uhlmann fidelity, trace distance, or von Neumann entropy of a d-dimensional quantum state requires Ω̃(d²) samples, matching known upper bounds up to polylog factors.

desk verdict The central Ω~(d²) lower-bound claim is very likely correct and important, but the current manuscript has a fixable isometry bug in the key lemma and an unproved, sign-error-ridden moment-matching corollary; it deserves peer review, not desk rejection. read the letter →

arxiv 2608.02600 v1 pith:VHC3UTHG submitted 2026-08-03 quant-ph cs.CCcs.ITmath.IT

Qisheng Wang This is my paper

classification quant-phcs.CCcs.ITmath.IT

keywords boundslowerquantumdistanceentropyestimatingfidelityfunctionals

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Quantum states are described by long lists of numbers. Three summary quantities matter for experiments: fidelity (how much two states overlap), trace distance (a statistical distance between states), and von Neumann entropy (how random a state is). Existing algorithms estimate all three using about d² copies of a d-dimensional state, where d can be in the thousands; the strongest previously proven lower bound only showed that about d copies are needed. This paper closes the gap: estimating these three quantities requires roughly d² samples.

The proof builds two families of quantum states that no measurement on fewer than roughly d² copies can tell apart, even though the families have different values of the quantity being estimated. The trick is classical: pick two probability distributions whose first K moments agree exactly — averages, variances, higher moments — but whose expectations of the relevant function (√x, |x−1|/2, x log x) differ by a constant. The distributions sit in the eigenvalues of states with random directions, and Schur–Weyl duality — the mathematics of many copies of a random state — proves indistinguishability up to d²/polylog(d) copies.

If the details check out, roughly a dozen quantum algorithms from the last decade are essentially optimal in copy count; future work should focus on constants and time. The submission is openly a draft: the Acknowledgements promise more literature comparisons, readability, and refined proofs in a later version, and load-bearing steps — the moment-matching distributions of Section 2.2 and a channel definition in Lemma 4.1 — are not fully written.

Extended reading notes

Core claim

Theorem 1.1: 'Estimating the Uhlmann fidelity F(ρ,σ), trace distance T(ρ,σ), and von Neumann entropy S(ρ) requires sample complexity Ω̃(d²)', with ε-dependence Ω(d²/(ε² log⁴ d)) for fidelity and trace distance, and Ω(d²/(ε log⁴ d log² log d) + log² d/ε²) for entropy (Sections 1, 5, 6). If true, no estimator reading n ≪ d²/polylog(d) copies of an unknown d-dimensional state achieves constant additive error on any of the three functionals, and the quadratic-in-d scaling of the known algorithms ([UNWT25], [LT26], [WZ24], [WZ25b], [AISW20], [BMW16]) is inherent. The framework reduces every case to constructing two distributions μ₀, μ₁ on [1/4, Θ(K²)] whose first K+1 moments match yet whose expectation of φ ∈ {√x, |x−1|/2, x log x} differs by Ω(1) (Corollaries 2.4–2.6), and then hiding them in the eigenvalues of a Haar-randomly rotated state (Section 4).

Load-bearing premise

Lemma 4.1 — the indistinguishability of the two hard ensembles — assumes a channel Φ exists, independent of the i-th eigenvector pair (Y_i, |u_i⟩), with Φ(ς_{Z,u_i}) = σ_{i,t} on the good event E_i = {U_i ≤ r/(2t) − M}, where Z = t(D_i(Y_i−1)+U_i)/(D_i−tU_i) (Section 4, Lemma 4.1 proof, the paragraph defining the superoperator Φ). The step needs (i) moment-matched Y_i to stay moment-matched through Z — true because Z is affine in Y_i given the conditioned variables — and (ii) an isometry V_i whose columns span W_i, the orthogonal complement of the other eigenvectors. The displayed V_i = [|u₁⟩ … |u_{i−1}⟩ |u_{i+1}⟩ … |u_q⟩] lies in the complement of W_i and has the wrong shape (d × (q−1) rather than d × D_i); as written it annihilates the |u_i⟩ component, so the equality fails. The central lower bound collapses if this is not a transcription error. The author must also supply the missing proofs of Corollaries 2.4–2.6, since the moment-matching distributions are load-bearing.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take on arXiv:2608.02600. The headline is that this paper claims to close the decade-old Ω(d)-vs-O(d²) gap for sample complexity of estimating Uhlmann fidelity, trace distance, and von Neumann entropy, with matching lower bounds Ω~(d²). That would be a real result: the previous lower bound was only Ω(d) from OW21, and a dozen upper-bound papers since 2016 would become essentially optimal. The core recipe is right: take classical moment-matching distributions, hide them in the eigenvalues of a Haar-randomly rotated state, and use Schur–Weyl invariance to show n≪d² copies cannot distinguish the two hypotheses. Section 2's reduction to functionals L_φ and the ε-scaling arguments (t=Θ(ε), p=Θ(ε²)) are sound. The trace distance proof in Theorem 5.1 is essentially complete, modulo the moment-matching corollaries.

The soft spots are real, but in proportion they are addressable, not fatal. First, Lemma 4.1's displayed V_i is wrong: the matrix [|u1>…|ui-1>|ui+1>…|uq>] has q−1 columns in the span of {|u_j>:j≠i}, which is W_i^⊥, not W_i. With that V_i, V_i^† annihilates |u_i>, so Φ(ς_{Z,u_i})≠σ_{i,t}. The fix is easy—take V_i to be any isometry with range W_i, e.g., the inclusion map—and then Φ(X)=(A/d)X+(1−A/d)ω_i tr(X) does the job. But the proof as written does not discharge the central indistinguishability step. Second, Corollaries 2.4–2.6, which supply the moment-matched distributions, are asserted without proof. Worse, Corollary 2.6's displayed positive separation is actually negative: (4/5)log(5/8)−(1/2)log2 < 0. That is a sign error in a load-bearing constant, so the entropy lower bound's main term is currently unsupported. Third, Section 1.4 honestly says this is a preliminary version: comparisons, readability, refined proofs, applications are pending. That is transparent, but it confirms the manuscript is not self-contained.

Is the central claim true? I'd bet yes. The framework is the standard hard-instance construction, and the errors smell like typos and omitted details rather than conceptual failures. The reader's CONDITIONAL verdict is fair; the stress-test's concern is real but repairable.

Recommendation: send it out. A good referee can verify the repaired Lemma 4.1 and ask for the missing corollary proofs. If the constants work out, this is a publishable resolution of a real open problem. If not, the errors will be caught. It deserves referee time.

Referee Report

3 major / 4 minor

Summary. The paper presents a unified framework for proving sample lower bounds for estimating three quantum functionals—Uhlmann fidelity, trace distance, and von Neumann entropy. The main claim (Theorem 1.1) is that each requires Ω~(d^2) samples, with explicit ε-dependence: Ω(d^2/(ε^2 log^4 d)) for fidelity and trace distance, and Ω(d^2/(ε log^4 d log^2 log d) + log^2 d/ε^2) for entropy. The framework reduces the problem to constructing pairs of probability distributions with matching moments but different expectations under φ ∈ {√x, |x−1|/2, x log x}, then embedding them as eigenvalues of a Haar-randomly rotated quantum state. The core technical steps are: exact identities linking the functionals to L_φ(ρ), a Schur–Weyl sampling indistinguishability lemma (Theorem 3.1), and a reduction lemma (Lemma 4.1) that turns moment matching into n-copy indistinguishability. Corollaries give matching query lower bounds via sample-to-query lifting.

Significance. If correct, these results resolve a substantial open problem in quantum state property estimation, settling the sample complexity of fidelity, trace distance, and von Neumann entropy estimation up to polylogarithmic factors. The framework is elegant and genuinely unifying: it connects classical moment-matching techniques for functional estimation with Schur–Weyl sampling and Haar-random rotations. The hard instances are explicit and parameter-free, with no fitted constants. The paper also correctly identifies that the lower bounds imply near-optimality of a wide range of existing quantum algorithms (e.g., [AISW20], [WZ24], [UNWT25]). The derivation of the functional identities (Section 2) is clean, and the main high-level structure—moment matching to eigenvalue perturbations to n-copy indistinguishability—is convincing. However, several load-bearing proof details are missing or incorrect as written, and these must be fixed before the claims are fully established.

major comments (3)

[Section 4, Lemma 4.1] The displayed isometry V_i = [|u1> … |u_{i-1}> |u_{i+1}> … |uq>] ∈ C^{d×D_i} is dimensionally wrong: it has q−1 columns, not D_i = d−q+1. More importantly, its columns lie in W_i^⊥, not W_i, so V_i^† annihilates |u_i> and V_i ς_{Z,u_i} V_i^† cannot produce the (1+tX_i)/d |u_i><u_i| contribution to σ_{i,t}. The claimed identity Φ(ς_{Z,u_i}) = σ_{i,t} fails as written. This is the central bridge between moment matching and n-copy indistinguishability, so the proofs of Theorems 5.1, 6.4, and 6.5 are not discharged. The repair is straightforward: take V_i to be any isometry from C^{D_i} into C^d with range W_i (e.g., the natural inclusion map). With that replacement, Φ is CPTP and the identity holds on E_i. The manuscript must be corrected.
[Section 2.1, Lemma 2.3 and Corollaries 2.4–2.6] The proof of Lemma 2.3 sets ν_1 = 2Λ_+ and ν_0 = 2Λ_- as 'two probability distributions'. Under Fact 2.1's normalization 1/2∫|Λ|=1, we have ∫Λ_+=∫Λ_-=1, so 2Λ_± have total mass 2, not 1. Using the probability measures Λ_± instead gives a φ-gap of Δ/6, not Δ/3; the factor-of-two discrepancy is not accounted for. In addition, Corollaries 2.4–2.6 are stated without proof. These corollaries supply the moment-matched distributions and the crucial support bounds (M=Θ(K^2) and M=Θ(K^2 log K)) that Theorems 5.1 and Section 6 rely on. The missing proofs are load-bearing for the claimed rates. The factor is harmless for big-O lower bounds, but the derivation must be corrected and the corollaries proved.
[Section 6.2, Theorems 6.4 and 6.5] The reduction from constant-precision indistinguishability to ε-precision via mixing with |0> states is stated without proof. For \tilde ρ = (1-p)|0><0| ⊕ pρ, the n-copy state is a direct sum over subsets S of size k with weight (1-p)^{n-k}p^k, and the claim T(E_{Π0}\tilde ρ^{⊗n}, E_{Π1}\tilde ρ^{⊗n}) = o(1) for n ≤ c n0/p requires a binomial large-deviation argument (Pr[K>n0] small) and a crude bound on T_k for k>n0. This argument is missing. Also, in the proof of Theorem 6.4, the second expectation in the trace distance is over Π0, which is a typo; it should be over Π1.

minor comments (4)

[Section 1.4] The Acknowledgment contains placeholder text ('In the next version of this paper...') and should be removed or replaced with substantive acknowledgments.
[Lemma 2.3 statement] The support of Y is stated as [1/4, 1/4+3a/4], but from Y = 1/4 + 3T/(4a) with T∈{0}∪[a/2,1] the support should be [1/4, 1/4+3/(4a)].
[Lemma 2.3 proof] In the displayed chain, the second inequality should involve Ψ_{φ,a}, not x^j: it reads '∫ x^j dν1 − ∫ x^j dν0 ≥ 2Δφ/(3a)' but the integrand should be Ψ_{φ,a}.
[Theorem 6.4 proof] The expression T(E_{ρ∼Π0} \tilde ρ^{⊗n}, E_{ρ∼Π0} \tilde ρ^{⊗n}) should have the second expectation over Π1, not Π0.

Assumptions & free parameters 5 free parameters · 7 assumptions · 0 invented entities

The ledger is lean: no fitted data, no invented entities. The hard-instance states ρ_{b,t} are constructions, not postulates. The load-bearing background consists of published external results (Fact 2.1 from JVHW17/WY16; Schur–Weyl theorems from OW21; the d↑μ bound from AISW20; the classical entropy lower bound from JVHW17/WY16; the sample-to-query lifting from WZ25a/TWZ25/CWZ25). The hand-chosen parameters listed above are construction constants; they set the polylog exponents and ε-scaling but are not fit to any datum. The only un-discharged assumption is the channel-reduction step in Lemma 4.1, whose written form is internally inconsistent and is flagged separately.

free parameters (5)

c₀ = 1/4, s₀ = 3/4 = c₀ = 1/4, s₀ = 3/4
Fixed constants in the map Y = c₀ + (s₀/a)T used to convert the signed-measure variable T into the hard-instance eigenvalue distributions; hand-chosen so that both μ₀ and μ₁ have mean E[Y] = 5/8 (Section 2.1, proof of Lemma 2.3). Not fitted to data.
a ∈ (0, 1/2] = unspecified in (0,1/2]; implicitly Θ(1/K²)
Scaling parameter of the polynomial-approximation interval I_a = [a/2, 1] in Lemma 2.2; sets the support [1/4, Θ(K²)] of the moment-matching distributions in Corollaries 2.4–2.6.
K = ⌈log₂ d⌉ (L = K+1) = ⌈log₂ d⌉
Moment-matching order. Chosen as Θ(log d) so the indistinguishability error 4^(−L) is o(1) while the sample threshold n₀ = Θ(d²/K⁴) gives the desired d²/polylog(d) scale (Sections 3, 5).
M (support bound of μ_b) = Θ(K²) for fidelity/trace distance; Θ(K² log K) for entropy
Support bound of the moment-matching distributions; enters the indistinguishability threshold n₀ = Θ(d²/(t²M²)) and thereby produces the log⁴ d and log² log d factors in the rates.
t, p (precision-scaling parameters) = t = Θ(ε) (trace distance); p = Θ(ε²) (fidelity); p = Θ(ε) (entropy)
Link the constant-precision hard-instance gap to additive error ε (Theorems 5.1, 6.4, 6.5): chosen so the functional gap is Ω(ε) while the indistinguishability threshold scales as d²/ε² or d²/ε.

assumptions (7)

standard math Fact 2.1: if E_K(f,I) > 0 there exists a finite signed Borel measure Λ on I with (1/2)∫|Λ| = 1, ∫x^j dΛ = 0 for j = 0..K, and ∫f dΛ = E_K(f,I)
Cited from [JVHW17, Lemma 10] and [WY16, Appendix E]. The entire construction of the moment-matching distributions μ₀, μ₁ (Lemma 2.3) rests on this existence theorem (Section 2.1).
standard math Schur–Weyl expansion (OW21 Thms 4.6–4.7): s_λ(1+zv)/s_λ(1) = Σ_μ z^{|μ|} s_μ(v)/d↑μ s_μ(λ) and the orthogonality E[A_s A_t] = δ_{s=t} n↓t Σ s_μ(v)²/(d↑μ d^t)
From [OW21] (quantum spectrum testing). The indistinguishability bound of Lemma 3.1 — the core of the framework — is built directly on these two theorems (Section 3).
standard math d↑μ ≥ (d/e)^t for |μ| = t (AISW20 Lemma 15)
Used inside Lemma 3.1's bound on E[(Δ_L)²] to absorb the partition-count and Schur-value factors into the 8e constant (Section 3).
domain assumption Quantum sample-to-query lifting converts Ω̃(d²) sample lower bounds to Ω̃(d) query lower bounds under purified query access
Theorem 1.3 invokes [WZ25a], [TWZ25], [CWZ25] (two of three self-authored). The lifting is a published SIAM J. Comput. theorem with its own proof, so the step is not circular, but the applicability conditions are not restated in this paper.
domain assumption Given rows |u_j⟩ (j≠i) of a Haar unitary, the conditional distribution of |u_i⟩ is Haar-uniform on W_i = span{|u_j⟩: j≠i}⊥
Needed in Lemma 4.1 to reuse Lemma 3.1 with |u_i⟩ Haar on the D_i-dimensional subspace W_i; standard invariant property of Haar unitaries, unstated in detail (Section 4).
standard math Markov brothers' inequality: sup_{I_a}|p′| ≤ 4K² sup_{I_a}|p| for deg(p) ≤ K
Used in Lemma 2.2 to convert the separation of p at two points into the contradiction that yields E_K(Ψ_{φ,a}, I_a) ≥ Δ_φ/(3a) (Section 2.1).
standard math Classical Shannon entropy estimation requires Ω(log² d/ε²) samples
Import of [JVHW17, WY16] as the second term of Theorem 6.5's entropy lower bound; the bound transfers to quantum states because diagonal density matrices simulate classical distributions (Section 6.2).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nearly tight lower bounds for estimating quantum functionals: Uhlmann fidelity, trace distance, and von Neumann entropy." pith.science (2026). https://pith.science/paper/VHC3UTHG

@misc{pith2026260802600,
  author       = {Pith},
  title        = {Pith review of: Nearly tight lower bounds for estimating quantum functionals: Uhlmann fidelity, trace distance, and von Neumann entropy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VHC3UTHG}},
  note         = {Machine review of arXiv:2608.02600}
}

abstract

In this paper, we present a unified framework for proving lower bounds for estimating functionals of quantum states. We therefore resolve several open problems by establishing lower bounds that match known upper bounds: we show that it requires $\widetilde{\Omega}(N^2)$ samples to estimate the Uhlmann fidelity, trace distance, and von Neumann entropy. Moreover, they immediately imply matching query lower bounds of $\widetilde{\Omega}(N)$ by quantum sample-to-query lifting. These lower bounds imply the near-optimality of a dozen quantum algorithms since 2016.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

16 extracted references · 4 linked inside Pith

[1]

Communications in Mathematical Physics , volume =

O'Donnell, Ryan and Wright, John , title =. Communications in Mathematical Physics , volume =. doi:10.1007/s00220-021-04180-1 , year =

doi:10.1007/s00220-021-04180-1
[2]

and Wagner, Aaron B

Acharya, Jayadev and Issa, Ibrahim and Shende, Nirmal V. and Wagner, Aaron B. , title =. IEEE Journal on Selected Areas in Information Theory , volume =. doi:10.1109/JSAIT.2020.3015235 , year =

arXiv 2020
[3]

IEEE Transactions on Information Theory , volume =

Wu, Yihong and Yang, Pengkun , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2016.2548468 , year =

arXiv 2016
[4]

IEEE Transactions on Information Theory , volume =

Jiao, Jiantao and Venkat, Kartik and Han, Yanjun and Weissman, Tsachy , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2017.2733537 , year =

arXiv 2017
[5]

Quantum algorithms for

Utsumi, Takeru and Nakata, Yoshifumi and Wang, Qisheng and Takagi, Ryuji , howpublished=. Quantum algorithms for. 2509.03619 , year=

arXiv
[6]

2606.23592 , year=

Random dimension reduction and learning symmetric properties of quantum states , author=. 2606.23592 , year=

arXiv
[7]

Bavarian, Mohammad and Mehraban, Saeed and Wright, John , title =
[8]

IEEE Transactions on Information Theory , volume =

Fast quantum algorithms for trace distance estimation , author =. IEEE Transactions on Information Theory , volume =. 2024 , doi =

2024

Show all 16 references

[9]

2606.26034 , year=

Wang, Qisheng , title =. 2606.26034 , year=

arXiv
[10]

2512.01971 , year =

A list of complexity bounds for property testing by quantum sample-to-query lifting , author =. 2512.01971 , year =
[11]

IEEE Transactions on Information Theory , volume =

Wang, Qisheng and Zhang, Zhicheng , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2025.3576137 , year =

2025
[12]

Distributional property testing in a quantum world , booktitle =

Gily. Distributional property testing in a quantum world , booktitle =. doi:10.4230/LIPIcs.ITCS.2020.25 , year =

2020 doi
[13]

IEEE Transactions on Information Theory , volume =

Wang, Qisheng and Guan, Ji and Liu, Junyi and Zhang, Zhicheng and Ying, Mingsheng , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2024.3399014 , year =

2024
[14]

SIAM Journal on Computing , volume =

Wang, Qisheng and Zhang, Zhicheng , title =. SIAM Journal on Computing , volume =. doi:10.1137/24M1638616 , year =

doi
[15]

2510.07622 , year =

Conjugate queries can help , author =. 2510.07622 , year =

arXiv
[16]

2607.29680 , year =

Spectrum Estimation is Almost as Hard as Tomography , author =. 2607.29680 , year =

arXiv

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

Communications in Mathematical Physics , volume =

O'Donnell, Ryan and Wright, John , title =. Communications in Mathematical Physics , volume =. doi:10.1007/s00220-021-04180-1 , year =

doi:10.1007/s00220-021-04180-1

[2] [2]

and Wagner, Aaron B

Acharya, Jayadev and Issa, Ibrahim and Shende, Nirmal V. and Wagner, Aaron B. , title =. IEEE Journal on Selected Areas in Information Theory , volume =. doi:10.1109/JSAIT.2020.3015235 , year =

arXiv 2020

[3] [3]

IEEE Transactions on Information Theory , volume =

Wu, Yihong and Yang, Pengkun , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2016.2548468 , year =

arXiv 2016

[4] [4]

IEEE Transactions on Information Theory , volume =

Jiao, Jiantao and Venkat, Kartik and Han, Yanjun and Weissman, Tsachy , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2017.2733537 , year =

arXiv 2017

[5] [5]

Quantum algorithms for

Utsumi, Takeru and Nakata, Yoshifumi and Wang, Qisheng and Takagi, Ryuji , howpublished=. Quantum algorithms for. 2509.03619 , year=

arXiv

[6] [6]

2606.23592 , year=

Random dimension reduction and learning symmetric properties of quantum states , author=. 2606.23592 , year=

arXiv

[7] [7]

Bavarian, Mohammad and Mehraban, Saeed and Wright, John , title =

[8] [8]

IEEE Transactions on Information Theory , volume =

Fast quantum algorithms for trace distance estimation , author =. IEEE Transactions on Information Theory , volume =. 2024 , doi =

2024