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

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

Chandra Sekhar Mukherjee, Subhamoy Maitra

Published Apr 27, 2020• 0 citations
OpenAlex

Abstract

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.

Related papers

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.

arXiv:2004.12942•Apr 27, 2020•2 citations

Characterization of exact one-query quantum algorithms (ii): for partial functions

Zekun Ye, Lvzhou Li

The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.

arXiv:2008.11998•Aug 27, 2020•1 citation

Exact Quantum 1-Query Algorithms and Complexity

Daowen Qiu, Guoliang Xu

Deutsch–Jozsa problem (D–J) has exact quantum 1-query complexity (“exact” means no error), but requires super-exponential queries for the optimal classical deterministic decision trees. D–J problem is equivalent to a symmetric partial Boolean function, and in fact, all symmetric partial Boolean functions having exact quantum 1-query complexity have been found out and these functions can be computed by D–J algorithm. A special case is that all symmetric Boolean functions with exact quantum 1-query complexity follow directly and these functions are also all total Boolean functions with exact quantum 1-query complexity obviously. Then there are pending problems concerning partial Boolean functions having exact quantum 1-query complexity and new results have been found, but some problems are still open. In this paper, we review these results regarding exact quantum 1-query complexity and in particular, we also obtain a new result that a partial Boolean function with exact quantum 1-query complexity is constructed and it cannot be computed by D–J algorithm. Further problems are pointed out for future study.

SPIN•Aug 12, 2021•3 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.

arXiv:2008.06317•Aug 14, 2020•0 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

Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order

Alastair A. Abbott, Mehdi Mhalla, Pierre Pocreau

Computational models typically assume that operations are applied in a fixed sequential order.In recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure and showing that such "causally indefinite" computations can provide advantages in various tasks.Recently, the quantum query complexity of Boolean functions has been used as a tool to probe their computational power in a standard complexity theoretic framework, but no separation in exact query complexity has thus-far been found.In this paper, we investigate this problem starting with the simpler and fully classical notion of deterministic query complexity of Boolean functions, and using classical-deterministic processes -which may exhibit causal indefiniteness -as a generalised computational framework.We first show that the standard polynomial and certificate lower bounds of deterministic query complexity also hold in such generalised models.Then, we formulate a Boolean function for which causal indefiniteness permits a reduction in query complexity and show that this advantage can be amplified into a polynomial separation.Finally, with the insights gained in the classical-deterministic setting, we give a Boolean function whose quantum query complexity is reduced by causally indefinite computations.

arXiv:2506.05187•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•0 citations
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 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.
The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.
Deutsch–Jozsa problem (D–J) has exact quantum 1-query complexity (“exact” means no error), but requires super-exponential queries for the optimal classical deterministic decision trees. D–J problem is equivalent to a symmetric partial Boolean function, and in fact, all symmetric partial Boolean functions having exact quantum 1-query complexity have been found out and these functions can be computed by D–J algorithm. A special case is that all symmetric Boolean functions with exact quantum 1-query complexity follow directly and these functions are also all total Boolean functions with exact quantum 1-query complexity obviously. Then there are pending problems concerning partial Boolean functions having exact quantum 1-query complexity and new results have been found, but some problems are still open. In this paper, we review these results regarding exact quantum 1-query complexity and in particular, we also obtain a new result that a partial Boolean function with exact quantum 1-query complexity is constructed and it cannot be computed by D–J algorithm. Further problems are pointed out for future study.
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.
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.
Computational models typically assume that operations are applied in a fixed sequential order.In recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure and showing that such "causally indefinite" computations can provide advantages in various tasks.Recently, the quantum query complexity of Boolean functions has been used as a tool to probe their computational power in a standard complexity theoretic framework, but no separation in exact query complexity has thus-far been found.In this paper, we investigate this problem starting with the simpler and fully classical notion of deterministic query complexity of Boolean functions, and using classical-deterministic processes -which may exhibit causal indefiniteness -as a generalised computational framework.We first show that the standard polynomial and certificate lower bounds of deterministic query complexity also hold in such generalised models.Then, we formulate a Boolean function for which causal indefiniteness permits a reduction in query complexity and show that this advantage can be amplified into a polynomial separation.Finally, with the insights gained in the classical-deterministic setting, we give a Boolean function whose quantum query complexity is reduced by causally indefinite computations.