Optimal Diamond Distance Estimation for Unitary Channels

Abstract

The diamond distance between two quantum channels determines the optimal probability of distinguishing them from a single use. We give a quantum algorithm that estimates the diamond distance between two unknown $d$-dimensional unitary channels to within additive error $\varepsilon$, using $O(\sqrt{d}/\varepsilon)$ queries to the unitary channels and their inverses. The query complexity is optimal, as it matches the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).

The paper studies additive-error estimation of the diamond distance between two unknown $d$-dimensional unitary channels, given query access to $U$, $V$, and their inverses. It gives an estimator with error at most $\varepsilon$ and success probability at least $2/3$ using $O(\sqrt d/\varepsilon)$ queries in the worst case, for $d\ge2$ and $0<\varepsilon\le1/4$. This improves the cited spectrum-estimation-based upper bound of $O(d\log^2 d/\varepsilon)$ and matches a known $\Omega(\sqrt d/\varepsilon)$ lower bound inherited from unitary channel certification. The construction uses the identity $\|\mathcal U-\mathcal V\|_\diamond=2\sin(\min\{\ell(U^\dagger V),\pi\}/2)$, where $\ell$ is the shortest spectral containing-arc length. A retained, unknown reference eigenvector and controlled-SWAP routing enable estimation of relative eigenphases without controlled access to the unknown unitaries. Bounded-error quantum search over eigenvector labels, initialized through a maximally entangled state, supplies comparisons for a multiscale interval search. Running this search in both phase directions estimates the truncated spectral width. Phase estimates near the wraparound cut are accepted conservatively; when this prevents two-sided phase accuracy, the diamond distance is already close to its maximum value of $2$, allowing the required final accuracy. Scale-dependent precision and failure probabilities avoid additional asymptotic logarithmic factors. The guarantee is specifically for unitary channels with inverse-query access and measures query complexity rather than total gate cost. It also reproduces the known $O(\sqrt d/\varepsilon)$ upper bound for promised unitary channel certification.