Deutch-Jozsa algorithm

We are given a black box function which is either

• constant everywhere (i.e. either 0 or 1 everywhere)
• OR balanced (i.e. exactly half the inputs give 0)

We want to find whether is balanced or constant
Classically we need operations.

Quantum improves:

The setting

Let

The algorithm

Step 1

Initialize all qubits in state

Step 2

Step 3

where

Step 4

Discard the last qubit i.e. left with qubit state

Note that:
If is constant we can find

If is balanced
Let

Take inner product

if is balanced.
Thus

Step 5

Apply to

Step 6

Measure these qubits in a complete basis

1. If is constant the outcome is
2. If is balanced then mmt outcome is NOT all 0

Conclusion

We have used 1 query of and another other operations.