On estimating operator norm distance, with optimal trace distance estimation when one state is pure

Yupan Liu, Qisheng Wang, Zhan Yu (Jul 07 2026).

Abstract: We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(\rho_0,\rho_1)$, defined via the operator norm $\|A\|_{\infty} = \sigma_{\max}(A)$, given ${\rm poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $\rho_0$ and $\rho_1$. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using $\Theta(1/\epsilon)$ queries to the state-preparation circuits. Consequently, for constant additive error, say $\epsilon=1/5$, our estimator runs in ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|\psi\rangle\!\langle\psi|,\rho)$ is exactly half of the trace distance ${\rm T}(|\psi\rangle\!\langle\psi|,\rho)$, our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gilyén, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with ${\rm rank}(\rho)$, which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/\epsilon^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$-complete and improves the ${\sf QMA}$ upper bound sketched by Liu and Wang (ESA 2025). Together with an $\Omega(1/\epsilon)$ quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state $|\psi\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|\psi\rangle\!\langle\psi|-\rho$, reflecting a structural feature specific to the operator norm distance.

Arxiv: https://arxiv.org/abs/2607.03905