Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

On quantum versus classical query complexity

RSS-Feed




Revision #2
Authors: Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming
Accepted on: 28th August 2021 02:31
Downloads: 535
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
Downloads: 269
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
Downloads: 748
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$).



ISSN 1433-8092 | Imprint