Revision #2 Authors: Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming

Accepted on: 28th August 2021 02:31

Downloads: 679

Keywords:

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.

Revision #1 Authors: Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming

Accepted on: 24th August 2021 05:46

Downloads: 357

Keywords:

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})$.

TR21-115 Authors: Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming

Publication: 8th August 2021 03:29

Downloads: 850

Keywords:

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$).