Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography
share
Quantum State Tomography is the task of estimating a quantum state, given many measurements in different bases. We discuss a few variants of what exactly “estimating a quantum state" means, including maximum likelihood estimation and computing a Bayesian average. We show that, when the measurements are fixed, this problem is NP-Hard to approximate within any constant factor. In the process, we find that it reduces to the problem of approximately computing the permanent of a Hermitian positive semidefinite (HPSD) matrix. This implies that HPSD permanents are also NP-Hard to approximate, resolving a standing question with applications in quantum information and BosonSampling.
READ FULL TEXT