Introduction to Quantum Computing

Dipan Ghosh

August 25, 2025

1 / 40
What is a Quantum Computer?

• Quantum Information and Computation is a subject which owes its

birth to the seminal work of Feynman and others in the 1970s. Before
this most development in computers was devoted to making the
integrated circuits smaller and smaller and increasing the speed of
computing.

• As the transistors become smaller and smaller and become close to

molecular scale, their behaviour is no longer governed by laws of
classical physics. The molecular wavefunctions would overlap leading
to significant overlap effects.

• Increasing number of bits would lead to substantial energy loss by

Landauer’s principle according which erasing one bit of information
costs kB T ln 2 amount of energy.

2 / 40
What is a Quantum Computer?

• Quantum computation provided a new way of doing computation and

also lead to the development of the exciting field of Quantum
Information with its application in the areas of

• Cryptography ( secure communication protocol with potential to

replace the currently used RSA cryptographic protocol)

• Finance (Quantum optimization algorithm with potential to be

used in trading)

• Urban transport

• Quantum gravity for blackhole simulation

3 / 40
What is a Quantum Computer?

• All physical systems are governed by laws of quantum mechanics.

Thus the functioning of our laptop or desktop is also governed by
quantum mechanics. But these cannot be called quantum computers.
Let us call our familiar computers as Classical Computers to
distinguish them from Quantum Computers.

• The working of electronic components in a classical computers (such

as those of diodes, transistors, gates etc) are all based on laws of
quantum mechanics but the logic they follow is classical.

• A quantum computer uses quantum mechanics to process its internal

states in a way that classical computers cannot.

• A Quantum Computer is not just a fast computer, though, it has the

potential to solve certain problems faster than classical computers.
4 / 40
What is a Quantum Computer?

• A Quantum computer exploits certain special quantum mechanical

phenomena, such as, superposition, entanglement etc. to transform
its internal states. Though the laws of QM are applicable to all
systems, they become more noticeable in systems in very small scale
such as atoms or molecules.

• These computers, however, are more difficult to control and are more
sensitive to errors because of a phenomenon called decoherence,
which is a process by which a quantum system loses its unique
behaviour and then it behaves more like a classical system. This
arises due to the interaction of our system of interest with the
environment (which has negligible effect with the classical computers
) which can be very harmful to a quantum computer.

5 / 40
REVIEW - Postulates of Quantum Mechanics
• Physical systems are represented by state vectors in an abstract
space called Hilbert Space, which is a normed linear space over a
field of complex numbers. Dirac called such states as kets.

• An arbitrary vector in this space is

N
X
|ψi = αn |ψn i
i=1

αn are complex numbers, |ψn i are basis vectors in the space.

• The time evolution of |ψi is given by Schrödinger equation

∂
i~ |ψi = H |ψi
∂t
where H is the operator corresponding to the classical Hamiltonian.
6 / 40
REVIEW - Postulates of Quantum Mechanics

• Outcome of measurement of a physical variable A is one of the

possible eigenvalues of the corresponding hermitian operator Â.

• Collapse of the wavefunction : An arbitrary wavefunction is a

superposition of states. In such a state a physical quantity that is
being measured does not have a well defined value. When a
measurement of a physical quantity is made, the wavefunction of the
system collapses from such a superposition to a state in which the
value of the physical quantity is precise. This state is an eigenstate of
the operator mentioned above.

7 / 40
What is a Quantum Computer

• All computers, classical or quantum, are based on laws of physics and

mathematical logic.

• The working of the electronic components, such as transistors and

gates, in a classical computer are based on principles of quantum
mechanics but the logic they follow is classical.

• Traditional computers are designed for serial computation. Classical

computers which do parallel computation exist but they are simply
usual computers with more than one CPU which can simultaneously
perform tasks which can be done simultaneously.

8 / 40
What is a Quantum Computer
• A classical transistor based computer stores information in bits (we
will call them cbits to distinguish them from quantum bits), which is
an abstraction of bistable physical systems which can exist in one of
the two possible states, 0 or 1. This is easy to implement by a switch
(on or off) or by a magnetic field which may be directed up or down.

• To perform computation, we should be able to (a) store information,

(b) change the state of the system which results in change the stored
information and (c) retrieve the changed information from the
physical system.The last function is done by a directed measurement.

• To perform meaningful computation, we need a fairly large number of

