arXiv:2609.35975
Deciding the Attainability of the Multiparameter Quantum Fisher Information is NP-Hard
Lorcan O. Conlon, Laura Shou, V Vijendran, Kishor Bharti, Aritra Das, Simon K. Yung, Jacob M. Taylor, Alexey V. Gorshkov, Jun Suzuki, Syed M. Assad
Abstract
The quantum Fisher information (QFI) sets a fundamental bound on the attainable precision when estimating multiple parameters simultaneously. Incompatibility among the individually optimal measurements can, in some cases, imply that the precision limit set by the QFI is not attainable. In certain special cases, including pure states and full-rank states, the exact conditions for when the precision limit set by the QFI can be saturated are known. However, general conditions for the attainability of the QFI with measurements on individual copies of the quantum state have long been sought. Indeed, this was recently stated as one of the five problems in quantum information theory highlighted by [P. Horodecki et al, PRX Quantum 3, 010101 (2022)]. In this work we prove that exact attainability with individual measurements is NP-hard to decide, even for a restricted set of real, constant-rank quantum models. The source problem for our proof is the NP-hard problem of deciding whether a given bipartite density matrix is separable or not. Our result shows that the longstanding difficulty in obtaining general conditions for QFI attainability reflects a fundamental computational obstruction, rather than merely a limitation of existing mathematical techniques: unless P=NP, no efficiently computable necessary-and-sufficient criterion can exist in general.
AI Summary
The paper asks whether one can efficiently decide if the multiparameter SLD quantum Cramér–Rao bound is exactly attainable by measurements on individual copies, with locally unbiased estimators. It proves NP-hardness under polynomial-time Turing reductions for rational local model data, even for real models whose rank is constant as parameters vary. The rank and number of parameters grow with the input size. The reduction encodes real bipartite separability into the existence of commuting extensions of SLD operators, using the established equivalence between such extensions and exact attainability. A polynomial-time rational factorization $H=BB^T$ supplies the support–kernel SLD blocks; an auxiliary commuting sector ensures positive-definite QFI. The construction gives a smooth statistical model with the prescribed local data. The hardness also holds with an inverse-polynomial precision gap. For normalized $H$, if its Frobenius distance from the normalized real-separable set is at least $\delta$, then every locally unbiased estimator satisfies $\operatorname{Tr}[V-\mathcal J_Q^{-1}]\geq\delta^2/[100(p+r+1)(pr+1)]$. The encoded gap problem additionally belongs to PromiseNP. On these models, the Nagaoka–Hayashi and Holevo bounds equal the SLD bound, so deciding their exact single-copy attainability is also NP-hard. A discretization argument shows that arbitrary-outcome measurements offer no advantage for the moments considered. The results concern worst-case local estimation with growing dimensions and parameter counts. They do not establish hardness for fixed parameter counts, global estimation, or existential-real completeness. They exclude general polynomial-time necessary-and-sufficient tests unless $P=NP$, rather than excluding mathematical characterizations or efficient tests for restricted model classes.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 5 pages, comments very welcome