Deutsch's Algorithm:

A Quantum Approach
to Problem Solving

Dr. Om Pal
(Associate Professor)
University of Delhi
Basic working framework of All
quantum algorithms :
• The system will start with the qubits in a particular classical state.
• From there the system is put into a superposition of many states.
• This is followed by acting on this superposition with several unitary
operations.
• U−1 = U*. Thus, unitary operators are just automorphisms of Hilbert spaces,
i.e., they preserve the structure (the vector space structure, the inner
product, and hence the topology) of the space on which they act.
• U preserves the inner product of the Hilbert space, H.

• And finally, a measurement of the qubits.

What is Deutsch's Algorithm?
The simplest quantum algorithm designed to solve a specific problem
faster than any classical algorithm. It was one of the first algorithms to
demonstrate the potential advantage of quantum computing over
classical computing.

Objective of the Algorithm

To determine whether a given function f(x): {0,1}→{0,1} is:
• Constant: Outputs the same value for all inputs {e.g. f(0) = f(1)}
• Balanced: Outputs {e.g. f(0)≠f(1) }
How does It work
Deutsch’s algorithm, solves a slightly contrived problem. This algorithm is
concerned with functions from the set {0, 1} to the set {0,1}.
There are four such functions that might be visualized as

Call a function f: {0, 1} — {0, 1} balanced if f(0) ≠ f(1), i.e., it is one to one.
In contrast, call a function constant if f(0) = f(1).
Of the four functions, two are balanced and two are constant.
What does it solve?
Given a function f: {0, 1} — {0, 1} as a black box, where one can
evaluate an input, but cannot “look inside” and “see” how the function
is defined, determine if the function is balanced or constant.

With a classical computer, one would have to first evaluate f on one

input, then evaluate f on the second input and so on (up to 2n-1+1) and
finally, compare the outputs.
The following decision tree shows what a classical
computer must do

The point is that with a classical computer, f must be evaluated twice.

Can we do better with a quantum computer?
A quantum computer can be in a superposition of two basic states at
the same time.
We shall use this superposition of states to evaluate both inputs at one
time.
In classical computing, evaluating a given function f corresponds to
performing the following operation:

Such a function can be thought of as a matrix acting on the input. For

instance,

the function is equivalent to the matrix

Multiplying state |0 ⟩ on the right of this matrix would result in state |1
⟩, and multi- plying state |1 ⟩ on the right of this matrix would result in
state |0 ⟩.
The column name is to be thought of as the input and the row name as
the output.
However, this will not be enough for a quantum system. Such a system
demands a little something extra: every gate must be unitary (and thus
reversible). Given the output, we must be able to find the input.
If f is the name of the function, then the following black-box Uf will be the quantum
gate that we shall employ to evaluate input:

The top input, |x), will be the qubit value that one wishes to evaluate and the
bottom input, |y), controls the output.
The top output will be the same as the input qubit |x) and the bottom output will be
the qubit |y ⊕ f(x) ⟩, where ⊕ is XOR, the exclusive-or operation (binary addition
modulo 2.) We are going to write from left to right the top qubit first and then the
bottom.
So we say that this function takes the state |x, y⟩ to the state |x, y ⊕ f(x) ⟩.
If y = 0, this simplifies |x, 0⟩ to |x,0 ⊕ f(x) ⟩ = |x, f(x) ⟩.
This gate can be seen to be reversible as we may demonstrate by
simply looking at the following circuit:

State |x, y ⟩ goes to |x, y ⊕ f(x) ⟩, which further goes to:

where the first equality is due to the associativity of ⊕ and the second
equality holds because ⊕ is idempotent. From this we see that Uf is its
own inverse.
In quantum systems, evaluating f is equivalent to multiplying a state by
the unitary matrix Uy.

For function the corresponding unitary matrix,

Uf, is:

Remember that the top column name corresponds to the input |x, y⟩ and
the left-hand row name corresponds to the outputs |x’, y’). A 1in the x y
column and the x’y’ row means that for input |x, y⟩, the output will be |x’,
y’⟩.
Let us remind ourselves of the task at hand. We are given such a matrix
that expresses a function but we cannot “look inside” the matrix to “see”
how it is defined. We are asked to determine if the function is balanced or
constant.
Let us take a first stab at a quantum algorithm to solve this problem.
Rather than evaluating f twice, we shall try our trick of superposition of states. Instead
of having the top input to be either in state |0⟩ or in state |1⟩, we shall put the top input
in state which is “half-way” |0⟩ and “half-way” |1⟩.

The Hadamard matrix can place a qubit in such a state.

The obvious (but not necessarily correct) state to put the bottom input into is state
|0⟩.
Thus we have the following quantum circuit:

The at the bottom of the quantum circuit

will be used to describe the state of the
qubits at each time click.
In terms of matrices this circuit corresponds to
The tensor product |0, 0⟩ can be written as and entire circuit is then:

We shall carefully examine the states of the system at every time click. The system starts
in
We then apply the Hadamard matrix only to the top input leaving the bottom input
alone to get

After multiplying with Uf, we have For function

the state would be

If we measure the top qubit, there will be a 50-50 chance of finding it
in state |0⟩ and a 50-50 chance of finding it in state |1⟩. Similarly, there
is no real information to be gotten by measuring the bottom qubit.
So the obvious algorithm does not work. We need a better trick.
Let us take another stab at solving our problem.
Rather than leaving the bottom qubit in state |0⟩, let us put it in the superposition
state:

