Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2004.12942

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

Chandra Sekhar Mukherjee, Subhamoy Maitra

Published Apr 27, 2020• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2004.12942

Related papers

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.

arXiv:2008.06317•Aug 14, 2020•0 citations

An Exact Quantum Query Algorithm Beyond Parity using Maiorana-McFarland (MM) type Bent functions.

Chandra Sekhar Mukherjee, Subhamoy Maitra

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 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 $\frac{n}{2} + \lceil \frac{n}{8} \rceil$ query exact quantum algorithm that is not a parity decision tree and evaluates a non-symmetric subclass of MM type Bent functions on $n$ variables consisting of $\left(2^{\lfloor \frac{n}{4} \rfloor}!\right)\left(2^{\lceil \frac{n}{4} \rceil}!\right) 2^{2^{\lfloor \frac{n}{4} \rfloor}}$ functions. Finally we also extend this technique for functions defined on odd values of $n$ using the Bent concatenation method. To the best of our knowledge, this is the first algorithm beyond parity for a general class of non-symmetric functions.

•Aug 14, 2020•0 citations

Classical-Quantum Separations in Minimal Query Complexity of Boolean Functions.

Chandra Sekhar Mukherjee, Subhamoy Maitra

Query complexity is a model of computation in which functions are evaluated by making queries to the variables. In a very recent paper [Physical Review A 101, 022325 (2020)], Chen, Ye and Li provided a characterization of exact one-query quantum algorithms. We first note that this result is an immediate corollary of what was proved five years back by Montanaro, Jozsa and Mitchison [Algorithmica 71, pp. 775-796 (2015)]. Further, in this model, we concentrate on understanding the differences between classical and quantum computation in terms of number of influencing variables of a function given lowest query complexity in the classical domain. We explore the parity decision tree model to portray possible separations between classical and quantum computations in specific cases. Our results classify different classes of Boolean functions on $n$-variables ($n$ being a function of $k$), that can be evaluated (i) with exactly $k$ queries in both classical and exact quantum model or (ii) with $k$ queries in classical model and $(k-1)$ queries in exact quantum model.

•Apr 27, 2020•0 citations

Separations in query complexity based on pointer functions

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs +3 more

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function f on n=2k bits defined by a complete binary tree of NAND gates of depth k, which achieves R0(f) = O(D(f)0.7537…). We show this is false by giving an example of a total boolean function f on n bits whose deterministic query complexity is Ω(n/log(n)) while its zero-error randomized query complexity is Õ(√n). We further show that the quantum query complexity of the same function is Õ(n1/4), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities.

ACM Symposium on Theory of Computing (STOC)•Jun 10, 2016•30 citations

Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful

Xiaoming Sun, Yufan Zheng

In this paper, we introduce the hybrid query complexity, denoted as $\mathrm{Q}(f;q)$, which is the minimal query number needed to compute $f$, when a classical decision tree is allowed to call $q'$-query quantum subroutines for any $q'\leq q$. We present the following results: $\bullet$ There exists a total Boolean function $f$ such that $\mathrm{Q}(f;1) = \widetilde{\mathcal{O}}(\mathrm{R}(f)^{4/5})$. $\bullet$ $\mathrm{Q}(f;q) = Ω(\mathrm{bs}(f)/q + \sqrt{\mathrm{bs}(f)})$ for any Boolean function $f$; the lower bound is tight when $f$ is the ${\rm O{\small R}}$ function. $\bullet$ $\mathrm{Q}(g \circ {\rm X{\small OR}}_{C \log n};1) = \widetildeΩ(\sqrt{n})$ for some sufficiently large constant $C$, where $g := {\rm B{\small OOL}S{\small IMON}}_n$ is a variant of Simon's problem. Note that $\mathrm{Q}(g\circ {\rm X{\small OR}}_{C \log n}) = \mathcal{O}(\mathrm{polylog}\; n)$. Therefore an exponential separation is established. Furthermore, this open the road to prove the conjecture $\forall k,\,\mathrm{Q}(g \circ {\rm X{\small OR}}_{C \log^{k+1} n};\log^{k} n) = \widetildeΩ(\sqrt{n})$, which would imply the oracle separation $\mathsf{HP}(\mathsf{QSIZE}(n^α))^\mathfrak{O} \subsetneq \mathsf{BQP}^\mathfrak{O}$ for any $α$, where $\mathsf{HP}(\mathsf{QSIZE}(n^α))$ is a complexity class that contains $\mathsf{BQTIME}(n^α)^{\mathsf{BPP}}$ and $\mathsf{BPP}^{\mathsf{BQTIME}(n^α)}$ in any relativized world.

