Comprehensive Class Notes:

Quantum Computation and

Quantum Information
Advanced Theoretical Physics & Computer Science Program
Current Academic Year

Abstract

These extensive class notes provide a rigorous, in-depth exploration of quantum

computation, quantum information theory, and the mathematical foundations that
underpin this transformative field. Designed for advanced graduate students, this
manuscript bridges the gap between abstract linear algebra, quantum mechanics,
and practical algorithmic implementation. Over the course of these sections, we
cover the postulates of quantum mechanics, detailed derivations of quantum logic
gates, in-depth analysis of universal quantum circuits, and extensive walkthroughs
of flagship algorithms including Quantum Teleportation, Superdense Coding, the
Deutsch-Jozsa algorithm, Grover’s search, and Shor’s factorization algorithm. Fur-
thermore, we delve into the physical realities of quantum systems, examining de-
coherence, quantum error correction protocols, and the current landscape of fault-
tolerant quantum hardware. This document aims to serve as both a study guide
and a standalone reference for the theory of quantum computing.

1
Contents
1 Mathematical Foundations of Quantum Mechanics 3
1.1 Vector Spaces and the Hilbert Space . . . . . . . . . . . . . . . . . . . . 3
1.2 The Qubit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 The Bloch Sphere Representation . . . . . . . . . . . . . . . . . . . . . . 3
1.4 The Four Postulates of Quantum Mechanics . . . . . . . . . . . . . . . . 4
1.4.1 Postulate 1: State Space . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.2 Postulate 2: Evolution . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.3 Postulate 3: Measurement . . . . . . . . . . . . . . . . . . . . . . 4
1.4.4 Postulate 4: Composite Systems . . . . . . . . . . . . . . . . . . . 5

2 Quantum Logic Gates and Circuits 5

2.1 Single Qubit Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Multi-Qubit Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Entanglement and Bell States . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Quantum Communication Protocols 7

3.1 Superdense Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Quantum Teleportation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4 Flagship Quantum Algorithms 8

4.1 Deutsch-Jozsa Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Grover’s Search Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 Shor’s Factoring Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 9

5 Decoherence and Quantum Error Correction 10

5.1 The Need for Quantum Error Correction (QEC) . . . . . . . . . . . . . . 10
5.2 The Shor Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.3 Fault-Tolerant Quantum Computation . . . . . . . . . . . . . . . . . . . 11

6 Physical Implementations 11

7 Conclusion 12

2
1 Mathematical Foundations of Quantum Mechanics
1.1 Vector Spaces and the Hilbert Space
The mathematical foundation of quantum computing is built upon linear algebra. The
state of a quantum system is mathematically described by a vector in a complex vector
space equipped with an inner product. This specific type of vector space is known as a
Hilbert space, denoted as H.
For a finite-dimensional quantum system, the Hilbert space is isomorphic to Cd , where
d is the dimension of the system. We utilize Dirac notation (bra-ket notation) to represent
vectors. A column vector is represented as a "ket" |ψ⟩, while its conjugate transpose (row
vector) is represented as a "bra" ⟨ψ|.

1.2 The Qubit

The fundamental unit of classical information is the bit, which takes a value of either 0 or
1. In quantum information, the fundamental unit is the quantum bit, or qubit. A qubit
is a two-dimensional quantum system whose state lives in a two-dimensional complex
Hilbert space, C2 .
We define the computational basis states as:
   
1 0
|0⟩ =   , |1⟩ =   (1)
0 1

Unlike a classical bit, a qubit can exist in a linear combination, or superposition, of

these basis states. A general pure state of a qubit is written as:

|ψ⟩ = α|0⟩ + β|1⟩ (2)

where α, β ∈ C are complex numbers called probability amplitudes. The normalization

condition, arising from the probabilistic interpretation of quantum mechanics, dictates
that:
|α|2 + |β|2 = 1 (3)

1.3 The Bloch Sphere Representation

Because the global phase of a quantum state is physically unobservable, we can rewrite
the state of a qubit in a more geometrically intuitive form. We can factor out a phase eiγ
and express the state using two real parameters, θ and ϕ:
! !
θ θ
|ψ⟩ = cos |0⟩ + eiϕ sin |1⟩ (4)
2 2

