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.

Start Free Trial

No credit card required