This note complements the upcoming paper "One-Way Ticket to Las Vegas and the Quantum Adversary" by Belovs and Yolcu, to be presented at QIP 2023. I develop the ideas behind the adversary bound - universal algorithm duality therein in a different form. This form may be faster to understand for a general quantum information audience: It avoids defining the "unidirectional filtered $\gamma _{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 $\Theta(\log(1/\epsilon))$ factor from the runtime compared to the previous discrete-time algorithm.
翻译:本说明补充Belovs和Yolcu在QIP 2023上提交的即将出版的论文“前往拉斯维加斯和量子断面单车票”,我以不同的形式发展了对手约束的背后的思想-通用运算的双重性。对于一般量子信息受众来说,这种形式可能更快地理解:它避免了定义“单向过滤的$\gama ⁇ 2} $-bound ”,并明确将其与查询算法联系起来。这个证据也比较笼统,因为较低约束的(和通用查询算法)适用于最佳控制问题,而不仅仅是查询问题。除了在Belovs-Yolcu中讨论的优势外,这就是避免阶段估计和光谱分析的更基本的算法和正确性证明,允许对噪音进行有限的处理,并且从运行时的另外一个 $Theta (log (1/\ epsilon) ) 系数与以前的离散时间算法相比,它也比较笼统。