We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. The soft rank is a somehow relaxed variant of the rank. Among all decision trees of depth d, the complete binary decision tree (the most balanced tree) has maximum soft rank d, the decision list (the most unbalanced tree) has minimum soft rank √d, and any other trees have soft rank between √d and d. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f.We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. The soft rank is a somehow relaxed variant of the rank. Among all decision trees of depth d, the complete binary decision tree (the most balanced tree) has maximum soft rank d, the decision list (the most unbalanced tree) has minimum soft rank √d, and any other trees have soft rank between √d and d. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f.

Computing: The Australasian Theory SymposiumJan 1, 20090 citations

Complexity measures and decision tree complexity: a survey

Harry Buhrman, Ronald de Wolf

Theoretical Computer ScienceOct 1, 2002666 citations

Classical-Quantum Separations in Certain Classes of Boolean Functions-- Analysis using the Parity Decision Trees

Chandra Sekhar Mukherjee, Subhamoy Maitra

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 $\frac{n}{2} \leq Q_E(f) \leq \lceil \frac{3n}{4} \rceil$ . Our results highlight how different classes of Boolean functions can be analyzed for classical-quantum separation exploiting the parity decision tree method.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 $\frac{n}{2} \leq Q_E(f) \leq \lceil \frac{3n}{4} \rceil$. Our results highlight how different classes of Boolean functions can be analyzed for classical-quantum separation exploiting the parity decision tree method.

arXiv:2004.12942Apr 27, 20202 citations

Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions

Chandra Sekhar Mukherjee, Subhamoy Maitra

In Exact Quantum Query model, almost all of the Boolean functions for which non-trivial query algorithms exist are symmetric in nature. The most well known techniques in this domain exploit parity decision trees, in which the parity of two bits can be obtained by a single query. Thus, exact quantum query algorithms outperforming parity decision trees are rare. In this paper we first obtain optimal exact quantum query algorithms ( $Q_{algo}(f)$ ) for a direct sum based class of $Ω\left( 2^{\frac{\sqrt{n}}{2}} \right)$ non-symmetric functions. We construct these algorithms by analyzing the algebraic normal form together with a novel untangling strategy. Next we obtain the generalized parity decision tree complexity ( $D_{\oplus}(f)$ ) analysing the Walsh Spectrum. Finally, we show that query complexity of $Q_{algo}$ is $\lceil \frac{3n}{4} \rceil$ whereas $D_{\oplus}(f)$ varies between $n-1$ and $\lceil \frac{3n}{4} \rceil+1$ for different classes, underlining linear separation between the two measures in many cases. To the best of our knowledge, this is the first family of algorithms beyond generalized parity (and thus parity) for a large class of non-symmetric functions. We also implement these techniques for a larger (doubly exponential in $\frac{n}{4}$ ) class of Maiorana-McFarland type functions, but could only obtain partial results using similar algorithmic techniques.In Exact Quantum Query model, almost all of the Boolean functions for which non-trivial query algorithms exist are symmetric in nature. The most well known techniques in this domain exploit parity decision trees, in which the parity of two bits can be obtained by a single query. Thus, exact quantum query algorithms outperforming parity decision trees are rare. In this paper we first obtain optimal exact quantum query algorithms ($Q_{algo}(f)$) for a direct sum based class of $Ω\left( 2^{\frac{\sqrt{n}}{2}} \right)$ non-symmetric functions. We construct these algorithms by analyzing the algebraic normal form together with a novel untangling strategy. Next we obtain the generalized parity decision tree complexity ($D_{\oplus}(f)$) analysing the Walsh Spectrum. Finally, we show that query complexity of $Q_{algo}$ is $\lceil \frac{3n}{4} \rceil$ whereas $D_{\oplus}(f)$ varies between $n-1$ and $\lceil \frac{3n}{4} \rceil+1$ for different classes, underlining linear separation between the two measures in many cases. To the best of our knowledge, this is the first family of algorithms beyond generalized parity (and thus parity) for a large class of non-symmetric functions. We also implement these techniques for a larger (doubly exponential in $\frac{n}{4}$) class of Maiorana-McFarland type functions, but could only obtain partial results using similar algorithmic techniques.

arXiv:2008.06317Aug 14, 20200 citations

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

n

variables

D(f) = n

, separation can be achieved as

\frac{n}{2} \leq Q_E(f) \leq \lceil \frac{3n}{4} \rceil

. Our results highlight how different classes of Boolean functions can be analyzed for classical-quantum separation exploiting the parity decision tree method.

Q_{algo}(f)

) for a direct sum based class of

Ω\left( 2^{\frac{\sqrt{n}}{2}} \right)

non-symmetric functions. We construct these algorithms by analyzing the algebraic normal form together with a novel untangling strategy. Next we obtain the generalized parity decision tree complexity (

D_{\oplus}(f)

) analysing the Walsh Spectrum. Finally, we show that query complexity of

Q_{algo}

\lceil \frac{3n}{4} \rceil

whereas

D_{\oplus}(f)

varies between

n-1

and

\lceil \frac{3n}{4} \rceil+1

for different classes, underlining linear separation between the two measures in many cases. To the best of our knowledge, this is the first family of algorithms beyond generalized parity (and thus parity) for a large class of non-symmetric functions. We also implement these techniques for a larger (doubly exponential in

\frac{n}{4}

) class of Maiorana-McFarland type functions, but could only obtain partial results using similar algorithmic techniques.