  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.
