Deutsch–Jozsa Algorithm

Daowen Qiu, Shenggen Zheng

E. S. Guerra

The Deutsch-Jozsa algorithm is a generalization of the Deutsch algorithm which was the first algorithm written. We present schemes to implement the Deutsch algorithm and the Deutsch-Jozsa algorithm via cavity QED.

Johnny Hooyberghs

In the previous chapter, you learned about Deutsch’s algorithm. David Deutsch introduced his paper, discussing this algorithm, in 1985 and made improvements with the help from Richard Jozsa, an Australian mathematician. Together, they proposed the Deutsch-Jozsa algorithm in 1992.

Hao Li, Daowen Qiu, Le Luo

Hiu Yung Wong

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.