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

Abstract

We investigate the computational complexity of estimating the operator norm distance ${\mathrm{T}}_{\infty }(\ddot{I}{}_0,\ddot{I}{}_1)$, defined via the operator norm $\Vert A{\Vert }_{\infty }=\ddot{I}{ƒ}_{\max }(A)$, given $\mathrm{poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $\ddot{I}{}_0$ and $\ddot{I}{}_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 $\hat{I}˜(1/\hat{I}\mu )$ queries to the state-preparation circuits. Consequently, for constant additive error, say $\hat{I}\mu =1/5$, our estimator runs in $\mathrm{poly}(n)$ time. Since the operator norm distance ${\mathrm{T}}_{\infty }(|\ddot{I}ˆ⟩⟨\ddot{I}ˆ|,\ddot{I})$ is exactly half of the trace distance $\mathrm{T}(|\ddot{I}ˆ⟩⟨\ddot{I}ˆ|,\ddot{I})$, 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 $\mathrm{rank}(\ddot{I})$, which can be $\exp (n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\tilde{O}(1/\hat{I}{\mu }^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is $\mathsf{BQP}$-complete and improves the $\mathsf{QMA}$ upper bound sketched by Liu and Wang (ESA 2025). Together with an $\hat{I}\text{c◯}(1/\hat{I}\mu )$ 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 $|\ddot{I}ˆ⟩$ has overlap at least $1/2$ with the top unit eigenvector of $|\ddot{I}ˆ⟩⟨\ddot{I}ˆ|-\ddot{I}$, reflecting a structural feature specific to the operator norm distance.

28 pages, 2 algorithms. To appear in ESA 2026