COMP 4820

Introduction to Quantum Computing

Course Notes — Lectures 1 through 8
Professor J. Okonkwo | Faculty of Computer Science | Fall Semester 2024
Compiled by: Student Notes Collective

Last updated: November 2024

COMP 4820 — Introduction to Quantum Computing | Page 1 of 7

STUDY NOTE: These notes are supplementary to the official course materials. Always refer to the
textbook Nielsen & Chuang 'Quantum Computation and Quantum Information' for formal definitions.
Formula sheets for midterm/final posted on the course portal.

Lecture 1-2: Classical vs Quantum Computing — Motivation

and Foundations
Why do we need quantum computers?
Classical computers represent information as bits — physical systems with two distinguishable
states (0 or 1). Every computation reduces to sequences of logical operations on these binary
values. Moore's Law predicted the doubling of transistor density roughly every 18-24 months,
and for decades this prediction held. However, we are approaching fundamental physical limits:
• Transistors are now ~2-3 nm wide — quantum tunneling causes electrons to 'leak'
through barriers
• Heat dissipation at this scale is a major engineering challenge
• Some problems (e.g. simulating quantum chemistry, factoring large integers) remain
intractable classically regardless of hardware improvements
Quantum computers exploit quantum mechanical phenomena — superposition, entanglement,
and interference — to perform certain computations exponentially faster than any known
classical algorithm.

1.1 The Qubit

The fundamental unit of quantum information is the qubit (quantum bit). Unlike a classical bit, a
qubit can exist in a superposition of its basis states |0⟩ and |1⟩:
|ψ⟩ = α|0⟩ + β|1⟩ where |α|² + |β|² = 1
Here α and β are complex probability amplitudes. When we measure the qubit, it collapses to |
0⟩ with probability |α|² or to |1⟩ with probability |β|². The normalization condition |α|² + |β|² = 1
ensures probabilities sum to 1.
Physical implementations of qubits:
• Superconducting circuits (IBM, Google) — Josephson junctions cooled to ~15 mK
• Trapped ions (IonQ, Quantinuum) — individual ions suspended in electromagnetic field
• Photonic qubits — polarization states of single photons
• Topological qubits (Microsoft) — Majorana fermions (still largely experimental)

1.2 The Bloch Sphere

The state of a single qubit can be visualized as a point on the surface of the Bloch sphere.
Using spherical coordinates:
|ψ⟩ = cos(θ/2)|0⟩ + e^(iφ) sin(θ/2)|1⟩
The north pole (θ=0) represents |0⟩, the south pole (θ=π) represents |1⟩. Points on the equator
represent equal superpositions like |+⟩ = (|0⟩ + |1⟩)/√2. The Bloch sphere is useful for visualizing
single-qubit gates as rotations, but cannot represent multi-qubit states — the state space grows
exponentially.

COMP 4820 — Introduction to Quantum Computing | Page 2 of 7

Lecture 3: Quantum Gates and Circuits
Quantum gates are the quantum analogue of classical logic gates. They are unitary operations,
meaning they preserve the norm of quantum states and are reversible. Unlike classical gates,
every quantum gate is inherently reversible — this is required by quantum mechanics (unitarity).

2.1 Single-Qubit Gates

Represented as 2×2 unitary matrices acting on the state vector:

Gate Matrix Effect on |0⟩ Notes

Pauli-X (NOT) [[0,1],[1,0]] |0⟩ → |1⟩ Bit flip, like classical
NOT

Hadamard (H) 1/√2 · [[1,1],[1,-1]] |0⟩ → |+⟩ Creates equal

superposition

Pauli-Z [[1,0],[0,-1]] |0⟩ → |0⟩ Phase flip, maps |

1⟩→-|1⟩

T gate (π/8) [[1,0],[0,e^(iπ/4)]] |0⟩ → |0⟩ Essential for universal

QC

2.2 The CNOT Gate (Two-Qubit)

