机构名称：
¥ 4.0
我们证明，由随机排序的两结果投影测量序列对量子系统造成的预期扰动的上限为该序列中至少一个测量被接受的概率的平方根。我们将此界限称为温和随机测量引理。然后，我们扩展用于证明此引理的技术以开发用于问题的协议，在这些协议中，我们可以采样访问未知状态 ρ，并被要求估计一组测量 { M 1 , M 2 , . . . , M m } 的接受概率 Tr[ M i ρ ] 的属性。我们将这些类型的问题称为量子事件学习问题。具体而言，我们表明随机排序投影测量解决了量子 OR 问题，回答了 Aaronson 的一个悬而未决的问题。我们还给出了一个适用于非投影测量的量子 OR 协议，其性能优于本文分析的随机测量协议以及 Harrow、Lin 和 Montanaro 的协议。但是，该协议需要一种更复杂的测量类型，我们称之为混合测量。在对测量集 { M 1 , ... , M m } 提供额外保证的情况下，我们表明，本文开发的随机和混合测量量子 OR 协议也可用于查找使得 Tr[ M i ρ ] 较大的测量 M i 。我们将寻找这种测量的问题称为量子事件寻找。我们还表明，混合测量为量子均值估计提供了一种样本高效的协议：该问题的目标是估计一组对未知状态的测量的平均接受概率。最后，我们考虑 O'Donnell 和 B˘adescu 描述的阈值搜索问题，其中给定一组测量 { M 1 , ... , M m } , M m } 以及对未知状态 ρ 的样本访问，其中对于某个 M i ，满足 Tr[ M i ρ ] ≥ 1 / 2，目标是找到一个测量值 M j ，使得 Tr[ M j ρ ] ≥ 1 / 2 − ϵ 。通过在我们的量子事件查找结果的基础上，我们表明随机排序（或混合）测量可用于解决这个问题，使用 O ( log 2 ( m ) /ϵ 2 ) 个 ρ 副本。这与 O'Donnell 和 B˘adescu 给出的算法的性能相匹配，但不需要在测量中注入噪声。因此，我们获得了一种阴影断层扫描算法，该算法与当前已知最佳样本复杂度相匹配（即需要 ˜ O ( log 2 ( m ) log( d ) /ϵ 4 ) 个样本）。该算法不需要在量子测量中注入噪声，但需要以随机顺序进行测量，因此不再在线。
量子事件学习和温和随机测量
主要关键词
相关文件推荐
