# The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal Control

arXiv: https://arxiv.org/abs/2211.16293 · HTML: https://mlsanity.com/paper/2211.16293/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2022.

## Built on by (most cited first, 1 of 1)

- [The R-algebra of Quasiknowledge and Convex Optimization](https://mlsanity.com/paper/2212.04606/) (2022)

## Abstract (arXiv)

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 Theta(log(1/ε)) factor from the runtime compared to the previous discrete-time algorithm.