Approximating the Trace Distance Between Product Quantum States

Dimitrios Myrisiotis; Junhong Nie; Kun He; Zongqi Wan

REVIEW 2 major objections 4 minor 29 references

Approximating the Trace Distance Between Product Quantum States

T0 review · 2 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 This paper gives a deterministic polynomial-time algorithm that approximates the trace distance between two product quantum states within a universal factor of 4.73, and proves exact computation is #P-hard even for diagonal qubit inputs.

desk verdict Genuinely new deterministic 4.73-approximation for noncommuting product-state trace distance; coherent proof whose two fragile external steps—the conic-program black box and the asserted dual formula—need referee pressure before the poly-time claim is fully self-contained. read the letter →

arxiv 2608.01841 v1 pith:HHPAFLLW submitted 2026-08-03 cs.DS

Kun He , Dimitrios Myrisiotis , Junhong Nie , Zongqi Wan This is my paper

classification cs.DS MSC 68Q1768W2581P45

keywords tracedistanceproductstatesapproximationalgorithmquantumstatediscriminationnormconvexoptimizationtotalvariationUhlmannfidelity

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

This paper asks whether the trace distance between two product quantum states—the maximum advantage any measurement can have in telling them apart—can be computed efficiently from the local factors, when the global Hilbert space is exponentially large. The answer is a deterministic yes within a universal constant: the paper proves a polynomial-time algorithm in the number of factors, local dimension, and input bit length outputs a rational estimate within a factor 4.73 of the true distance. The approximation is multiplicative, so it remains meaningful in the hard nearly indistinguishable regime where fidelity bounds blow up and the true distance can be exponentially small. The paper also proves that exact computation is #P-hard even when each local state is a diagonal qubit, so the problem sits between exact hardness and fine-grained relative approximation.

What carries the argument

The key machinery is the decomposition of the difference state into Uhlmann-optimal product purifications, isolating the first-order part X_1 (Definition 3.4), together with the local convex surrogate K_loc(x; Ω) defined as an infimal convolution of trace norms (head) and Jordan-square costs (tail). The paper proves X_1 = (∏ c_i²) Y where Y = ∑_i Ω_{≠i} ⊗ x_i, with Ω_i the local bisector state and x_i = (ρ_i−σ_i)/c_i². The trace norm of Y is compared with K_loc through two inequalities: one direction follows from a matrix square-function estimate, the reverse direction from duality that dephases Y into independent scalar variables and applies a centered Johnson–Schechtman disjointification b

What would settle it

Take a small rational product pair (for example n=3, m=2), compute the true trace distance by exact diagonalization of the 8×8 difference matrix, run the paper's algorithm, and check the 4.73 sandwich; a single counterexample falsifies the theorem. Alternatively, exhibit any feasible instance of (3.3) arising from the construction whose optimum cannot be certified in polynomial time—for instance, because the feasible set has no polynomial-time separation oracle—which would falsify the runtime guarantee.

Watch

Extended reading notes

Core claim

The central discovery is that the global trace distance of two product states is controlled, within universal constants, by two local quantities: the fidelity defect δ_F = 1 − ∏_i F(ρ_i, σ_i) and the trace norm of a first-order operator X_1 built from Uhlmann-optimal local purifications. The paper proves ∥ρ−σ∥₁ ≤ ∥X₁∥₁ + 4δ_F and ∥X₁∥₁ ≤ 3∥ρ−σ∥₁. The operator X₁, after extracting a locally computable scalar, becomes a sum of tensor products Ω_{≠i} ⊗ x_i, and the paper shows its trace norm is within the dimension-free constant θ = 4 + 4 log 2 of a convex local surrogate K_loc. That surrogate is the optimum of a polynomial-size conic program with variables only of local size, so the exponentia

Load-bearing premise