3
where 0 ≤ θ ≤ π and 0 ≤ ϕ < 2π. The parameters θ and ϕ define a point on the surface
of a unit sphere in three-dimensional real space R3 , known as the Bloch sphere. The
North Pole corresponds to |0⟩, the South Pole to |1⟩, and points on the equator represent
equal superpositions (e.g., |+⟩ = √1 (|0⟩
2
+ |1⟩)).

1.4 The Four Postulates of Quantum Mechanics

The theoretical framework of quantum mechanics can be summarized by four fundamental
postulates. These postulates govern how we describe states, how states evolve over time,
how we extract information from them, and how we combine multiple systems.

1.4.1 Postulate 1: State Space

Associated with any isolated physical system is a complex vector space with an inner
product (that is, a Hilbert space) known as the state space of the system. The system
is completely described by its state vector, which is a unit vector in the system’s state
space.

1.4.2 Postulate 2: Evolution

The time evolution of the state of a closed quantum system is described by the Schrödinger
equation:
d|ψ(t)⟩
iℏ = H|ψ(t)⟩ (5)
dt
where ℏ is the reduced Planck constant and H is a Hermitian operator known as the
Hamiltonian of the system. For quantum computing, we often prefer the discrete-time
picture. The evolution of a closed quantum system between two times t1 and t2 is de-
scribed by a unitary operator U (such that U † U = I):

|ψ(t2 )⟩ = U (t1 , t2 )|ψ(t1 )⟩ (6)

1.4.3 Postulate 3: Measurement

Quantum measurements are described by a collection {Mm } of measurement operators.

These operators act on the state space of the system being measured. The index m refers
to the measurement outcomes that may occur. The probability of obtaining outcome m
when measuring the state |ψ⟩ is given by:

p(m) = ⟨ψ|Mm
†
Mm |ψ⟩ (7)

4
The state of the system immediately after the measurement collapses to:

Mm |ψ⟩
q (8)
p(m)

The measurement operators must satisfy the completeness equation, †

Mm = I,
P
m Mm
ensuring that the sum of the probabilities of all possible outcomes equals 1.

1.4.4 Postulate 4: Composite Systems

The state space of a composite physical system is the tensor product of the state spaces
of the component physical systems. If we have systems A and B, the joint state space is
HA ⊗ HB . If system A is prepared in state |ψA ⟩ and system B is in state |ϕB ⟩, the joint
state is |ψA ⟩ ⊗ |ϕB ⟩.

2 Quantum Logic Gates and Circuits

Classical computation models use logic gates (AND, OR, NOT, XOR) to process bi-
nary information. Similarly, quantum computation uses quantum logic gates to process
quantum information. According to Postulate 2, any deterministic transformation on a
quantum state must be unitary. Therefore, all quantum gates are represented by unitary
matrices, which implies that quantum computation is inherently reversible.

2.1 Single Qubit Gates

Any 2 × 2 unitary matrix represents a valid single-qubit gate. The most fundamental set
of single-qubit gates are the Pauli gates.
Pauli-X (Bit-flip) Gate:  
0 1
X= (9)
1 0
X|0⟩ = |1⟩ and X|1⟩ = |0⟩. It is the quantum equivalent of the classical NOT gate.
Pauli-Y Gate:  
0 −i
Y =  (10)
i 0
The Y gate applies a bit-flip and a phase-flip, introducing an imaginary phase factor.
Pauli-Z (Phase-flip) Gate:
 
1 0
Z=  (11)
0 −1

5
Z|0⟩ = |0⟩ and Z|1⟩ = −|1⟩. It alters the relative phase of the qubit without changing
the measurement probabilities in the computational basis.
Hadamard Gate: The Hadamard gate (H) is one of the most widely used gates in
quantum algorithms. It maps the computational basis states to mutually unbiased basis
states (equal superpositions):  
1 1 1
H=√  (12)
2 1 −1

H|0⟩ = √1 (|0⟩
2
+ |1⟩) ≡ |+⟩
H|1⟩ = √1 (|0⟩
2
− |1⟩) ≡ |−⟩
Phase Gate (S gate) and T Gate:
   
