Approximating the Trace Distance Between Product Quantum States
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.