Introduction to Quantum Algorithms for beginers

A quantum algorithm is a step-by-step procedure for a quantum computer to solve problems using qubits, which can exist in superposition (0 and 1 simultaneously), become entangled, and use interference, allowing faster, more efficient solutions than classical computers.

1. 10/09/2025 Anandaraman, NISER Bhubaneswar 1
Introduction to Quantum Algorithms

2. 10/09/2025 Anandaraman, NISER Bhubaneswar 2
Motivation
Why quantum algorithms?
Classical computers → bottlenecks with exponential problems
Quantum computers → exploit superposition, entanglement, and interference
Famous quote: “Quantum computers won’t just be faster—they’ll be different.”

3. 10/09/2025 Anandaraman, NISER Bhubaneswar 3
Computational Basis
Computational basis refers to a specific set of basis states used to represent the state of a
qubit.
Classical Bit: Two states (0 or 1)
Qubit: Two states (|0 and |1 ), but can also be in a superposition of both simultaneously.
⟩ ⟩
In the computational basis, a qubit can be in either:
|0 (ket-zero): Represented as "off" or 0, similar to a classical bit.
⟩
|1 (ket-one): Represented as "on" or 1, again similar to a classical bit.
⟩

4. 10/09/2025 Anandaraman, NISER Bhubaneswar 4
Superposition
Unlike a classical bit, a qubit can be in both states at the same time.
It's like the light switch being both on and off simultaneously. We call this state a
superposition.
A qubit in superposition is represented by a combination of |0 and |1 , with complex
⟩ ⟩
numbers indicating the probability of finding it in either state when measured. It's written as:
|ψ = α |0 + β |1
⟩ ⟩ ⟩
where α and β are complex numbers and their squares add up to 1 (|α|^2 + |β|^2 = 1).
The modulus of a complex number z = x + iy, denoted by |z|, is given by the formula |z| =
√(x2 + y2), where x is the real part and y is the imaginary part of the complex number z.

5. 10/09/2025 Anandaraman, NISER Bhubaneswar 5
Review: Matrix Multiplication

6. 10/09/2025 Anandaraman, NISER Bhubaneswar 6
What are the four operations on one bit?
1. Reversible means given the operation and output value, you can find the input value
For Ax=b, given b and A, you can uniquely find x.
2. Operations which permute are reversible; operations which erase & overwrite are not.
(Identity and Negation are reversible, constant-0 and constant-1 are not reversible)
3. Quantum computers use only reversible opetations.
4. Reversible gate reduces power dissipation.
5. All quantum operators are their own inverses.

7. 10/09/2025 Anandaraman, NISER Bhubaneswar 7
Review: Tensor product of vectors

8. 10/09/2025 Anandaraman, NISER Bhubaneswar 8
Representing multiple qbits

9. 10/09/2025 Anandaraman, NISER Bhubaneswar 9
Quantum logic gates
Quantum logic gates are represented by unitary matrices.
computational basis of the two-level qubit system represented with vectors as follows;
I, X and H Gates
Identity (I) Gate, NOT (X) Gate, Hadamard (H) Gate

10. 10/09/2025 Anandaraman, NISER Bhubaneswar 10
Identity gate, X gate and Hadamard gate
Identity gate doesn't affect any qubit state, and thus it can be same as buffer in classical
circuits.
NOT or X gate inverts the state of the qubit i.e., |0>changes to |1> and |1>changes to |0>.
Transforms a qubit into superposition of two states

11. 10/09/2025 Anandaraman, NISER Bhubaneswar 11
CNOT, CCNOT and CSWAP Gates
CNOT Gate (Controlled-NOT Gate): Two-qubit gate with one control and one target qubit.
If the control qubit is |1 , it applies a NOT operation on the target qubit; otherwise, it leaves the target
⟩
qubit unchanged. This gate is essential for creating entanglement and implementing
quantum circuits.
Toffoli Gate (CCNOT Gate): Three-qubit gate with two control and one target qubit.
If both control qubits are |1 , it applies a NOT operation on the target qubit;
⟩
otherwise, it leaves the target qubit unchanged. The Toffoli gate
is also known as the “controlled-controlled-NOT” gate.
Swap Gate: The swap gate exchanges the states of two qubits. It has applications in
various quantum algorithms, particularly for rearranging qubit states during computation.
CSWAP Gate: Controlled SWAP gate is abbreviated as CSWAP as it swaps the values of B
and C at the output when A = 1

