A View on the Deutsch Algorithm

 

The Deutsch Algorithm is an excellent example of the application of quantum parallelism using superposition of states. The problem which is solved by the algorithm is the following: Given an unknown function f(x): {0:1} -> {0,1}, by using the minimum amount of queries to this function, determine if the function is constant (it always returns 0 or always returns 1) or balanced (on half of the inputs it returns 0 and the other half, 1).

In the classical case, we need to query the function twice, one for x=0 and a second for x=1. In case of the quantum algorithm, a single query can define if the function is balanced or constant.

There are many articles explaining how the algorithm works. Here I've taken a different approach: After a brief recap of the algorithm, the analysis of the algorithm follows by opening each state and showing how the problem definition and the function we want to classify contributes to the algorithm output.

 On its simplest form, the algorithm utilizes two qubits, the first on state $x=|0⟩$ and the second on state $y=|1⟩$. The two states are then submitted to Hadamard gates to create the respective superpositions $x^{\prime }=Hx=|+⟩$ and $y^{\prime }=Hy=|-⟩$. 

The superpositions are used as an input for an Oracle function $|{\psi }_1⟩$ = O(x',y') = $x^{\prime }\otimes y^{\prime }\oplus f(x^{\prime })$. Finally, Hadamard is applied to the first qubit of the output of the Oracle function $|{\psi }_2⟩=H\otimes \mathbb{1}\cdot O(x^{\prime },y^{\prime })$ followed by the measurement of the first qubit. If the measure results in 0, the function is constant, if it results in 1, it's balanced. The following picture illustrates the circuit.

 

Let's understand why it works!

        To recap...

                    $|+⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$

                    $|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$

        ... and looking at  $|{\psi }_1⟩$ we have...

                    $|{\psi }_1⟩=O(x,y)|+⟩\otimes |-⟩=\frac{1}{2}[|0⟩|0⟩\oplus f(0)-|0⟩|1⟩\oplus f(0)+|1⟩|0⟩\oplus f(1)-|1⟩|1⟩\oplus f(1)]$ 

        ... regrouping the terms... 

                    $|{\psi }_1⟩=\frac{1}{2}[|0⟩|0⟩\oplus f(0)+|1⟩|0⟩\oplus f(1)-(|0⟩|1⟩\oplus f(0)+|1⟩|1⟩\oplus f(1))]$  

        ... and replacing $|a⟩|b⟩$ by $s_{ab}$ ...

                    $|{\psi }_1⟩=\frac{1}{2}[s_{00}\oplus f(0)+s_{10}\oplus f(1)-(s_{01}\oplus f(0)+s_{11}\oplus f(1))]$

Note the operator $\oplus$ applies to the second qubit of the states. Moreover, the states are now split into two groups of two states, differing only by the phase (positive and negative). We'll see next that the function f(x) will move states from the positive to the negative phases. This allows the algorithm to determine if the function f(x) is constant or balanced in one single query.

Let's have a closer look on the function f(x). The function is unknown, but as it is defined as having a binary input and output, there are only four possible functions, being:

                            for f(x) constant:                                        for f(x) balanced:

                                        f(0) = f(1) = 0                                        f(0) = 0; f(1) = 1

                                        f(0) = f(1) = 1                                        f(0) = 1; f(1) = 0

Let's look at each of the four possible functions, focusing on the states $s_{00}$ and $s_{10}$

                    1 - f(x) constant with f(0)=0; f(1)=0 $⟹$ $|{\psi }_1⟩=\frac{1}{2}[\left(s_{00}+s_{10}\right)-(s_{01}+s_{11})]$

                    2 - f(x) constant with f(0)=1; f(1)=1 $⟹$ $|{\psi }_1⟩=\frac{1}{2}[(s_{01}+s_{11})-\left(s_{00}+s_{10}\right)]$

                    3 - f(x) balanced with f(0)=0; f(1)=1 $⟹$ $|{\psi }_1⟩=\frac{1}{2}[(s_{00}+s_{11})-(s_{01}+s_{10})]$

                    4 - f(x) balanced with f(0)=1; f(1)=0 $⟹$ $|{\psi }_1⟩=\frac{1}{2}[(s_{01}+s_{10})-(s_{00}+s_{11})]$

The four states above show how each function f(x) changes the phases of the states in four distinct combinations, allowing the state $|{\psi }_1⟩$ to identify uniquely each of the four functions.

Here is the main reason for the algorithm to work...

The function has the effect of grouping states into two categories. These categories align with the concept of constant and balanced function. For example, note that in case 1) the function is constant and 0. Factoring and considering only the first qubit (the one on which Hadamard will be applied in the next step) gives $\frac{1}{\sqrt{2}}(|s_0⟩+|s_1⟩)$ which is nothing more than $|+⟩$. Likewise, the second constant function maps to $-|+⟩$. Extending, the constant functions map to $\pm |+⟩$ while balanced functions map to $\pm |-⟩$. The details of the steps described here follows.

First, lets re-organize the four states above by factoring them. The factoring gives us the following results:

                    1 - f(x) constant with f(0)=0; f(1)=0 $⟹$ $|{\psi }_1⟩=+|+⟩|-⟩$

                    2 - f(x) constant with f(0)=0; f(1)=1 $⟹$ $|{\psi }_1⟩=-|+⟩|-⟩$ 

                    3 - f(x) balanced with f(0)=0; f(1)=1 $⟹$ $|{\psi }_1⟩=+|-⟩|-⟩$

                    4 - f(x) balanced with f(0)=1; f(1)=0 $⟹$ $|{\psi }_1⟩=-|-⟩|-⟩$ 

Obtaining $|{\psi }_2⟩=H\otimes \mathbb{1}\cdot O(x^{\prime },y^{\prime })$ is straightforward and given by the next four equations:

                    1 - f(x) constant with f(0)=0; f(1)=0 $⟹$ $|{\psi }_2⟩=+|0⟩|-⟩$

                    2 - f(x) constant with f(0)=0; f(1)=1 $⟹$ $|{\psi }_2⟩=-|0⟩|-⟩$ 

                    3 - f(x) balanced with f(0)=0; f(1)=1 $⟹$ $|{\psi }_2⟩=+|1⟩|-⟩$

                    4 - f(x) balanced with f(0)=1; f(1)=0 $⟹$ $|{\psi }_2⟩=-|1⟩|-⟩$

  The measurement of the first qubit is now given by:

                    1 - f(x) constant with f(0)=0; f(1)=0 $⟹$ 0

                    2 - f(x) constant with f(0)=1; f(1)=1 $⟹$ 0

                    3 - f(x) balanced with f(0)=0; f(1)=1 $⟹$ 1

                    4 - f(x) balanced with f(0)=1; f(1)=0 $⟹$ 1

As can be observed, if f(x) is constant, the Deutsch Algorithm returns 0, and if f(x) is balanced, it returns 1. All this in only one single query to the Oracle.

So, a quick recap...

• Using superposition allows the parallelism on the query
• The usage of phase is important to create a set of states that can be manipulated by the function
  
• Functions actuate in states in a specific way, nicely mapping constant functions to the state $\pm |+⟩$ and balanced functions to the state $\pm |-⟩$
  
• The fact that global phases do not influence on measurements allow the measurements to always return 0 for constant functions and 1 for balanced functions.

References and Further Readings

1. Nielsen, M., & Chuang, I. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511976667
2. https://learn.qiskit.org/course/ch-algorithms/deutsch-jozsa-algorithm