  The general adversary dual is a powerful tool in quantum computing because it
gives a query-optimal bounded-error quantum algorithm for deciding any Boolean
function. Unfortunately, the algorithm uses linear qubits in the worst case,
and only works if the constraints of the general adversary dual are exactly
satisfied. The challenge of improving the algorithm is that it is brittle to
arbitrarily small errors since it relies on a reflection over a span of
vectors. We overcome this challenge and build a robust dual adversary algorithm
that can handle approximately satisfied constraints. As one application of our
robust algorithm, we prove that for any Boolean function with polynomially many
1-valued inputs (or in fact a slightly weaker condition) there is a
query-optimal algorithm that uses logarithmic qubits. As another application,
we prove that numerically derived, approximate solutions to the general
adversary dual give a bounded-error quantum algorithm under certain conditions.
Further, we show that these conditions empirically hold with reasonable
iterations for Boolean functions with small domains. We also develop several
tools that may be of independent interest, including a robust approximate
spectral gap lemma, a method to compress a general adversary dual solution
using the Johnson-Lindenstrauss lemma, and open-source code to find solutions
to the general adversary dual.
