### 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

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

We then send the state `$|\Psi_0\rangle = |0\rangle|1\rangle$`

through 2
Hadamard gates to give us

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

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

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)$`

.

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

or in matrix form this gives us the 4 cases

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

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!