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

Physical Review A

Generalized Deutsch-Jozsa problem and the optimal quantum algorithm

Daowen Qiu, Shenggen Zheng

Published Jun 20, 2018• 33 citations
Publisher

Abstract

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.

DOI
10.1103/physreva.97.062331

Related papers

Characterizations of symmetrically partial Boolean functions with exact quantum query complexity

Daowen Qiu, Shenggen Zheng

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.

arXiv:1603.06505•Mar 21, 2016•12 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•5 citations

DE-QUANTIZING THE SOLUTION OF DEUTSCH'S PROBLEM

Cristian S. Calude

Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called Deutsch's problem. Consider a Boolean function f: {0,1} → {0,1} and suppose that we have a (classical) black box to compute it. The problem asks whether f is constant [that is, f(0) = f(1)] or balanced [f(0) ≠ f(1)]. Classically, to solve the problem seems to require the computation of f(0) and f(1), and then the comparison of results. Is it possible to solve the problem with only one query on f? In a famous paper published in 1985, Deutsch posed the problem and obtained a "quantum" partial affirmative answer. In 1998, a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello and Mosca. Here we will show that the quantum solution can be de-quantized to a deterministic simpler solution which is as efficient as the quantum one. The use of "superposition," a key ingredient of quantum algorithm, is — in this specific case — classically available.

arXiv:quant-ph/0610220•International Journal of Quantum Information•May 30, 2007•23 citations

Generalizations of the distributed Deutsch–Jozsa promise problem

Jozef Gruska, Daowen Qiu, Shenggen Zheng

