About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Computational Complexity
Paper
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.