The Controlled-NOT gate is the fundamental two-qubit gate. It flips the TARGET qubit if and
only if the CONTROL qubit is |1⟩:
• |00⟩ → |00⟩ (control=0, no flip)
• |01⟩ → |01⟩ (control=0, no flip)
• |10⟩ → |11⟩ (control=1, flip target)
• |11⟩ → |10⟩ (control=1, flip target)
Together with the Hadamard gate, the CNOT is sufficient to create Bell states (maximally
entangled two-qubit states), which are central to quantum teleportation and superdense coding.

COMP 4820 — Introduction to Quantum Computing | Page 3 of 7

Lecture 4: Quantum Entanglement
Entanglement is arguably the most counterintuitive feature of quantum mechanics and a key
resource for quantum computation. Two qubits are entangled if their joint state cannot be written
as a product of individual qubit states.

3.1 Bell States

The four maximally entangled two-qubit states (Bell states or EPR pairs):
|Φ+⟩ = (|00⟩ + |11⟩)/√2 |Φ-⟩ = (|00⟩ - |11⟩)/√2
|Ψ+⟩ = (|01⟩ + |10⟩)/√2 |Ψ-⟩ = (|01⟩ - |10⟩)/√2
Key property: If Alice measures her qubit in |Φ+⟩ and gets |0⟩, Bob's qubit instantly collapses to |
0⟩ regardless of their spatial separation. This is NOT superluminal communication — the
outcomes are random and no information can be transmitted. However, the correlations are
stronger than any classical model can explain (Bell inequality violations).

3.2 Creating Bell States

Circuit to create |Φ+⟩ from |00⟩:
• Step 1: Apply Hadamard (H) to qubit 1: |00⟩ → (|0⟩+|1⟩)/√2 ⊗ |0⟩ = (|00 ⟩+|10 ⟩)/√2
• Step 2: Apply CNOT with qubit 1 as control, qubit 2 as target: → (|00 ⟩+|11 ⟩)/√2 = |Φ+ ⟩

COMP 4820 — Introduction to Quantum Computing | Page 4 of 7

Lecture 5-6: Quantum Algorithms
4.1 Deutsch-Jozsa Algorithm
The Deutsch-Jozsa algorithm was the first quantum algorithm to demonstrate an exponential
speedup over classical computation. The problem: given a black-box function f:{0,1}^n → {0,1}
promised to be either constant (all outputs same) or balanced (exactly half outputs 0, half 1),
determine which.
Classical complexity: O(2^(n-1)+1) queries in the worst case. Quantum complexity: O(1)
query — solved in a single oracle call regardless of n.
Algorithm steps:
• Initialize n+1 qubits: |0⟩^n|1⟩
• Apply Hadamard to all qubits: creates equal superposition over all inputs + ancilla |−⟩
• Apply oracle Uf: |x⟩|y⟩ → |x⟩|y⊕f(x)⟩
• Apply Hadamard to first n qubits again
• Measure first n qubits: all |0⟩ = constant function; any |1⟩ = balanced function
Why it works: The oracle applies phase kickback, encoding f's global properties into
interference patterns. Constructive interference at |0...0⟩ indicates constant f; destructive
interference (no probability at |0...0⟩) indicates balanced f.

4.2 Shor's Factoring Algorithm

Shor's algorithm (1994) is arguably the most consequential quantum algorithm. It solves integer
factorization in polynomial time O((log N)^3), compared to the best classical algorithms which
run in sub-exponential but super-polynomial time. Breaking RSA-2048 encryption would require
approximately 4,000 logical qubits — currently far beyond reach (NIST estimates 2030s-2040s).
High-level steps:
• Reduce factoring to period-finding: if gcd(a,N) > 1, found a factor; otherwise find period r
of f(x) = a^x mod N
• Use Quantum Fourier Transform (QFT) to find period r exponentially faster than classical
• If r is even and a^(r/2) ≠ -1 mod N: factors are gcd(a^(r/2) ± 1, N)

4.3 Grover's Search Algorithm

Grover's algorithm provides a quadratic speedup for unstructured search. Finding a marked
item in N unsorted items: classical O(N), Grover's O(√N). While less dramatic than Shor's
exponential speedup, it has broad applicability.
The key operation is the 'Grover iteration' or 'Grover diffusion operator' — an amplitude
amplification technique that increases the probability amplitude of the target state while
decreasing amplitudes of non-target states. After approximately π/4 · √N iterations, a
measurement yields the target with high probability.

