Aaronson and Ambainis (STOC 2015, SICOMP 2018) claimed that the acceptance probability of every quantum algorithm that makes $q$ queries to an $N$-bit string can be estimated to within $\epsilon$ by a randomized classical algorithm of query complexity $O_q((N/\epsilon^2)^{1-1/2q})$. We describe a flaw in their argument but prove that the dependence on $N$ in this upper bound is correct for one-query quantum algorithms ($q = 1$). Bravyi, Gosset, and Grier had already obtained the improved bound $O(q \epsilon^{-1/q} N^{1-1/2q})$.

Corrected a mistake in the bound of Bravyi, Gosset, and Grier.

Aaronson and Ambainis (STOC 2015, SICOMP 2018) claimed that the acceptance probability of every quantum algorithm that makes $q$ queries to an $N$-bit string can be estimated to within $\epsilon$ by a randomized classical algorithm of query complexity $O_q((N/\epsilon^2)^{1-1/2q})$. We describe a flaw in their argument but prove that the dependence on $N$ in this upper bound is correct for one-query quantum algorithms ($q = 1$).

Update: Bravyi, Gosset, and Grier had already obtained the improved bound $O(2^q \epsilon^{-2 + 2/q} N^{1 - 1/q})$.

Aaronson and Ambainis (STOC 2015, SICOMP 2018) claimed that the acceptance probability of every quantum algorithm that makes $q$ queries to an $N$-bit string can be estimated to within $\epsilon$ by a randomized classical algorithm of query complexity $O_q((N/\epsilon^2)^{1-1/2q})$. We describe a flaw in their argument but prove that the dependence on $N$ in this upper bound is correct for one-query quantum algorithms ($q = 1$).