## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required Chapter 5
Quantum algorithms
An algorithm is a systematic procedure or a set of instructions to perform
a particular computational task. Many people to associate algorithms with
programming and believe that all algorithms were developed after the intro-
duction of the modern computer (computer languages). This is a common
misconception. Actually, algorithms are independent of machine and lan-
guage and there are many nice algorithms that are more than a thousand
years old. For example, Euclid’s algorithm to ﬁnd the greatest common
divisor was introduced around 300 BC. Although the journey of the algo-
rithm started before Christ, the speciﬁc word “algorithm” appeared much
later. In fact, the word “algorithm” originates from the name of the Persian
mathematician Abu Abdullah Muhammad bin Musa al-Khwarizmi
1
,who
was part of the royal court in Baghdad and who lived from about 780 to
850 AD. Most probably the word “algebra” also originated from his works.
Here it would be apt to note that in our childhood when we learned addi-
tion, multiplication, etc. we essentially learned a set of algorithms as those
were the systematic procedures for doing speciﬁc computational tasks.
A quantum algorithm is a physical process, which performs a com-
putational task with the help of quantum eﬀects. There exist a limited
number of quantum algorithms, which execute the job faster than their ex-
isting classical counterparts. Among these algorithms the most popular are
Grover’s algorithm for unsorted database search and Shor’s algorithm for
factorization. It is interesting to note that David Deutsch was the ﬁrst per-
son who explicitly described a computational task that can be performed
faster using quantum means than by any classical algorithm. Deutsch’s
original algorithm, which was a probabilistic one, has been modiﬁed by
many people, and here we will present a modiﬁed Deutsch’s algorithm.
The present version of Deutsch’s algorithm is very easy to understand and
it can convincingly establish the fact that quantum algorithms can perform
1
Readers can ﬁnd a small biography of Al-khwarizmi at
http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Al-Khwarizmi.html
173 174 Quantum algorithms
certain jobs faster than their existing classical counterparts.
This chapter is dedicated to quantum algorithms. In the following sec-
tion we describe Deutsch’s algorithm. In the subsequent sections we discuss
the Deutsch Jozsa algorithm, Grover’s algorithm, Simon’s algorithm and
Shor’s algorithm.
5.1 Deutsch’s algorithm
Consider a function f(x) having one bit domain and range. In a more
lucid language the previous statement means both x and f(x) can only
have values 0 and 1. Thus we can have only four single bit functions
f(x):{0, 1}→{0, 1}. Out of these four functions two are constant (f(0) =
f(1) = 0 and f(0) = f(1) = 1) and two are balanced (f(0) = 0,f(1) = 1
and f(0) = 1,f(1) = 0) in the sense that output values 0 and 1 occur an
equal number of times. Now assume that a black box or an oracle is given
to us that can compute the value of the function f(x) for a given input
x. Our task is to determine whether the function computed by the oracle
is constant or balanced. Alternatively, the problem may be visualized as
follows. Consider a coin: if both sides of the coin have the same symbol
then it represents a constant function. If the symbols are diﬀerent then
the coin represents a balanced function. Our task is to check whether both
sides of the coin have the same symbol or not.
David Deutsch is one of the founders of quantum computing.
He was born in 1953 in Haﬁa, Israel. Presently he works at the
University of Oxford. In 1985 he introduced the idea of a uni-
versal quantum computer. In the same year he discovered the
ﬁrst quantum algorithm. His works provided physical mean-
ing to the Church-Turing hypothesis. He has also contributed
enormously to the ﬁeld of quantum circuits and quantum error
correction.
Photo credit: Lulie Tanett, photo courtesy: D. Deutsch.

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required