1 0 1 0 
S= , T =  (13)
0 i 0 eiπ/4

The T gate is particularly important for fault-tolerant quantum computing and achieving
universality.

2.2 Multi-Qubit Gates

To process information stored across multiple qubits and create entanglement, multi-qubit
gates are required.
Controlled-NOT (CNOT) Gate: The CNOT gate acts on two qubits: a control
qubit and a target qubit. It applies an X gate (NOT) to the target qubit if and only if
the control qubit is in the state |1⟩. Its matrix representation in the computational basis
(|00⟩, |01⟩, |10⟩, |11⟩) is:  

1 0 0 0
0 1 0 0
 
CNOT =   (14)
0 0 0 1
 
 
0 0 1 0
Toffoli (CCNOT) Gate: The Toffoli gate is a three-qubit gate with two control
qubits and one target qubit. It flips the target qubit if and only if both control qubits
are in the state |1⟩. The Toffoli gate is universal for classical reversible computation.

2.3 Entanglement and Bell States

Entanglement is a phenomenon where the quantum state of a composite system cannot
be factored into the tensor product of the states of its individual components. Consider
the circuit where we apply a Hadamard gate to the first qubit of the state |00⟩, followed

6
by a CNOT gate with the first qubit as control and the second as target:

|0⟩ + |1⟩ |00⟩ + |10⟩ |00⟩ + |11⟩

! !
CNOT1→2 (H ⊗ I)|00⟩ = CNOT √ ⊗ |0⟩ = CNOT √ = √
2 2 2
(15)
The resulting state is known as the |Φ+ ⟩ Bell state. The four Bell states form a maximally
entangled, orthonormal basis for a two-qubit system:

1
|Φ± ⟩ = √ (|00⟩ ± |11⟩) (16)
2
1
|Ψ± ⟩ = √ (|01⟩ ± |10⟩) (17)
2

3 Quantum Communication Protocols

Quantum information theory enables communication tasks that are fundamentally im-
possible using classical physics alone.

3.1 Superdense Coding

Superdense coding allows Alice to transmit two classical bits of information to Bob by
sending only a single qubit, provided they pre-share an entangled Bell pair.

1. Setup: Alice and Bob share the state |Φ+ ⟩ = √1 (|00⟩

2
+ |11⟩). Alice possesses the
first qubit, Bob possesses the second.

2. Encoding: Depending on the two classical bits (b1 , b2 ) Alice wants to send, she
applies a local unitary operation to her qubit:

• 00: Apply I → |Φ+ ⟩

• 01: Apply X → |Ψ+ ⟩
• 10: Apply Z → |Φ− ⟩
• 11: Apply iY = XZ → |Ψ− ⟩

3. Transmission: Alice sends her single qubit to Bob.

4. Decoding: Bob now has both qubits of the Bell pair. He applies a CNOT gate
followed by a Hadamard gate on the first qubit, and measures both qubits in the
computational basis, deterministically obtaining (b1 , b2 ).

7
3.2 Quantum Teleportation
Quantum teleportation is the converse of superdense coding. It allows Alice to transmit
an unknown quantum state |ψ⟩ = α|0⟩ + β|1⟩ to Bob by sending two classical bits of
information, assuming they pre-share an entangled pair.

1. Setup: Alice wants to send |ψ⟩. Alice and Bob share |Φ+ ⟩AB . The total initial
state is |ψ⟩ ⊗ |Φ+ ⟩AB .

2. Interaction: Alice applies a CNOT gate using |ψ⟩ as the control and her half of
the Bell pair as the target, followed by a Hadamard gate on |ψ⟩.

3. Measurement: Alice measures her two qubits in the computational basis. The
joint state collapses into one of four possibilities, and Bob’s qubit collapses into a
state that is a unitary transformation away from |ψ⟩.

4. Correction: Alice transmits her two classical measurement outcomes to Bob.

Based on these bits, Bob applies the appropriate Pauli matrix (I, X, Z, or XZ)
to his qubit, recovering the exact state |ψ⟩.

Importantly, the original state |ψ⟩ at Alice’s end is destroyed, upholding the No-Cloning
Theorem, which states that it is impossible to create an identical copy of an arbitrary
unknown quantum state.

