论文标题
重新审视的对手界：从最佳查询算法到最佳控制
The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal Control
论文作者
论文摘要
本说明补充了“拉斯维加斯和量子对手的单程票”（Arxiv：2301.02003）。我使用与barnum-saks-szegedy相同的观点，在其中以不同形式的对手结合 - 通用算法二元性背后的思想，其中查询算法被定义为可行的降低密度矩阵的序列，而不是单位序列。对于一般量子信息受众，这种形式可能会更快地理解：它避免定义“单向相对$γ_{2} $ - 绑定”，并将其明确地与查询算法联系起来。该证明也更为笼统，因为下限（和通用查询算法）适用于一类最佳控制问题，而不仅仅是查询问题。这是在Belovs-Yolcu中要讨论的优点，即避免相位估计和频谱分析，允许噪声的有限处理，并删除与以前的运行时相比，与先前的运行时相比，避免相位估计和频谱分析，允许有限的噪声处理，允许有限的噪声处理，与先前的噪声处理有限，相比，与先前的噪声处理有限，相比，这是其他算法和正确性证明的优势。
This note complements the paper "One-Way Ticket to Las Vegas and the Quantum Adversary" (arxiv:2301.02003). I develop the ideas behind the adversary bound - universal algorithm duality therein in a different form, using the same perspective as Barnum-Saks-Szegedy in which query algorithms are defined as sequences of feasible reduced density matrices rather than sequences of unitaries. This form may be faster to understand for a general quantum information audience: It avoids defining the "unidirectional relative $γ_{2}$-bound" and relating it to query algorithms explicitly. This proof is also more general because the lower bound (and universal query algorithm) apply to a class of optimal control problems rather than just query problems. That is in addition to the advantages to be discussed in Belovs-Yolcu, namely the more elementary algorithm and correctness proof that avoids phase estimation and spectral analysis, allows for limited treatment of noise, and removes another $Θ(\log(1/ε))$ factor from the runtime compared to the previous discrete-time algorithm.
