Parity decision tree in classical-quantum separations for certain classes of Boolean functions

In this paper, we study the separation between the deterministic (classical) query complexity (D) and the exact quantum query complexity (Q(E)) of several Boolean function classes using the parity decision tree method. We first define the query friendly (QF) functions on n variables as the ones with minimum deterministic query complexity D(f). We observe that for each n, there exists a non-separable class of QF functions such that D(f) = Q(E) (f). Further, we show that for some values of n, all the QF functions are non-separable. Then, we present QF functions for certain other values of n where separation can be demonstrated, in particular, Q(E) (f) = D(f) - 1. In a related effort, we also study theMaiorana-McFarland (MM)-type Bent functions. We show that while for any MM Bent function f on n variables D(f) = n, separation can be achieved as n/2 <= Q(E) (f) <= inverted right perpendicular3n/4inverted left perpendicular. Our results highlight how different classes of Boolean functions can be analyzed for classical-quantum separation exploiting the parity decision tree method.

Automated summary

This paper explores the separation between classical and quantum query complexity of various Boolean function classes using the parity decision tree method. The study reveals instances where separation exists and how different classes of Boolean functions can be analyzed for this separation.