12. 10/09/2025 Anandaraman, NISER Bhubaneswar 12

13. 10/09/2025 Anandaraman, NISER Bhubaneswar 13
Quantum gates
CNOT gate is also called as Feynman gate.
CCNOT gate is also called as Toffoli gate.
CSWAP gate is also called as Fredkin gate.
As far as the number of outputs are concerned, they are same as inputs due to reversibility
(Reversible unitary operation)
Reversible gate reduces power dissipation
Identity gate doesn't affect any qubit state, and thus it can be same as buffer in classical
circuits.
Hadamard or H Gate transforms a qubit into superposition of two states from a definite
computational basis state.

14. 10/09/2025 Anandaraman, NISER Bhubaneswar 14
Reversibility & Unitarity in Quantum Computing
1. Quantum states are vectors in a complex Hilbert space.
2. Quantum gates (operations) are represented by unitary matrices U (where U†U=I).
3. Why unitary?
Ensures reversibility (no information loss).
Preserves probability (normalization) of the quantum state.

15. 10/09/2025 Anandaraman, NISER Bhubaneswar 15
Measurement ≠ Gate
1. Measurement is not unitary → it is an irreversible, probabilistic process.
2. Mathematically described by projection operators:
For 1 qubit in computational basis:
M0= 0 0 , M
∣ ⟩⟨ ∣
1= 1 1
∣ ⟩⟨ ∣
These project the quantum state onto the basis states 0 or 1 .
∣ ⟩ ∣ ⟩
3. After measurement, the quantum state collapses to the observed eigenstate.
4. Example:
State: ψ =α 0 +β 1
∣ ⟩ ∣ ⟩ ∣ ⟩
Measure → outcome 0 with probability α
∣ ∣
2
, outcome 1 with probability β
∣ ∣
2
.

16. 10/09/2025 Anandaraman, NISER Bhubaneswar 16
Projection operator

17. 10/09/2025 Anandaraman, NISER Bhubaneswar 17
Concepts used
Image: www.youtube.com/@pspace9458

18. 10/09/2025 Anandaraman, NISER Bhubaneswar 18
Deutsch’s Problem
First quantum algorithm (1985)
Goal: Determine if a function is constant or balanced
The Deutsch problem addresses how to determine the behavior of a complicated Boolean
function with simple inputs and outputs.
Classically:
Need 2 evaluations → f(0) and f(1)
Quantumly (QC):
Can be solved in 1 computation

19. 10/09/2025 Anandaraman, NISER Bhubaneswar 19
Deutsch’s Algorithm – Overview
1. The oracle encodes the function.
2. The input state is prepared in superposition so the function is evaluated on both
inputs simultaneously.

20. 10/09/2025 Anandaraman, NISER Bhubaneswar 20
Step 2 (After Oracle Application)

21. 10/09/2025 Anandaraman, NISER Bhubaneswar 21
Deutsch’s Algorithm – Execution
If f is constant, measurement gives 0 .
∣ ⟩
If f is balanced, measurement gives 1 .
∣ ⟩
Thus, one quantum query is enough.
Computational basis (Z-basis):
distinguishes between 0 and 1 .
∣ ⟩ ∣ ⟩
Hadamard basis (X-basis): distinguishes
between superpositions + and − .
∣ ⟩ ∣ ⟩

22. 10/09/2025 Anandaraman, NISER Bhubaneswar 22
Case Analysis

23. 10/09/2025 Anandaraman, NISER Bhubaneswar 23
The Quantum Solution involves just 1 query

24. 10/09/2025 Anandaraman, NISER Bhubaneswar 24
What is Phase Kickback?
Phase kickback happens when you apply a controlled operation (like a controlled-U or an
oracle) where the target qubit is in a special state (usually − ), and instead of the target
∣ ⟩
changing, the control qubit picks up a phase.
So the "kick" of the phase goes back to the control qubit.

