Classical-Quantum Separations in Certain Classes of Boolean Functions– Analysis using the Parity Decision Trees
share
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 the Maiorana McFarland (M-M) type Bent functions. We show that while for any M-M Bent function f on n variables D(f) = n, separation can be achieved as n/2≤ Q_E(f) ≤⌈3n/4⌉. Our results highlight how different classes of Boolean functions can be analyzed for classical-quantum separation exploiting the parity decision tree method.
READ FULL TEXT