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

arXiv:2303.10663

Distributed exact quantum algorithms for Deutsch-Jozsa problem

Hao Li, Daowen Qiu, Le Luo

Published Mar 19, 2023• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2303.10663

Related papers

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.

Physical Review A•Jun 20, 2018•31 citations

Generalized Deutsch-Jozsa Algorithm for Applications in Data Classification, Logistic Regression, and Quantum Key Distribution

M. Ghadimi, V. Salari, S. Bakrani +4 more

We present a generalized Deutsch-Jozsa (DJ) quantum algorithm that not only determines both the global type of an unknown Boolean function (constant or balanced) but also determines explicit output values of the function in a single oracle query. Unlike the original DJ algorithm, which identifies only whether a function is constant or balanced, our generalization retrieves actual function output values at the same time with using a Bell state as ancilla. This makes a richer function characterization with minimal queries to have practical quantum advantages, e.g. data classification, logistic regression, and quantum cryptography.

quant-pharXiv:2512.00715•Physical Review A•Dec 2, 2025•0 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.

arXiv:2112.12416•International Journal of Foundations of Computer Science•Jan 30, 2026•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

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•14 citations

What can exact one-query quantum algorithms do?

Weijiang Chen, Zekun Ye, Lvzhou li

Quantum query models are one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including Deutsch-Jozsa algorithm, Simon algorithm, Grover algorithm and so on. 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 \rightarrow \{0,1\}$ can be exactly computed by a one-query quantum algorithm if and only if $f(x)=x_{i_1}$ or $f(x)=x_{i_1} \oplus 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$.

•Dec 7, 2019•0 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 fff: {0,1}n→{0,1}\{0,1\}^n\rightarrow \{0,1\}{0,1}n→{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 fff being constant (balanced) and some properties of fff'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.
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 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 ${2}^{n\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}$, 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+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 present a generalized Deutsch-Jozsa (DJ) quantum algorithm that not only determines both the global type of an unknown Boolean function (constant or balanced) but also determines explicit output values of the function in a single oracle query. Unlike the original DJ algorithm, which identifies only whether a function is constant or balanced, our generalization retrieves actual function output values at the same time with using a Bell state as ancilla. This makes a richer function characterization with minimal queries to have practical quantum advantages, e.g. data classification, logistic regression, and quantum cryptography.
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.
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.
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.
Quantum query models are one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including Deutsch-Jozsa algorithm, Simon algorithm, Grover algorithm and so on. 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→{0,1}f:\{0,1\}^n \rightarrow \{0,1\}f:{0,1}n→{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 $f(x)=x_{i_1} \oplus 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.