We study the relative advantage of classical and quantum distinguishers of bounded query complexity over $n$-bit strings, focusing on the case of a single quantum query. A construction of Aaronson and Ambainis (STOC 2015) yields a pair of distributions that is $\epsilon$-distinguishable by a one-query quantum algorithm, but $O(\epsilon k/\sqrt{n})$-indistinguishable by any non-adaptive $k$-query classical algorithm.

We show that every pair of distributions that is $\epsilon$-distinguishable by a one-query quantum algorithm is distinguishable with $k$ classical queries and
(1) advantage $\min\{\Omega(\epsilon\sqrt{k/n})), \Omega(\epsilon^2k^2/n)\}$ non-adaptively (i.e., in one round), and (2) advantage $\Omega(\epsilon^2k/\sqrt{n\log n})$ in two rounds.

As part of our analysis we introduce a general method for converting unbiased estimators into distinguishers.