On the Fine-Grained Query Complexity of Symmetric Functions

Watrous conjectured that the randomized and quantum query complexities of symmetric functions are polynomially equivalent, which was resolved by Aaronson & Ambainis (2014) and was later improved by Chailloux (2019) and Ben-David et al. (2020). This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to 1/2. Our contributions include the following: We analyze the optimal success probabilities of quantum and randomized query algorithms of two fundamental partial symmetric Boolean functions given a fixed number of queries. We establish that for any total symmetric Boolean function f, if a quantum algorithm uses T queries to compute f with success probability 1/2+β, then there exists a randomized algorithm using O(T2) queries to compute f with success probability 1/2+Ωδβ2 on a 1-δ fraction of inputs, where β,δ can be arbitrarily small positive values. Moreover, we prove a randomized version of Aaronson-Ambainis Conjecture (Aaronson & Ambainis 2014) for symmetric Boolean functions in the regime where the success probability of algorithms can be arbitrarily close to 1/2. We present tight polynomial equivalence for several fundamental complexity measures of partial symmetric Boolean functions.