Exact Quantum Query Algorithms Outperforming Parity – Beyond The Symmetric functions
share
The Exact Quantum Query model is the least explored query model, and almost all of the functions for which non-trivial query algorithms exist are symmetric in nature. In this paper we first explore the Maiorana-McFarland(MM) type Bent functions, defined on all even n variables. The (classical) Deterministic Query Complexity (D(f)) of all functions in this class is n. In this regard we construct an n/2 + ⌈n/8⌉ query family of exact quantum algorithms that are not parity decision trees to evaluate a subclass of MM type Bent functions consisting of Ω(2^2^⌊n/4⌋) non-PNP equivalent functions. Although we achieve better query complexity than any known parity decision tree technique, we cannot prove optimality of these algorithms. Next we modify our techniques to apply it to a class of Ω(2^√(n)/2) non symmetric Boolean functions that we design based on Direct Sum Constructions. We show that in this case the algorithms designed by us require ⌊3n/4⌋ queries and our family of algorithms is optimal, outperforming any possible parity decision tree technique. To the best of our knowledge, this is the first family of algorithms beyond parity for a general class of non-symmetric functions.
READ FULL TEXT