The whole polynomial-time guarantee rests on the claim, made in the proof of Theorem 3.8, that the conic program (3.3) can be solved to certified additive error in polynomial time by 'standard weak conic optimization'; the paper supplies no separation oracle, bit-length bounds, or solver implementation, and if solving (3.3) to the required precision is not feasible in polynomial time, the running-time result collapses.

Editorial extensions

If this is right

Product-state trace distance is approximable in polynomial time with a universal constant, even though exact computation is #P-hard and the global Hilbert space dimension is exponential.
The approximation is multiplicative and uniform, covering the nearly indistinguishable regime where fidelity bounds like Fuchs–van de Graaf have unbounded ratio; the algorithm returns zero exactly when the two states are identical.
The result separates the commuting (classical product distribution) case—where fully polynomial-time approximation schemes are known—from the noncommuting case, showing that noncommutativity alone does not prevent constant-factor approximation for succinctly specified product inputs.
The hardness result shows exact trace distance is #P-hard even for diagonal qubit product states, matching known hardness for total variation distance between product distributions.
The structural inequality ∥X₁∥₁ ≤ 3∥ρ−σ∥₁ and the local conic surrogate give a template for approximating other global tensor-product norms without ever constructing the global operator.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the conic-solver gap is closed with an explicit polynomial-time separation oracle or a self-contained interior-point analysis, the same 4.73 guarantee becomes fully constructive; until then the runtime claim inherits a black-box assumption.
The local head–tail surrogate suggests a route toward approximating trace norms of other structured tensor sums, such as matrix-product operators of bounded bond dimension, where a similar first-order truncation might hold.
One could test numerically whether the constant 4 + 4 log 2 in the scalar disjointification bound is tight for small n; any smaller admissible constant would immediately improve the approximation factor, since 4.73 is computed directly from θ.
Whether a (1+ε)-relative approximation exists for noncommuting product states is left open; a natural next step is to check whether the first-order reduction becomes exact in some asymptotic regime or whether a different measurement-local argument can achieve a polynomial-time approximation scheme.

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

Two things to know before you spend time on 2608.01841. The main theorem is genuinely new: a deterministic poly(n,m,B)-time approximation of trace distance between noncommuting product states, with a universal constant factor pinned at 4.73. Prior work covered commuting product distributions or quantum-access models; the noncommuting succinct case was open, and this is the first constant-factor algorithm for it. Second, the proof is coherent and the constant is tracked end-to-end, but two load-bearing steps sit outside the proofs as given: the conic program in Theorem 3.8 is delegated to "standard weak conic optimization," and the dual formula in Theorem 3.7 is asserted with "duality gives." Neither looks wrong; both need referee attention.

What earns credit. The first-order reduction is the right pivot: Uhlmann-optimal purifications, truncate at two or more excitations, and let fidelity absorb the discarded mass. Theorem 3.5's bound is clean, and the local convex surrogate in Section 3.4 is a genuine technical idea—a dimension-free comparison between a global trace norm and a local infimal convolution. The paper also handles the hard cases honestly: Lemma 3.1 gives an explicit 2^{-O(B)} lower bound for nonzero inputs, regularization gets a quantitative eigenvalue floor, and the approximation-factor arithmetic checks out (I re-ran the 4.7293 < 4.73 comparisons). The #P-hardness is a simple diagonal-embedding reduction, correctly one paragraph. Related-work coverage matches what I know of that literature: classical FPTAS, quantum-access additive-error bounds, tensor-network heuristics.

Soft spots, in proportion. Theorem 3.8 is the real gap. The whole polynomial-time claim rests on solving (3.3), and the proof does not provide a precise oracle-based theorem statement, verified weak separation oracles, or output bit-length bounds. The paper does give a strict feasible point and claims bounded inner/outer radii, so this is a completeness gap in the standard GLS-ellipsoid pattern, not a demonstrated contradiction—but the hypotheses need explicit checking. Second, the dual characterization in Theorem 3.7 is stated without derivation, and it is exactly the step that carries the reverse inequality K_loc ≤ θ||Y||₁; a subtle sign or norm error there would collapse the constant. I read it as plausible but unproven. Minor: the authors acknowledge heavy AI assistance and take responsibility; that is honest, but it raises rather than lowers the bar for independent verification of exactly these two steps.

