arXiv:2112.12416 · International Journal of Foundations of Computer Science

Polynomial Representation of General Partial Boolean Functions with a Single Quantum Query

Guoliang Xu, Daowen Qiu

Published Jan 30, 2026• 0 citations

Abstract

Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query, and thus achieved the best separation between classical deterministic and exact quantum query complexity. Recently, it was clarified that all symmetric partial Boolean functions with a single quantum query can be computed exactly by Deutsch-Jozsa algorithm. For the general partial Boolean functions with a single quantum query, the latest characterizations is complex and not very satisfactory. Based on this, this paper proves and discovers three new results: (1) Under a new equivalence, each partial Boolean function with a single quantum query can be transformed to a simple partial Boolean function whose polynomial degree is just one; (2) For partial Boolean functions up to four bits, there are only 10 non-trivial partial Boolean functions with a single quantum query; (3) For each quantum 1-query algorithm with undefined measurement, there exists a constructive method for finding out all partial Boolean functions that can be computed exactly by the algorithm.

DOI: 10.1142/s0129054126500012

Related papers

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

Zekun Ye, Lvzhou Li

arXiv:2008.11998Aug 27, 20201 citation

Exact Quantum 1-Query Algorithms and Complexity

Daowen Qiu, Guoliang Xu

SPINAug 12, 20213 citations

Partial Boolean Functions With Exact Quantum Query Complexity One

Guoliang Xu, Daowen Qiu

arXiv:2007.10924EntropyFeb 3, 20216 citations

Distributed exact quantum algorithms for Deutsch-Jozsa problem

Hao Li, Daowen Qiu, Le Luo

arXiv:2303.10663Mar 19, 20235 citations

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

Chandra Sekhar Mukherjee, Subhamoy Maitra

arXiv:2008.06317Aug 14, 20200 citations

Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\Exact^5_{3,4}$

Guoliang Xu, Haoran Zhang, Mengfan Wu +2 more

Let $f = \text{EXACT}^5_{3,4}$ be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of $f$ is $4$. For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function $\text{EXACT}^7_{3,4}$ and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound $\frac{25600}{43779488192449}>0$ on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.

quant-pharXiv:2610.24518Oct 20, 20260 citations

arXiv:2112.12416 · International Journal of Foundations of Computer Science

Polynomial Representation of General Partial Boolean Functions with a Single Quantum Query

Guoliang Xu, Daowen Qiu

Published Jan 30, 2026• 0 citations

arXiv HTML PDF

Abstract

DOI: 10.1142/s0129054126500012

Related papers

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.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.11998Aug 27, 20201 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.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.

SPINAug 12, 20213 citations

Partial Boolean Functions With Exact Quantum Query Complexity One

Guoliang Xu, Daowen Qiu

We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm. Due to the second characterization, we construct a function F that maps any n-bit partial Boolean function to some integer, and if an n-bit partial Boolean function f depends on k bits and can be computed exactly by a 1-query quantum algorithm, then F(f) is non-positive. In addition, we show that the number of all n-bit partial Boolean functions that depend on k bits and can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on n and k. Most importantly, the upper bound is far less than the number of all n-bit partial Boolean functions for all efficiently big n.We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm. Due to the second characterization, we construct a function F that maps any n-bit partial Boolean function to some integer, and if an n-bit partial Boolean function f depends on k bits and can be computed exactly by a 1-query quantum algorithm, then F(f) is non-positive. In addition, we show that the number of all n-bit partial Boolean functions that depend on k bits and can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on n and k. Most importantly, the upper bound is far less than the number of all n-bit partial Boolean functions for all efficiently big n.

arXiv:2007.10924EntropyFeb 3, 20216 citations

Distributed exact quantum algorithms for Deutsch-Jozsa problem

Hao Li, Daowen Qiu, Le Luo

Deutsch-Jozsa (DJ) problem is one of the most important problems demonstrating the power of quantum algorithm. DJ problem can be described as a Boolean function $f$ : $\{0,1\}^n\rightarrow \{0,1\}$ with promising it is either constant or balanced, and the purpose is to determine which type it is. DJ algorithm can solve it exactly with one query. In this paper, we first discover the inherent structure of DJ problem in distributed scenario by giving a number of equivalence characterizations between $f$ being constant (balanced) and some properties of $f$ 's subfunctions, and then we propose three distributed exact quantum algorithms for solving DJ problem. Our algorithms have essential acceleration over distributed classical deterministic algorithm, and can be extended to the case of multiple computing nodes. Compared with DJ algorithm, our algorithms can reduce the number of qubits and the depth of circuit implementing a single query operator. Therefore, we find that the structure of problem should be clarified for designing distributed quantum algorithm to solve it.Deutsch-Jozsa (DJ) problem is one of the most important problems demonstrating the power of quantum algorithm. DJ problem can be described as a Boolean function $f$: $\{0,1\}^n\rightarrow \{0,1\}$ with promising it is either constant or balanced, and the purpose is to determine which type it is. DJ algorithm can solve it exactly with one query. In this paper, we first discover the inherent structure of DJ problem in distributed scenario by giving a number of equivalence characterizations between $f$ being constant (balanced) and some properties of $f$'s subfunctions, and then we propose three distributed exact quantum algorithms for solving DJ problem. Our algorithms have essential acceleration over distributed classical deterministic algorithm, and can be extended to the case of multiple computing nodes. Compared with DJ algorithm, our algorithms can reduce the number of qubits and the depth of circuit implementing a single query operator. Therefore, we find that the structure of problem should be clarified for designing distributed quantum algorithm to solve it.

arXiv:2303.10663Mar 19, 20235 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

Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\Exact^5_{3,4}$

Guoliang Xu, Haoran Zhang, Mengfan Wu +2 more

Let $f = \text{EXACT}^5_{3,4}$ be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of $f$ is $4$ . For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function $\text{EXACT}^7_{3,4}$ and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound $\frac{25600}{43779488192449}>0$ on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.Let $f = \text{EXACT}^5_{3,4}$ be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of $f$ is $4$. For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function $\text{EXACT}^7_{3,4}$ and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound $\frac{25600}{43779488192449}>0$ on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.

quant-pharXiv:2610.24518Oct 20, 20260 citations

Deutsch-Jozsa (DJ) problem is one of the most important problems demonstrating the power of quantum algorithm. DJ problem can be described as a Boolean function

f

\{0,1\}^n\rightarrow \{0,1\}

with promising it is either constant or balanced, and the purpose is to determine which type it is. DJ algorithm can solve it exactly with one query. In this paper, we first discover the inherent structure of DJ problem in distributed scenario by giving a number of equivalence characterizations between

f

being constant (balanced) and some properties of

f

's subfunctions, and then we propose three distributed exact quantum algorithms for solving DJ problem. Our algorithms have essential acceleration over distributed classical deterministic algorithm, and can be extended to the case of multiple computing nodes. Compared with DJ algorithm, our algorithms can reduce the number of qubits and the depth of circuit implementing a single query operator. Therefore, we find that the structure of problem should be clarified for designing distributed quantum algorithm to solve it.

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.

Let

f = \text{EXACT}^5_{3,4}

be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of

f

4

. For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function

\text{EXACT}^7_{3,4}

and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound

\frac{25600}{43779488192449}>0

on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.