Keeping it simple with Deustch Jozsa’s algorithm.

The Deustch Jozsa algorithm stands out as one of the first quantum algorithms that performs better than the best classical algorithm. It is a simple and elegant algorithm that originated from the Deustch algorithm (for a single cubit) and was generalised to several qubits.

So what’s the problem we want to solve?

We are given a unknown Boolean function $f$ i.e. given a string of bits it returns either 0 or 1,
$f(\{x_0, x_1, \dotso\}) \rightarrow 0 \text{ or } 1$
$\text{ where } x_n \text{ is } 0 \text{ or } 1$
and this function is either balance or constant, meaning that a constant function will return 0’s or 1’s and a balance function will have 0’s for half of the inputs and 1’s for the other half. Is our function f balanced or not?

Solution:

In a classical computer in the best case scenario we would need at least 2 queries to the oracle to determine whether the function is balanced or not. In the worst case we need half the number of inputs plus one. The power of quantum computation lies in the fact that with a single query to the oracle we are able to know if our function is balanced or not.

Our function $f(x)$ implemented in the oracle is described as follows
$\begin{centering} f:|x\rangle|y\rangle \rightarrow |x\rangle |y \oplus f(x)\rangle \end{centering}$
where $\oplus$ is addition modulo 2.

So let’s describe the algorithm!

We get two quantum registers, one with n qubits initialized to $|0\rangle$ and a single qubit initialized to $|1\rangle$ . $|\psi_0 \rangle=|0\rangle^{\oplus n}|1\rangle$ .
We apply a Hadamard gate to each state to create superposition state. $|\psi_1\rangle = \frac{1}{\sqrt{2^{n+1}}} \sum_{x = 0}^{2^n-1} |x\rangle (|0\rangle-|1\rangle)$ .
We apply the quantum oracle that goes as follows: $\begin{aligned}|\psi_2\rangle & = \frac{1}{\sqrt{2^{n+1}}}\sum_{x = 0}^{2^n-1}|x\rangle(|f(x)\rangle-|1\oplus f(x)\rangle ) \\ &= \frac{1}{\sqrt{2^{n+1}}} \sum_{x = 0}^{2^n-1} (-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle ) \end{aligned}$
We then apply a Hadamard gate to each qubit in the first register. $\begin{aligned} |\psi_3\rangle &= \frac{1}{2^n} \sum_{x= 0}^{2^n-1}{-1}^{f(x)} \big[\sum_{y=0}^{2^n-1}{-1}^{x\cdot y}|y\rangle \big] \\ &= \frac{1}{2^n} \sum_{x=0}^{2^n-1}\big[\sum_{y=0}^{2^n-1}(-1)^{f(x)}(-1)^{x\cdot y}\big]|y \rangle \end{aligned}$
The last step is that we measure the first register. $|0\rangle ^{\oplus n }| \frac{1}{2^n}\sum_{x= 0}^{2^n-1}(-1)^{f(x)}|^2$ which evaluates to 1 if $f(x)$ is constant and to 0 if $f(x)$ is balanced.