QUANTUM COMPUTING

Complete Exam Notes

Lectures 1 - 5 | CSE

SYLLABUS COVERAGE:
- Classical Deterministic & Probabilistic Systems
- Quantum Systems & Basic Quantum Theory
- Quantum Bits (Qubits) & Bloch Sphere Representation
- Hilbert Space, Probabilities & Measurements
- Multiple Qubits | Vector Spaces | Inner Products
- Entropy & Information Theory | Logic Gates
LECTURE 1: Introduction to Quantum Computing
1.1 Why Quantum Computing?
Classical computers, despite being incredibly powerful, face fundamental limits when solving certain
classes of problems. As problems grow in complexity — drug discovery, optimization, cryptography,
machine learning — classical machines require exponentially more resources.
Quantum Computing (QC) harnesses the principles of quantum mechanics to perform computations in
fundamentally different ways. Tech giants including Google, IBM, Microsoft, and Intel are racing to build
practical quantum computers.

1.2 Classical Computing — Information Basics

The Bit
A bit is the smallest unit of information in classical computing. It is a 2-level system that can only be in
one of two states at any given time:
States: { 0, 1 }

Physical realizations of a bit:

Physical System State 0 State 1
Coin Heads (H) Tails (T)
Switch OFF ON
Voltage 0V +5V
Binary digit 0 1

Encoding Information with Bits

To represent a message with m possible states, we need log₂(m) bits:
Number of bits = log₂(m)
m = 2 ⇒ 1 bit (states: 0, 1)
m = 4 ⇒ 2 bits (states: 00, 01, 10, 11)
m = 8 ⇒ 3 bits (states: 000 to 111)

1.3 Probability Basics

Fundamentals
Probability is used to quantify uncertainty. For a random variable X with outcomes {x₁, x₂, ..., x ₙ} and
probabilities {p₁, p₂, ..., pₙ}:
• 0 ≤ pᵢ ≤ 1 (probability of any event is between 0 and 1)
 • Σ pᵢ = 1 (probabilities must sum to 1)
• pᵢ = nᵢ / n where nᵢ = count of j-th event, n = total events

Expectation Value
The expectation (average) value of a distribution is a core concept in both classical probability and
quantum mechanics:
⟨j⟩ = Σ j · P_j
Example: A group of 24 students scored: 95 (1 student), 85 (3), 77 (7), 71 (10), 56 (3)
Most probable score: 71 (highest frequency, P₇₁ = 10/24 = 0.42)
Expected (average) score: ⟨j⟩ = 95(1/24) + 85(3/24) + 77(7/24) + 71(10/24) + 56(3/24) = 74.3

1.4 Entropy and Information Theory

Shannon Information Content
Information content I of an event with probability p is defined as:
I = -log₂(P) where 0 ≤ P ≤ 1
Key insight: The lower the probability of an event, the higher its information content.
• If P = 0.995 (almost certain): I = -log₂(0.995) ≈ 0.007 bits (almost no info)
• If P = 0.005 (very unlikely): I = -log₂(0.005) ≈ 7.64 bits (lots of info)
As P decreases (event becomes rarer), I increases. As P increases (event becomes more certain), I
decreases toward 0.

Shannon Entropy H(X)

Entropy is the expected (average) information content of a random variable X. It measures the
uncertainty or randomness in a system:
H(X) = -Σ p_i · log₂(p_i) where Σ p_i = 1
Example: Signal always sending value 2 (like: 2 2 2 2...)
• All outcomes same ⇒ p = 1 ⇒ H = -log₂(1) = 0 (no uncertainty)
Example: Signal alternating 1 and 2 equally (p₁ = p₂ = 1/2):
H = -½ log₂(½) - ½ log₂(½)
= ½ + ½ = 1 bit (maximum uncertainty for 2 outcomes)

1.5 Classical Logic Gates

Logic gates are the building blocks of classical computation. A logic gate is a function:
f : {0,1}^n → {0,1}^m
It maps n input bits to m output bits.
Single-Bit Gates (n=1)
Gate Symbol Input 0 Input 1 Description
Identity I (buffer) 0 1 Output = Input (no change)
NOT a → a̅ 1 0 Flips the bit

