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 · Quantum Information Processing

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

Chandra Sekhar Mukherjee, Subhamoy Maitra

Published Jun 1, 2021• 5 citations
arXivHTMLPDF
DOI
10.1007/s11128-021-03158-1

Related papers

On the Power of Parity Queries in Boolean Decision Trees

Raghav Kulkarni, Youming Qiao, Xiaoming Sun

Lecture notes in computer science•Jan 1, 2015•1 citation

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

Implementation of Classical Decision Trees in a Quantum Computing Paradigm

Manuel Pegalájar Cuéllar, L. G. B. Ruiz, M. C. Pegalajar

Lecture notes in computer science•Oct 8, 2024•2 citations

Lower bounds on quantum query complexity for read-once decision trees with parity nodes

Hideaki Fukuhara, Eiji Takimoto

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 Symposium•Jan 1, 2009•0 citations

Efficient Quantum Algorithm for the Parity Problem of a Certain Function

Koji Nagata, Tadao Nakamura, Josep Amengual i Batle +1 more

International Journal of Theoretical Physics•Jul 16, 2018•2 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•7 citations
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.
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.
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.