《Finite-Size Limits of Adaptive Pauli Prediction》证明自适应 Pauli 预测的有限规模下界

研究证明，在固定精度下，n 个量子比特上的 M 次自适应 Pauli 预测需要 $Ω(\sqrt{m}in{n,M})$ 份数据。作者结合已发表上界指出，该下界在 M≤n 时是紧致的；因此 n 次自适应预测需要 $Θ(\sqrt{n})$ 份数据，而固定预测列表只需 $O(log n)$ 份数据。证明使用对角态和可交换观测量，并进一步刻画了成本随精度提高而增加的关系；以上结论基于论文摘要。