bits and ability to access and modify them fast. As the requirement
for larger number of bits grows, the systems become more and more
compact, in order to accommodate them in the limited space
available for a desktop or a small computer, the physical system used
to implement it becomes smaller and smaller, ultimately reaching the
9 / 40
Qubits
• Just as a classical computer uses bits to store information, a quantum
computer use Qubits to store information. Like cbits, a qubit can
also exists in a state 0 or 1. In addition, it can exist in any linear
superposition of 0 and 1.

• In reviewing postulates of quantum mechanics, we mentioned that

physical systems are represented by state vectors in Hilbert space. A
qubit |ψi is a vector in a two dimensional complex vector space. In
Dirac notation, we represent it by a ket
|ψi = α |0i + β |1i
where |0i and |1i is an orthonormal set of basis vectors called the
computational basis. The coefficients α and β are complex
numbers, subject to
| α |2 + | β |2 = 1
This state is known as a superposition of basis vectors.
10 / 40
Qubits

• If we measure such a superposition of states, we get |0i with a

probability | α |2 and the state |1i with a probability |√β |2 . For
3 1
instance, if we measure a qubit which is in the state |0i + |1i,
2 2
3
we get the state |0i with a probability and the state |1i with a
4
probability |1i 4.

• |0i and |1i are just one of the many possible choices for the basis
|0i + |1i
vectors. We could have equally well chosen |+i = √ and
2
|0i − |1i
|−i = √ to represent the basis for a qubit.
2

11 / 40
Bloch Sphere

• We may express the state |ψi using three real numbers θ, ϕ and γ, in
terms of which the state |ψi may be written as

θ θ
 
|ψi = e iγ cos |0i + sin |1i
2 2
θ θ
with α = e iγ cos and β = e iγ sin . The overall phase factor γ is
2 2
not observable. The above satisfy the normalization condition.
ẑ = |0i
|ψi
θ
ŷ
ϕ
x̂

−ẑ = |1i
12 / 40
Bloch Sphere

• In the figure, the point where x-axis meets the surface is given by
1
θ = 90◦ and ϕ = 0◦ . For this point α = cos(θ)/2 = √ = β. This
2
gives the state |+i.

• While a classical bit may be located only at the north or the south
pole, the qubit may be represented by a continuum of points on the
Bloch sphere.

13 / 40
Quantum Registers

• In a classical computer, we have an array of memory registers

containing bits, which in turn, contain information. In a quantum
computer, we have quantum memory registers consisting of several
qubits. If we consider an n− state system, our Hilbert space has n−
dimensions.

• When we measure the system, we will find it in exactly one state.

However, when the system is not measured, it can be in a
superposition of 2n possible states. In a matrix notation, we may
represent the state of the register
 
α1
α 
|ψi =  2 
 
. . . 
αn

14 / 40
Quantum Registers - Exponential memory content.
• We can store any number from 0 to 2n−1 in a quantum memory
register, as long as we have enough classical bits to represent that
number. The general state of an n− qubit register is represented by
n −1
2X
|ψi = αx |x i
x =0

where |x i is one of the basis states, such as |000i , |001i . . . etc. and
αx are complex numbers satisfying x | αx |2 = 1.
P

• For specifying content of a n− qubit register, we need 2n complex

numbers (each complex number requires 2 real numbers to specify).
This is exponential in n. A classical register only requires n bits.

• However, we cannot access all the information in the register at a

given time because the process of measurement would collapse the
state into one single state out of the superposition.
15 / 40
Entanglement - Spooky Action at a Distance

• Qubits in a quantum register may be entangled, meaning thereby that

the states may be correlated. For instance, a two qubit quantum state
1
may of of the form |ψi = √ [|00i + |11i]. In this state a
2
measurement of any of the qubits determines the state of both the
qubits.

• Measurement reveals only one of the possible states in the

superposition, which just yields n− bits of classical information.
Quantum algorithms are designed such that they can extract useful
and required information with a very high degree of probability.

• Quantum processes are reversible in nature. This requires that

quantum gates be reversible, unlike the classical gates, which other
than the NOT operation, are irreversible.

16 / 40
Principle of Computation : Deutsch-Church-Turing Thesis

• A foundational aspect of classical computation is the Church-Turing

thesis, which states that any computable function of natural numbers
can be calculated by a systematic mechanical procedure through a
Turing machine. This implies that all models of computation are
equivalent in power to a Turing machine.

• There is a corresponding proposition in quantum computing which

extends the above to quantum computation which is not rigorously
proved but it holds currently.

• The premise states that any computation that can be done by a

physical device can be efficiently performed by a quantum computer
with at most a polynomial overhead.