In thedistributed Deutsch–Jozsa promise problem, two parties are to determine whether their respective stringsx, y∈ {0,1}nare at theHamming distanceH(x, y) = 0 orH(x, y) = $\frac{n}{2}$ . Buhrmanet al.(STOC' 98) proved that the exactquantum communication complexityof this problem isO(logn) while thedeterministic communication complexityisΩ(n). This was the first impressive (exponential) gap between quantum and classical communication complexity. In this paper, we generalize the above distributed Deutsch–Jozsa promise problem to determine, for any fixed $\frac{n}{2}$ ⩽k⩽n, whetherH(x, y) = 0 orH(x, y) =k, and show that an exponential gap between exact quantum and deterministic communication complexity still holds ifkis an even such that $\frac{1}{2}$ n⩽k< (1 − λ)n, where 0 < λ < $\frac{1}{2}$ is given. We also deal with a promise version of the well-knowndisjointnessproblem and show also that for this promise problem there exists an exponential gap between quantum (and also probabilistic) communication complexity and deterministic communication complexity of the promise version of such a disjointness problem. Finally, some applications to quantum, probabilistic and deterministic finite automata of the results obtained are demonstrated.

arXiv:1402.7254•Mathematical Structures in Computer Science•May 6, 2015•41 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•3 citations

Characterization of exact one-query quantum algorithms

Weijiang Chen, Zekun Ye, Lvzhou Li

The quantum query model is one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including the Deutsch-Jozsa algorithm, the Simon algorithm, the Grover algorithm, and others. In this paper, we characterize the computational power of exact one-query quantum algorithms. It is proved that a total Boolean function $f:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ can be exactly computed by a one-query quantum algorithm if and only if $f(x)={x}_{{i}_{1}}$ or ${x}_{{i}_{1}}\ensuremath{\bigoplus}{x}_{{i}_{2}}$ (up to isomorphism). Note that, unlike most work in the literature based on the polynomial method, our proof does not resort to any knowledge about the polynomial degree of $f$.

arXiv:1912.03493•Physical Review A•Feb 20, 2020•15 citations
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 DJn0:0,1n\ensuremath→0,1{\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}DJn0​:0,1n\ensuremath→0,1 defined as DJn0(x)=1{\text{DJ}}_{n}^{0}(x)=1DJn0​(x)=1 for ∣x∣=n/2,DJn0(x)=0|x|=n/2, {\text{DJ}}_{n}^{0}(x)=0∣x∣=n/2,DJn0​(x)=0 for ∣x∣=0,n|x|=0,n∣x∣=0,n, and it is undefined for the rest of the cases, where nnn is even, and ∣x∣|x|∣x∣ is the Hamming weight of xxx. The optimal quantum algorithm needs only one query to compute DJn0{\text{DJ}}_{n}^{0}DJn0​ but the classical deterministic algorithm requires 2n\ensuremath−1+1{2}^{n\ensuremath{-}1}+12n\ensuremath−1+1 queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as DJnk(x)=1{\text{DJ}}_{n}^{k}(x)=1DJnk​(x)=1 for ∣x∣=n/2,DJnk(x)=0|x|=n/2, {\text{DJ}}_{n}^{k}(x)=0∣x∣=n/2,DJnk​(x)=0 for ∣x∣|x|∣x∣ in the set 0,1,...,k,n\ensuremath−k,n\ensuremath−k+1,...,n{0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}0,1,...,k,n\ensuremath−k,n\ensuremath−k+1,...,n, and it is undefined for the rest of the cases, where 0\ensuremath≤k<n/20\ensuremath{\le}k<n/20\ensuremath≤k<n/2. In particular, we give and prove an optimal exact quantum query algorithm with complexity k+1k+1k+1 for computing the generalized Deutsch-Jozsa problem DJnk{\text{DJ}}_{n}^{k}DJnk​. It is clear that the case of k=0k=0k=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.
We give and prove an optimal exact quantum query algorithm with complexity k+1k+1k+1 for computing the promise problem (i.e., symmetric and partial Boolean function) DJnkDJ_n^kDJnk​ defined as: DJnk(x)=1DJ_n^k(x)=1DJnk​(x)=1 for ∣x∣=n/2|x|=n/2∣x∣=n/2, DJnk(x)=0DJ_n^k(x)=0DJnk​(x)=0 for ∣x∣|x|∣x∣ in the set {0,1,…,k,n−k,n−k+1,…,n}\{0, 1,\ldots, k, n-k, n-k+1,\ldots,n\}{0,1,…,k,n−k,n−k+1,…,n}, and it is undefined for the rest cases, where nnn is even, ∣x∣|x|∣x∣ is the Hamming weight of xxx. The case of k=0k=0k=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 fff has exact quantum 1-query complexity if and only if fff 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 {⌊n/2⌋,⌈n/2⌉}\{ \lfloor n/2\rfloor, \lceil n/2\rceil \}{⌊n/2⌋,⌈n/2⌉} and Hamming weight in the set {0,n}\{ 0, n\}{0,n} for all odd nnn. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.
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.
Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called Deutsch's problem. Consider a Boolean function f: {0,1} → {0,1} and suppose that we have a (classical) black box to compute it. The problem asks whether f is constant [that is, f(0) = f(1)] or balanced [f(0) ≠ f(1)]. Classically, to solve the problem seems to require the computation of f(0) and f(1), and then the comparison of results. Is it possible to solve the problem with only one query on f? In a famous paper published in 1985, Deutsch posed the problem and obtained a "quantum" partial affirmative answer. In 1998, a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello and Mosca. Here we will show that the quantum solution can be de-quantized to a deterministic simpler solution which is as efficient as the quantum one. The use of "superposition," a key ingredient of quantum algorithm, is — in this specific case — classically available.
In thedistributed Deutsch–Jozsa promise problem, two parties are to determine whether their respective stringsx, y∈ {0,1}nare at theHamming distanceH(x, y) = 0 orH(x, y) = n2\frac{n}{2}2n​ . Buhrmanet al.(STOC' 98) proved that the exactquantum communication complexityof this problem isO(logn) while thedeterministic communication complexityisΩ(n). This was the first impressive (exponential) gap between quantum and classical communication complexity. In this paper, we generalize the above distributed Deutsch–Jozsa promise problem to determine, for any fixed n2\frac{n}{2}2n​ ⩽k⩽n, whetherH(x, y) = 0 orH(x, y) =k, and show that an exponential gap between exact quantum and deterministic communication complexity still holds ifkis an even such that 12\frac{1}{2}21​ n⩽k< (1 − λ)n, where 0 < λ < 12\frac{1}{2}21​ is given. We also deal with a promise version of the well-knowndisjointnessproblem and show also that for this promise problem there exists an exponential gap between quantum (and also probabilistic) communication complexity and deterministic communication complexity of the promise version of such a disjointness problem. Finally, some applications to quantum, probabilistic and deterministic finite automata of the results obtained are demonstrated.
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 quantum query model is one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including the Deutsch-Jozsa algorithm, the Simon algorithm, the Grover algorithm, and others. In this paper, we characterize the computational power of exact one-query quantum algorithms. It is proved that a total Boolean function $f:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ can be exactly computed by a one-query quantum algorithm if and only if f(x)=xi1f(x)={x}_{{i}_{1}}f(x)=xi1​​ or ${x}_{{i}_{1}}\ensuremath{\bigoplus}{x}_{{i}_{2}}$ (up to isomorphism). Note that, unlike most work in the literature based on the polynomial method, our proof does not resort to any knowledge about the polynomial degree of fff.