Quantum Query Complexity of Almost All Functions with Fixed On-set Size

Abstract

This paper considers the quantum query complexity of almost all functions in the set FN,M of N-variable Boolean functions with on-set size M( 1 ≤ M≤ 2 N/ 2) , where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in FN,M except its polynomially small fraction, the quantum query complexity is Θ(logMc+logN-loglogM+N) for a constant c> 0. This is quite different from the quantum query complexity of the hardest function in FN,M: Θ(NlogMc+logN-loglogM+N). In contrast, almost all functions in FN,M have the same randomized query complexity Θ (N) as the hardest one, up to a constant factor.