Two-Bit Gates (n=2)

Gate 00 01 10 11 Notes
AND 0 0 0 1 Output 1 only if both inputs are 1
OR 0 1 1 1 Output 1 if at least one input is 1
XOR 0 1 1 0 a ⊕ b = a+b (mod 2); used in half-
adders
NAND 1 1 1 0 NOT(AND); universal gate
NOR 1 0 0 0 NOT(OR); universal gate

Special Gates
• FANOUT: Copies a bit → x ⇒ (x, x). One input, two outputs.
• CROSSOVER: Swaps two wires → (a, b) ⇒ (b, a)
IMPORTANT: NAND and NOR are UNIVERSAL gates for classical computing.
Any Boolean function can be built using only NAND gates (or only NOR gates).
This is the classical analog of universal quantum gate sets (H + CNOT).
LECTURE 2: Classical vs Quantum & The Qubit
2.1 Classical vs Quantum Computing — Comparison Table
Concept Classical Quantum
Fundamental unit Bit (0 or 1) Qubit |0⟩ or |1⟩ or superposition
Gates Logic gates Unitary gates
Universal gate set NAND, NOR Hadamard (H) + CNOT
Algebra Boolean algebra Linear algebra
State space Vector space (real) Hilbert space (complex)
Programming language Verilog OpenQASM, Qiskit
Error correction CML, Repetition code Shor code
Complexity class P BQP (Bounded Error Quantum Poly)

2.2 The Qubit (Quantum Bit)

A qubit is the fundamental unit of quantum information. It is analogous to a classical bit, but with a
crucial difference: while a bit must be 0 OR 1, a qubit can exist in a superposition of both states
simultaneously.
Definition: A qubit is a 2-level quantum mechanical system.

The Qubit State

|ψ⟩ = α|0⟩ + β|1⟩ (Equation 1 — Fundamental)
Where: α, β are complex numbers called probability amplitudes of states |0⟩ and |1⟩ respectively.
The qubit state |ψ⟩ is a vector in a 2-dimensional complex vector space (Hilbert space).

Physical Realizations of a Qubit

• Two different polarizations of a photon: |↑⟩, |→⟩
• Alignment of nuclear spin in a uniform magnetic field: |↑⟩, |↓⟩
• Two states of an electron: ground state |0⟩ (lower energy), excited state |1⟩ (higher energy)
Geometrically, a qubit state is represented using the BLOCH SPHERE (named after Felix
Bloch).

2.3 Dirac Notation (Bra-Ket Notation)

In quantum mechanics, states are written using Dirac (bra-ket) notation:
Symbol Name Mathematical Form Meaning
|ψ⟩ Ket Column vector Quantum state vector
 ⟨ψ| Bra Row vector (conjugate Dual of ket
transpose)
⟨φ|ψ⟩ Bracket Inner product Overlap between states
|⟩⟨| Outer Matrix Projection operator
product

Computational Basis States

|0⟩ = (1) = ⟨|of state 0
(0)

|1⟩ = (0) = ⟨|of state 1

(1)
These two states {|0⟩, |1⟩} form the computational basis states. They are orthonormal and span the 2-D
complex vector space C²:
⟨0|0⟩ = 1, ⟨1|1⟩ = 1 (normalized)
⟨0|1⟩ = 0, ⟨1|0⟩ = 0 (orthogonal)

2.4 Superposition
Superposition is the quantum mechanical principle that a qubit can be in |0⟩ AND |1⟩ simultaneously,
until measured. The qubit exists in a linear superposition of both basis states at the same time.
|ψ⟩ = α|0⟩ + β|1⟩
This is NOT like classical uncertainty — the qubit genuinely exists in both states at once.

2.5 Measurement and Probability

When we measure a qubit, the superposition collapses to one of the basis states. This is called
wavefunction collapse.
• Measuring |ψ⟩ gives outcome 0 with probability |α|²
• Measuring |ψ⟩ gives outcome 1 with probability |β|²

Since probabilities must sum to 1:

|α|² + |β|² = 1 (Normalization condition)

Consequence: A qubit's state is a UNIT VECTOR in Hilbert space (length = 1).

