期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 by a randomized classical algorithm of query complexity Oq((N2)1−12q) . 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−1qN1−12q) .