Who it is for and what I would do. This deserves a serious referee; the result is important enough for quantum information and the technique is novel enough to justify engagement. I would send it for review and, if I were the referee, ask for (1) a full proof of the dual formula and (2) an explicit instantiation of the weak-optimization step with the oracle hypotheses verified. Conditional accept is in reach if those land.

Referee Report

2 major / 4 minor

Summary. The paper studies the trace distance between two product quantum states specified by their local density matrices. The main contribution is a deterministic polynomial-time algorithm (in the number of factors n, local dimension m, and input bit length B) that outputs a rational approximation within a universal constant factor 4.73. The algorithm first performs exact zero detection and a white-noise regularization, then reduces the global distance to two locally computable quantities: the product-fidelity defect and the trace norm of a structured first-order operator X1. The latter is estimated through a local convex surrogate (3.3), whose optimal value is compared with ||X1||_1 via a square-function upper bound and a dual lower bound based on a centered Johnson--Schechtman disjointification estimate. The paper also proves that exact computation of the trace distance is #P-hard already for rational diagonal qubit states, via the #P-hardness of total variation distance for product distributions. The proof is organized into detailed lemmas; several computational and analytic steps are deferred to appendices.

Significance. If the proof is completed, this is a significant algorithmic result: it shows that a global, exponentially sized distinguishing quantity can be approximated to a universal constant factor in polynomial time from succinct product-state descriptions, despite the absence of a common eigenbasis and the possibility of exponentially small distances. The paper is careful with the approximation constant and error propagation, and it gives exact zero detection and a clean hardness complement. The use of Uhlmann purifications and a local convex surrogate is a meaningful structural idea. The manuscript does not fit parameters to data, and the constants are explicit.

major comments (2)

[Theorem 3.8 (proof, after Eq. (3.18))] The polynomial-time guarantee of the main theorem rests on the assertion that the conic program (3.3) can be solved to certified additive error by 'standard weak conic optimization'. This is load-bearing: if (3.3) cannot be solved in the stated time, Theorem 3.10 collapses. The proof does not state or verify the hypotheses of any concrete weak-optimization theorem: no separation oracle is exhibited for the intersection of the PSD blocks and the ellipsoidal cone z^T Q z <= t^2, no starting point/outer-radius/inner-radius are quantified rigorously, and no bit-length bound for the rational output bK is given. Please provide a precise lemma (e.g., ellipsoid method or a citation to a standard theorem) and verify these conditions for the specific program, or replace the delegation by a fully specified polynomial-time algorithm.
[Theorem 3.7 (first display of the proof)] The reverse bound Kloc(x; Omega) <= theta ||Y||_1 depends on the exact dual formula asserted immediately after 'Duality for the infimal convolution in (3.15) gives'. This dual characterization is nontrivial, involving the eigenvalue-range norm alpha_i and the weighted variance beta_i, and it is load-bearing for the lower bound. The paper does not provide a proof or a precise citation, nor does it check the Slater/feasibility conditions under which strong duality holds for this infinite-dimensional-looking but finite-dimensional program. Please supply a complete derivation, including the identification of the dual norm on the traceless Hermitian subspace and the invertibility of the map a_i -> (Omega_i a_i + a_i Omega_i)/2.

minor comments (4)