Key insight: Measurement gives classical information (0 or 1), but the qubit BEFORE
measurement holds quantum information encoded in α and β simultaneously.
After measurement, the superposition is destroyed — the qubit stays in the measured state.
Example: Verify Normalization
Q: |ψ⟩ = (1/√3)|0⟩ + √(2/3)|1⟩
Check: |1/√3|² + |√(2/3)|² = 1/3 + 2/3 = 1 ✓

2.6 Complex Numbers in Quantum Mechanics

Since α and β are complex numbers, we need to understand complex arithmetic.
z = x + iy (complex number)
z* = x - iy (complex conjugate)
|z|² = z · z* = (x+iy)(x-iy) = x² + y²
|z| = √(x² + y²) (magnitude / modulus)
For probability amplitudes: prob = |amplitude|² = amplitude × complex conjugate

2.7 Geometrical Representation: The Bloch Sphere

Any qubit state can be written (ignoring global phase) as:
|ψ⟩ = cos(θ/2)|0⟩ + e^(iφ) sin(θ/2)|1⟩
Where θ (theta, 0 to π) and φ (phi, 0 to 2π) are real numbers specifying a point on a sphere.
The Bloch Sphere is a unit sphere where every point on the surface represents a valid (pure) qubit
state. Points inside the sphere represent mixed states.

Key points on the Bloch Sphere:

State Position Coordinates (x,y,z)
|0⟩ North pole (top, +z axis) (0, 0, 1)
|1⟩ South pole (bottom, -z axis) (0, 0, -1)
|+⟩ = (|0⟩+|1⟩)/√2 +x axis (1, 0, 0)
|-⟩ = (|0⟩-|1⟩)/√2 -x axis (-1, 0, 0)
|+i⟩ = (|0⟩+i|1⟩)/√2 +y axis (0, 1, 0)
|-i⟩ = (|0⟩-i|1⟩)/√2 -y axis (0, -1, 0)

The overall phase γ (e^(iγ) factor) has NO observable effect on measurement outcomes.
This is called the global phase and is not physically meaningful.
|ψ⟩ and e^(iγ)|ψ⟩ represent the SAME physical qubit state.

Bloch sphere states:

|+⟩ = (1/√2)(|0⟩ + |1⟩) ← x-axis (V.V. Important!)
 |-⟩ = (1/√2)(|0⟩ - |1⟩) ← x-axis
|+i⟩ = (1/√2)(|0⟩ + i|1⟩) ← y-axis
|-i⟩ = (1/√2)(|0⟩ - i|1⟩) ← y-axis

Bloch Sphere Examples from Lectures

Example 1: |ψ₁⟩ = (√3/2)|0⟩ + (1/2)|1⟩
Check: |√3/2|² + |1/2|² = 3/4 + 1/4 = 1 ✓ → Located in Northern/Southern hemisphere (need to
compute θ)
Example 2: |ψ₂⟩ = (2/3)|0⟩ + ((1-2i)/3)|1⟩
Check: |2/3|² + |(1-2i)/3|² = 4/9 + (1+4)/9 = 4/9 + 5/9 = 1 ✓ → Valid qubit state (SHS = Southern
Hemisphere)
LECTURE 3: Vector Spaces & Linear Algebra
3.1 Vector Spaces
In quantum computing, the mathematical framework is provided by complex vector spaces, specifically
Hilbert spaces.
Definition: A vector space V is a non-empty set with elements (called vectors) u, v, w, ... and two
operations defined:
• Vector Addition: u + v = w, where w ∈ V
• Scalar Multiplication: αu ∈ V, where α is a scalar

Vector Space Axioms

The following axioms must hold for all u, v, w ∈ V and scalars α, β:
Axi Name Rule
om
1 Associativity of Addition (u + v) + w = u + (v + w)
2 Zero Vector (Identity) u + 0 = 0 + u = u (0 ∈ V)
3 Additive Inverse u + (-u) = (-u) + u = 0
4 Commutativity of Addition u+v=v+u

3.2 Cⁿ — The n-Dimensional Complex Vector Space

In quantum computing, the vector space is Cⁿ (C-n), which consists of n-tuples of complex numbers
arranged as column vectors (kets |ψ⟩):
Cⁿ = {|a⟩, |b⟩, |c⟩, ...}