Notice the minus sign. Even though there is a negation, this state is also “half-way” in
state |0⟩ and “half-way” in state |1⟩. This change of phase will help us get our
desired results. We can get to this superposition of states by multiplying state |1)
with the Hadamard matrix. We shall leave the top qubit as an ambiguous |x⟩.

In terms of matrices, this becomes

What would happen if we evaluate either the top or the bottom state?
Again, this does not really help us. We do not gain any information if we measure
the top qubit or the bottom qubit. The top qubit will be in state |x) and the bottom
qubit will be either in state |0⟩ or in state |1⟩. We need something more.
Now let us combine both these attempts to actually give Deutsch’s algorithm.
Deutsch’s algorithm works by putting both the top and the bottom qubits into a
superposition. We will also put the results of the top qubit through a Hadamard
matrix.
In terms of matrices this becomes or
At each point of the algorithm the states are as
follows:
We saw from our last attempt at solving this problem that when we put the bottom
qubit into a superposition and then multiply by Uf, we will be in the superposition

For a general function f, let us look carefully at

If f is constant, this becomes either
(depending on being constantly 0 or constantly 1).
If f is balanced, it becomes either
(depending on which way it is balanced).
Summing up, we have that

For example, if f(0) =1and f(1) =0, then we get

Now, we simply measure the top qubit. If it is in state |0), then we know that f is a
constant function, otherwise it is a balanced function. This was all accomplished
with only one function evaluation as opposed to the two evaluations that the
classical algorithm demands.
Notice that although the ±1 tells us even more information, namely, which of the
two balanced functions or two constant functions we have, measurement will not
grant us this information. Upon measuring, if the function is balanced, we will
measure |1⟩ regardless if the state was (-1)|1 ⟩ or (+1)|1 ⟩.
There are four possible functions, and we saw in decision that with a classical
computer we needed two bits of information to determine which of the four
functions we were given. What we are really doing here is changing around the
information. We might determine which of the four functions is the case by asking
the following two questions: “Is the function balanced or constant?” and “What is
the value of the function on 0?”
Deutsch-JOZSA
Algorithm
Let us generalize the Deutsch algorithm to other functions.
Rather than talking about functions f:{0,1}→{0,1},let us talk about
functions with a larger domain. Consider functions f:{0,1}n→{0,1}, which
accept a string of n 0’s and 1’s and outputs a zero or one.
The domain might be thought of as any natural number from 0 to 2n -1.

A function f:{0,1}n→{0,1} balanced if exactly half of the inputs go to 0 (and

the other half go to 1).
A function constant if all the inputs go to 0 or all the inputs go to 1.
What does it solve?
Suppose you are given a function from :{0,1}n to {0, 1} which you can evaluate but
cannot “see” the way it is defined. Suppose further that you are assured that the
function is either balanced or constant.
Determine if the function is balanced or constant. Notice that when n = 1, this is
exactly the problem that the Deutsch algorithm solved.
Classically, this algorithm can be solved by evaluating the function on different
inputs.
The best case scenario is when the first two different inputs have different outputs,
which assures us that the function is balanced. In contrast, to be sure that the
function is constant, one must evaluate the function on more than half the possible
inputs.
So the worst case scenario requires 2n/2+1=2n-1+1 function evaluations.
Can we do better?
We solved a problem by entering into a superposition of two possible input states.
Now, we solve the problem by entering a superposition of all 2n possible input
states.
The function f will be given as a unitary matrix that we shall depict as
Let’s take an example

Consider the following

balanced function from
{0,1}n to {0, 1}:
In order to place a single qubit in a superposition of |0 and |1), we
used a single Hadamard matrix. To place n qubits in a superposition, we
are going to use the tensor product of n Hadamard matrices.
What does such a tensor product look
like?

Remember that the Hadamard matrix is defined as

where i and j are the row and column numbers in binary.
we see that this will equal the leftmost column of
• For an arbitrary basic state |y⟩, which can be represented by a column vector
with a single 1 in position y and 0’s everywhere else, we will be extracting the yth
column of

Let us return to the problem at hand. We are trying to tell whether the given
function is balanced or constant. we were successful by placing the bottom control
qubit in a superposition. Let us see what would happen if we did the same thing
here.
In terms of matrices this amounts to
For an arbitrary as an input in the top n qubits, we will
have the following states:
After the bottom Hadamard matrix, we have
Applying Uf we get

This is almost exactly like Equation in the last

section. And, it is just as unhelpful.
Let us take another stab at the problem and present the Deutsch-Jozsa algorithm.
This time, we shall put into a superposition in which all 2n
possible strings have equal probability. We saw that we can get such a
superposition by multiplying Thus, we have

In terms of matrices this amounts to

Each state can be written as
After applying the Uf unitary matrix, we have

Finally, we apply to the top qubits that are already in a superposition of

different x states to get a superposition of a superposition

from Equation
We can combine parts and “add” exponents to get
So, the probability of collapsing to |0⟩ is totally dependent on f(x). If f(x) is constant
at 1, the top qubits become

If f(x) is constant at 0, the top qubits become

And finally, if f is balanced, then half of the x’s will cancel the other half and the
top qubits will become

When measuring the top qubits of , we will only get |0⟩ if the function is
constant. If anything else is found after being measured, then the function is
balanced.
In conclusion, we have solved the admittedly contrived problem in one
function evaluation as opposed to the 2n-1+1 function evaluations
needed in classical computations.
That is an exponential speedup!