论文标题
通过单拷贝测量的学习量子状态的下限
Lower Bounds for Learning Quantum States with Single-Copy Measurements
论文作者
论文摘要
我们使用对单个的，相同的$ d $维状态的相同副本进行的测量来研究量子断层扫描和阴影层析成像的问题。由于Haah等人，我们首先重新审视已知的下限。 （2017年）在痕量距离的准确性$ε$的量子断层扫描上，当测量选择与先前观察到的结果无关（即，它们是非适应性的）。我们简要地证明了这一结果。当学习者使用具有恒定结果数量的测量值时，这会导致更强的下限。 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 $Ω(r^2 d/ε^2)$ and $Ω(r^2 d^2/ε^2)$ for learning rank $r$ states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. 除样品复杂性外，学习量子状态具有实际意义的资源是算法使用的不同测量值的数量。我们将下限扩展到学习者从固定的$ \ exp（o（d））$测量中执行自适应测量的情况。这特别意味着适应性并不能使用有效实施的单拷贝测量值给我们带来任何优势。在目标是预测给定的可观测值序列的期望值的情况下，我们还获得了类似的结合，即被称为阴影断层扫描的任务。最后，如果可以使用多项式大小的电路实现自适应，单拷贝测量，我们证明了基于计算给定可观察物的样本平均值的直接策略是最佳的。
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 $ε$ 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 $Ω(r^2 d/ε^2)$ and $Ω(r^2 d^2/ε^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.