4 Flagship Quantum Algorithms

Quantum algorithms exploit superposition, entanglement, and quantum interference to
solve certain computational problems exponentially or quadratically faster than the best
known classical algorithms.

4.1 Deutsch-Jozsa Algorithm

The Deutsch-Jozsa algorithm was the first to demonstrate an exponential separation
between classical deterministic algorithms and quantum algorithms. Problem: We are
given a black-box boolean function f : {0, 1}n → {0, 1}. We are guaranteed that f is
either constant (returns the same output for all inputs) or balanced (returns 0 for half of
the inputs and 1 for the other half). The goal is to determine which property f has.
Classically, in the worst-case scenario, we must evaluate f a total of 2n−1 + 1 times
to be absolutely certain.
Quantum Solution: We use an oracle Uf that performs the transformation |x⟩|y⟩ →
|x⟩|y ⊕ f (x)⟩. 1. Prepare an n-qubit input register in |0⟩⊗n and a 1-qubit target register

8
in |1⟩. 2. Apply Hadamard gates to all n + 1 qubits. The state becomes:
n −1
1 2X |0⟩ − |1⟩
√ |x⟩ ⊗ √ (18)
2 x=0
n 2

3. Apply the oracle Uf . This utilizes the "phase kickback" trick, where the function value
is encoded into the phase of the input states:
n −1
1 2X |0⟩ − |1⟩
√ (−1) f (x)
|x⟩ ⊗ √ (19)
2n x=0 2

4. Apply Hadamard gates to the n-qubit input register again. 5. Measure the input
register. If f is constant, the final state is ±|0⟩⊗n , so measuring all zeros occurs with
probability 1. If f is balanced, the amplitude of |0⟩⊗n is exactly 0 due to destructive
interference. Hence, a single query determines the function’s nature.

4.2 Grover’s Search Algorithm

Grover’s algorithm provides a quadratic speedup for unstructured search problems. Given
an unsorted database of N items, finding a specific item classically requires O(N ) oper-
√
ations. Grover’s algorithm finds it in O( N ) operations.
The algorithm relies on amplitude amplification. 1. Initialize the system in an equal
superposition of all N = 2n states: |s⟩ = |x⟩. 2. Repeatedly apply the Grover
PN −1
√1
N x=0
operator G = Us Uf : - Uf is the oracle that flips the phase of the solution state(s) |w⟩:
|x⟩ → (−1)f (x) |x⟩. - Us = 2|s⟩⟨s| − I is the diffusion operator, representing an inversion
about the mean amplitude. Geometrically, each application of G rotates the state vector
√ √
|s⟩ toward the solution state |w⟩ by an angle θ ≈ 2/ N . After approximately π4 N
iterations, the probability of measuring the solution state approaches 1.

4.3 Shor’s Factoring Algorithm

Shor’s algorithm is a milestone in quantum computing. It solves the integer factoriza-
tion problem—finding the prime factors of a composite integer N —in polynomial time
O((log N )3 ), whereas the best known classical algorithm (General Number Field Sieve)
runs in sub-exponential time. Because the security of public-key cryptography systems
like RSA relies on the difficulty of factoring, Shor’s algorithm has profound implications
for global cybersecurity.
Shor’s algorithm reduces the problem of factoring to the problem of order finding
(period finding). 1. Choose a random integer a < N such that gcd(a, N ) = 1. 2. Define
the modular exponentiation function f (x) = ax (mod N ). This function is periodic
with an unknown period r, such that f (x) = f (x + r). 3. Use the Quantum Fourier

9
Transform (QFT) to find the period r efficiently. - The QFT is a linear transformation
analogous to the discrete Fourier transform, but it acts on the quantum amplitudes. It
can be implemented using O(n2 ) quantum gates, providing an exponential speedup over
the classical Fast Fourier Transform (FFT). - The algorithm creates a superposition of
all values of x, computes f (x) in superposition, measures the output register (which
leaves the input register in a superposition of states separated by the period r), and then
applies the QFT to the input register. The QFT extracts the periodicity r from the
superposition. 4. Once the period r is found classically, if r is even, the factors of N can
be found by calculating gcd(ar/2 ± 1, N ).

5 Decoherence and Quantum Error Correction

