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$$ 1 / 2 . Our contributions include the following: 1. 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. 2. We establish that for any total symmetric Boolean function f f , if a quantum algorithm uses T T queries to compute f f with success probability 1/2+β 1 / 2 + β , then there exists a randomized algorithm using O(T²) O ( T 2 ) queries to compute f f with success probability 1/2+Ωδβ² 1 / 2 + Ω δ β 2 on a 1-δ 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. 3. We present tight polynomial equivalence for several fundamental complexity measures of partial symmetric Boolean functions.