Quantum Query Complexity of Boolean Functions with Small On-Sets

摘要

The main objective of this paper is to show that the quantum query complexity Q(f) of an iV-bit Boolean function f is bounded by a function of a simple and natural parameter, i.e., M = |{x | f(x) = 1}| or the size of f''s on-set. We prove that: (ⅰ) For poly(N) ≤ M ≤ 2~(Nd) for some constant 0 < d < 1, the upper bound of Q(f) is O(N log M/ log N~(1/2)). This bound is tight, namely there is a Boolean function / such that Q(f) = Ω (N log M /log N~(1/2)). (ⅱ) For the same range of M, the (also tight) lower bound of Q(f) is Ω(N~(1/2)). (ⅲ) The average value of Q(f) is bounded from above and below by Q(f) = O(logM + N~(1/2)) and Q{f) = Ω(log M/logN+N~(1/2)), respectively. The first bound gives a simple way of bounding the quantum query complexity of testing some graph properties. In particular, it is proved that the quantum query complexity of planarity testing for a graph with n vertices is Θ(N~(3/4)) where N= (n(n-1))/2.