The most significant hurdle to building a scalable quantum computer is the fragility of
quantum states. The interaction of a quantum system with its surrounding environment
leads to decoherence—the loss of quantum superposition and entanglement. Furthermore,
physical quantum gates are imperfect and introduce noise (errors).

5.1 The Need for Quantum Error Correction (QEC)

Classical error correction relies on redundancy, such as making copies of bits (e.g., 0 →
000). If an error flips a bit (001), a majority vote can correct it. However, quantum error
correction faces severe theoretical constraints: 1. No-Cloning Theorem: We cannot
make copies of unknown quantum states. 2. Measurement Collapse: Measuring a
quantum state to check for errors will collapse the superposition, destroying the quantum
information. 3. Continuous Errors: Quantum errors are not just bit-flips; they can be
continuous phase errors or combinations of both.

5.2 The Shor Code

Peter Shor devised the first quantum error-correcting code capable of protecting a single
logical qubit against arbitrary single-qubit errors (both bit-flip X and phase-flip Z errors).
The Shor code encodes 1 logical qubit into 9 physical qubits.
The encoding process first uses a 3-qubit phase-flip code, and then encodes each of
those 3 qubits using a 3-qubit bit-flip code. The logical basis states are defined as:

1
|0L ⟩ = √ (|000⟩ + |111⟩) ⊗ (|000⟩ + |111⟩) ⊗ (|000⟩ + |111⟩) (20)
2 2
1
|1L ⟩ = √ (|000⟩ − |111⟩) ⊗ (|000⟩ − |111⟩) ⊗ (|000⟩ − |111⟩) (21)
2 2

10
 To detect errors without collapsing the logical state, QEC utilizes syndrome mea-
surements. We measure operators (stabilizers) that yield information about what error
occurred without revealing any information about the actual encoded quantum state.
Once the error syndrome is known, the corresponding unitary correction can be applied.

5.3 Fault-Tolerant Quantum Computation

Error correction alone is insufficient if the gates used to perform the error correction
themselves introduce more errors than they fix. Fault-tolerant quantum computing is
a framework for designing circuits such that errors do not cascade uncontrollably. The
Threshold Theorem states that if the physical error rate per gate is below a certain
threshold (typically estimated between 10−3 and 10−2 depending on the architecture and
code), it is possible to perform arbitrarily long quantum computations with arbitrary
precision by increasing the level of encoding.
Surface codes are currently the leading candidates for practical fault tolerance due to
their low error thresholds and requirement for only nearest-neighbor interactions on a 2D
grid of qubits.

6 Physical Implementations
Building a quantum computer requires satisfying DiVincenzo’s criteria: well-characterized
qubits, long coherence times, universal gate operations, ability to initialize states, and
capability to measure states accurately.
Several physical platforms are actively being developed:

• Superconducting Qubits: Based on nonlinear LC circuits using Josephson junc-

tions operating at millikelvin temperatures. They offer fast gate times and are
heavily pursued by IBM, Google, and Rigetti.

• Trapped Ions: Atomic ions confined in vacuum using electromagnetic fields and
manipulated using highly tuned lasers. They boast extremely long coherence times
and high-fidelity gates but face challenges in scaling interconnects (e.g., IonQ,
Quantinuum).

• Photonic Qubits: Information is encoded in the polarization, path, or arrival

time of single photons. Photons do not interact with each other easily, making
them ideal for communication but challenging for implementing two-qubit logic
gates (e.g., PsiQuantum).

• Topological Qubits: A more theoretical approach aiming to encode information in

11
 non-Abelian anyons, leveraging topological properties to achieve intrinsic hardware-
level error protection (e.g., Microsoft).

7 Conclusion
Quantum computation represents a paradigm shift in our understanding of information
processing. By harnessing the strange laws of quantum mechanics, we unlock computa-
tional capabilities previously thought impossible. While profound engineering challenges
remain in the quest for large-scale, fault-tolerant machines, the theoretical foundations
laid out in these notes—from the Hilbert space formalism to complex algorithmic de-
sign—form the bedrock upon which the next generation of computing will be built. The
intersection of physics, computer science, and mathematics will continue to drive this
extraordinary field forward.

12