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

摘要

This paper considers the quantum query complexity of almost all functions in the set of -variable Boolean functions with on-set size , 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 except its polynomially small fraction, the quantum query complexity is Theta (logM/c+log N- log log M + root N) for a constant . This is quite different from the quantum query complexity of the hardest function in F-N,F-M : Theta (root N logM/c+log N- log log M + root N) . In contrast, almost all functions in have the same randomized query complexity as the hardest one, up to a constant factor.