17 / 40
Principle of Computation
• In quantum computers, there are two types of registers (i) an input
register to represent a number x and (ii) an output rester to store the
result of computation of f (x ). The primary reason for having different
registers for input and output is because often f (x ) assigns the same
value to different inputs. In such a case, the computation cannot be
inverted.

• A computation involves taking in an input x and producing an output

f (x ). In a quantum computer, these operations are done by unitary
operators. If the input has n qubits and the output is of m qubits,
f (x ) : {0, 1}n → {0, 1}m
Though the actual computation involves use of many auxiliary
registers, we will represent the process of computation by an n− qubit
input register and an m− qubit output register. The process of
computation is represented by
U{|x in |0im } = |x in |f (x )im (1)
18 / 40
Principle of Computation
• The transformation is performed by a unitary operator

U[|x i |y i] → |x i |y ⊕ f (x )i

where ⊕ is a modulo 2 bitwise addition, which is equivalent to an

XOR operation, e.g. 1101 ⊕ 0111 = 1010.

• If y = 0 then
U[|x i |y i] → |x i |f (x )i

• The above is reversible because

UU[|x i |y i] = U[|x i |y ⊕ f (x )i]

= |x i |y ⊕ f (x ) ⊕ f (x )i = |x i |y i

because for any z, we have z ⊕ z = 0.

19 / 40
Principle of Computation
• Quantum Parallelism:
When an operation U is performed on an input register containing
superposition of 2n states, the computation of f (x ) gets done in a
single computational step and one gets f (x ) value corresponding to
all the input values, i.e.
!
X X
U |x i |0i → |x i |f (x )i (2)
x

which contains information about all values of f (x )..

This is different from what happens in a classical parallel computer
where the operations are done by partitioning the problem into
different parts whose computation may be performed independently of
one another. The result of such parallel computation by different
processors are then integrated to arrive at the final solution of the
problem. In quantum machines, parallelism is inherent and is like
having parallel computation in a serial machine.
20 / 40
Principle of Computation

• Collapse of wave function and the process of measurement:

After a computation of the function f (x ) has been made, one would
like to know the value of f (|x i) corresponding to a given |x i. In a
classical computer, we could simply read the values or print them.
The process of reading the value does not disturb the output register
in any way.
In a quantum computer, on the other hand, there is no apparent way
to do it, for, the process of measurement makes the system collapse
to one of the eigenkets of the observable that is being measured. As
the input state |x i is a linear combination of various states |ik i with
probability | ωk |2 , when a measurement is made, one gets the value
of f (|ik i) with the probability | ωk |2 . As there is no way of predicting
what particular state the state would collapse to as a consequence of
the measurement, the situation is no different from doing the
calculation in a classical computer with a random input.

21 / 40
Quantum Gates

• Once we have an input register populated, we need to process it so

that it can compute the desired function. This is done by a sequence
of gates such as NOT, OR, AND etc. In classical computation, a
single universal gate like NAND or NOR is sufficient to implement
any Boolean function.

• In quantum computing, situation is similar but with some changes

due to continuous nature of quantum operations. Here also a finite
set of universal gates is sufficient to approximate a unitary operation
to arbitrary precision.

• These gates are Hadamard, Phase (S), CNOT, T.

22 / 40
Single Qubit Gates

• Quantum circuits can be formed by a few single qubit gates and one
two qubit gates. We represent the input and the output qubits as
column vectors. A unitary operation acts on the input state |ψi to
yield output state |φi :
|φi = U |ψi

!
1
• The gates are all reversible in nature. Let us represent |0i = and
0
!
0
|1i = . A NOT gate which flips these two states is given by the
1
matrix !
0 1
X=
1 0

23 / 40
Single qubit gates
• A Hadamard gate acting on |0i or |1i creates a superposition of
states
1
H |0i = √ [|0i + |1i]
2
1
H |1i = √ [|0i − |1i]
2
!
1 1 1
This is represented by matrix H = √
2 1 −1

• Phase gates are one qubit gates that act to change the phase of a
qubit. Z − gate introduces a phase difference of
! π between the states
1 0
|0i and |1i and is represented by Z = . The action of this
0 −1
! !
α α
gate on a superposition is given by Z =
β −β
24 / 40
Quantum Gates
• S gate introduces a phase change of π/2 while T gate introduces a
phase change of π/4.

• CNOT GATE : It is a two qubit gate with a control bit and a target
bit. If the control bit is |0i, the target is left unchanged. However, if
the control bit is |1i, the target bit is flipped. The quantum circuit
for this gate is as follows.

control

target

