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.
翻译:量子州地形学是估算量子状态的任务,考虑到不同基础的许多测量结果。我们讨论“估计量子状态”的确切含义的几种变体,包括最大可能性估算和计算贝叶斯平均值。我们表明,当测量结果固定下来时,这个问题是NP-Hard, 接近于任何恒定系数。在这个过程中,我们发现它减少了大约计算Hermitian正阳性半无限期(HPSD)矩阵永久值的问题。这意味着HPSD永久值也是NP-Hard,可以估计,解决在量子信息和博森抽样应用方面的一个长期问题。