[Algorithm 1, lines 9-10 and Section 3.2] The same symbol f_i is used for the lower enclosure and for the upper enclosure in the pseudocode and in the text. This is confusing; use f_i^- and f_i^+, or similar, consistently.
[References] The reference key [L W17] has a typographical space in the author name/citation key; it should be [LW17].
[Algorithm 1, line 14] The pseudocode states the solver returns OPT <= eN <= OPT + beta L/8, while Theorem 3.8 uses a general eta = beta lambda. The reader has to reconcile the two; a pointer to the theorem or a definition of lambda in the pseudocode would help.
[Section 3.4, proof of Theorem 3.8] The sentence 'the cone has a polynomial-time weak separation oracle' is too terse. Even if a standard solver is invoked, the separation oracle for the ellipsoidal cone should be stated explicitly, since weak separation for PSD constraints alone is not sufficient for the joint constraint.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivation is self-contained; the main theorem reduces to analytic inequalities and a conic program whose value is proven to approximate the target norm, not fitted to it.

full rationale

The paper's derivation chain is not circular. The constant-factor approximation is built from independent analytic ingredients: fidelity tensorization, Fuchs–van de Graaf inequalities, a self-contained Johnson–Schechtman disjointification estimate (Appendix A.1), and two-sided bounds on the local conic surrogate Kloc (Theorems 3.6 and 3.7). The conic program (3.3) is not defined in terms of the target trace distance; its optimum is proven to lie within a dimension-free constant of the first-order operator norm via the duality/dephasing argument of Theorem 3.7, and the final output is assembled from certified approximations to fidelity defects and this norm. No parameter is fitted to the answer, and no 'prediction' is defined as the input by construction. The only self-citation, the #P-hardness of total variation distance [BGM+25], is an external published result used for the hardness direction and is not load-bearing for the main approximation theorem. The claimed polynomial-time guarantee does depend on an unproven 'standard weak conic optimization' black box in Theorem 3.8, but that is a completeness or verification gap about solver hypotheses, not a circular reduction; it does not make the result equivalent to its inputs by definition. Overall, the central claim has independent mathematical content and no circular dependency was found.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The proof relies on standard inequalities and convex optimization machinery. The novel 'first-order operator' and 'bisector state' are defined mathematical objects, not new physical entities. The only non-standard dependency is the external conic solver.

free parameters (3)

beta = 10^-3
Hand-chosen tolerance controlling precision of fidelity and first-order estimates; appears in p, eta, and the final constant. The result holds for any sufficiently small beta, and this value yields the 4.73 factor.
tau = L/(2000n)
Regularization noise level set from the input-dependent lower bound L to control regularization error. It is a design choice, not a fit to data.
rescaling constant = 10583/100000
Chosen so that the final displayed bounds close under the 4.73 factor. A derived arithmetic choice, not a fit.

assumptions (6)

standard math Fuchs-van de Graaf inequalities
Used in Lemma 2.1 and throughout to relate fidelity and trace distance.
standard math Uhlmann's theorem (matrix form)
Used to construct fidelity-attaining purifications in Section 3.3 and Lemma 3.3.
standard math Sharp L1 Khintchine inequality (Szarek)
Used in Appendix A.1 to prove the centered disjointification estimate (Theorem 2.3).
standard math Weyl's eigenvalue perturbation bound
Used in Lemma B.2 and Theorem 3.9 to justify eigenvalue lower bounds after approximation.
standard math Matrix square-root perturbation bound (Schmitt)
Used in Lemma B.3 to control the error between exact and approximated square roots.
domain assumption Standard weak conic optimization / ellipsoid method for convex programs with weak separation oracle
Invoked in Theorem 3.8 to solve the conic program (3.3) in polynomial time. Not proven in the paper; the separation oracle and error analysis are not supplied.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Approximating the Trace Distance Between Product Quantum States." pith.science (2026). https://pith.science/paper/HHPAFLLW

@misc{pith2026260801841,
  author       = {Pith},
  title        = {Pith review of: Approximating the Trace Distance Between Product Quantum States},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HHPAFLLW}},
  note         = {Machine review of arXiv:2608.01841}
}

abstract

