{"ID":5937990,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-07T14:47:04.346462556Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.03905","arxiv_id":"2607.03905","title":"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 ${\\rm T}_{\\infty}(ρ_0,ρ_1)$, defined via the operator norm $\\|A\\|_{\\infty} = σ_{\\max}(A)$, given ${\\rm poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $ρ_0$ and $ρ_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 $Θ(1/ε)$ queries to the state-preparation circuits. Consequently, for constant additive error, say $ε=1/5$, our estimator runs in ${\\rm poly}(n)$ time. Since the operator norm distance ${\\rm T}_{\\infty}(|ψ\\rangle\\!\\langleψ|,ρ)$ is exactly half of the trace distance ${\\rm T}(|ψ\\rangle\\!\\langleψ|,ρ)$, 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}(ρ)$, which can be $\\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\\widetilde{O}(1/ε^{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 $Ω(1/ε)$ 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 $|ψ\\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|ψ\\rangle\\!\\langleψ|-ρ$, reflecting a structural feature specific to the operator norm distance.","short_abstract":"We investigate the computational complexity of estimating the operator norm distance ${\\rm T}_{\\infty}(ρ_0,ρ_1)$, defined via the operator norm $\\|A\\|_{\\infty} = σ_{\\max}(A)$, given ${\\rm poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $ρ_0$ and $ρ_1$. We provide efficient quantum estimators for t...","url_abs":"https://arxiv.org/abs/2607.03905","url_pdf":"https://arxiv.org/pdf/2607.03905v1","authors":"[\"Yupan Liu\",\"Qisheng Wang\",\"Zhan Yu\"]","published":"2026-07-04T14:59:03Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.DS\",\"cs.IT\"]","methods":"[]","has_code":false}