Deutsch-Jozsa Algorithm

Part of Womanium Quantum + AI 2024 program

Definition

Deutsch-Jozsa algorithm is a generalization of Deutsch's Algorithm, where we generalize the definition of the function $f$ as:

\begin{matrix} f : {0, 1} \to {0, 1} \\ ↓ \\ f : {0, 1}^{n} \to {0, 1} \end{matrix}

We say $f$ is:

Constant if it maps all possible strings to either 0 or 1.
Balanced if it maps exactly half of the strings to 0 and the other half to 1.

Deutsch-Jozsa Algorithm

The algorithm is very similar to Deutsch's algorithm, in fact it is the same algorithm except that we apply the Hadamard gate on multiple input qubits instead of just one.

Again, we can see that we are still utilizing phase kickback for this algorithm, which works even with multiple qubits as the input.

Before we start applying the algorithm let's define the following:

\begin{matrix} N = 2^{n} \\ H^{\otimes n} {| 0 ⟩}^{\otimes n} = \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} | x ⟩ \end{matrix}

Now we start applying the algorithm on the starting state ${| 0 ⟩}^{\otimes n} | 0 ⟩$ .

\begin{aligned} {| 0 ⟩}^{\otimes n} | 0 ⟩ & \overset{I \otimes X}{\to} {| 0 ⟩}^{\otimes n} | 1 ⟩ \\ \overset{H^{\otimes n} H}{\to} \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} | x ⟩ \otimes | - ⟩ \\ \overset{U_{f}}{\to} \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} (- 1)^{f (x)} | x ⟩ \otimes | - ⟩ \end{aligned}

Now let's discard of the ancilla that is $| - ⟩$ . Now let's define applying n Hadamard gates on a state of multiple qubits as:

H^{\otimes n} | x ⟩ = \frac{1}{\sqrt{2^{n}}} \sum_{z \in {0, 1}^{n}} (- 1)^{x \cdot z} | z ⟩

Now we continue applying the Hadamard gates:

\begin{aligned} ∴ \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} (- 1)^{f (x)} x \otimes | - ⟩ \to \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} (- 1)^{f (x)} | x ⟩ \\ \overset{H^{\otimes n}}{\to} \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} \frac{1}{\sqrt{N}} \sum_{z \in {0, 1}^{n}} (- 1)^{x \cdot z + f (x)} | z ⟩ \\ = \frac{1}{N} \sum_{x \in {0, 1}^{n}} \sum_{z \in {0, 1}^{n}} (- 1)^{x \cdot z + f (x)} | z ⟩ \end{aligned}

Now let's look at the amplitude for state state $| z ⟩ = {| 0 ⟩}^{\otimes n}$ , this also means that $x \cdot z = 0$ :

\frac{1}{N} \sum_{x \in {0, 1}^{n}} (- 1)^{f (x)}

If the function is constant then:

\begin{matrix} \frac{1}{N} \sum_{x \in {0, 1}^{n}} (- 1)^{f (x)} \\ = \frac{1}{N} (N * 1) = \frac{N}{N} = 1 \\ o r \\ = \frac{1}{N} (N * - 1) = \frac{- N}{N} = - 1 \\ ∴ \frac{1}{N} \sum_{x \in {0, 1}^{n}} (- 1)^{f (x)} = \pm 1 \end{matrix}

then we get the probability of measuring that state by squaring the amplitude ( $α^{2}$ ).

(\pm 1)^{2} = 1

That means if the function is constant we will measure the state ${| 0 ⟩}^{\otimes n}$ with 100% probability, and if the function is balanced we will measure any other value.

Measuring

{| 0 ⟩}^{\otimes n}

with a balanced function

If the function $f$ is balanced then the probability of measuring ${| 0 ⟩}^{\otimes n}$ is 0%, since exactly half of the elements will have an $f (x) = 0$ and the other half $f (x) = 1$ , making the summation cancel itself when adding $- 1$ and $1$ , and we end up with

\frac{1}{N} * (0) = 0

Conclusion

Deutsch-Jozsa algorithm generalizes Deutsch's algorithm to apply to a string of $n$ qubits instead of just one.

After applying the algorithm, which uses a single query only, if we measure ${| 0 ⟩}^{\otimes n}$ , then the function is constant, otherwise it's balanced.

< Prev | Next: Bernstein-Vazirani Algorithm >