|a⟩ = (a₁) ← n-dimensional column vector

(a₂)
( : )
(aₙ)

Operations on Cⁿ
1. Scalar Multiplication
α · |a⟩ = α(a₁) = (αa₁)
(a₂) (αa₂)
( : ) ( : )
 (aₙ) (αaₙ)
∴ Cⁿ is closed under scalar multiplication (result is still in Cⁿ)

2. Vector Addition
|a⟩ + |b⟩ = (a₁+b₁)
(a₂+b₂)
( : )
(aₙ+bₙ)
∴ Cⁿ is closed under vector addition

Example: In C³, given |u⟩ = (-1, 7i, 2)ᵀ and |v⟩ = (0, 2, 4)ᵀ, find 7|u ⟩ + 2|v ⟩:
7|u⟩ + 2|v⟩ = 7(-1, 7i, 2) + 2(0, 2, 4)
= (-7, 49i, 14) + (0, 4, 8)
= (-7, 4+49i, 22)

3.3 Linear Combinations and Span

Given a set of vectors {|vᵢ⟩} and complex coefficients {αᵢ}, a linear combination is:
α₁|v₁⟩ + α₂|v₂⟩ + ... + αₙ|vₙ⟩ = Σ αᵢ |vᵢ⟩

Span: If a set of vectors {|vᵢ⟩} can represent ANY vector |u⟩ in a vector space V through linear
combination, then the set SPANS V.

Example: Does {|0⟩, |1⟩} span C²?

Any |ψ⟩ ∈ C² can be written: |ψ⟩ = α|0⟩ + β|1⟩ = α(1,0)ᵀ + β(0,1)ᵀ = (α, β)ᵀ ✓
So YES — {|0⟩, |1⟩} spans C². Note: spanning sets are NOT unique.

3.4 Linear Independence

A set of vectors is linearly dependent if one vector can be expressed as a linear combination of the
others. Otherwise, the set is linearly independent.
Linearly DEPENDENT: α₁|v₁⟩ + α₂|v₂⟩ + ... = 0
has a non-trivial solution (not all αᵢ = 0)
Example from notes: |a⟩ = (1,2), |b⟩ = (-1,1), |c⟩ = (5,4)
To show linear dependence, show |c⟩ = α|a⟩ + β|b⟩ for some α, β
|c⟩ = 3|a⟩ - 2|b⟩ = 3(1,2) - 2(-1,1) = (3+2, 6-2) = (5,4) ✓
Therefore {|a⟩, |b⟩, |c⟩} is linearly dependent.

3.5 Basis and Dimension

Definition of Basis
A set of vectors forms a BASIS for a vector space V if:
• The vectors are linearly independent, AND
• They span the entire space V

Every vector in V can be UNIQUELY expressed as a linear combination of basis vectors.

Dimension
Dimension of V = number of vectors (elements/states) in the basis set
Example: Qubit lives in C², basis = {|0⟩, |1⟩}, so dimension = 2
For n-qubit system: C^(2ⁿ), dimension = 2ⁿ

Quantum States as Linear Expansions

Any quantum state |ψ⟩ can be expanded in terms of basis vectors:
n=2: |ψ⟩ = Σ Cᵢ |vᵢ⟩ (i = 1,2) = C₁|v₁⟩ + C₂|v₂⟩
↓ ↓ ↓
general = α|0⟩ + β|1⟩

n-dim: |ψ⟩ = C₁|v₁⟩ + C₂|v₂⟩ + ... + Cₙ|vₙ⟩

|Cᵢ|² = probability that measuring |ψ⟩ finds system in
state |vᵢ⟩

This connects linear algebra directly to quantum measurement: the expansion coefficients are
probability amplitudes!
LECTURE 4: Inner Products, Bras, and Orthonormality
4.1 Inner Product (Dot Product in Quantum Mechanics)
The inner product ⟨φ|ψ⟩ is a generalization of the dot product to complex vector spaces. It takes two
vectors and returns a complex number.
⟨φ|ψ⟩ = (φ₁*, φ₂*, ..., φₙ*) · (ψ₁, ψ₂, ..., ψₙ)ᵀ
= Σ φᵢ* · ψᵢ
Where φᵢ* is the complex conjugate of the i-th component of |φ⟩

