arXiv:1603.06505

Characterizations of symmetrically partial Boolean functions with exact quantum query complexity

Daowen Qiu, Shenggen Zheng

Published Mar 21, 2016• 8 citations

Abstract

We give and prove an optimal exact quantum query algorithm with complexity $k+1$ for computing the promise problem (i.e., symmetric and partial Boolean function) $DJ_n^k$ defined as: $DJ_n^k(x)=1$ for $|x|=n/2$, $DJ_n^k(x)=0$ for $|x|$ in the set $\{0, 1,\ldots, k, n-k, n-k+1,\ldots,n\}$, and it is undefined for the rest cases, where $n$ is even, $|x|$ is the Hamming weight of $x$. The case of $k=0$ is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function $f$ has exact quantum 1-query complexity if and only if $f$ can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight $\{ \lfloor n/2\rfloor, \lceil n/2\rceil \}$ and Hamming weight in the set $\{ 0, n\}$ for all odd $n$. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.

DOI: 10.48550/arxiv.1603.06505

Related papers

Exact Quantum 1-Query Algorithms and Complexity

Daowen Qiu, Guoliang Xu

SPINAug 12, 20213 citations

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

Guoliang Xu, Daowen Qiu

arXiv:2112.12416International Journal of Foundations of Computer ScienceJan 30, 20260 citations

Generalized Deutsch-Jozsa problem and the optimal quantum algorithm

Daowen Qiu, Shenggen Zheng

Physical Review AJun 20, 201831 citations

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

Zekun Ye, Lvzhou Li

arXiv:2008.11998Aug 27, 20201 citation

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

Exact quantum query complexity of weight decision problems.

Xiaoyu He, Xiaoming Sun, Guang Yang +1 more

Jan 17, 20183 citations

arXiv:1603.06505

Characterizations of symmetrically partial Boolean functions with exact quantum query complexity

Daowen Qiu, Shenggen Zheng

Published Mar 21, 2016• 8 citations

arXiv HTML PDF

Abstract

We give and prove an optimal exact quantum query algorithm with complexity

k+1

for computing the promise problem (i.e., symmetric and partial Boolean function)

DJ_n^k

defined as:

DJ_n^k(x)=1

for

|x|=n/2

DJ_n^k(x)=0

for

|x|

in the set

\{0, 1,\ldots, k, n-k, n-k+1,\ldots,n\}

, and it is undefined for the rest cases, where

n

is even,

|x|

is the Hamming weight of

x

. The case of

k=0

is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function

f

has exact quantum 1-query complexity if and only if

f

can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight

\{ \lfloor n/2\rfloor, \lceil n/2\rceil \}

and Hamming weight in the set

\{ 0, n\}

for all odd

n

. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.

DOI: 10.48550/arxiv.1603.06505

Related papers

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

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

Guoliang Xu, Daowen Qiu

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.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.

arXiv:2112.12416International Journal of Foundations of Computer ScienceJan 30, 20260 citations

Generalized Deutsch-Jozsa problem and the optimal quantum algorithm

Daowen Qiu, Shenggen Zheng

The Deutsch-Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It was proposed by Deutsch and Jozsa in 1992 with improvements by Cleve, Ekert, Macchiavello, and Mosca in 1998. The Deutsch-Jozsa problem is a promise problem and we can equivalently describe it as a partial function ${\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ defined as ${\text{DJ}}_{n}^{0}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{0}(x)=0$ for $|x|=0,n$ , and it is undefined for the rest of the cases, where $n$ is even, and $|x|$ is the Hamming weight of $x$ . The optimal quantum algorithm needs only one query to compute ${\text{DJ}}_{n}^{0}$ but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as ${\text{DJ}}_{n}^{k}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{k}(x)=0$ for $|x|$ in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity $k+1$ for computing the generalized Deutsch-Jozsa problem ${\text{DJ}}_{n}^{k}$ . It is clear that the case of $k=0$ is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.The Deutsch-Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It was proposed by Deutsch and Jozsa in 1992 with improvements by Cleve, Ekert, Macchiavello, and Mosca in 1998. The Deutsch-Jozsa problem is a promise problem and we can equivalently describe it as a partial function ${\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ defined as ${\text{DJ}}_{n}^{0}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{0}(x)=0$ for $|x|=0,n$, and it is undefined for the rest of the cases, where $n$ is even, and $|x|$ is the Hamming weight of $x$. The optimal quantum algorithm needs only one query to compute ${\text{DJ}}_{n}^{0}$ but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as ${\text{DJ}}_{n}^{k}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{k}(x)=0$ for $|x|$ in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity $k+1$ for computing the generalized Deutsch-Jozsa problem ${\text{DJ}}_{n}^{k}$. It is clear that the case of $k=0$ is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.

Physical Review AJun 20, 201831 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.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 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

Exact quantum query complexity of weight decision problems.

Xiaoyu He, Xiaoming Sun, Guang Yang +1 more

The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular, both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length- $n$ input is $k$ or it is $l$ . Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of $(\frac{k}{n},\frac{l}{n})$ and sufficiently large $n$ , the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of $(\frac{k}{n},\frac{l}{n})$ with matching upper and lower bounds, and finally we generalize to other cases via a new \emph{quantum padding} technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular, both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length-$n$ input is $k$ or it is $l$. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of $(\frac{k}{n},\frac{l}{n})$ and sufficiently large $n$, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of $(\frac{k}{n},\frac{l}{n})$ with matching upper and lower bounds, and finally we generalize to other cases via a new \emph{quantum padding} technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.

Jan 17, 20183 citations

We give and prove an optimal exact quantum query algorithm with complexity

k+1

for computing the promise problem (i.e., symmetric and partial Boolean function)

DJ_n^k

defined as:

DJ_n^k(x)=1

for

|x|=n/2

DJ_n^k(x)=0

for

|x|

in the set

\{0, 1,\ldots, k, n-k, n-k+1,\ldots,n\}

, and it is undefined for the rest cases, where

n

is even,

|x|

is the Hamming weight of

x

. The case of

k=0

f

has exact quantum 1-query complexity if and only if

f

can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight

\{ \lfloor n/2\rfloor, \lceil n/2\rceil \}

and Hamming weight in the set

\{ 0, n\}

for all odd

n

. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.

{\text{DJ}}_{n}^{0}(x)=1

for

|x|=n/2, {\text{DJ}}_{n}^{0}(x)=0

for

|x|=0,n

, and it is undefined for the rest of the cases, where

n

is even, and

|x|

is the Hamming weight of

x

. The optimal quantum algorithm needs only one query to compute

{\text{DJ}}_{n}^{0}

but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as

{\text{DJ}}_{n}^{k}(x)=1

for

|x|=n/2, {\text{DJ}}_{n}^{k}(x)=0

for

|x|

in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity

k+1

for computing the generalized Deutsch-Jozsa problem

{\text{DJ}}_{n}^{k}

. It is clear that the case of

k=0

is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.

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.

n

input is

k

or it is

l

. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of

(\frac{k}{n},\frac{l}{n})

and sufficiently large

n

, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of

(\frac{k}{n},\frac{l}{n})

with matching upper and lower bounds, and finally we generalize to other cases via a new \emph{quantum padding} technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.