arXiv:1911.13091•Nov 29, 2019•2 citations

Towards better separation between deterministic and randomized query complexity

Sagnik Mukhopadhyay, Swagato Sanyal

We show that there exists a Boolean function F which gives the following separations among deterministic query complexity (D(F)), randomized zero error query complexity (R0(F)) and randomized one-sided error query complexity (R1(F)): R1(F) = Õ( √ D(F)) and R0(F) = Õ(D(F))3/4. This refutes the conjecture made by Saks and Wigderson that for any Boolean function f, R0(f) = Ω(D(f))0.753.. This also shows widest separation between R1(f) and D(f) for any Boolean function. The function F was defined by Göös, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous nondeterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function F certify optimal (quadratic) separation between D(f) and R0(f), and polynomial separation between R0(f) and R1(f). Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considered in the work of Ambainis et al are different variants of F, in this work we show that the original function F itself is sufficient to refute the Saks-Wigderson conjecture and obtain widest possible separation between the deterministic and one-sided error randomized query complexity.

•Dec 1, 2015•2 citations
In this paper we study the separation between the deterministic (classical) query complexity (DDD) and the exact quantum query complexity (QEQ_EQE​) of several Boolean function classes using the parity decision tree method. We first define the Query Friendly (QF) functions on nnn variables as the ones with minimum deterministic query complexity (D(f))(D(f))(D(f)). We observe that for each nnn, there exists a non-separable class of QF functions such that D(f)=QE(f)D(f)=Q_E(f)D(f)=QE​(f). Further, we show that for some values of nnn, all the QF functions are non-separable. Then we present QF functions for certain other values of nnn where separation can be demonstrated, in particular, QE(f)=D(f)−1Q_E(f)=D(f)-1QE​(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 fff on nnn variables D(f)=nD(f) = nD(f)=n, separation can be achieved as n2≤QE(f)≤⌈3n4⌉\frac{n}{2} \leq Q_E(f) \leq \lceil \frac{3n}{4} \rceil2n​≤QE​(f)≤⌈43n​⌉. Our results highlight how different classes of Boolean functions can be analyzed for classical-quantum separation exploiting the parity decision tree method.
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 (Qalgo(f)Q_{algo}(f)Qalgo​(f)) for a direct sum based class of Ω(2n2)Ω\left( 2^{\frac{\sqrt{n}}{2}} \right)Ω(22n​​) 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⊕(f)D_{\oplus}(f)D⊕​(f)) analysing the Walsh Spectrum. Finally, we show that query complexity of QalgoQ_{algo}Qalgo​ is ⌈3n4⌉\lceil \frac{3n}{4} \rceil⌈43n​⌉ whereas D⊕(f)D_{\oplus}(f)D⊕​(f) varies between n−1n-1n−1 and ⌈3n4⌉+1\lceil \frac{3n}{4} \rceil+1⌈43n​⌉+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 n4\frac{n}{4}4n​) class of Maiorana-McFarland type functions, but could only obtain partial results using similar algorithmic techniques.
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 explore the Maiorana-McFarland(MM) type Bent functions, defined on all even nnn variables. The (classical) Deterministic Query Complexity (D(f)D(f)D(f)) of all functions in this class is nnn. In this regard we construct an n2+⌈n8⌉\frac{n}{2} + \lceil \frac{n}{8} \rceil2n​+⌈8n​⌉ query exact quantum algorithm that is not a parity decision tree and evaluates a non-symmetric subclass of MM type Bent functions on nnn variables consisting of (2⌊n4⌋!)(2⌈n4⌉!)22⌊n4⌋\left(2^{\lfloor \frac{n}{4} \rfloor}!\right)\left(2^{\lceil \frac{n}{4} \rceil}!\right) 2^{2^{\lfloor \frac{n}{4} \rfloor}}(2⌊4n​⌋!)(2⌈4n​⌉!)22⌊4n​⌋ functions. Finally we also extend this technique for functions defined on odd values of nnn using the Bent concatenation method. To the best of our knowledge, this is the first algorithm beyond parity for a general class of non-symmetric functions.
Query complexity is a model of computation in which functions are evaluated by making queries to the variables. In a very recent paper [Physical Review A 101, 022325 (2020)], Chen, Ye and Li provided a characterization of exact one-query quantum algorithms. We first note that this result is an immediate corollary of what was proved five years back by Montanaro, Jozsa and Mitchison [Algorithmica 71, pp. 775-796 (2015)]. Further, in this model, we concentrate on understanding the differences between classical and quantum computation in terms of number of influencing variables of a function given lowest query complexity in the classical domain. We explore the parity decision tree model to portray possible separations between classical and quantum computations in specific cases. Our results classify different classes of Boolean functions on nnn-variables (nnn being a function of kkk), that can be evaluated (i) with exactly kkk queries in both classical and exact quantum model or (ii) with kkk queries in classical model and (k−1)(k-1)(k−1) queries in exact quantum model.
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function f on n=2k bits defined by a complete binary tree of NAND gates of depth k, which achieves R0(f) = O(D(f)0.7537…). We show this is false by giving an example of a total boolean function f on n bits whose deterministic query complexity is Ω(n/log(n)) while its zero-error randomized query complexity is Õ(√n). We further show that the quantum query complexity of the same function is Õ(n1/4), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities.
In this paper, we introduce the hybrid query complexity, denoted as Q(f;q)\mathrm{Q}(f;q)Q(f;q), which is the minimal query number needed to compute fff, when a classical decision tree is allowed to call q′q'q′-query quantum subroutines for any q′≤qq'\leq qq′≤q. We present the following results: ∙\bullet∙ There exists a total Boolean function fff such that Q(f;1)=O~(R(f)4/5)\mathrm{Q}(f;1) = \widetilde{\mathcal{O}}(\mathrm{R}(f)^{4/5})Q(f;1)=O(R(f)4/5). ∙\bullet∙ Q(f;q)=Ω(bs(f)/q+bs(f))\mathrm{Q}(f;q) = Ω(\mathrm{bs}(f)/q + \sqrt{\mathrm{bs}(f)})Q(f;q)=Ω(bs(f)/q+bs(f)​) for any Boolean function fff; the lower bound is tight when fff is the OR{\rm O{\small R}}OR function. ∙\bullet∙ Q(g∘XORClog⁡n;1)=Ω~(n)\mathrm{Q}(g \circ {\rm X{\small OR}}_{C \log n};1) = \widetildeΩ(\sqrt{n})Q(g∘XORClogn​;1)=Ω(n​) for some sufficiently large constant CCC, where g:=BOOLSIMONng := {\rm B{\small OOL}S{\small IMON}}_ng:=BOOLSIMONn​ is a variant of Simon's problem. Note that Q(g∘XORClog⁡n)=O(polylog  n)\mathrm{Q}(g\circ {\rm X{\small OR}}_{C \log n}) = \mathcal{O}(\mathrm{polylog}\; n)Q(g∘XORClogn​)=O(polylogn). Therefore an exponential separation is established. Furthermore, this open the road to prove the conjecture ∀k, Q(g∘XORClog⁡k+1n;log⁡kn)=Ω~(n)\forall k,\,\mathrm{Q}(g \circ {\rm X{\small OR}}_{C \log^{k+1} n};\log^{k} n) = \widetildeΩ(\sqrt{n})∀k,Q(g∘XORClogk+1n​;logkn)=Ω(n​), which would imply the oracle separation HP(QSIZE(nα))O⊊BQPO\mathsf{HP}(\mathsf{QSIZE}(n^α))^\mathfrak{O} \subsetneq \mathsf{BQP}^\mathfrak{O}HP(QSIZE(nα))O⊊BQPO for any ααα, where HP(QSIZE(nα))\mathsf{HP}(\mathsf{QSIZE}(n^α))HP(QSIZE(nα)) is a complexity class that contains BQTIME(nα)BPP\mathsf{BQTIME}(n^α)^{\mathsf{BPP}}BQTIME(nα)BPP and BPPBQTIME(nα)\mathsf{BPP}^{\mathsf{BQTIME}(n^α)}BPPBQTIME(nα) in any relativized world.
We show that there exists a Boolean function F which gives the following separations among deterministic query complexity (D(F)), randomized zero error query complexity (R0(F)) and randomized one-sided error query complexity (R1(F)): R1(F) = Õ( √ D(F)) and R0(F) = Õ(D(F))3/4. This refutes the conjecture made by Saks and Wigderson that for any Boolean function f, R0(f) = Ω(D(f))0.753.. This also shows widest separation between R1(f) and D(f) for any Boolean function. The function F was defined by Göös, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous nondeterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function F certify optimal (quadratic) separation between D(f) and R0(f), and polynomial separation between R0(f) and R1(f). Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considered in the work of Ambainis et al are different variants of F, in this work we show that the original function F itself is sufficient to refute the Saks-Wigderson conjecture and obtain widest possible separation between the deterministic and one-sided error randomized query complexity.