25. 10/09/2025 Anandaraman, NISER Bhubaneswar 25
Deutsch–Jozsa Algorithm
1. Deutsch Algorithm provides a two-time speedup in the
computation.
2. Deutsch-Jozsa Algorithm provides an exponential speedup
over the classical one
3. The Deutsch-Josza algorithm, proposed by David Deutsch and
Richard Josza in 1992.
4. Generalization to n bits, for n-qubit problem, Classical requires
2
n−1
+1 computations, but only 1 computation using the Deutsch-
Jozsa Algorithm.
5. The Deutsch Algorithm also provides an exponential speedup,
but it just happens that n=1 and thus it only has two times of
speedup.

26. 10/09/2025 Anandaraman, NISER Bhubaneswar 26
Deutsch–Jozsa Algorithm– Execution
1. Step 1: Prepare n qubits in the state 0 ^n and the
∣ ⟩
ancillary qubit in the state1
∣ ⟩
2. Step 2: Apply Hadamard gate to each qubit, which puts
the qubits in a superposition of all possible n-bit strings.
3. The resulting state is ( 0 + 1 )^n 1 / sqrt(2^(n+1)).
∣ ⟩ ∣ ⟩ ⊗ ∣ ⟩
4. Step 3: Apply the black-box function f to the n qubits,
controlled by the ancillary qubit, which maps the state to
( 0 ^n |f(0) 1> + 1 ^n |f(1) 1>) / sqrt (2^(n+1))).
∣ ⟩ ⊗ ⊕ ∣ ⟩ ⊗ ⊕
5. Step 4: Apply a Hadamard gate to each qubit except the
ancillary qubit.

27. 10/09/2025 Anandaraman, NISER Bhubaneswar 27
Quantum Oracle (A black box)
1. Quantum Oracles allow users to implement solutions without knowing the internal workings
of the problem-solving function.
2. The function f(x) in quantum algorithms is essential for solving specific problems and is not
limited to the Deutsch algorithm.
3. For an oracle represented as Uf (unitary operator corresponding to the function f(x)), it must
be a unitary gate, ensuring reversibility crucial to quantum computation.
4. Two types of quantum oracles
1. XOR quantum oracle
2. Phase quantum oracle
5. A Quantum oracle is nothing but just a quantum gate. Therefore it must be unitary and
reversible.

28. 10/09/2025 Anandaraman, NISER Bhubaneswar 28
Oracle working process
∣x : input to the function f.
⟩
∣y : an auxiliary qubit, sometimes called a workspace or target.
⟩
Uf : a unitary operator — must be reversible.
That’s why the oracle is defined with XOR (y f(x)), not overwrite.
⊕
XOR oracle: Uf: x,y x,y f(x)
∣ ⟩↦∣ ⊕ ⟩
phase oracle (after putting y = − ):O
∣ ⟩ ∣ ⟩
f
​
: x (−1)
∣ ⟩↦
f(x)
x
∣ ⟩

29. 10/09/2025 Anandaraman, NISER Bhubaneswar 29
Quantum Oracle (Multi-bit)

30. 10/09/2025 Anandaraman, NISER Bhubaneswar 30
XOR Oracle

31. 10/09/2025 Anandaraman, NISER Bhubaneswar 31
Phase Oracle
In Some applications, we encode f(x) so that it changes the phase of the input basis
vector based on f(x) and uses it as an output.

32. 10/09/2025 Anandaraman, NISER Bhubaneswar 32
Grover’s Search Algorithm
Problem: Search unsorted database of N items
Classical: O(N)
Quantum: O(√N)
Applications: optimization, AI, machine learning

33. 10/09/2025 Anandaraman, NISER Bhubaneswar 33
Shor’s Algorithm
Problem: Integer factorization (basis of RSA cryptography)
Classical best: Sub-exponential
Quantum: Polynomial time (O((log
⁡N)
3
)
Implication: Post-quantum cryptography

34. 10/09/2025 Anandaraman, NISER Bhubaneswar 34
Other Notable Algorithms
Quantum Fourier Transform (QFT) – building block
Quantum Phase Estimation – eigenvalue problems
Variational Quantum Algorithms (VQE, QAOA) – hybrid NISQ approaches

35. 10/09/2025 Anandaraman, NISER Bhubaneswar 35
Challenges & Future Directions
Hardware limitations (noise, decoherence, qubits)
Error correction is resource-heavy
Current stage: NISQ (Noisy Intermediate-Scale Quantum)
Need for hybrid quantum-classical workflows

36. 10/09/2025 Anandaraman, NISER Bhubaneswar 36