We study the trace distance \[D_{\mathrm{tr}}(\rho,\sigma) =\frac12\|\rho-\sigma\|_1, \rho=\bigotimes_{i=1}^n\rho_i,\quad \sigma=\bigotimes_{i=1}^n\sigma_i, \] when the two exponentially large states are specified by their local factors. We give a deterministic approximation within a universal constant factor for rational product inputs. Its running time is polynomial in the number of factors, the local dimension, and the input bit length. In the opposite direction, exact computation is $\#\mathsf P$-hard even for diagonal qubit states, by the corresponding hardness of total variation distance between product distributions. The proof uses local Uhlmann-optimal purifications to reduce the problem to estimating the product-fidelity defect and the trace norm of a structured first-order operator. Although this operator acts on an exponentially large space, we approximate its trace norm by a local convex surrogate that admits a polynomial-size classical conic formulation. A square-function estimate shows that the surrogate upper-bounds this trace norm. Conversely, duality and local dephasing reduce the reverse comparison to a head--tail inequality for independent centered random variables, showing that the surrogate is at most a dimension-free constant times the same norm.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references

[1]

and Myrisiotis, Dimitrios and Pavan, A

Bhattacharyya, Arnab and Gayen, Sutanu and Meel, Kuldeep S. and Myrisiotis, Dimitrios and Pavan, A. and Vinodchandran, N. V. , title =. Information Processing Letters , volume =. 2025 , doi =

2025
[2]

TheoretiCS , volume =

Feng, Weiming and Guo, Heng and Jerrum, Mark and Wang, Jiaheng , title =. TheoretiCS , volume =. 2023 , doi =

2023
[3]

, title =

Recht, Benjamin and Fazel, Maryam and Parrilo, Pablo A. , title =. SIAM Review , volume =. 2010 , doi =

2010
[4]

Exact Matrix Completion via Convex Optimization , journal =

Cand. Exact Matrix Completion via Convex Optimization , journal =. 2009 , doi =

2009
[5]

Quantum Science and Technology , volume =

Chen, Ranyiliu and Song, Zhixin and Zhao, Xuanqiang and Wang, Xin , title =. Quantum Science and Technology , volume =. 2022 , doi =

2022
[6]

, title =

Rethinasamy, Soorya and Agarwal, Rochisha and Sharma, Kunal and Wilde, Mark M. , title =. Physical Review A , volume =. 2023 , doi =

2023
[7]

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 =. 2024 , doi =

2024
[8]

IEEE Transactions on Information Theory , volume =

Wang, Qisheng and Zhang, Zhicheng , title =. IEEE Transactions on Information Theory , volume =. 2024 , doi =

2024

Show all 29 references

[9]

IEEE Transactions on Information Theory , volume =

Wang, Qisheng , title =. IEEE Transactions on Information Theory , volume =. 2024 , doi =

2024
[10]

SIAM Journal on Matrix Analysis and Applications , volume =

Ubaru, Shashanka and Chen, Jie and Saad, Yousef , title =. SIAM Journal on Matrix Analysis and Applications , volume =. 2017 , doi =

2017
[11]

, title =

