Approximating the Trace Distance Between Product Quantum States
2026-08-03 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to measure the difference between two large quantum states when these states are described by smaller, local parts. They develop a method to quickly approximate this difference within a constant factor, which runs efficiently based on the number of parts and their sizes. They also show that exactly calculating this difference is very hard in general. Their approach uses mathematical tools to simplify the problem to a smaller, manageable one, allowing a good estimate with reasonable computational effort.
Trace distanceQuantum statesProduct statesApproximation algorithmsComputational complexityTotal variation distanceUhlmann fidelityConvex optimizationTrace norm
Authors
Kun He, Dimitrios Myrisiotis, Junhong Nie, Zongqi Wan
Abstract
We study the trace distance \[D_{\mathrm{tr}}(ρ,σ) =\frac12\|ρ-σ\|_1, ρ=\bigotimes_{i=1}^nρ_i,\quad σ=\bigotimes_{i=1}^nσ_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.