Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #2 to TR21-115 | 28th August 2021 02:31

On quantum versus classical query complexity

Revision #2
Authors: Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming
Accepted on: 28th August 2021 02:31
Keywords:

Abstract:

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

Changes to previous version:

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

Revision #1 to TR21-115 | 24th August 2021 05:46

On quantum versus classical query complexity

Revision #1
Authors: Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming
Accepted on: 24th August 2021 05:46
Keywords:

Abstract:

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

Changes to previous version:

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

Paper:

TR21-115 | 6th August 2021 08:38

On quantum versus classical query complexity

TR21-115
Authors: Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming
Publication: 8th August 2021 03:29
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$).