We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown $d$-dimensional state. We first revisit a known lower bound due to Haah et al. (2017) on quantum tomography with accuracy $\epsilon$ in trace distance, when the measurements choices are independent of previously observed outcomes (i.e., they are nonadaptive). We give a succinct proof of this result. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes. In particular, this rigorously establishes the optimality of the folklore ``Pauli tomography" algorithm in terms of its sample complexity. We also derive novel bounds of $\Omega(r^2 d/\epsilon^2)$ and $\Omega(r^2 d^2/\epsilon^2)$ for learning rank $r$ states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of different measurements used by an algorithm. We extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of $\exp(O(d))$ measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.
翻译:我们利用在个人身上进行的测量来研究量成像学和影子成像学的问题。 我们首先研究量成像和影成像学的问题, 使用以个人为单位进行的测量, 相同的副本, 未知的美元维度状态。 我们首先从Haah等人( 2017年) 开始重新研究已知的较低约束值, 精确度为$\epsilon$, 追踪距离, 当测量选择独立于先前观察到的结果( 即它们不适应性) 。 我们简单地证明了这一结果。 这导致当学习者使用测量数据时, 使用数量不变的结果数量不变的测量结果, 特别是, 这严格地确立了民俗“ Pauli tomography” 算法的最优化值。 我们还从Omega (r\2 d/\ eepsilon>2美元) 和 $(rmega) (r2 d§2/\ epsilon2) 的精确度选择值的新界限。 我们从一个精确度的精确度测算法中, 向一个特定的精确度测算法的精确度的精确度, 我们从一个精确度测算的精确度的测算来, 将一个特定的测算进一个特定的测算来, 直到一个特定的测算。