Deutsch-Jozsa algorithm

Deutsch’s algorithm works on a single input bit in the simple case where f(0, 1) → (0,1). A generalization of the algorithm known as Deutsch-Jozsa algorithm. It can act on an n-bit function f(0, 1)ⁿ → (0,1).

Assuming a 2-bit function of the form (0, 1)² → (0,1) is provided and it is known at the outset that the function. In the worst case, the function (black box) needs to be called 2ⁿ⁺¹ + 1 times to check whether it is balanced or constant. Deutsch and Jozsa introduced an algorithm that can answer this with 100% accuracy using only one query.

The Deutsch-Jozsa algorithm uses two quantum registers x and y, x having n qubits and y having only 1 qubit. The circuit diagram of the Deutsch-Jozsa algorithm is shown below:

As can be seen in the diagram, the total number of input qubits is (n+1) which is the sum of qubits in the x and the y register. The n qubits in the x register are initialized to |0>, and the qubit in the y register is initialized to a |1>.