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

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

Chandra Sekhar Mukherjee, Subhamoy Maitra

Published Aug 14, 2020• 0 citations
OpenAlex

Abstract

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.

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

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

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

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

Properties and application of nondeterministic quantum query algorithms

Alina Dubrovska

Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require O(n) queries.

arXiv:quant-ph/0606248•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Apr 27, 2007•3 citations

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$

Yao, Penghui, Ye, Zekun

The query model has generated considerable interest in both classical and quantum computing communities. Typically, quantum advantages are demonstrated by showcasing a quantum algorithm with a better query complexity compared to its classical counterpart. Exact quantum query algorithms play a pivotal role in developing quantum algorithms. For example, the Deutsch-Jozsa algorithm demonstrated exponential quantum advantages over classical deterministic algorithms. As an important complexity measure, exact quantum query complexity describes the minimum number of queries required to solve a specific problem exactly using a quantum algorithm. In this paper, we consider the exact quantum query complexity of the following two $n$-bit symmetric functions $\text{MOD}_m^n:\{0,1\}^n \rightarrow \{0,...,m-1\}$ and $\text{EXACT}_{k,l}^n:\{0,1\}^n \rightarrow \{0,1\}$, which are defined as $\text{MOD}_m^n(x) = |x| \bmod m$ and $ \text{EXACT}_{k,l}^n(x) = 1$ iff $|x| \in \{k,l\}$, where $|x|$ is the number of $1$'s in $x$. Our results are as follows: i) We present an optimal quantum algorithm for computing $\text{MOD}_m^n$, achieving a query complexity of $\lceil n(1-\frac{1}{m}) \rceil$ for $1 < m \le n$. This settles a conjecture proposed by Cornelissen, Mande, Ozols and de Wolf (2021). Based on this algorithm, we show the exact quantum query complexity of a broad class of symmetric functions that map $\{0,1\}^n$ to a finite set $X$ is less than $n$. ii) When $l-k \ge 2$, we give an optimal exact quantum query algorithm to compute $\text{EXACT}_{k,l}^n$ for the case $k=0$ or $k=1,l=n-1$. This resolves the conjecture proposed by Ambainis, Iraids and Nagaj (2017) partially.

arXiv:2303.10935•Mar 20, 2023•0 citations
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.
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 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.
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.
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.
Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require O(n) queries.
On the exact quantum query complexity of MODmn\text{MOD}_m^nMODmn​ and EXACTk,ln\text{EXACT}_{k,l}^nEXACTk,ln​
The query model has generated considerable interest in both classical and quantum computing communities. Typically, quantum advantages are demonstrated by showcasing a quantum algorithm with a better query complexity compared to its classical counterpart. Exact quantum query algorithms play a pivotal role in developing quantum algorithms. For example, the Deutsch-Jozsa algorithm demonstrated exponential quantum advantages over classical deterministic algorithms. As an important complexity measure, exact quantum query complexity describes the minimum number of queries required to solve a specific problem exactly using a quantum algorithm. In this paper, we consider the exact quantum query complexity of the following two nnn-bit symmetric functions MODmn:{0,1}n→{0,...,m−1}\text{MOD}_m^n:\{0,1\}^n \rightarrow \{0,...,m-1\}MODmn​:{0,1}n→{0,...,m−1} and EXACTk,ln:{0,1}n→{0,1}\text{EXACT}_{k,l}^n:\{0,1\}^n \rightarrow \{0,1\}EXACTk,ln​:{0,1}n→{0,1}, which are defined as MODmn(x)=∣x∣ mod m\text{MOD}_m^n(x) = |x| \bmod mMODmn​(x)=∣x∣modm and $ \text{EXACT}_{k,l}^n(x) = 1$ iff ∣x∣∈{k,l}|x| \in \{k,l\}∣x∣∈{k,l}, where ∣x∣|x|∣x∣ is the number of 111's in xxx. Our results are as follows: i) We present an optimal quantum algorithm for computing MODmn\text{MOD}_m^nMODmn​, achieving a query complexity of ⌈n(1−1m)⌉\lceil n(1-\frac{1}{m}) \rceil⌈n(1−m1​)⌉ for 1<m≤n1 < m \le n1<m≤n. This settles a conjecture proposed by Cornelissen, Mande, Ozols and de Wolf (2021). Based on this algorithm, we show the exact quantum query complexity of a broad class of symmetric functions that map {0,1}n\{0,1\}^n{0,1}n to a finite set XXX is less than nnn. ii) When l−k≥2l-k \ge 2l−k≥2, we give an optimal exact quantum query algorithm to compute EXACTk,ln\text{EXACT}_{k,l}^nEXACTk,ln​ for the case k=0k=0k=0 or k=1,l=n−1k=1,l=n-1k=1,l=n−1. This resolves the conjecture proposed by Ambainis, Iraids and Nagaj (2017) partially.