Chapter 4

Qubits

4.1 Lecture on Qubits and measurements

Now, any quantum system with two dimensional state space is called a qubit. Example would be an
atomic dipole with spin S = 1/2.

4.1.1 Classical description of an atomic dipole

Consider an atom with a fixed dipole moment µ0 . Assume that it is fixed in space and has only
rotational degrees of freedom. Here the state of the system is same as the orientation of this dipole
moment, which can be described by two angles, zenith angle ✓ and azimuthal angle . Thus the state
of the system is same as the dipole moment vector
2 3
sin ✓ cos
~ = µ0 4 sin ✓ sin 5 .
µ
cos ✓
Now a classical measurement does not affect the state of system. Consider an ensemble of atoms from
an oven. The state of the system (orientation of the dipole moment) is random such that each state is
equally likely. If we measure the z-component of the dipole moment, every value between µ0 to +µ0
is possible and the probability of getting an outcome µ is given by
s ✓ ◆2
2 µ
p (µ) = 1 ???????????.
µ0 µ0
After one measurement, the system is undisturbed. On successive measurement one gets the same
outcome with the same probabilities.

4.1.2 Quantum description of an atomic dipole

This part will be based on the chapter 3 of Principles of Quantum Computation and Information
by authors G. Benenti, G. Casati and G Strini.
The basic ideas covered would be:

1. Bloch Sphere Representation of a Qubit

2. The Ciruit Model of Computation: Classical and Quantum
3. Single Qubit Gates: Controlled gates, Universal Gates
4. Algorithms: Function Evaluation, Quantum Adder, Deutsch’s Algorithm, Quantum Search.
(And possibly Schor’s Algorithm)

23
CHAPTER 4. QUBITS 24

4.2 Bloch Sphere Representation of a Qubit

⇤ Qubit is a system whose state space is 2D Hilbert space C2 . Ex: Spins, Light polarization,
Superconducting islands etc.

⇤ B = {|0i , |1i} will be called as computational basis

⇤ Any state (a ray in C2 ) of qubit


↵
| i = ↵ |0i + |1i ⌘ (4.1)

where and |↵|2 + | |2 = 1. Let ↵ = r1 ei✓1 and = r2 ei✓2 , then


i✓1 r1
| i=e .
ei(✓2 ✓1 ) r2

Since the phase is unimportant and state is normalized, only two real parameters are needed to
describe it. Let (✓2 ✓1 ) mod(2⇡) = and r2 /r1 = tan 2✓ . Thus each state of the qubit can be
expressed as 
cos 2✓
| i= . (4.2)
e sin 2✓
i

And clearly the domain of is [0, 2⇡) and that of ✓ is [0, ⇡].

⇤ Note that a point, say P , on a unit-sphere (called Bloch Sphere) is uniquely determined by two
angles and has coordinates 2 3 2 3
x sin ✓ cos
P ⌘ 4 y 5 = 4 sin ✓ sin 5 . (4.3)
z cos ✓
Then it is easy to see that there is a bijection from rays in C2 to S2 a sphere in three dimensions,
that is 2 3
 ✓ sin ✓ cos
cos 2
| i= ! P = 4 sin ✓ sin 5 . (4.4)
ei sin 2✓
cos ✓
In other words, with every state we can assign a vector in 3D. Loosely speaking, point P denotes
the direction of | i. And commonly, the states are written as | (✓, )i.

1
Example 67. The state |0i = = | (0, 0)i is the north pole and |1i = | (⇡, 0)i is represnted by
0

↵ 1 p1
the south pole of the Bloch sphere. The state corresponding to the x-direction is ⇡
2 , 0 = ,
1 2

↵ 1
the state corrsponding to the negative x- direction is ⇡
2 , ⇡ = p1 . The the angles of the
1 2
 p
1/ 2
point on Bloch sphere in [1, 1, 0] direction are ✓ = ⇡/2 and = ⇡/4 then | (⇡/2, ⇡/4)i = .
(1 + i)/2
Exercise 68. Show that the state
2 r 3
1+z
6 2 7
| (✓, )i = 6
4 x + iy
7
5
p
2 (1 + z)

where x, y and z are the cartesian coordinates of point on the Bloch sphere that represents | i.
Exercise 69. Suppose P and P 0 are two diametrically opposite points. Show the states corresponding
to these points are orthogonal.
CHAPTER 4. QUBITS 25

⇤ What is special about the “direction” of the state?

Note that the measurement of the component of the spin of the atom along the direction n̂ is
given by the operator
n̂ · ~ = nx x + ny y + nz z . (4.5)
Now if the state is | (✓, )i, then the average components are
h | z| i = cos ✓ = z
h | x| i = sin ✓ cos =x
h | y| i = sin ✓ sin =y (4.6)
Thus the average value of the spin vector of the system represented by | (✓, )i is “classical”
value of the spin vector.
⇤ | (✓, )i is eigenvector of n̂ · ~ if n̂ = (sin ✓ cos , sin ✓ sin , cos ✓).
Note that
(n̂ · ~ ) | (✓, )i = | (✓, )i
Thus measurement along n̂ will always yield (with 100% surety) +1 as the outcome.
⇤ How to determine | i?
This amounts to determining ↵ and in eq 4.1, which is equivalent to determining corresponding
(✓, ) pair or, alternatively, x, y and z. This can be done by measuring the three components
of the ensemble of large number of systems with the given state and looking at the average.
Remember that any accuracy can be achieved by choosing large number of the systems in the
ensemble. That is the trade off!
Also note that if p0 is the probability that the outcome of z measurement results in +1 and p1
that of result 1, then
✓
p0 = |h0, i|2 = cos2
2
✓
p1 = |h1, i|2 = sin2
2
and
✓ ✓
z = p0 p1 = cos2sin2 = cos ✓
2 2
In case, only z measurements can be done, follow the procedure given below.
– Measure z component of N systems. Let N0 be number of systems with +1 as the outcome,
and N1 with 1. Then
N0 N1 N0 N1
z = cos ✓ = lim ⇡
N !1 N N

1 1
– Take N more systems. Perform U1 = p12 on | i and then measure z component.
1 1
Now
1
p0 = (1 + sin ✓ cos )
2
1
p1 = (1 sin ✓ cos )
2
Then
N0 N1
x = sin ✓ cos = p0 p1 ⇡
N