• The matrix representation of the CNOT operator is as follows:

 
1 0 0 0
0 1 0 0
CNOT = 
 
0 0 0 1

25 / 40
Creating Entanglement

• The following circuit creates one of the four Bell states

• If we start with |00i, the Hadamard gate makes the first qubit to
|0i + |1i
become √
2
|0i + |1i
|00i = |0i ⊗ |0i → √ ⊗ |0i
2
|00i + |11i
→ √
2

26 / 40
Principle of Computation

• Example : Consider a 3 qubit quantum register. It can hold a linear

combination of 8 basis states. Starting with a state |000i, if we apply
apply Hadamard gates on each qubit, we get an equal linear position
of the 8 basis states,
1
|ψi = √ [|000i + |001i + |010i + |011i + |100i + |101i + |110i + |111i
8

• At this stage if we measure the qubits, we get only one of them,

randomly, with a probability of 1/8.

27 / 40
Parallelism
• Consider an equal superposition of 2 qubit basis states
1
|ψi = [|00i + |01i + |10i + |11i] as the input to calculate the
2
function f (x ) = x mod 2. The function returns 0 if the input is even
and 1 if the input is odd, i.e. f (00) = f (10) = 0 and
f (01) = f (11) = 1. A classical computer requires 4 computations.

• The following circuit computes the function in one step because of

parallelism. The output is
1
|φi = [|00, 0i + |01, 1i + |10, 0i + |11, 1i]
2
However, we can only extract one result by a single measurement.

x = |00i H |x i
f (x )
y = |0i Oracle |f (x ) + y i
28 / 40
Di Vincenzo Criteria
• In 2000 David Vincenzo enunciated a set of criteria for a physical
system to be a viable platform for quantum computing.

• A scalable physical physical system with well defined qubits

• Ability to initialize to a simple fiducial state such as |0i

• Long coherence compared to the gate operation time

• A universal set of quantum gates

• Qubit specific measurement capability

• To more criteria were added later : (a) Ability to convert a stationary

qubit to a flying qubit and (b) Ability to faithfully transmit flying
qubits
29 / 40
Experimental Quantum Computing

• Till about 2010, the workhorse of quantum computing was based on

Nuclear Magnetic Resonance (NMR). The method uses nuclear spin
states of molecules such as H-1, C-13, N-15 etc. Liquid samples of
molecules are placed in a strong magnetic field in which the spins are
either aligned or oppositely aligned creating |0i and |1i states.
Though the energy difference between these states is very small, the
thermal average of the states put the assembly in |0i state.

• When radio wave matching the frequency difference between |0i and
|1i is incident on it, it acts like a gate creating a superposition or a
spin flip. The method provided excellent control and has long
coherence time. However, the method was good for creating only
about 10 or 12 qubits. NMR computing is no longer used because of
development of much better platforms.

30 / 40
Ion Trap Quantum Computing

• Atoms like Be, Mg, Ca, Yb etc. are ionized and are trapped in a
region of space using electric fields. The preferred method of trapping
is called Paul Trap which creates a potential region with a minimum
at which the ion gets trapped. This is done by a combination of static
electric field and a radio frequency field.

31 / 40
Ion Trap Quantum Computing
• After ionization, such elements will show a hydrogen-like spectrum of
energy states, two of these states, viz. its ground state and the
excited state , will be singled out and identified with the abstract
states |0i and |1i. The transition from the ground state can be either
optical (visible, 380 to 790 nm) or in the hyperfine range (3 to 300
mm in GHz range. The hyperfine qubits have a longer life time
(about 10 min) compared to the visible ones (about 1 s). and are
therefore preferred.

• The energy states can be manipulated by laser pulses or sometimes by

microwave fields. The duration of the pulse and its phase determine
the rotation on the Bloch sphere. For instance a π pulse results in an
X gate while a π/2 pulse with appropriate phase can be used for
Hadamard gate. As the ions are isolated in vacuum, their interaction
with environment or among themselves is minimal which results in
long coherence time (∼ seconds). As of now ion trap based quantum
computers are stable for about 20 to 50 qubits with high fidelity.
32 / 40
Quantum Computing with photons

• Photons can encode information by their having different degrees of

freedom. For instance, one can use its two states of polarization
(horizontal or vertical) to represent the two states of the qubit. It is
possible to use different optical paths to represent different states.

• As photons have very little interaction with the surrounding, their

coherence time is practically infinite. It is easy to transmit them and
the computer can be used at room temperature. Gates are
implemented using optical elements such as beam splitters, polarizers
or phase shifters.

• A few qubits ( 10 to 20) have been demonstrated for logic gates and
small algorithm.

33 / 40
Computing using superconducting qubits

• Superconducting quantum computing uses electrical circuits made

from superconducting materials, which behaves like an atom with
quantized energy levels. The phenomenon of Josephson junction is
used for this purpose. Information can be stored in the ground state
or excited state of such an artificial atom.

• Single qubit gates are implemented by microwave pulses to rotate the

state on the Bloch sphere. The gate speed are fast (10 to 100 ns).
Coherence time is very small (milli seconds to micro seconds) and it
requires very low temperatures. The number of physical qubits can be
between 100 to 1000.

34 / 40
Spin based Quantum Computing

• A spin-based quantum computer is a type of quantum computer that

uses the intrinsic angular momentum, or spin, of electrons or other
particles to encode and process information. The two quantum states
of a qubit |0i and |1i are represented by the spin up and spin down
orientations of a particle in a magnetic field.

• Most spin-based quantum computers use quantum dots, which are

nanoscale semiconductor structures that can confine and isolate
individual electrons. Superposition and entanglement can be achieved
by applying magnetic field or microwave pulses. Spin is manipulated
by ESR using oscillating magnetic field.

35 / 40
Spin based Quantum Computing

• Using nuclear spins can give long coherence time, up to a few seconds
or even minutes. Gate speeds are very fast, between 10 ns to 100 ns.

• The number of qubits is small, typically about 5 to 7 qubits.

Maintaining coherence and precise control across many spins is harder
than by other methods. However, compatibility with CMOS
technology suggests potential for large scale, chip based fabrication.

36 / 40
Grover’s Search Algorithm
• Search algorithms are useful in locating an item in a database, which
may either be structured or unstructured. Searching for an element in
an unstructured database is like the proverbial searching for a “needle
in a haystack”.

• One can formulate the problem mathematically by defining a function

f (k) which has a value zero for all values of k, (1 ≤≤ N = 2n ) except
for one particular value of k = k0 for which f (k0 ) = 1. If the
database of N values are random, then, in order to locate the element
k = k0 , one has to search through the entire database, evaluate f (k)
for each k until such time that we locate a k for which f (k) = 1.
Thus a classical search requires O(N) number of queries.

• If the search has a unique solution,√Grover’s algorithm can locate the

item with a high probability in O( N) number of trials resulting in a
quadratic speeding up. The algorithm attains this by a selective
amplification of the amplitude of the state corresponding to the item
37 / 40
Grover’s Search Algorithm
• The quantum oracle calculates a function f for n qubit inputs and
returns 1 when the input matches a particular string w , called the
marked string, in all other cases it returns zero. Thus
f : {0, 1}⊗n → {0, 1} with the property
(
0 for x 6= w
fw (x ) = (3)
1 for x = w

|x i |x i

Uf

|y i |y ⊕ f (x )i

Figure: The Oracle

38 / 40
RSA and Shor’s Algorithm
• RSA crypto-system was developed in 1977 by Ron Rivest, Adi Shamir
and Leonard Adleman of the MIT. The crypto system uses a public
key encryption for securing and transmitting sensitive data over the
internet. The public key is linked to a private decryption key which is
only known to the person who receives the message. It also enables
one to authenticate the sender’s identity to the receiver. RSA uses
what is known as a trap-door function, f which is defined as a
function which has two characteristics. The function f is easy to
compute, i.e., it can be computed in polynomial time. However, the
inverse of the function f −1 cannot be computed easily from a
knowledge of f or vice versa. The name trapdoor function has its
origin in the fact that it is easy to fall through a trap door but is not
easy to climb back to where one dropped from.

• In RSA the trap-door function is multiplication of two large prime

numbers, which is obviously easy to compute. However, given the
product, there is no known algorithm which can achieve prime
39 / 40
Shor’s factorization Algorithm

• It is well known that prime factorisation, i.e., factorisation of a large

composite number to its prime factors is computationally a hard
problem requiring exponential time and memory. Shor’s factorisation
uses built in parallelism of a quantum computer to speed up this
process so that the task can be achieved to a high degree of
probability in a polynomial time. The execution of the algorithm
requires implementation of a fast Fourier transform to determine
period of a function using a quantum computer.

• However, this method so far has not met with a significant success as
of now. The largest number that has been factorized by a quantum
computer is a 48 bit number which has been factorized by a
superconductor based quantum computer, using an approximate
optimization problem which is different from Shor’s method.

40 / 40
THANK YOU

41 / 40