Li, Yi and Woodruff, David P. , title =. 44th International Colloquium on Automata, Languages, and Programming (. 2017 , doi =

2017
[12]

Efficient Approximation for Global Functions of Matrix Product Operators , journal =

August, Moritz and Ba. Efficient Approximation for Global Functions of Matrix Product Operators , journal =. 2018 , doi =

2018
[13]

2026 , eprint =

Lee, Seunghun and Moon, Eun-Gook , title =. 2026 , eprint =

2026
[14]

Proceedings of the 2024 ACM--SIAM Symposium on Discrete Algorithms (SODA) , pages =

Feng, Weiming and Liu, Liqiang and Liu, Tianren , title =. Proceedings of the 2024 ACM--SIAM Symposium on Discrete Algorithms (SODA) , pages =. 2024 , doi =

2024
[15]

and Harrow, Aram W

Bacon, Dave and Chuang, Isaac L. and Harrow, Aram W. , title =. Proceedings of the Eighteenth Annual ACM--SIAM Symposium on Discrete Algorithms (SODA) , pages =
[16]

and van de Graaf, Jeroen , title =

Fuchs, Christopher A. and van de Graaf, Jeroen , title =. IEEE Transactions on Information Theory , volume =. 1999 , doi =

1999
[17]

Non-Commutative

Lust-Piquard, Fran. Non-Commutative. Arkiv f. 1991 , doi =

1991
[18]

Journal of Functional Analysis , volume =

Haagerup, Uffe and Musat, Magdalena , title =. Journal of Functional Analysis , volume =. 2007 , doi =

2007
[19]

On the Best Constants in the

Szarek, Stanis. On the Best Constants in the. Studia Mathematica , volume =. 1976 , doi =

1976
[20]

and Schechtman, Gideon , title =

Johnson, William B. and Schechtman, Gideon , title =. The Annals of Probability , volume =. 1989 , doi =

1989
[21]

2013 , eprint =

Li, Jian and Shi, Tianlin , title =. 2013 , eprint =

2013
[22]

, title =

Guo, Chun-Hua and Higham, Nicholas J. , title =. SIAM Journal on Matrix Analysis and Applications , volume =. 2006 , doi =

2006
[23]

, title =

Higham, Nicholas J. , title =. Numerical Algorithms , volume =. 1997 , doi =

1997
[24]

, title =

Schmitt, Bernhard A. , title =. Linear Algebra and its Applications , volume =. 1992 , doi =

1992
[25]

, title =

Gawlik, Evan S. , title =. SIAM Journal on Matrix Analysis and Applications , volume =. 2019 , doi =

2019
[26]

SIAM Journal on Optimization , volume =

de Klerk, Etienne and Vallentin, Frank , title =. SIAM Journal on Optimization , volume =. 2016 , doi =

2016
[27]

1997 , doi =

Bhatia, Rajendra , title =. 1997 , doi =

1997
[28]

2018 , doi =

Watrous, John , title =. 2018 , doi =

2018
[29]

, title =

Goodman, Roe and Wallach, Nolan R. , title =. 2009 , doi =

2009

Pith tools

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

[1] [1]

and Myrisiotis, Dimitrios and Pavan, A

Bhattacharyya, Arnab and Gayen, Sutanu and Meel, Kuldeep S. and Myrisiotis, Dimitrios and Pavan, A. and Vinodchandran, N. V. , title =. Information Processing Letters , volume =. 2025 , doi =

2025

[2] [2]

TheoretiCS , volume =

Feng, Weiming and Guo, Heng and Jerrum, Mark and Wang, Jiaheng , title =. TheoretiCS , volume =. 2023 , doi =

2023

[3] [3]

, title =

Recht, Benjamin and Fazel, Maryam and Parrilo, Pablo A. , title =. SIAM Review , volume =. 2010 , doi =

2010

[4] [4]

Exact Matrix Completion via Convex Optimization , journal =

Cand. Exact Matrix Completion via Convex Optimization , journal =. 2009 , doi =

2009

[5] [5]

Quantum Science and Technology , volume =

Chen, Ranyiliu and Song, Zhixin and Zhao, Xuanqiang and Wang, Xin , title =. Quantum Science and Technology , volume =. 2022 , doi =

2022

[6] [6]

, title =

Rethinasamy, Soorya and Agarwal, Rochisha and Sharma, Kunal and Wilde, Mark M. , title =. Physical Review A , volume =. 2023 , doi =

2023

[7] [7]

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 =. 2024 , doi =

2024

[8] [8]

IEEE Transactions on Information Theory , volume =

Wang, Qisheng and Zhang, Zhicheng , title =. IEEE Transactions on Information Theory , volume =. 2024 , doi =

2024