Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi +4

This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the functio…