Title: Error regions in quantum state tomography: computational complexity caused by geometry of quantum states Show Chinese title

Title: 量子态层析成像中的误差区域：由量子态的几何结构引起的计算复杂性

Abstract: The outcomes of quantum mechanical experiments are inherently random. It is therefore necessary to develop stringent methods for quantifying the degree of statistical uncertainty about the results of quantum experiments. For the particularly relevant task of quantum state estimation, it has been shown that a significant reduction in uncertainty can be achieved by taking the positivity of quantum states into account. However -- the large number of partial results and heuristics notwithstanding -- no efficient general algorithm is known that produces an optimal uncertainty region from experimental data and the prior constraint of positivity. Here, we make this problem precise and show that the general case is NP-hard. Our result leaves room for the existence of efficient approximate solutions, and therefore does not yet imply that the practical task of quantum uncertainty quantification is intractable. However, it does show that there exists a non-trivial trade-off between optimality and computational efficiency for error regions. We prove two versions of the result: One for frequentist and one for Bayesian statistics. Show Chinese abstract

Abstract: 量子力学实验的结果本质上是随机的。 因此，有必要开发严格的方法来量化关于量子实验结果的统计不确定性程度。 对于特别相关的量子态估计任务，已经表明，通过考虑量子态的正定性，可以显著减少不确定性。 然而——尽管有许多部分结果和启发式方法——尚未发现一种有效的通用算法，可以从实验数据和正定性的先验约束中产生最优的不确定性区域。 在这里，我们将这个问题精确化，并证明一般情况下是NP难的。 我们的结果为存在有效近似解留出了空间，并不意味着量子不确定性量化这一实际任务是不可处理的。 然而，它确实表明误差区域之间存在非平凡的最优性和计算效率之间的权衡。 我们证明了两种版本的结果：一种适用于频率学派统计，另一种适用于贝叶斯统计。