Quantum Computing (CST Part II)
Lecture 7: Deutsch-Jozsa Algorithm
Computer programming is an art form,
like the creation of poetry or music.
Donald Knuth
1 / 19
Quantum algorithms
We have seen that using quantum states can lead to tangible advantages
in certain information processing tasks.
We now turn our attention to the potential benefits of using quantum
information in algorithms: that is, quantum computing proper. We have
seen that quantum computing does not violate the Church-Turing thesis,
and so our attention will be on the extent to which quantum computing
can speed-up computational tasks.
The story starts with an algorithm discovered in 1985 by David Deutsch,
which was the first to display a computational advantage compared to
the best possible corresponding classical algorithm.
2 / 19
Binary numbers and quantum states
It is usually convenient to express the action of a quantum circuit for any
computational basis state and then use linearity to express a sum of
superposed terms if necessary. To do so, we analyse the circuit for a
general n-qubit computational basis state, |xi:
|xi = |x1 x2 · · · xn i = |x1 i ⊗ |x2 i ⊗ · · · ⊗ |xn i
where xi ∈ {0, 1} for i = 1 · · · n and associated with |xi is the n-bit
binary number x.
3 / 19
Computing mathematical functions on quantum computers
In order to design quantum algorithms we need to know how to execute
functions on a quantum computer. In particular, we are interested in
functions that take a (binary) number, and output a truth value (i.e.,
{0, 1}). That is, functions of the form f : {0, 1}n → {0, 1}.
𝑥 = 0,1 𝑛 𝑓(𝑥) 0,1
However, we know that a quantum circuit is composed of quantum gates,
which are unitary operations, and apart from for trivial functions, this is
not a unitary.
4 / 19
Arbitrary mathematical functions as unitaries
Instead, we must use the same trick that allowed us to write down the
Toffoli gates as a quantum (unitary) version of the classical AND gate:
as well as evaluating the function we output the input data:
𝑛 𝑛
𝑥 𝑥
U
𝑦 𝑦⊕𝑓(𝑥)
U can easily be seen to be self-inverse, and the universality of quantum
computing implies that any function f (x) can be efficiently encoded in
this way (to desired accuracy) as a quantum circuit consisting of gates
from a finite universal set.
The crossed through wire labelled “n” in the circuit denotes a bundle of
n qubits, sometimes termed a n-qubit register. It is also worth pointing
out that the same principle holds when the output of f (x) is not
restricted to be a single bit, but rather can be nf bits, and thus the
second wire is itself a nf -qubit register.
5 / 19
Constant and balanced function on a single bit
If the input, x, is a single bit (as is the output), then we have four
possible functions:
Function x f (x) Type Unitary
0 0 𝑥 𝑥
f (x) = 0 Constant
1 0 𝑦 𝑦⊕𝑓(𝑥)
0 1 𝑥 𝑥
f (x) = 1 Constant
1 1 𝑦 X 𝑦⊕𝑓(𝑥)
0 0 𝑥 𝑥
f (x) = x Balanced
1 1 𝑦 𝑦⊕𝑓(𝑥)
0 1 𝑥 𝑥
f (x) = x ⊕ 1 Balanced
1 0 𝑦 X 𝑦⊕𝑓(𝑥)
6 / 19
Deutsch’s algorithm set-up
We want to find out whether a particular function, with one input bit and
one output bit is constant or balanced. Classically, we need to evaluate
the function twice (i.e., for input = 0 and input = 1), but remarkably, we
only need to evaluate the function once quantumly, by using Deutsch’s
algorithm.
We have a two qubit unitary, which is one of the four on the previous
slide (we don’t know which):
𝑥 𝑥
U
𝑦 𝑦⊕𝑓(𝑥)
Which we are going to incorporate into a quantum circuit.
7 / 19
Deutsch’s algorithm (1)
0 H 𝑥 𝑥 H
1 H 𝑦 𝑦⊕𝑓(𝑥)
𝜓0 𝜓1 𝜓2 𝜓3
Initially we prepare the state:
|ψ0 i = |01i
Which the initial Hadamard gates put in the superposition state:
|0i + |1i |0i − |1i
|ψ1 i = √ √
2 2
1
= (|00i − |01i + |10i − |11i)
2
8 / 19
Deutsch’s algorithm (2)
1
|ψ1 i = (|00i − |01i + |10i − |11i)
2
Next the unitary is implemented, which sets the second qubit to
y ⊕ f (x), so we have four options for |ψ2 i:
1
f (x) = 0 |ψ2 i = 2 (|00i − |01i + |10i − |11i)
1
f (x) = 1 |ψ2 i = 2 (|01i − |00i + |11i − |10i)
1
f (x) = x |ψ2 i = 2 (|00i − |01i + |11i − |10i)
1
f (x) = x ⊕ 1 |ψ2 i = 2 (|01i − |00i + |10i − |11i)
which factorises as:
± |0i+|1i
√
|0i−|1i
√ if f (0) = f (1)
2 2
|ψ2 i =
± |0i−|1i
√
|0i−|1i
√ if f (0) 6= f (1)
2 2
That is the two balanced cases differ only by an unobservable global
phase (and likewise for the two constant cases).
9 / 19
Deutsch’s algorithm (3)
± |0i+|1i
√
|0i−|1i
√ if f (0) = f (1)
2 2
|ψ2 i =
± |0i−|1i
√
|0i−|1i
√ if f (0) 6= f (1)
2 2
The next step is to use the Hadamard gate to interfere the superposition
on the first qubit, which yields:
± |0i |0i−|1i
√ if f (0) = f (1)
2
|ψ3 i =
|0i−|1i
± |1i √ if f (0) 6= f (1)
2
The final step is to measure the first qubit, and we can see that the
outcome will always be 0 if the function is constant, and 1 if balanced.
We can see that superposition and interference, in some sense, play
complementary roles: we prepare a state in superposition, perform some
operations, and then use interference to discern some global property of
the state.
10 / 19
Quantum computing jargon
Query complexity:
In Deutsch’s algorithm we are not using a quantum computer to
evaluate a “classically difficult” function per se, but rather using
quantum phenomena to reduce the number of queries we need to
make to an unknown function, to ascertain some information
thereabout.
Oracles and black boxes:
In Deutsch’s algorithm, and other query complexity algorithms, we
query U, which is known as a “black box”, or often in quantum
computing an “oracle”. The oracle in Deutsch’s algorithm is
sufficiently simple that we can explicitly express each possible
option, but frequently in quantum computing problems are framed in
terms of oracles, even when this is not the case.
11 / 19
Deutsch-Jozsa algorithm
Together with Richard Jozsa, who
is now a Professor here in DAMTP,
in 1992 David Deutsch generalised
the algorithm to apply to constant
/ balanced functions of any input
size.
Academia Europaea
Richard Jozsa
12 / 19
Deutsch’s problem
The Deutsch-Jozsa algorithm is usually motivated in terms of Deutsch’s
problem:
We have a function f : {0, 1}n → {0, 1}.
We are promised this function is either constant (same output for
each x) or balanced (f (x) is equal to each of 0 and 1 for exactly
half of the possible values of x).
Classically, we can see that we may need to query the function
2n
2 + 1 times to be sure whether the function is constant or
balanced. That is, because there are 2n possible bitstrings, x, so in
n
the worst case even if we get the same outcome the first 22 times
we classically query the oracle, we cannot be sure whether the
n
function is constant and balanced – only the 22 + 1 th query will
tell us this.
But quantumly, if the function is encoded as a quantum oracle, then
the Deutsch-Jozsa algorithm allows us to determine whether the
function is constant or balanced with only a single oracle call.
13 / 19
Deutsch-Jozsa algorithm (1)
The circuit of the Deutsch-Jozsa algorithm closely resembles that of
Deutsch’s algorithm:
𝑛
0 ⊗𝑛 H⊗𝑛 𝑥 𝑥 H⊗𝑛
1 H 𝑦 𝑦⊕𝑓(𝑥)
𝜓0 𝜓1 𝜓2 𝜓3
The initial state of which can be expressed:
⊗n
|ψ0 i = |0i |1i
which is then put into superposition, which can conveniently be
expressed:
X 1
|ψ1 i = √ |xi (|0i − |1i)
x∈{0,1}n
2n+1
14 / 19
Deutsch-Jozsa algorithm (2)
X 1
|ψ1 i = √ |xi (|0i − |1i)
x∈{0,1}n
2n+1
The unitary transforms |ψ1 i to:
X 1
|ψ2 i = √ (−1)f (x) |xi (|0i − |1i)
x∈{0,1}n
2n+1
We now address the interference H ⊗n on the first n wires, for which we
use the expression:
1 X
H ⊗n |xi = √ (−1)x·z |zi
2n z∈{0,1}n
which allows us to express:
X X 1 |0i − |1i
|ψ3 i = (−1)x·z+f (x) |zi √
2n 2
x∈{0,1}n z∈{0,1}n
15 / 19
Deutsch-Jozsa algorithm (3)
We can now determine whether the function is constant or balanced by
measuring the first n qubits of the final state (i.e., we neglect the final
qubit which is in the |−i state):
X X 1 |0i − |1i
|ψ3 i = n
(−1)x·z+f (x) |zi √
n n
2 2
z∈{0,1} x∈{0,1}
Specifically, we consider the probability of measuring zero on every qubit,
⊗n
which corresponds to the term in the superposition where |zi is |0i :
In the case where the function is constant, then the co-efficient of
⊗n P
|0i , x (−1)f (x) /2n is equal to ±1... as this has amplitude 1,
⊗n
then we measure |0i with probability one.
In
P the case where the function is balanced then
f (x) ⊗n
x (−1) /2n = 0, and so we will never measure |0i .
So it follows that measuring the first n qubits allows us to determine
with certainty whether the function is constant (measure all zeros) or
balanced (measure at least one 1).
16 / 19
Potential for exponential speed-up using a quantum
computer
Imagine now that the oracle is held by a person, “Bob”, who is spatially
separated from the person, “Alice”, who is trying to determine whether
the function is constant or balanced.
To resolve an instance of Deutsch’s problem, classically Alice
n
transmits 22 + 1 messages, each of size n bits, and each of which
Bob replies to with a one bit message.
Whereas quantumly the Deutsch-Jozsa algorithm requires only the
transmission of a single n + 1 qubit message by Alice, to which Bob
replies with a n qubit message.
So there is an exponential reduction in the amount of information
transfer required to solve an instance of Deutsch’s problem. 17 / 19
Where is this potential exponential advantage coming
from?
Consider a function, f , which takes a n-bit binary number as an input.
Note there are 2n different n-bit binary numbers.
Classically, we can only evaluate f for one of these binary numbers
at a time.
But quantumly, noting the direct correspondence between quantum
states and binary numbers highlighted at the start of this lecture, we
can evaluate the function for a superposition of all 2n binary
numbers in one go.
This fundamental property of quantum computing got everybody very
excited but, as we shall see, finding useful quantum algorithms with an
exponential advantage is actually rather more nuanced.
18 / 19
Summary
We can encode any mathematical function as a unitary matrix.
Deutsch’s algorithm was the first algorithm that demonstrated a
quantum advantage: specifically a reduction in query complexity
compared to the classical case.
The Deutsch-Jozsa algorithm generalises Deutsch’s algorithm, and
reveals the possibility of exponential speed-ups using quantum
computers.
19 / 19