1 i
Exercise 70. Let the state | i be transformed by U2 = p12 . Then show that
i 1
N0 N1
y = sin ✓ sin = p1 p0 ⇡ .
N
Chapter 5

Lectures on Quantum Computation

5.1 Turing Machines

⇤ Description of a Turing Machine

⇤ Example Program

⇤ Computability and Church-Turing hypothesis

5.2 Classical Circuits

⇤ The basic alphabet is binary {0, 1}.

⇤ In a circuit model binary numbers are denoted by a states. Most commonly state is represented
by the electrical voltage at a point of a circuit.

⇤ Circuits consist of wires (that preserve the state) and gates (that change the state).
Example: (a) Simplest circuit is a wire. (b) wire and a not gate.

⇤ Logic Gate: A device that computes a function

f : {0, 1}k ! {0, 1}l

We will say this gate has k-bit input and l-bit output.

⇤ Represent action of a gate by a truth-table. For example, truth table of XOR gate is:

x1 x2 y1
0 0 0
0 1 1
1 0 1
1 1 0

⇤ NOT, OR(_), AND(^), XOR( ), NAND("), NOR(#), FANOUT (COPY) and CROSSOVER

⇤ Example of circuit using gates: Addition

– Half adder: Adds two bits with carry over. if a and b are to be added to sum bit s and
carry bit c, then

s = a b
c = a^b

26
CHAPTER 5. LECTURES ON QUANTUM COMPUTATION 27

The circuit is shown in the figure

– Full adder adds the two bits and a carry to give sum and carry. a and b are added with the
carry c to get sum s and carry c0 , then

s = (a b) c
0
c = (a ^ b) _ ((a b) ^ c) (5.1)

Exercise 71. Verify that the bits s and c0 defined in the eq 5.1 represent the sum and carry of three
bits. Draw a circuit that implements this logic.

⇤ Computation: A classical (deterministic) computer computes a function. Thus a function f :

{0, 1}m ! {0, 1}l is called a computation. It can be seen as l seperate functions fk : {0, 1}m !
{0, 1} where k = 1, . . . , l.

⇤ Universality: Any computation can computed by designing a circuit using elementary gates like
AND, OR, NOT and FANOUT.

– Constructive Proof (See Benenti):

Consider a function f : {0, 1}m ! {0, 1} with one bit output, we can easily extend this to l
bits. Let
S = {a 2 {0, 1}m | f (a) = 1} .
Now for each a in S construct a function fa (called minterm ) such that
(
1 when x = a
fa (x) =
0 else.

It is easy to see that

f (x) = fa1 (x) _ fa2 (x) _ · · ·
Now each minterm fa (x) can be constructed as follows: Let a = (a0 a1 · · · ). Now, for any
bit a, let ã = ā if a = 0 and is a if a = 1. Then

fa (x) = a˜0 ^ a˜1 ^ · · ·

– Inductive Proof (See Nielsen): It is easy to see that if m = 1, there are four possible function.
1. Identity: f (a) = a
2. Not: f (a) = ā
3. Zero: f (a) = 0 = a ^ ā
4. One: f (a) = 1 = a _ ā
To complete the induction, suppose that any function on m bits may be computed by
a circuit, and let f be a function on n + 1 bits. Define n-bit functions f0 and f1 by
f0 (x1 , ..., xn ) = f (0, x1 , ..., xn ) and f1 (x1 , ..., xn ) = f (1, x1 , ..., xn ). These are both n-bit
functions, so by the inductive hypothesis there are circuits to compute these functions. It
is now an easy matter to design a circuit which computes f . The circuit computes both f0
and f1 on the last n bits of the input. Then, depending on whether the first bit of the input
was a 0 or a 1 it outputs the appropriate answer. A circuit to do this is shown in Figure
below. This completes the induction.
CHAPTER 5. LECTURES ON QUANTUM COMPUTATION 28

⇤ FANOUT AND CROSSOVER Gates. These are implicitly assumed in the classical computer.
But not in quantum computer.

Exercise 72. Show that all gates can be constructed using only NAND and FANOUT gates.

5.3 Circuit Model for Quantum Computer

⇤ Simillar to wires and gates.

⇤ Registers/wires are now replaced by n-qubits. The basis has 2n states. The computational basis
is used.

⇤ Computation will involve three steps

– Preparation of n-qubit initial state

⇤ one of the basis states
– Manipulation of n-qubits
⇤ use gates to control or change the state.
– Measurement of output state.
⇤ not possible in single measurement.
⇤ Measurement is almost always probabilistic in nature.

5.4 Single Qubit Gates

⇤ Every unitary operator is a gate.

⇤ The most trivial gate is the identity gate I. That does not change the state of input qubit.

⇤ The Pauli operators are the next three operators: denoted by X = x, Y = y, and Z = z.

⇤ If the input state is one of the basis states then X behaves like a classical NOT gate. That is

X |0i = |1i
X |1i = |0i

But the input state is not restricted to the basis states.

⇤ Hadamard gate: 
1 1 1
H=p
2 1 1
CHAPTER 5. LECTURES ON QUANTUM COMPUTATION 29

The action on basis states is

1
H |0i = p (|0i + |1i) = |+i
2
1
H |1i = p (|0i |1i) = | i
2

⇤ The phase shift gate: 

1 0
Rz ( ) =
0 ei
Its action on the state
 
cos 2✓ cos 2✓
Rz ( ) | (✓, )i = Rz ( ) i = = | (✓, + )i
e sin 2✓ ei( + ) sin 2✓

If the input state and the output states are represented by points Pi and Po on the Bloch sphere,
Po can be obtained by rotating Pi about z-axis by angle . Thus the name Rz ( ) .

⇤ In general, a rotation operator about an axis n̂ by an angle is given by

✓ ◆
Rn̂ ( ) = exp i n̂ · ~ = I cos i (n̂ · ~ ) sin . (5.2)
2 2 2

⇤ Special cases are 

cos 2 i sin 2
Rx ( ) = I cos iX sin =
2 2 i sin 2 cos 2
and 
cos 2 sin 2
Ry ( ) = I cos iY sin =
2 2 sin 2 cos 2

Exercise 73. Prove that the action Eq 5.2 is to rotate the point on the bloch sphere.

Theorem 74. Claims: Every unitary operator is just a rotation operator upto an overall phase, that
is, given U , it is possible to find n̂, and ↵ such that

U = ei Rn̂ (✓) .

U11 U12
Proof. Let U = . Note that:
U21 U22

⇤ det U is unimodular, that is, it is equal to ei for some 2 [0, 2⇡).

⇤ Also, |Uij |  1 for all matrix elements.

⇤ |TrU |  1

⇤ And U22 = ei /2 U ⇤
11 and U21 = e i /2 U ⇤
21

Now compare the two sides,


i i ✓ ✓
U = e Rn̂ (✓) = e cos i (n̂ · ) sin
2 2
  ✓ ✓
U11 U12 cos 2 inz sin 2 i (nx iny ) sin 2✓
) = ei ✓
U21 U22 i (nx + iny ) sin 2 cos 2✓ + inz sin 2✓
CHAPTER 5. LECTURES ON QUANTUM COMPUTATION 30

Note that,

det U = ei2
✓
TrU = 2ei cos
2
✓
U22 U11 = 2iei nz sin
2
✓
U12 + U21 = 2iei nx sin
2
✓
U21 U12 = 2ei ny sin
2
This gives a way to compute all parameters:
1
= log (det U )
2i
✓ i ◆
1 e TrU
✓ = 2 cos
2
e i
nz = (U22 U11 ) ✓ 6= 0
2i sin(✓/2)
e i
nx = (U21 + U12 ) ✓ 6= 0
2i sin(✓/2)
e i
ny = (U21 U12 ) ✓ 6= 0
2 sin(✓/2)

Note that |det U | = 1 implies that 2 [0, ⇡). |TrU |  2 implies that ✓ 2 [0, 2⇡). And it is clear that
nx , ny and nz are real and n2x + n2y + n2z = 1

Theorem 75. From theory of rotations we know that it is possible to decompose each rotation into a
product of three rotation operators (Euler decomposition)

U = ei↵ Rz ( ) Ry ( ) Rz ( ) .

Exercise 76. Find n̂ and for H operator.

⇤ Use these rotation operators to simplify circuits.

Exercise 77. Show that the unitary operator moving the state parametrized on the Bloch sphere by
the angles (✓1 , 1 ) into the state (✓2 , 2 ) is given by
⇣⇡ ⌘ ⇣ ⇡ ⌘
Rz + 2 HRz (✓2 ✓1 ) HRz 1 .
2 2

5.5 Two Qubit Gates

⇤ With two qubits there are product states and entangles states. A general state is given by

| i = ↵ |00i + |01i + |10i + |11i .

It may not always be possible to write | i as product of two single qubit states. When, there
exist | 1 i and | 2 i such that
| i = | 1i ⌦ | 2i
then we say | i is a product state (unentangled), otherwise it is said to be entangled state.

⇤ We have already seen that the Bell states are entangled.

 CHAPTER 5. LECTURES ON QUANTUM COMPUTATION 31

⇤ It is easy perceive the entanglement. In general, six real parameters are needed to specify a
general two qubit state. Howerver for a product state, only four parameters are needed.
⇤ With two input qubits, it is simple to implement single qubit gates. For example U1 is a single
qubit gate acting on qubit and if U2 is a gate acting on qubit two then the combined gate
U = U1 ⌦ U2
acts independently on each qubit.
⇤ More interesting gates are the ones where the result depends on both qubits.

5.5.1 Controlled NOT Gate

⇤ Controlled NOT is a two-qubit gate with one of the qubits is called control qubit and the
other one is target qubit. If control qubit is in state |1i then the target qubit is “flipped” else it
is unaffected. The action can be written as
CNOT (|ci ⌦ |ti) = |ci ⌦ |c ti
when |ci and |ti are 1-qubit basis states, that is |0i or |1i. The symbol for the gate is
|ci • |ci
|ti |c ti

⇤ The matrix representation of the CNOT gate:

2 3
1 0 0 0
60 1 0 07
CNOT = 6
40
7
0 0 15
0 0 1 0

⇤ The CNOT gate generates entangled states if the control bit is not in one of the basis states.
Example 78. Note
CNOT |0i ⌦ (↵ |0i + |1i) = |0i ⌦ ( |1i + ↵ |0i)
CNOT |1i ⌦ (↵ |0i + |1i) = |1i ⌦ ( |0i + ↵ |1i)
Here the control bit is in the basis state but the target bit is in arbitrary state. And the output
is still unentangled state (product state). Now consider
CNOT (↵ |0i + |1i) ⌦ |0i = ↵ |0i ⌦ |0i + |1i ⌦ |1i .
But now, we get an entangled state in the output! (Not a product state)

⇤ Generalized CNOT gates. A CNOT gate with second qubit as control qubit can also be
constructed. The symbol for this gate is shown in the figure.
|ti |c ti
|ci • |ci

The matrix is of this is given by

2 3
1 0 0 0
60 0 0 17
CNOT = 6
40
7
0 1 05
0 1 0 0
A CNOT gate which flips the target if the control is in |0i state is shown the figure below:
|ci |ci
|ti |c̄ ti
 CHAPTER 5. LECTURES ON QUANTUM COMPUTATION 32

5.5.2 Simple Circuits with CNOT gates

In this section we will learn to analyze some simple circuits

Example 79. Here is simple example of two CNOT gates
|xi • •
|yi
0 1 2

This circuit can be analyzed in two ways. One is the matrix method. Clearly

2 = (CNOT) 1 = (CNOT) (CNOT) 0

Thus the net effect of the circuit will be

U = (CNOT) (CNOT)
2 32 3
1 0 0 0 1 0 0 0
60 1 0 07 60 1 0 07
= 6 76
40 0 0 15 40
7
0 0 15
0 0 1 0 0 0 1 0
= I4

We can also evaluate the effect of the circuit on specific inputs using bra and ket notations. That is,
if 0 = |10i, then

U |10i = (CNOT) (CNOT) |10i

= (CNOT) |11i
= |10i

Example 80. Consider the circuit shown in the figure.

• •
•

The net effect of this gate is

2 32 32 3
1 0 0 0 1 0 0 0 1 0 0 0
60 1 0 07 6 17 6 07
U = 6 7 60 0 0 7 60 1 0 7
40 0 0 1 40
5 0 1 0 40
5 0 0 15
0 0 1 0 0 1 0 0 0 0 1 0
2 3
1 0 0 0
60 0 1 07
= 6
40
7
1 0 05
0 0 0 1

Quite clearly,
U |xi ⌦ |yi = |yi ⌦ |xi
when x and y are basis states. This is an implementation of the CROSSOVER or SWAP gate.

⇤ In fact any single qubit gate can be controlled. A general form of this would be

I2⇥2 02⇥2
02⇥2 U

⇤ Construction of controlled U gate:

CHAPTER 5. LECTURES ON QUANTUM COMPUTATION 33

– Step 1: Euler Decomposition: U = ei Rz (↵) Ry (✓) Rz ( ) for some ↵, , ✓ and .

– Step 2: Show that U = ei AXBXC where ABC = I. One choice is

A = Rz (↵) Ry (✓/2)
✓ ◆
+↵
B = Ry ( ✓/2) Rz
2
✓ ◆
↵
C = Rz
2

– Then the circuit would be

Figure 5.1: Controlled U gate

5.6 Universal Gates

⇤ Toffoli Gate: It is shown below with its construction

Here, the 
1 0
V =
0 i

⇤ Toffoli gate can be used as a NAND gate in classical computer. Which means with the help of
Toffoli gate, all classical computations can be done.

⇤ C (k) U gate:
CHAPTER 5. LECTURES ON QUANTUM COMPUTATION 34

⇤ Now, every unitary operator U operating on 2n dimensional Hilbert space of n qubits can be
decomposed in terms of rotations of the axes alone
n 1 i
2Y Y
U= Vij
i=0 j=0

where Vij is a rotation of axis |ii to |ji. This means, if a circuit rotates any axis into another,
the proof of universality would be complete.
Chapter 6

Algorithms

6.1 Function Evaluations

6.2 Quantum Adder

6.3 Parallel Computation:

Consider a function f : {0, 1}n ! {0, 1}. This circuit can be implemented using CNOT gates. The
circuit uses n + 1 qubits with the first n qubits forming the input register and the (n + 1)th qubit for
the result/ouput. The input to the circuit is written as |xi |yi, where |xi is the state of the input
register and |yi, the initial state of the output. The unitary operator Uf for this circuit performs the
following action
Uf |xi |yi = |xi |y f (x)i |xi 2 B
where B is the computational basis. Thus, if we set y = 0, then we get
Uf |xi |0i = |xi |f (x)i |xi 2 B

But since Uf is a linear operator,

!
X X X
Uf ck |xi |0i = ck Uf (|xi |0i) = ck |xi |f (x)i .
x x x

Thus, the in the output state, we have linear combination of all inputs |xi and corresponding function
values |f (x)i in just one function call ! This is called as quantum parallelism. However, in this form,
it not much of a use, since one measurement still gives us only one outcome or one |xi |f (x)i pair. If
we want all function values, we need to run the circuit as many times.
Example 81. As an example, consider the following function resulting in AND of two bits. That is
Uf |x1 x2 i |yi = |x1 x2 i |y (x1 · x2 )i .

|xi |0i |x1 x2 i |0i Output

|0i |0i |00i |0i |00i |0i
|1i |0i |01i |0i |01i |0i
|2i |0i |10i |0i |10i |0i
|3i |0i |11i |0i |11i |1i
Then,
3
!
X
Uf |0i |0i = Uf (|0i |0i + |1i |0i + |2i |0i + |3i |0i)
x=0
= |0i |0i + |1i |0i + |2i |0i + |3i |1i .

35
 CHAPTER 6. ALGORITHMS 36

The circuit for function evaluation works as expected when input |xi is a basis state and result qubit
is initially |0i. Since our circuit is quantum circuit, we can now play with various other states, both
for input states and result qubit. For example, if we set y = 1, then we get
E
Uf |xi |1i = |xi |1 f (x)i = |xi f (x) |xi 2 B

where f (x) is complement of f (x).

Example 82. Consider the same function resulting in AND of two bits. That is
Uf |x1 x2 i |yi = |x1 x2 i |y (x1 x2 )i .
The following table shows output for various initial states of the result qubit.
output state when intially
|xi |x1 x2 i
|xi |yi = |xi |0i |xi |yi = |xi |1i |xi |yi = |xi p12 (|0i ± |1i)
|0i |00i |0i |1i p1 (|0i ± |1i)
2
|1i |01i |0i |1i p1 (|0i ± |1i)
2
|2i |10i |0i |1i p1 (|0i ± |1i)
2
|3i |11i |1i |0i ± p12 (|0i ± |1i)
The circuit will work as AND operator only if |xi is a basis state and |yi = |0i. It works as a NAND
if initially |yi = |1i. With | + i as initial state, it is unaffected by the ciruit.

Let | ±i = p1
2
(|0i ± |1i). Then,

Uf |xi | +i = |xi | +i

Uf |xi | i = ( 1)f (x) |xi | i = ei⇡f (x) |xi | i

The use of | i is very important since it takes the value f (x) out of the index of the state to the
amplitude of the state.
If the first qubit is one bit register, then
Uf |0i | i = ( 1)f (0) |0i | i
Uf |1i | i = ( 1)f (1) |1i | i

6.4 Deutsch’s Algorithm

This algorithm demonstrates the possibility of parallelism in quantum computations.

Definition 83. A boolean function f : {0, 1}n ! {0, 1} is called balanced if half of the elements from
the domain are mapped to 0 and remaining to 1.

Consider a quantum circuit that evaluates a function f : {0, 1} ! {0, 1}. This function is either
balanced function or constant function. The aim is to construct a circuit that decides whether this
circuit is balanced or constant. Note that one will need to run a classical circuit twice to answer this
question, that is, evaluate the function for both inputs. However, the quantum parallelism can be used
and in one single query, the question can be answered.
1 uint function ( uint x ) {
2 if ( x == 0 ) return 1;
3 else return 1;
4 }
5 int main () {
6 if (( function (0) + function (1) ) == 1 ) printf ( " Even Function \ n " ) ;
7 else printf ( " Constant Function \ n " )
8 }
Listing 6.1: Classical Deutsch Program
CHAPTER 6. ALGORITHMS 37

|0i H H
Uf
|1i H

Figure 6.1: Deutsch’s Quantum Circuit

Consider the circuit given below. Just before final H gate, the output will be

1 1
Uf p (|0i + |1i) p (|0i |1i)
2 2
1h ⇣ E⌘ ⇣ E⌘i
= |0i |f (0)i f (0) + |1i |f (1)i f (1)
2
Now, notice that
(
E (|0i |1i) = ( 1)f (x) (|0i |1i) f (x) = 0
|f (x)i f (x) = f (x)
(|1i |0i) = ( 1) (|0i |1i) f (x) = 1

Then

1 1 1h i
Uf p (|0i + |1i) p (|0i |1i) = ( 1)f (0) |0i (|0i |1i) + ( 1)f (1) |1i (|0i |1i)
2 2 2
1 ⇣ ⌘ 1
= p ( 1)f (0) |0i + ( 1)f (1) |1i p (|0i |1i)
2 2
Now apply H operation to the first bit. Then, the state of the first bit is
1⇣ ⌘ ⇣ ⌘
( 1)f (0) + ( 1)f (1) |0i + ( 1)f (0) ( 1)f (1) |0i |1i
2
Then the measurement of the first qubit answers the query. Clearly, if the function is constant the
first qubit is |0i else the state is |1i.

6.5 Deutsch-Jozsa Algorithm

Consider a quantum circuit that evaluates a function f : {0, 1}n ! {0, 1}. It is guaranteed that the
function is either balanced function or constant function. The aim is to construct a circuit that decides
whether this circuit is balanced or constant. Note that one will need to run a classical circuit at least
twice and at most n/2 + 1 times to answer this question.
The quantum circuit is shown below:

i
|00 · · · 0i / H ⌦n H ⌦n
Uf
|1i H

Figure 6.2: Deutsch-Jozsa Circuit

Consider the action of H gate on 1-qubit state |xi.

( 1
p (|0i + |1i) x = 0
H |xi = 2
p1 (|0i |1i) x = 1
2

1 ⇣ ⌘ 1
x·0 x·1 1 X
= p ( 1) |0i + ( 1) |1i = p ( 1)x·y |yi
2 2 y=0
CHAPTER 6. ALGORITHMS 38

Let x = (x0 x1 . . . xn 1) and y = (y0 y1 . . . yn 1 ). Then

H ⌦n |xi = (H |x0 i) (H |x1 i) · · ·
0 10 1
1 1
1 @X X
= n/2 ( 1)x0 ·y0 |y0 iA @ ( 1)x1 ·y1 |y1 iA · · ·
2 y =0 y =0
0 1
n 1
2X
1
= ( 1)x·y |yi
2n/2 y=0

Example 84. For a 3-qubit system

1
H ⌦3 |0i = p (|0i + |1i + |2i + |3i + |4i + |5i + |6i + |7i)
8
1
H ⌦3 |2i = p (|0i + |1i |2i |3i + |4i + |5i |6i |7i)
8
Note that |2i = |010i. The following table shows the values of 2 · x in our context:
|xi |0i |1i |2i |3i |4i |5i |6i |7i
Binary representation |000i |001i |010i |011i |100i |101i |110i |111i
2·x 0 0 1 1 0 0 1 1

After the application of the Uf , the output will be

2 3
2 1 n
1 X
Uf H ⌦n ⌦ H |xi |1i = Uf 4 n/2 ( 1)x·y |yi | i5
2 y=0
n 1
2X
1
= ( 1)x·y+f (y) |yi | i
2n/2 y=0

If |xi = |00 · · · i, then

n 1
2X
1
Uf H ⌦n
⌦ H |00 · · · i |1i = ( 1)f (y) |yi | i.
2n/2 y=0

Thus, the first n input qubits, after H ⌦n give us linear combination of all states with equal coefficient
of 1/2n/2 . After Uf , we get the same linear combination but those inputs for which f (y) = 1, aquire a
negative sign (a phase of ⇡).
Now, we apply the last H ⌦n to the first n qubits to obtain
n 1
2X
1
H ⌦n
⌦ I Uf H ⌦n
⌦ H |xi |1i = ( 1)x·y+f (y) H ⌦n |yi ((|0i |1i))
2(n+1)/2 y=0
n 1
2X n 1
2X
1 x·y+f (y)
= ( 1) ( 1)y.z |zi ((|0i |1i))
2n+1/2 y=0 z=0
0 1
n 1
2X n 1
2X
1
= @ ( 1)(x+z)·y+f (y) A |zi ((|0i |1i))
2n+1/2 z=0 y=0

Now, if |xi = |00 · · · i then the coefficient of |zi = |00 · · · i is

0 1 (
2n 1
1 @X 1 f (y) is constant
n
( 1)f (y) A =
2
y=0
0 f (y) is balanced

Thus, upon measurement of n qubits, we can determine if f is constant or balanced.

 CHAPTER 6. ALGORITHMS 39

6.6 Quantum Search: Grover’s Algorithm

⇤ Problem Statement: To search an item in an unstructured database.

⇤ Application example: Phone directories are sorted on names (possibly after geographic data like
city etc.). Thus, finding the phone number given a person is very quick. The problem of finding
the name for a given phone number is very hard since the directory is not sorted (unstructured)
on phone numbers.

⇤ To make the problem more definitive, assume that we have and indexed list of N items (not
sorted though). And we are trying to find an item which is has index x0 . Define a marking
function (also called oracle 1 function) f as
(
1 x = x0
f (x) =
0 x 6= x0 .

The meaning of search here is to make calls to f with different arguments till it returns 1.

⇤ Clasical algorithm is brute force and will have to make O(N ) queries for an item search. Look
at the classical algorithm given below.

1
2 uint db [10] = { 4 , 3 ,2 ,1 ,0 ,9 ,8 ,7 ,6 ,5};
3
4 uint oracle ( uint index , uint x ) {
5 if ( db [ index ] == x ) return 1;
6 else return 0;
7 }
8
9 int main () {
10 uint x = 8;
11 uint N = 10;
12 for ( i = 0; i < N ; i ++ ) if ( oracle (i , x ) == 1 ) break ;
13 if ( i == N ) printf ( " Item not found \ n " ) ;
14 else printf ( " Item found after % d function calls \ n " , i +1) ;
15 }
Listing 6.2: Classical Search in Random Array

6.6.1 Quantum Search: 4 Items

D Operator
|0i H H X • X H

|0i H O H X H H X H

|1i H

Figure 6.3: Grover’s Quantum Search Algorithm for N = 4.

⇤ The circuit is shown in the diagram above. Let us begin by letting x0 = (10)b .
1
A person giving wise or authoritative decisions or opinions
CHAPTER 6. ALGORITHMS 40

⇤ After the application of the oracle the state becomes

1 X
| 2 i = n/2 ( 1)f (x) |xi | i
2 x
1
= (|00i + |01i |10i + |11i) | i
2
⇤ In general, we will get a linear combination of all states with coefficient +1 except exactly one
state, |x0 i with coefficient 1.
⇤ Ignoring the ancillary qubit, it is easy to see that the operator
0 1
1 1 1 1
1B 1 1 1 1C
D = ( I + 2 |++i h++|) = B @
C
2 1 1 1 1A
1 1 1 1
isolates the state |x0 i. That is
0 1 0 1 0 1
1 1 1 1 1 0
1B 1 1 1 1CC1B
B 1 C B0C
C B
D | 2i = B = C = |x0 i .
2@ 1 1 1 1 A 2@ 1A @1A
1 1 1 1 1 0
. Note that the same operator will work for any |x0 i.
⇤ To Implement D,
– D = ( I + 2 |++i h++|) = H ⌦2 ( I + 2 |00i h00|) H ⌦2 . And
0 1 0 10 10 1
1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1
B0 1 0 C B
0C B0 0 1 0C B0 C B 1 0 C B
0 C B0 0 1 0C
(I 2 |00i h00|) = B
@0 0 1 = C
0A @0 1 0 0A @0 0 1 0 A @0 1 0 0A
0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0
= X ⌦2 CMINUSX ⌦2 = X ⌦2 (I ⌦ H)CNOT(I ⌦ H)X ⌦2

6.6.2 Quantum Search: N items

⇤ The same idea does not work as is for N > 4 as is. That is, isolating x0 in with just one function
call is not possible.
⇤ Define an operator called Grover operator G = DO where
D = H ⌦n ( I + 2 |0i h0|) H ⌦n
X
= (I 2 |Si hS|) . |Si = |yi .
y

⇤ And if Uf is the unitary operator corresponding to oracle function f , then

(x,x0 )
Uf |xi | i = ( 1) |xi | i
= (I 2 |x0 i hx0 |) |xi | i
Let O be the operator on the input register such that
(x,x0 )
O |xi = ( 1) |xi
= (I 2 |x0 i hx0 |) |xi .
That is
O=I 2 |x0 i hx0 | .
Remember, restriction of Uf is O only when (n + 1)th qubit is in state | i
CHAPTER 6. ALGORITHMS 41

⇤ These two operators are a kind of mirror operation in the Hilbert space. In N dimensional
Hilbert space, the mirror operation changes the sign of only one coordinate keeping all other co-
ordinates unaffected. This is same as reflction in (N 1) dimensional hyperplane perpendicular
the corresponding axis.
⇤ Now, consider the plane containing |Si and |x0 i

⇤ From the diagram it is clear that

↵ under operation G, at state is rotated towards |x0 i by angle 2✓
(the angle between |Si and x0 which is given by
?

1
sin ✓ = hxo , Si = p
N
p
If N is large then ✓ ⇡ 1/ N
⇤ Thus, if we start with | 0i = |Si and iterate using Grover operator, that is

| ki = Gk | 0i .
↵
The angle between x0 ? and | ki
✓k = (2k + 1) ✓.

⇤ Since

hx0 , ki = sin ✓k
⇡1 if ✓k = ⇡/2

⇤ for large N , ✓ ⇡ p1
N
and thus after

1 ⇣⇡ p ⌘
k= N 1
2 2
we get k ⇡ x0 .

6.7 Discrete Fourier Transform

6.7.1 Classical DFT

Definition 85. The DFT of a N -vector (ntuplet), x = {x0 , . . . , xN 1} of complex numbers is defined
as a n-vector y = {y0 , . . . , yN 1 } where
N 1 ✓ ◆ N 1
1 X k 1 X kj
yk = p exp 2⇡i j xj = p ! xj (6.1)
N j=0 N N j=0

where ! = exp 2⇡i

N .
CHAPTER 6. ALGORITHMS 42

⇤ ! N = 1. Thus ! kj = ! kjModN .

⇤ Matrix of DFT for N = 8.

0 1 0 10 1
y0 1 1 1 1 1 1 1 1 x0
By 1 C B 1 ! !2 !3 !4 !5 !6 !7 C Bx 1 C
B C B CB C
By 2 C B 1 !2 !4 !6 1 !2 !4 !6 C Bx 2 C
B C B CB C
By 3 C 1 B 3 !6 !4 !7 !2 !5 C Bx 3 C
B C= p B 1 ! ! CB C
By 4 C B
NB 1 !
4 1 !4 1 !4 1 !4 C Bx 4 C
B C CB C
By 5 C B 1 !5 !2 !7 !4 ! !6 !3 C Bx 5 C
B C B CB C
@y 6 A @ 1 !6 !4 !2 1 !6 !4 !2 A @x 6 A
y7 1 !7 !6 !5 !4 !3 !2 ! x7
p
where ! = exp (i⇡/4) = (1 + i)/ 2.

⇤ In general DFT matrix F is given by

Fjk = ! (j 1)(k 1)
.

Remember the matrix rows/columns are indexed from 1 to N . This matrix is symmetric and
unitary.
⇣ ⌘ X 1 X l(k
F †F = Fjl† Flk = ! j)
jk N
l l
(
1 k=j
=
6 j
0 k=

⇤ Algorithm based on the equation (6.1) is ⇥ N 2 .

⇤ If, N = 2r , an algorithm called FFT is ⇥ (N r) or ⇥ (N log N ). FFT is is based on the following

example.

Example 86. For N = 22 = 4, then ! = i.

0 1 0 10 1
y0 1 1 1 1 x0
By1 C 1 B 1 i 1 i C Bx 1 C
B C= B CB C
@y2 A 2 @ 1 1 1 1 A @x 2 A
y3 1 i 1 i x3

1 1
y0 = (x0 + x2 ) + (x1 + x3 )
2 2
1 1
y1 = (x0 x2 ) + i (x1 x3 )
2 2
1 1
y2 = (x0 + x2 ) (x1 + x3 )
2 2
1 1
y1 = (x0 x2 ) i (x1 x3 )
2 2
This idea of grouping can be used to reduce the number of operations.
CHAPTER 6. ALGORITHMS 43

6.7.2 Quantum DFT

⇤ Let H be state space of a n-qubits quantum system. dim (H) = 2n = N .

⇤ The standard computational basis vectors are denoted by |ji where j = 1, . . . , N .

Definition 87. The DFT operator UF on H is defined as

N 1 ✓ ◆ N 1
1 X k 1 X jk
Uf |ji = p exp 2⇡i j |ki = p ! |ki j = 1, . . . , N (6.2)
N k=0 N N k=0

where ! = exp 2⇡i

N .

⇤ Note that
0 1
X N 1 N
X1 ✓ ◆
1 X k
Uf @ xj |jiA = p xj exp 2⇡i j |ki
N j=0 N
j k=0
2 3
N
X1 NX1 ✓ ◆ N
X1
4p1 k
= xj exp 2⇡i j 5 |ki = yk |ki
N N
k=0 j=0 k=0

where
N 1 ✓ ◆
1 X k
yk = p exp 2⇡i j xj .
N j=0 N

Thus, the matrix of the operator Uf acting on the vector of coefficients {xj } gives us the DFT
of the {xj }.

⇤ Now, remember that if 0  j < N = 2n then j is a n bit number. Let thePbinary representation
of j = (j1 j2 . . . jn ) where j1 is the msb. Then j = j1 2n 1 + · · · + jn 20 = nk=1 2n k jk . Also, let
us define fractional binary numbers as
n
X
k
0.j1 j2 . . . jn = jk 2 .
k=1
CHAPTER 6. ALGORITHMS 44

⇤ Now,
N 1 ✓ ◆
1 X k
Uf |ji = p exp 2⇡i j |ki
N k=0 N
1 1
!
1 X X j X n l
=p ··· exp 2⇡i n kl 2 |k1 i ⌦ · · · ⌦ |kn i
N k =0 2
1 kn =0 l
0 1 0 1
1 ✓ ◆ 1 ✓ ◆
1 @X j X j
=p exp 2⇡i 1 k1 |k1 iA ⌦ · · · ⌦ @ exp 2⇡i n kn |kn iA
N k =0 2 2
1 kn =0
✓ ◆n ✓ ✓ ◆ ◆ ✓ ✓ ◆ ◆
1 j j
= p |0i + exp 2⇡i 1 |1i ⌦ · · · ⌦ |0i + exp 2⇡i n |1i
2 2 2

⇤ Now, look at the nth qubit

✓ ✓ ◆ ◆ ✓ ✓ ◆ ◆
j 1
|0i + exp 2⇡i n |1i = |0i + exp 2⇡i n (j1 j2 · · · jn ) |1i
2 2
= (|0i + exp (2⇡i (0.j1 j2 · · · jn )) |1i)
 
1 0 1
=
0 exp (2⇡i (0.j1 · · · jn )) 1
  
1 0 1 0 1
= n ···
0 exp (2⇡ijn /2 ) 0 exp (2⇡ij1 /2) 1
 jn  j2  
1 0 1 0 1 0 1
= ···
0 exp (2⇡i/2n ) 0 exp 2⇡i/22 0 exp (2⇡ij1 /2) 1
| {z }
H|j1 i
jn j2
= (Rn ) · · · (R2 ) H |j1 i

Here 
1 0
Rk = 2⇡i/2 k .
0 e

Now, look at the (n 1)th qubit

✓ ✓ ◆ ◆ ✓ ✓ ◆ ◆
j 1
|0i + exp 2⇡i n 1 |1i = |0i + exp 2⇡i n 1 (j1 j2 · · · jn ) |1i
2 2
= (|0i + exp (2⇡i (j1 .j2 · · · jn )) |1i)
 
1 0 1
=
0 exp (2⇡i (0.j2 · · · jn )) 1
  
1 0 1 0 1
= ···
0 exp 2⇡ijn /2n 1 0 exp (2⇡ij2 /2) 1
jn
= (Rn 1) · · · (R2 )j3 H |j2 i

⇤ Finally,
✓ ◆n
1
Uf |ji = p (|0i + exp (2⇡i [Link] ) |1i) ⌦ · · · ⌦ (|0i + exp (2⇡i 0.j1 j2 . . . jn ) |1i)
2

⇤ Then the circuit will be

CHAPTER 6. ALGORITHMS 45

If we index the qubits from top to bottom, then the output is bits need to be swapped. The
swap part is not shown in the circuit above.
⇣ ⌘
2
⇤ The number of gates required are of the order of n . Thus, this algorithm is ⇥ n = ⇥ (log N ) .
2 2

Remember FFT algorithm was ⇥ (N log N ).

⇤ QFT to compute actual FT of arbitrary input is not efficient. Bottlenecks are in initial and final
stages.
P
– Preparing initial state input = j xj |ji. Do not know how to prepare this state efficiently.
All this while, we were talking about classical input which is just the basis state.
P
– Measuring the final state output = j yj |ji. This is inefficient.

6.7.3 Phase Estimation

⇤ Unitary operators have unimodular eigenvalues.

Phase Estimation Statement Let |ui be eigenstate of a unitary operator U with eigenvalue ei ,
that is,
U |ui = e2⇡i |ui 0  < 1.
Given |ui we want to esitmate to n bits.

The circuit is shown below:

CHAPTER 6. ALGORITHMS 46

To prove, consider the j th bit of the first register from top:

⇣ t j
⌘ 1 ⇣ t j
⌘
C U2 H |0i |ui = p C U 2 (|0i + |1i) |ui
2
1 ⇣ t j
⌘
= p |0i + e2⇡i 2 |1i |ui
2
0 1
1
X
1
=p @ exp 2⇡i kj 2t j |k1 iA |ui
2 k =0
j

Thus, leaving the second register out (which remains unaffected), the final state of the first register is
✓ ◆t
1
| i= p |0i + exp 2⇡i 2t 1 |1i ⌦ · · · ⌦ |0i + exp 2⇡i 20 |1i
2
0 1 0 1
✓ ◆ 1 1
1 t@X X
= p exp 2⇡i k1 2t 1 |k1 iA ⌦ · · · ⌦ @ exp 2⇡i kt 20 |kt iA
2 k1 =0 kt =0
0 1
✓ ◆t 2X t 1
1 @
= p exp (2⇡i k) |kiA
2 k=0

Now take an inverse QFT of this state

✓ ◆ 2t 1
1 tX
Uf† | i= p exp (2⇡i k) Uf† |ki
2 k=0
✓ ◆t 2X t 1 2Xt 1 ✓ ◆
1 kl
= exp (2⇡i k) exp 2⇡i t |li
2 2
k=0 l=0
2 3
t 1
2X ✓ ◆t 2Xt 1 ✓ ✓ ◆◆ t 1
2X
4 1 l 5 |li =
= exp 2⇡i k cl |li
2 2t
l=0 k=0 l=0

where
✓ ◆t 2X
t 1 ✓ ✓ ◆◆
1 l
cl = exp 2⇡i k
2 2t
k=0
✓ ◆t 2Xt 1 ✓ ✓ ◆◆ k
1 l
= exp 2⇡i
2 2t
k=0
✓ ◆t
1 1 exp 2⇡i 2t l
= l
2 1 exp 2⇡i 2t

Since < 1, we can write the binary representation of = 0. 1 2... t t+1 . . ..

Case 1: Suppose that is a t-bits long (

= 0 if j > t). Then 2t is an integer between 0 and
j
2t 1. And (
1 l = 2t
cl =
0 otherwise
↵
This means that the final state of the first register is 2t ! Measurement of the first register
directly gives the value of the phase.
CHAPTER 6. ALGORITHMS 47

Case 2: Suppose that has more than t bits. Let a be the nearest integer to 2t . Let = a/2t + .
Then, = ±0. 00 . . . 0} t+2 . . . = 2 (t+1) 0. t+2 . . . < 2 (t+1)2 . That is = a/2t + Then,
| {z
(t+1)

✓ ◆t
1 1 exp (2⇡i (a l)) exp 2⇡i 2t
cl = .
2 1 exp (2⇡i (a l) /2t ) exp 2⇡i

Thus,
✓ ◆t
1 1 exp 2⇡i 2t
ca =
2 1 exp 2⇡i
✓ ◆2t 2
1 1 exp 2⇡i 2t
|ca |2 =
2 |1 exp 2⇡i |2
2 2 2
Now, the numerator 1 exp 2⇡i 2t = 2 sin ⇡ 2t 16 2t and the denominator |1 exp 2⇡i |2 
4⇡ 2 | |2 3 . Thus,
4
|ca |2
⇡ 0.4052
⇡2
Thus, upon measurement chances of hitting a during measurement is very high. One can lower
the expectation and settle for less number of bits to increase the probability of the hit.

6.7.4 Order Finding

Definition 88. For positive integers x and N , x < N , with no common factors, the order of x modulo
N is defined to be the least positive integer, r, such that xr = 1( mod N ).

⇤ Let L be the number of bits needed to represent N , that is 0 < N  2L . x is a given number
such that gcd (x, N ) = 1 and order of x modulo N is r.

⇤ Consider an operator U (for a given x)such that

(
|xy mod N i y < N
U |yi =
|yi N  y  2L 1

⇤ Note that ( ↵
k xk y mod N y<N
U |yi =
|yi N  y  2L 1

⇤ Also note that for 0  s  r 1,

1 X
r 1 E
2⇡isk/r
|us i = p e xk mod N
r
k=0

is an eigenstate U with eigenvalue e2⇡is/r .

Example 89. Let N = 15 and x = 7. The order of 7 is r = 4 modulo 15. We need a Hilbert space
that is at least 15-dimensional. Let us use 4 qubits which gives us a space which is 16-dimensional.
Then, the action of U on the basis states is given in the table below.

|yi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|7yMod15i 0 7 14 6 13 5 12 4 11 3 10 2 9 1 8 15
2
Because of rounding the bit t+1 will always be zero.
3
For |x|  1/2, we have 2 |x|  |sin ⇡x|  ⇡ |x|
CHAPTER 6. ALGORITHMS 48

It is easy to see that the subspace W = span {|1i , |7i , |4i , |13i} is invariant under U . Restriction of U
on W is given by 0 1
0 0 0 1
B1 0 0 0C
B C
@0 1 0 0A
0 0 1 0
The eigenvalues and eigenvectors are listed below:

s exp (2⇡is/r) |us i

1
0 1 2 (|1i + |7i + |4i + |13i)
1
1 i 2 (|1i i |7i |4i + i |13i)
1
2 1 2 (|1i |7i + |4i |13i)
1
3 i 2 (|1i + i |7i |4i i |13i)

⇤ Now,
!
r 1
X r 1 r 1
1 X X 2⇡isk/r E
|us i = p e xk mod N
s=0
r
k=0 s=0
(p
r |1i k = 0
=
0 k 6= 0

P
⇤ In phase estimation circuit, at input we apply |1i, which is same as p1r rs=01 |us i. In the output
P
we will get p1r rs=01 |s/ri. Upon measurement, we will get one of the fractions s/r.

⇤ When s/r 6= 0, we can deduce r by an algorithm called continued fractions algorithm.

6.8 Prime Factorization: Shor’s Algorithm

Theorem 90. Suppose N is an L bit composite number, and x is a non-trivial solution to the equation
x2 = 1( mod N ) in the range 1  x  N, that is, neither x = 1( mod N ) nor x = N 1 = 1(
mod N ). Then at least one of gcd(x 1, N ) and gcd(x + 1, N ) is a non-trivial factor of N that can be
computed using O(L3 ) operations.

Algorithm 91. Reduction of factoring problem to order-finding problem:

1. If N is even, return the factor 2.

2. Determine whether N = ab for integers a 1 and b 2, and if so return the factor a (classical
algorithm).

3. Randomly choose x in the range 1 to N 1. If gcd(x, N ) > 1 then return the factor gcd(x, N ).
(gcd: classical algorithm)

4. Use the order-finding subroutine to find the order r of x modulo N .(quantum algorithm)

5. If r is even and xr/2 = 1( mod N ) then compute gcd(xr/2 1, N ) and gcd(xr/2 + 1, N ),

and test to see if one of these is a non-trivial factor, returning that factor if so. Otherwise, the
algorithm fails.