Deutsch's Algorithm

Part of Womanium Quantum + AI 2024 program

Definition

Deutsch's algorithm is one of the first presented quantum algorithms that provided a quantum advantage over classical computers for a specific problem.

Problem

Assume we have a function binary $f$ , such that

f : {0, 1} \to {0, 1}

We say function $f$ is:

Balanced if $f (0) \neq f (1)$ .
Constant if $f (0) = f (1)$ .

Using the least numbers of queries to the function $f$ , determine if the function is balanced or constant.

Classical Solution

To solve this problem classically we have to query the function two times to get the result of both $f (0)$ and $f (1)$ . Therefore we need to cover the entire search space / function domain.

Deutsch's Algorithm

We assume we have an oracle that implements the function $f$ , call it $U_{f}$ , as a unitary operation.

Todo

Review Implementing Classical Operations as Quantum Operations.

The algorithm uses phase kickback to solve the problem with a single query of the oracle. This can be seen in the following implementation of the algorithm.

We notice that a phase kickback will occur when $f (x) = 1$ . Now let's apply these gates on our initial state $| 0 ⟩ | 0 ⟩$ .

\begin{aligned} | 0 ⟩ | 0 ⟩ & \overset{I \otimes X}{\to} | 0 ⟩ | 1 ⟩ \overset{H H}{\to} | + ⟩ | - ⟩ \\ = (\frac{1}{\sqrt{2}} | 0 ⟩ + \frac{1}{\sqrt{2}} | 1 ⟩) | - ⟩ \\ = \frac{1}{\sqrt{2}} | 0 ⟩ | - ⟩ + \frac{1}{\sqrt{2}} | 1 ⟩ | - ⟩ \\ \overset{U_{f}}{\to} U_{f} (\frac{1}{\sqrt{2}} | 0 ⟩ | - ⟩ + \frac{1}{\sqrt{2}} | 1 ⟩ | - ⟩) \\ = \frac{1}{\sqrt{2}} U_{f} | 0 ⟩ | - ⟩ + \frac{1}{\sqrt{2}} U_{f} | 1 ⟩ | - ⟩ \\ = (- 1)^{f (0)} \frac{1}{\sqrt{2}} | 0 ⟩ | - ⟩ + (- 1)^{f (1)} \frac{1}{\sqrt{2}} | 1 ⟩ | - ⟩ \\ = ((- 1)^{f (0)} \frac{1}{\sqrt{2}} | 0 ⟩ + (- 1)^{f (1)} \frac{1}{\sqrt{2}} | 1 ⟩) | - ⟩ \end{aligned}

Now if $f$ is constant (i.e. $f (0) = f (1)$ ), then both the $| 0 ⟩$ and $| 1 ⟩$ states would have the same phase, which means it's a global phase and we can ignore it.

\begin{aligned} ∴ ((- 1)^{f (0)} \frac{1}{\sqrt{2}} | 0 ⟩ + (- 1)^{f (1)} \frac{1}{\sqrt{2}} | 1 ⟩) | - ⟩ \\ = (\frac{1}{\sqrt{2}} | 0 ⟩ + \frac{1}{\sqrt{2}} | 1 ⟩) | - ⟩ \\ = | + ⟩ | - ⟩ \\ \overset{H \otimes I}{\to} | 0 ⟩ | - ⟩ \end{aligned}

Therefore if $f$ is constant then the output after measurement is $0$ .

Now what if $f$ is balanced (i.e. $f (0) \neq f (1)$ ), then the states $| 0 ⟩$ and $| 1 ⟩$ would have opposite phases, therefore it can be represented as $| - ⟩$ .

\begin{aligned} ∴ ((- 1)^{f (0)} \frac{1}{\sqrt{2}} | 0 ⟩ + (- 1)^{f (1)} \frac{1}{\sqrt{2}} | 1 ⟩) | - ⟩ \\ = (\frac{1}{\sqrt{2}} | 0 ⟩ - \frac{1}{\sqrt{2}} | 1 ⟩) | - ⟩ \\ = | - ⟩ | - ⟩ \\ \overset{H \otimes I}{\to} | 1 ⟩ | - ⟩ \end{aligned}

That means that we would measure $1$ if $f$ is balanced.

Conclusion

Deutsch's algorithm uses an oracle to implement function $f$ , then uses a single query to figure out whether the function is balanced or constant. This is done by employing phase kickback in the oracle implementation, where the result is dependent on a qubit in superposition, therefore we get a different phase kickback depending on the state.

At the end, if the measured result is $0$ then $f$ is constant, and if the measured result is $0$ then $f$ is balanced.

Practicality

Deutsch's algorithm is used to prove the existence of a quantum advantage over classical computers, and the algorithm is not used in real applications due to its specific and impractical problem.

Next: Deutsch-Jozsa Algorithm >