Deutsch–Jozsa (DJ) problem is one of the most important problems demonstrating the power of quantum algorithms, which can be described as a Boolean function \(f: \{0,1\}^n\rightarrow \{0,1\}\) promised to be either constant or balanced, and the purpose is to determine which type it is. The DJ algorithm can compute it exactly with one query. However, classical deterministic algorithm requires \(2^{n-1} + 1\) queries to compute it in the worse case. Therefore, the DJ algorithm is essentially faster than any possible classical deterministic algorithm for computing DJ problem. In this paper, we discover the intrinsic 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. We propose three distributed DJ algorithms, which have exponential speedup over distributed classical deterministic DJ algorithm. In comparison with the DJ algorithm, our algorithms can reduce the number of qubits for a single computing node. Furthermore, compared to distributed DJ algorithm with errors, our algorithms possess accuracy and improved scalability.