Properties of Inner Product

• ⟨ψ|ψ⟩ ≥ 0 (always non-negative real)
• ⟨ψ|ψ⟩ = 0 iff |ψ⟩ = 0 (zero vector)
• ⟨φ|ψ⟩ = ⟨ψ|φ⟩* (conjugate symmetry)
• ⟨φ|(α|ψ⟩ + β|χ⟩) = α⟨φ|ψ⟩ + β⟨φ|χ⟩ (linearity)

Norm (Length) of a Vector

||ψ|| = √⟨ψ|ψ⟩
For a valid qubit: ||ψ|| = 1 (unit vector — normalization condition)

4.2 Orthonormality
Orthogonal Vectors
Two vectors |φ⟩ and |ψ⟩ are orthogonal if their inner product is zero:
⟨φ|ψ⟩ = 0

Orthonormal Basis
A set of vectors is orthonormal if they are both orthogonal to each other AND each has unit norm:
⟨vᵢ|vⱼ⟩ = δᵢⱼ (Kronecker delta)
= 1 if i = j (same vector: length 1)
= 0 if i ≠ j (different vectors: orthogonal)
The computational basis {|0⟩, |1⟩} is an orthonormal basis for C²:
⟨0|0⟩ = 1 ✓ (normalized)
⟨1|1⟩ = 1 ✓ (normalized)
⟨0|1⟩ = 0 ✓ (orthogonal)
 ⟨1|0⟩ = 0 ✓ (orthogonal)

4.3 The Bra Vector

The bra ⟨ψ| is the conjugate transpose (Hermitian conjugate / dagger operation) of the ket |ψ ⟩:
If |ψ⟩ = (α) then ⟨ψ| = (α*, β*)
(β)
The bra is a ROW vector; the ket is a COLUMN vector.

4.4 Probability from Inner Products

The inner product connects directly to quantum probability:
P(measuring state |vᵢ⟩) = |⟨vᵢ|ψ⟩|²
Example: For |ψ⟩ = α|0⟩ + β|1⟩:
P(0) = |⟨0|ψ⟩|² = |⟨0|(α|0⟩ + β|1⟩)|²
= |α⟨0|0⟩ + β⟨0|1⟩|²
= |α(1) + β(0)|² = |α|² ✓

4.5 Hilbert Space

A Hilbert space is a complete inner product space. For quantum computing:
• It is a complex vector space equipped with an inner product
• Qubit state space = 2-dimensional Hilbert space (C²)
• n-qubit state space = 2ⁿ-dimensional Hilbert space (C^(2ⁿ))
• States are unit vectors (normalized) in Hilbert space
DEFINITION: A qubit's state is a UNIT VECTOR in Hilbert space.
All valid quantum states satisfy: ⟨ψ|ψ⟩ = 1 (normalization)
LECTURE 5: Multiple Qubits & Further Concepts
5.1 Vector Spaces Revisited — Full Summary
Vector spaces in quantum computing (Cⁿ) satisfy all vector space axioms and support the inner product
structure of Hilbert space. Key summary:
Property Classical Bit Qubit (C²)
State {0, 1} α|0⟩ + β|1⟩, α,β ∈ C
Normalization N/A |α|² + |β|² = 1
After measurement Stays the same Collapses to |0⟩ or |1⟩
Superposition No Yes — can be both at once
Information content 1 bit Infinite (but only 1 bit extractable per
measurement)

5.2 Linear Independence — Detailed

Test for Linear Dependence: Solve α₁|v₁⟩ + α₂|v₂⟩ + ... = |0⟩
• If ONLY solution is all αᵢ = 0 ⇒ set is LINEARLY INDEPENDENT
• If non-zero αᵢ exist ⇒ set is LINEARLY DEPENDENT

Spanning Set is NOT Unique:

Both {|0⟩, |1⟩} and {|+⟩, |-⟩} span C². There are infinitely many spanning sets.
Q: Does {|u₁⟩, |u₂⟩} span C²?
|u₁⟩ = (1, 1)ᵀ and |u₂⟩ = (1, -1)ᵀ
Answer: YES — these are linearly independent and span C²

