June 1, 2018

Deutch's Algorithm (or Two Birds One Quantum Gate)

Why is this important?

Let’s say we have to find a binary function $f$, but we are only given the gate $U_f$ and our goal is to guess what $f$ could be based on the output of a circuit. (Don’t worry about the specifics of the gate, it can be a black box for now.) Classically, it should take two evaluations of the function just to determine the following result: $f(0) \oplus f(1)$. (This is called a global property.)


Figure 1: All 4 possible single-input binary functions

In other words, two evaluations will eliminate two possibilities for what the function $f$ could be, which makes intuitive sense. However, as we shall see in a moment, a quantum algorithm lets us determine this global property - in essence eliminating two possibilities for $f$ - in just one evaluation of the function! Although quantum computers are capable of far more than just two-birds-with-one-stone tricks, this is one way to get a flavour for why quantum computing is so exciting and potentially quite powerful.


Figure 2: A qubit visualized as a Bloch sphere. From https://www.sciencenews.org/sites/default/files/2017/06/main/articles/070817_essay_qubit_main.png

The Algorithm

The problem statement is that we are given two qubits $|x\rangle$ and $|y\rangle$ which can take values of 0 or 1. The question is, “Is it possible to solve the global property $f(0) \oplus f(1)$, knowing only that $U_f$ has the effect of taking the qubit $|y\rangle$ and adding $f(x)$ to its original value?” (In other words, we don’t get to see the explicit form of $U_f$.) The answer, unsurprisingly, is yes.

The Deutsch algorithm accomplishes this. The Deutsch algorithm can determine $f(0) \oplus f(1)$ using quantum parallelism. For example, if $f$ is the identity function, the expected global property would be $f(0) \oplus f(1) = 1$ in all cases (essentially just adding a 1 and a 0 to get 1 here.) Although the algorithm successfully determines this global property of our chosen function, it should be noted that this property alone is not sufficient to deduce that $f$ is the identity function. This is because a NOT gate would yield the same results, where we have $f(1)=0$ and $f(0)=1$. What this global property does successfully is rule out the other two possibilities for a function with a one bit input and output - these are the constant functions $f(x) = 0$ and $f(x)=1$. Why? In these cases, we get either 1 + 1 or 0 + 0 and in either case this is 0 after you apply the mod 2, not a 1.

So how does it work? As mentioned before, we choose $U_f$ such that

$$ \begin{align*} U_f | x \rangle |y\rangle = |x\rangle |y\oplus f(x)\rangle \\ \\ \end{align*} $$

We will also need the concept of a Hadamard gate, which is defined as having the effect of

$$ \begin{align*} H|0\rangle = \frac{|0\rangle+|1\rangle}{\sqrt{2}}, \ H|1\rangle = \frac{|0\rangle-|1\rangle}{\sqrt{2}} \end{align*} $$

We then send the state $|\Psi_0\rangle = |0\rangle|1\rangle$ through 2 Hadamard gates to give us

$$ \begin{align*} |\Psi_1\rangle = \left[\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right]\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \end{align*} $$

The following result can be verified (somewhat tediously) but drags down the explanation less if it is merely stated.

$$ \begin{align*} |\Psi_2\rangle = U_f|\Psi_1\rangle = \begin{cases} \pm \left[\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right]\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \ \text{if} \ f(0) = f(1)\\ \pm \left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \ \text{if} \ f(0) \neq f(1) \end{cases} \end{align*} $$

Then, we cleverly apply the Hadamard gate once more to the first qubit, which is unitary so that it is its own inverse and therefore yields the following

$$ \begin{align*} |\Psi_3\rangle = (H\otimes\hat{I})|\Psi_2\rangle = \begin{cases} \pm |0\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \ \text{if} \ f(0) = f(1)\\ \pm |1\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \ \text{if} \ f(0) \neq f(1) \end{cases} \end{align*} $$

Now, we just replace the conditions on the right with our global property, since another way of formulating the result that the first qubit is 0 if $f(0) = f(1)$ and 1 otherwise is by saying that the first qubit contains our global property, $f(0) \oplus f(1)$.

$$ \begin{align*} |\Psi_3\rangle = \pm |f(0) \oplus f(1)\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \end{align*} $$

So we conclude that our first ouput qubit contains our answer and that performing a measurement in the $\{|0\rangle,|1\rangle\}$ basis will reveal a global property of the binary function $f$, thereby eliminating 2 of the 4 possibilities as to what it could be.

Example: the Identity Function

Let’s try building a quantum circuit to simulate this algorithm working on a specific choice of $f$ (which in some sense defeats the purpose of the algorithm but we’ll pretend we forgot which $f$ we chose). We’ll use IBM Q to do this. If $f$ is the identity function, we will get

$$ \begin{align*} U_f | 0 \rangle |y\rangle = |0\rangle |y\oplus 0 \rangle \\ U_f | 1 \rangle |y\rangle = |0\rangle |y\oplus 1 \rangle \\ \end{align*} $$

or in matrix form this gives us the 4 cases

$$ \begin{align*} U_f \left(\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \end{matrix}\right) = \left(\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \end{matrix}\right), \ U_f \left(\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix}\right) = \left(\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix}\right), \ U_f \left(\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \end{matrix}\right) = \left(\begin{matrix} 0 \\ 0 \\ 0 \\ 1 \end{matrix}\right), \ U_f \left(\begin{matrix} 0 \\ 0 \\ 0 \\ 1 \end{matrix}\right) = \left(\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \end{matrix}\right) \end{align*} $$

By observation, (or solving a system of linear equations) you arrive at the result that

$$\begin{align*} U_f = \left(\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}\right) \end{align*}$$

which is the explicit form of the control-not gate in the z-basis. The setup for the circuit that will execute the algorithm is shown in the diagram below.


The identity function has $f(0) \oplus f(1) = 1$, so our result for the first output bit is the quantum state $|1\rangle$ to indicate that. Since this is an eigenstate of the associated basis, we should theoretically measure the state $|1\rangle$ for our first qubit 100% of the time, but the device has a margin of error associated with it so we don’t get a pure $|1\rangle$ state. However, our results (shown below) are pretty consistent with what we’d expect. So cool!


© Angus Lowe 2018

Powered by Hugo & Kiss.