论文标题
量子事件学习和温和的随机测量
Quantum Event Learning and Gentle Random Measurements
论文作者
论文摘要
我们证明，通过一系列随机排序的两个结果测量值对量子系统造成的预期干扰是由概率的平方根界定的，即序列接受至少一个测量值。我们将其称为温和的随机测量引理。 然后，我们考虑给出了对未知状态$ρ$示例访问的问题，并要求估算一组测量$ \ text {tr} [m_iρ] $的属性的属性。我们将这些类型的问题称为量子事件学习问题。使用温和的随机测量引理，我们显示随机排序的投影测量方法解决了量子或问题，回答了Aaronson的开放问题。我们还提供了一种用于非项目测量的量子或协议，但需要更复杂的测量类型，我们称之为混合测量。给出了一组测量值$ \ {m_1，\ ldots，m_m \} $的其他保证，我们显示本文开发的量子或协议也可以用于查找测量$ m_i $，以便$ \ text {tr} [m_iρ] $很大。我们还提供了基于混合测量的协议，用于估计未知状态上一组测量值的平均接受概率。 最后，我们考虑了O'Donnell和Bădescu所描述的阈值搜索问题。通过在我们的量子事件发现结果上构建，我们表明可以使用$ O（\ log^2（m） /ε^2）$ $ρ$的$ o（\ log^2（m） /ε^2）随机排序（或混合）测量值。因此，我们获得了阴影断层扫描算法，该算法需要$ \ tilde {o}（\ log^2（m）\ log（d）/ε^4）$样品，与当前最著名的样品复杂性匹配。该算法不需要在量子测量中注入噪声，但确实需要按随机顺序进行测量，因此不再在线。
We prove the expected disturbance caused to a quantum system by a sequence of randomly ordered two-outcome projective measurements is upper bounded by the square root of the probability that at least one measurement in the sequence accepts. We call this bound the Gentle Random Measurement Lemma. We then consider problems in which we are given sample access to an unknown state $ρ$ and asked to estimate properties of the accepting probabilities $\text{Tr}[M_i ρ]$ of a set of measurements $\{M_1, M_2, \ldots , M_m\}$. We call these types of problems Quantum Event Learning Problems. Using the gentle random measurement lemma, we show randomly ordering projective measurements solves the Quantum OR problem, answering an open question of Aaronson. We also give a Quantum OR protocol which works on non-projective measurements but which requires a more complicated type of measurement, which we call a Blended Measurement. Given additional guarantees on the set of measurements $\{M_1, \ldots, M_m\}$, we show the Quantum OR protocols developed in this paper can also be used to find a measurement $M_i$ such that $\text{Tr}[M_i ρ]$ is large. We also give a blended measurement based protocol for estimating the average accepting probability of a set of measurements on an unknown state. Finally we consider the Threshold Search Problem described by O'Donnell and Bădescu. By building on our Quantum Event Finding result we show that randomly ordered (or blended) measurements can be used to solve this problem using $O(\log^2(m) / ε^2)$ copies of $ρ$. Consequently, we obtain an algorithm for Shadow Tomography which requires $\tilde{O}(\log^2(m)\log(d)/ε^4)$ samples, matching the current best known sample complexity. This algorithm does not require injected noise in the quantum measurements, but does require measurements to be made in a random order and so is no longer online.