5.3 Multiple Qubits — The Tensor Product

When we have multiple qubits, the combined state space is formed by the tensor product of individual
qubit spaces.
For 2 qubits: State space = C² ⊗ C² = C⁴ (4-dimensional)
For n qubits: State space = C^(2ⁿ) (2ⁿ-dimensional)

The computational basis for 2 qubits:

|00⟩ = |0⟩⊗|0⟩ = (1,0,0,0)ᵀ
|01⟩ = |0⟩⊗|1⟩ = (0,1,0,0)ᵀ
|10⟩ = |1⟩⊗|0⟩ = (0,0,1,0)ᵀ
|11⟩ = |1⟩⊗|1⟩ = (0,0,0,1)ᵀ
A general 2-qubit state:
|ψ⟩ = α|00⟩ + β|01⟩ + γ|10⟩ + δ|11⟩ where |α|²+|β|²+|
γ|²+|δ|² = 1

5.4 Quantum vs Classical Information

How Much Information Does a Qubit Hold?
• Before measurement: A qubit stores complex amplitudes α and β (potentially infinite precision)
• After measurement: You only get 1 classical bit (0 or 1)
• Measurement collapses the superposition — you cannot extract more than 1 bit per
measurement

PARADOX: A qubit seems to 'contain' infinite information in its amplitudes,

but measurement only yields 1 bit. This is NOT contradiction — the power of
quantum computing comes from processing all amplitudes BEFORE measurement
via quantum interference and entanglement.

5.5 Key Formulas — Quick Reference

QUBIT STATE: |ψ⟩ = α|0⟩ + β|1⟩
NORMALIZATION: |α|² + |β|² = 1
PROBABILITIES: P(0) = |α|², P(1) = |β|²
BLOCH SPHERE: |ψ⟩ = cos(θ/2)|0⟩ + e^(iφ)sin(θ/2)|
1⟩
INNER PRODUCT: ⟨φ|ψ⟩ = Σ φᵢ* ψᵢ
ORTHONORMALITY: ⟨vᵢ|vⱼ⟩ = δᵢⱼ
BASIS EXPANSION: |ψ⟩ = Σ Cᵢ|vᵢ⟩
PROB FROM EXPANSION: P(vᵢ) = |Cᵢ|²
SHANNON ENTROPY: H(X) = -Σ pᵢ log₂(pᵢ)
INFORMATION CONTENT: I = -log₂(P)
EXAM TIPS & COMMON QUESTIONS
Normalization Check
Always verify a state is valid by checking |α|² + |β|² = 1 before answering any question.
Q: Is |ψ⟩ = (i/√3)|0⟩ + √(2/3)|1⟩ a valid qubit?
|i/√3|² + |√(2/3)|² = 1/3 + 2/3 = 1 ✓

Linear Dependence
To show a set is linearly dependent, find one vector as a linear combo of others.
Use the equation: x = αy + βz and solve for α, β.

Basis Test
A set is a basis if: (1) It is linearly independent, AND (2) It spans the space.
Minimum number of vectors for a basis of Cⁿ = n (same as dimension).

Entropy Calculation
1. Find all probabilities pᵢ (check they sum to 1)
2. Apply H = -Σ pᵢ log₂(pᵢ)
3. H = 0 means no uncertainty; H = 1 means maximum uncertainty (for 2 outcomes)

Bloch Sphere Hemisphere

Northern Hemisphere: θ ∈ [0, π/2] — |0⟩ component dominates (cos²(θ/2) > 1/2)
Southern Hemisphere: θ ∈ [π/2, π] — |1⟩ component dominates (sin²(θ/2) > 1/2)
Equator: |0⟩ and |1⟩ equally probable (cos²(θ/2) = sin²(θ/2) = 1/2)

REMEMBER THE BIG PICTURE:

Classical bit → 0 or 1 (definite)
Qubit → α|0⟩ + β|1⟩ (superposition until measured)
Measurement → collapses to |0⟩ (prob |α|²) or |1⟩ (prob |β|²)
Hilbert space → complex vector space where quantum states live
Basis {|0⟩,|1⟩} → orthonormal, spans C², dim=2