COMP 4820 — Introduction to Quantum Computing | Page 5 of 7

Lecture 7: Quantum Error Correction
Quantum computers are extraordinarily sensitive to noise. Unlike classical bits, qubits can
experience both bit flips (|0⟩↔|1⟩) and phase flips (|+⟩↔|-⟩), as well as combinations of both.
Furthermore, measuring a qubit to check for errors destroys the superposition. Quantum error
correction must detect and correct errors without directly measuring the encoded information.

5.1 The Three-Qubit Bit-Flip Code

Encode one logical qubit into three physical qubits:
|0_L⟩ = |000⟩ |1_L⟩ = |111⟩
Error detection uses ancilla qubits to measure parity checks (X⊗X⊗I and I⊗X⊗X) without
disturbing the encoded state. The 'syndrome' measurement tells us which qubit flipped without
revealing the logical state. Apply Pauli-X to the flipped qubit to correct.

5.2 The Surface Code

The surface code is the leading candidate for fault-tolerant quantum computing. It arranges
physical qubits on a 2D lattice and uses local stabilizer measurements to detect errors. Key
features:
• Threshold error rate: ~1% — if physical error rate < threshold, logical error rate
decreases with code size
• Only nearest-neighbor interactions required — compatible with superconducting qubit
architectures
• ~1000 physical qubits needed per logical qubit at current error rates
• This means a fault-tolerant quantum computer for Shor's would require ~4 million
physical qubits

COMP 4820 — Introduction to Quantum Computing | Page 6 of 7

Lecture 8: NISQ Era and Near-Term Applications
We are currently in the 'Noisy Intermediate-Scale Quantum' (NISQ) era — machines with 50-
1000+ noisy qubits, no error correction. While insufficient for fault-tolerant Shor's or Grover's,
NISQ devices may offer advantage for certain problems.

6.1 Variational Quantum Eigensolver (VQE)

VQE is a hybrid classical-quantum algorithm for estimating ground state energies of molecules
— directly relevant to drug discovery and materials science. The quantum circuit prepares a
parameterized trial state ('ansatz'), the classical optimizer tunes parameters to minimize energy.
Key advantage: circuits are shallow enough for NISQ hardware.

6.2 Quantum Approximate Optimization Algorithm (QAOA)

QAOA is designed for combinatorial optimization problems (MaxCut, TSP variants, portfolio
optimization). It alternates between problem-specific and mixing unitaries, with depths controlled
by parameter p. Higher p theoretically gives better approximations but requires more noise-
tolerant hardware. Current evidence on quantum advantage for QAOA is mixed.

6.3 Quantum Machine Learning (QML)

Quantum versions of machine learning algorithms (QSVMs, quantum neural networks) have
attracted enormous interest and hype. Be cautious: many proposed QML algorithms have
classical dequantization counterparts of similar complexity (Tang et al.), and input/output
bottlenecks may negate quantum speedups. Genuine QML advantage remains an open
research question.

Exam Preparation Notes

EXAM TIP (from Prof. Okonkwo): Know all four Bell states cold. Be able to derive them from |
00⟩ using H+CNOT circuit. Understand why measurement on one qubit affects the other — be
precise about what 'measurement' means in this context.
Topics confirmed for midterm:
• Qubit state representation and Bloch sphere
• Matrix computation of gate actions on qubit states
• CNOT truth table and circuit diagrams
• Bell state creation circuit
• Conceptual understanding of Deutsch-Jozsa, Shor's, Grover's (complexity comparison to
classical)
• Basic error types in quantum computers and why classical error correction doesn't work

Recommended further reading:

• Nielsen & Chuang — Chapters 1-4 (essential)
• Preskill's lecture notes (freely available at [Link])
• IBM Quantum Learning platform (hands-on circuit building)
• 'Quantum Computing: An Applied Approach' — Hidary (more accessible)

COMP 4820 — Introduction to Quantum Computing | Page 7 of 7