QUANTUM COMPUTING

LECTURE NOTES
Noise, Error Correction & Quantum Information

Topics Covered:
▸ Graph States and Codes
▸ Quantum Error Correction
▸ Fault-Tolerant Computation
▸ Classical vs. Quantum Information Theory
▸ Quantum Cryptography (BB84, B92, E91)
▸ Quantum Teleportation and Superdense Coding

Primary References:
[T1] Nielsen & Chuang — Quantum Computation and Quantum Information, Cambridge UP, 2010

[T2] Yanofsky & Mannucci — Quantum Computing for Computer Scientists, Cambridge UP, 2008
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

PART I: NOISE AND QUANTUM ERROR CORRECTION

1.1 Introduction to Quantum Noise

Noise is a fundamental challenge in quantum information processing. Unlike classical bits (0 or 1),
quantum states are described by continuous complex amplitudes, making them inherently fragile. Any
unwanted interaction with the environment disturbs the quantum state and introduces errors [T1, Ch.
8-10].

1.1.1 Why Quantum Error Correction Seems Impossible

Three apparent obstacles make quantum error correction seem impossible:
• No-Cloning Theorem: It is impossible to create an identical copy of an unknown quantum state.
Classical redundancy (simply copying bits) cannot be directly applied.
• Measurement Collapses States: Measuring a qubit to check for errors destroys the quantum
superposition we are trying to protect.
• Continuous Error Space: While classical bits suffer only bit-flips, a qubit can be rotated by any
angle in the Bloch sphere — an apparently continuous infinity of errors.

Key Point: Despite these obstacles, quantum error correction IS possible. The key insight (Nielsen &
Chuang, Sec. 10.3) is that the continuum of quantum errors can be discretised — correcting just a finite set
of basis errors automatically corrects ALL possible errors.

1.1.2 Types of Quantum Errors

For a single qubit the three fundamental error operators correspond to the Pauli matrices. Any
single-qubit error can be written as a linear combination of {I, X, Y, Z}:

Error Type Operator and Effect

Bit-flip (X error) X|0> = |1>, X|1> = |0> — flips the computational basis
state

Phase-flip (Z error) Z|0> = |0>, Z|1> = -|1> — negates the amplitude of

|1>

Bit-phase flip (Y error) Y = iXZ — combination of both bit-flip and phase-flip

No error (Identity) I|psi> = |psi> — qubit remains completely undisturbed

Exam Tip: In exams: {I, X, Y, Z} spans all 2x2 matrices. Correcting these four types automatically corrects
ALL single-qubit errors because any error E can be expanded as E = eI*I + eX*X + eY*Y + eZ*Z.

1.2 Graph States and Codes

1.2.1 Classical Linear Codes (Foundation)

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 2
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

Before studying quantum codes we review classical linear codes, which provide the algebraic foundation
for quantum error correction [T1, Sec. 10.4.1].

Classical Linear Code — Definition [T1, Sec. 10.4.1]

An [n, k] linear code encodes k logical bits into n physical bits (n > k).
Defined by:
Generator matrix G: c = G * m (maps k-bit message m to n-bit codeword c)
Parity-check matrix H: H * c = 0 (mod 2) for all valid codewords c
Minimum distance d: smallest Hamming weight of any non-zero codeword
An [n, k, d] code detects (d-1) errors and corrects floor((d-1)/2) errors.
Example: Hamming [7,4,3] code — encodes 4 bits in 7, corrects any 1-bit error.

1.2.2 Graph States — Definition and Construction

A graph state is a multi-qubit quantum state defined by a mathematical graph G = (V, E), where V is the
set of vertices (qubits) and E is the set of edges (entangling interactions). Graph states underlie
stabiliser codes and measurement-based quantum computation [T1, Ch. 10].

Constructing a Graph State

Step 1. Assign one qubit to each vertex v in V.
Initialise every qubit in |+> = (|0> + |1>) / sqrt(2).
Step 2. For each edge (a, b) in E apply a Controlled-Z (CZ) gate:
CZ = diag(1, 1, 1, -1) in the {|00>, |01>, |10>, |11>} basis.
The resulting state |G> satisfies stabiliser conditions for each vertex a:
Ka |G> = +|G>
Ka = Xa (tensor) Zb1 Zb2 ... Zbm
where b1,...,bm are the neighbours of vertex a in the graph.
All generators {Ka} commute with each other (even X/Z overlap).
The graph state is fully characterised by these stabiliser generators.

Key Point: Graph states form a universal resource for measurement-based quantum computation. Any
quantum circuit can be performed by preparing a suitable graph state, then making adaptive single-qubit
measurements in chosen bases.

1.2.3 Graph Codes

Graph states yield quantum error-correcting codes by partitioning the vertices into input vertices
(logical qubits encoding information) and syndrome/output vertices (ancilla qubits used to extract
error syndromes). The adjacency matrix of the graph directly gives the check matrix of the
corresponding stabiliser code — a clean correspondence that makes graph codes easy to visualise and
analyse.

1.3 Quantum Error Correction

1.3.1 The Three-Qubit Bit-Flip Code

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 3
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

The simplest quantum error-correcting code protects one logical qubit against a single bit-flip error
using three physical qubits [T1, Sec. 10.1.1]:

Three-Qubit Bit-Flip Code [T1, Sec. 10.1.1]

Encoding:
|0>_L --> |000>
|1>_L --> |111>
alpha|0> + beta|1> --> alpha|000> + beta|111>
Error Syndrome (measure Z1Z2 and Z2Z3 using ancilla qubits):
Syndrome (Z1Z2, Z2Z3) | Error | Correction
(+1, +1) | None | Apply I
(-1, +1) | X on qubit 1 | Apply X1
(-1, -1) | X on qubit 2 | Apply X2
(+1, -1) | X on qubit 3 | Apply X3
The syndrome reveals WHICH qubit flipped without revealing alpha or beta.
This is the central trick: extract error information with no information leakage.

Exam Tip: The syndrome measurement commutes with the logical operators X_L and Z_L. It extracts error
information without collapsing the encoded superposition alpha|000> + beta|111>. This is precisely what
makes quantum error correction possible.

1.3.2 The Three-Qubit Phase-Flip Code

Phase-flip (Z) errors are corrected by a code working in the Hadamard-rotated basis [T1, Sec. 10.1.2]:

Three-Qubit Phase-Flip Code [T1, Sec. 10.1.2]

Encoding (apply H to each qubit of the bit-flip encoding):
|0>_L --> |+++> = (|0>+|1>) x (|0>+|1>) x (|0>+|1>) / (2*sqrt(2))
|1>_L --> |--->
A Z error on any qubit flips one |+> to |->, detectable by measuring X1X2 and X2X3.
Syndrome (X1X2, X2X3) | Error | Correction
(+1, +1) | None | Apply I
(-1, +1) | Z on qubit 1 | Apply Z1
(-1, -1) | Z on qubit 2 | Apply Z2
(+1, -1) | Z on qubit 3 | Apply Z3

1.3.3 The Shor Code — Full Single-Qubit Error Correction

The Shor code [T1, Sec. 10.2] is a 9-qubit code that protects against ALL single-qubit errors (bit-flip,
phase-flip, and arbitrary rotations) using a two-level hierarchical construction:

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 4
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

Shor Code Construction [T1, Sec. 10.2]

Level 1 — Phase-flip protection (3-qubit outer code):
|0>_L --> (|000> + |111>) / sqrt(2)
|1>_L --> (|000> - |111>) / sqrt(2)
Level 2 — Bit-flip protection of each block (3-qubit inner code):
Each of the 3 qubits from Level 1 is itself encoded into 3 physical qubits.
Final encoding uses 9 physical qubits for 1 logical qubit.
|0>_L = (1/(2*sqrt(2))) * (|000>+|111>) x (|000>+|111>) x (|000>+|111>)
|1>_L = (1/(2*sqrt(2))) * (|000>-|111>) x (|000>-|111>) x (|000>-|111>)
Corrects: any single-qubit error E = eI*I + eX*X + eY*Y + eZ*Z.
The outer code corrects Z errors; the inner code corrects X errors.
Y = iXZ errors are corrected by both levels working together.

Key Point: The Shor code proved quantum error correction is possible. The crucial insight: any single-qubit
error expands in the Pauli basis, so correcting the discrete set {I, X, Y, Z} automatically corrects the entire
continuous family of errors.

1.3.4 General Theory — QEC Conditions

Nielsen and Chuang (Sec. 10.3) derive the general conditions for quantum error correction. These
characterise exactly when a set of errors can be corrected:

Quantum Error-Correction (QEC) Conditions [T1, Sec. 10.3]

A quantum code with projector P onto the code space corrects errors {Ek} if
and only if for ALL pairs of errors Ei, Ej in the set:
P * Ei_dagger * Ej * P = alpha_ij * P
where alpha_ij is a Hermitian matrix of complex constants.
(alpha_ij is independent of the specific code state.)
Two consequences:
1. NON-DEFORMABILITY: <psi_a| Ei_dagger Ej |psi_b> is the same for ANY
two code states |psi_a>, |psi_b>. All code states experience errors
identically, so correcting one state corrects them all.
2. ERROR DISTINGUISHABILITY: When alpha_ij is diagonal, different errors map
code states to orthogonal (distinguishable) subspaces.

1.3.5 Discretisation of Errors

Key Point: Discretisation Theorem [T1, Sec. 10.3.1]: If a code corrects errors {Ei}, it automatically corrects
any error in the linear span of the Ei. Therefore, correcting only {I, X, Y, Z} on each qubit is sufficient to
correct ALL single-qubit errors.

This collapses the apparently continuous problem of quantum error correction to a finite digital problem
— exactly analogous to classical error correction.

1.3.6 CSS Codes — Calderbank-Shor-Steane Construction

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 5
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

CSS codes [T1, Sec. 10.4.2] construct quantum codes directly from pairs of classical codes, separating
X-error and Z-error correction:

CSS Code Construction [T1, Sec. 10.4.2]

Given two classical binary linear codes C2 subset_of C1:
C1 = [n, k1] with parity-check matrix H1
C2 = [n, k2] with parity-check matrix H2
Requirement: H1 * H2_transpose = 0 (rows are orthogonal)
The CSS code CSS(C1, C2) is an [[n, k1-k2]] quantum code:
X-type stabilisers: rows of H2 --> detect Z errors
Z-type stabilisers: rows of H1 --> detect X errors
Logical codewords: cosets of C2 in C1
Steane [7,1,3] code: built from the Hamming [7,4,3] code and its dual [7,3,4].
Encodes 1 logical qubit in 7 physical qubits; corrects any single-qubit error.

Exam Tip: CSS codes separate X- and Z-error correction. X errors are detected by Z-type stabilisers (which
anticommute with X), and vice versa. CNOT gates are transversal for all CSS codes, making them ideal for
fault-tolerant implementations.

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 6
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

1.4 Stabiliser Codes

1.4.1 The Stabiliser Formalism

The stabiliser formalism [T1, Sec. 10.5] provides a compact classical description of a large class of
quantum codes without tracking exponentially many amplitudes:

Stabiliser Codes — Formal Definition [T1, Sec. 10.5.1]

The n-qubit Pauli group G_n: all n-fold tensor products of {I, X, Y, Z}
with overall phases +1, -1, +i, -i.
An [[n, k]] stabiliser code is defined by an abelian subgroup S of G_n,
generated by (n-k) independent, mutually commuting Pauli operators g1, ..., g_{n-k}.
Code space: V_S = { |psi> : g|psi> = +|psi> for all g in S }
Requirements:
[gi, gj] = 0 (all generators commute)
-I not in S (otherwise the code space is empty)
Dimension of code space: 2^k (encodes k logical qubits in n physical qubits)
Logical operators X_L, Z_L: commute with all g in S but are NOT themselves in S.

1.4.2 Steane Seven-Qubit Code

The Steane [[7, 1, 3]] code [T1, Sec. 10.5.1] encodes 1 logical qubit in 7 physical qubits with distance d
= 3, correcting any single-qubit error. Its 6 stabiliser generators are:

Generator Stabiliser Operator Type

g1 IIIXXXX X-type (detects Z errors)

g2 IXXIIXX X-type (detects Z errors)

g3 XIXIXIX X-type (detects Z errors)

g4 IIIZZZZ Z-type (detects X errors)

g5 IZZIIZZ Z-type (detects X errors)

g6 ZIZIZIZ Z-type (detects X errors)

Logical operators: X_L = X X X X X X X and Z_L = Z Z Z Z Z Z Z (apply to all 7 qubits).

The 6-bit syndrome uniquely identifies all 42 correctable single-qubit Pauli errors (7 qubits x 6 Pauli
types). The check matrix H = [A | B] is a 6x14 binary matrix: first 7 columns encode X-parts; last 7
columns encode Z-parts.

1.4.3 Syndrome Measurement and Error Recovery

Error correction in stabiliser codes proceeds in two stages:
1. Syndrome Measurement: Measure each generator gi using ancilla qubits. Each measurement
gives +1 or -1. The complete syndrome vector s = (s1, ..., s_{n-k}) uniquely identifies the error for a
distance-3 code.

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 7
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

2. Recovery Operation: Look up the syndrome in a correction table and apply the corresponding Pauli
correction. Since P^2 = I for Pauli operators, applying the identified error operator again undoes the
error.

Exam Tip: The syndrome is a classical bit string processed by a classical computer. Only the final correction
needs to be applied as a quantum gate. This hybrid quantum-classical structure is essential for all practical
implementations of quantum error correction.

1.5 Fault-Tolerant Quantum Computation

1.5.1 The Need for Fault Tolerance

Error correction alone is insufficient. The gates and measurements used to perform error correction may
themselves introduce errors. A single fault in an error-correction step could spread to multiple qubits,
defeating the code's protection. Fault-tolerant computation addresses this at every level [T1, Sec. 10.6].

Key Point: Fault-tolerance principle: If any single component fails with probability p, the probability the
overall procedure causes a LOGICAL error is O(p^2). A single fault must never propagate to an uncorrectable
multi-qubit error.

1.5.2 Transversal Gates

Transversal gates are the primary tool for fault-tolerant gate implementation. A gate is transversal if it
acts independently on corresponding qubits across code blocks, with no interactions between qubits
within the same block [T1, Sec. 10.6]:

Transversal Gates for the Steane [[7,1,3]] Code [T1, Sec. 10.6]
X_L : Apply X to all 7 qubits --> X^(tensor 7)
Z_L : Apply Z to all 7 qubits --> Z^(tensor 7)
H_L : Apply H to all 7 qubits --> H^(tensor 7) (swaps X and Z stabilisers)
CNOT_L: Apply CNOT between corresponding qubits of two separate code blocks.
Why transversal implies fault tolerant:
A single gate fault on qubit j causes at most ONE error in the code block.
The code can correct this single error before it propagates further.
NOT transversal (require special circuits): T gate, Toffoli gate.
These are handled via magic state distillation.

1.5.3 The Threshold Theorem

The most important theoretical result in fault-tolerant quantum computation:

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 8
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

The Fault-Tolerance Threshold Theorem [T1, Sec. 10.6]

There exists a threshold error rate p_th such that:
IF the error rate per physical gate p < p_th,
THEN arbitrarily long quantum computations can be performed
with arbitrarily small failure probability,
using only a POLYLOGARITHMIC overhead in gates and qubits.
Typical threshold estimates:
p_th ~ 10^(-4) (conservative, local depolarising noise model)
p_th ~ 10^(-2) (optimistic, with optimised code and decoding)
For Steane code with L levels of concatenation:
p_eff(L) = p_th * (p / p_th)^(2^L) -- double-exponential suppression
To achieve final error probability epsilon:
L = O(log log(1/epsilon)) levels needed.
Total qubits: n^L = poly(log(1/epsilon)) -- polylogarithmic overhead.

Exam Tip: The Threshold Theorem is the most important result in quantum computing. It proves scalable
quantum computation is physically possible provided hardware reaches sufficient quality. Know: the
statement, what p_th means, and why concatenated codes achieve double-exponential error suppression.

1.5.4 Universal Fault-Tolerant Gate Set

Transversal gates alone cannot form a universal gate set (true for ANY quantum error-correcting code).
A universal fault-tolerant set requires at least one non-transversal gate, typically the T gate via magic
state distillation:

Gate Fault-Tolerant Implementation

Pauli X, Y, Z Transversal — apply to all qubits in code block

Hadamard H Transversal for CSS codes; maps X-type to Z-type

stabilisers

Phase S = diag(1, i) Transversal for Reed-Muller codes

CNOT Transversal between two code blocks (bitwise CNOT)

T gate (pi/8) Magic state distillation — most resource intensive step

Toffoli (CCX) Constructed from T gates and Clifford gates

Key Point: {H, CNOT, T} is a universal fault-tolerant gate set. The T gate is the bottleneck: it requires magic
state distillation, so minimising T-gate count is a central optimisation goal in fault-tolerant quantum circuit
design.

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 9
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

PART II: QUANTUM INFORMATION AND CRYPTOGRAPHY

2.1 Classical Information Theory

2.1.1 Shannon Entropy

Shannon entropy [T1, Sec. 11.1; T2, Sec. 10.1] quantifies the average uncertainty or information content
of a probability distribution. It is the foundation of all classical information theory.

Shannon Entropy — Definition [T1, Sec. 11.1]

For a discrete random variable X with probability distribution {p_x}:
H(X) = - SUM_x p_x * log2(p_x) [units: bits]
Convention: 0 * log2(0) = 0
Key Properties:
Positivity: H(X) >= 0, equality iff one outcome is certain
Maximum: H(X) <= log2(|X|), equality iff X is uniform
Subadditivity: H(X,Y) <= H(X) + H(Y), equality iff X and Y independent
Chain rule: H(X,Y) = H(X) + H(Y|X)
Concavity: H is a concave function of {p_x}

2.1.2 Derived Quantities in Classical Information Theory

Quantity Formula and Interpretation

Joint entropy H(X,Y) H(X,Y) = -SUM_{x,y} p(x,y) log p(x,y) uncertainty in the
pair (X,Y)

Conditional entropy H(Y|X) H(Y|X) = H(X,Y) - H(X) >= 0 residual uncertainty in Y

given X

Mutual information I(X;Y) I(X;Y) = H(X)+H(Y)-H(X,Y) >= 0 information shared by X

and Y

Relative entropy H(p||q) H(p||q) = SUM p(x)*log(p(x)/q(x)) >= 0 distinguishability

of p from q

2.1.3 Shannon's Channel Coding Theorem

Shannon's Noisy Channel Coding Theorem [T1, Sec. 12.3.1]

Channel capacity: C = max_{input distribution p(x)} I(X;Y) bits per use
Achievability: For any rate R < C, codes exist that communicate reliably
(error probability --> 0 as block length n --> infinity).
Converse: No code can communicate reliably at rate R > C.
Example — Binary Symmetric Channel (BSC) with flip probability p:
C_BSC = 1 - H_bin(p) = 1 + p*log2(p) + (1-p)*log2(1-p)

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 10
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

2.2 Quantum Information Theory

2.2.1 Von Neumann Entropy

Von Neumann entropy [T1, Sec. 11.3; T2, Sec. 10.2] is the quantum generalisation of Shannon entropy,
defined for density matrices:

Von Neumann Entropy [T1, Sec. 11.3]

For a density matrix rho with eigenvalues lambda_1, ..., lambda_d:
S(rho) = -Tr( rho * log2(rho) ) = - SUM_i lambda_i * log2(lambda_i)
Properties:
S(rho) >= 0, equality iff rho is a PURE STATE (S(|psi><psi|) = 0)
S(rho) <= log2(d), equality iff rho = I/d (maximally mixed state)
Unitary invariance: S(U*rho*U_dagger) = S(rho) for any unitary U
Subadditivity: S(A,B) <= S(A) + S(B)
Strong subadditivity: S(A,B,C) + S(B) <= S(A,B) + S(B,C)
Entanglement entropy: For a PURE bipartite state |psi>_AB, S(rho_A) = S(rho_B).
This equals zero iff the state is a product state (unentangled).

2.2.2 Classical vs. Quantum Information — Key Comparisons

Property Classical (Shannon) Quantum (Von Neumann)

Unit of information Bit (0 or 1) Qubit (superposition)

Entropy measure H(X) = -SUM p_x log p_x S(rho) = -Tr(rho log rho)

State copying Freely possible No-Cloning Theorem: IMPOSSIBLE

State distinguishing Always possible in principle Impossible for non-orthogonal states

Data compression H(X) bits/symbol (Shannon) S(rho) qubits/qubit (Schumacher)

Conditional entropy H(Y|X) = H(X,Y)-H(X) >=0 always S(A|B) = S(A,B)-S(B) CAN BE

NEGATIVE!

Channel capacity C = max I(X;Y) (Shannon theorem) C = max chi (HSW theorem)

Error correction Classical codes (Hamming, BCH) Quantum codes (Steane, Shor, CSS)

Key Point: Most striking quantum/classical difference: conditional von Neumann entropy S(A|B) can be
NEGATIVE for entangled states. This has no classical analogue and directly reflects non-classical correlations.
It underlies the power of quantum communication protocols such as superdense coding and teleportation.

2.2.3 The Holevo Bound

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 11
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

Holevo Bound [T1, Sec. 12.1.1]

Suppose Alice sends Bob one of the quantum states {rho_x} with probability p_x.
Bob performs any POVM measurement to identify x.
The accessible information (maximum extractable mutual information) satisfies:
I_acc <= chi = S( SUM_x p_x * rho_x ) - SUM_x p_x * S(rho_x)
chi is the Holevo quantity.
Consequence: n qubits cannot transmit more than n bits of classical information
(even with the best possible measurement strategy).
Exception: Superdense coding sends 2 bits per qubit using pre-shared
entanglement as an additional resource beyond the qubit channel itself.

2.2.4 Schumacher Quantum Data Compression

Schumacher Compression Theorem [T1, Sec. 12.2.2]

For a quantum source emitting pure states |psi_x> with probability p_x,
with ensemble density matrix rho = SUM_x p_x |psi_x><psi_x|:
Can compress to S(rho) qubits per source output with vanishing error.
Cannot compress reliably below S(rho) qubits per source output.
Method: Project onto the 'typical subspace' -- the subspace spanned by
eigenvectors of rho with eigenvalues in the typical range.
This is the exact quantum analogue of Shannon's typical sequences approach.

2.3 Quantum Cryptography

2.3.1 Classical Cryptography and Quantum Threats

Classical Protocol Quantum Threat

RSA encryption Shor's algorithm factors integers in polynomial time —

BROKEN by large QC

Diffie-Hellman key exchange Shor's algorithm solves discrete logarithm — BROKEN by

large QC

AES-128 symmetric key Grover's algorithm halves security — key length must
double to 256 bits

AES-256 symmetric key Grover gives sqrt speedup — still adequate security at
256 bits

One-Time Pad (OTP) Provably secure — but secure key distribution remains
the problem!

2.3.2 BB84 Protocol — Complete Description

The BB84 protocol (Bennett and Brassard, 1984) [T1, Sec. 12.6; T2, Sec. 9.2] allows two parties to
establish a shared secret key with information-theoretic security — guaranteed by the laws of physics,
not mathematical hardness:

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 12
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

BB84 Protocol — Step by Step [T2, Sec. 9.2]

Setup: Alice and Bob share a quantum channel plus a public classical channel.
Encoding convention (4 states, 2 conjugate bases):
Plus basis (+): bit 0 = vertical polarisation, bit 1 = horizontal
Times basis (x): bit 0 = diagonal (+45 deg), bit 1 = anti-diagonal (-45 deg)
STEP 1 — Quantum transmission:
Alice randomly picks a bit value (0 or 1) AND a basis (+ or x) for each qubit.
She encodes the corresponding qubit and sends it to Bob.
STEP 2 — Bob measures:
Bob randomly picks a basis (+ or x) and measures each received qubit.
Bases match (50% of cases): Bob gets Alice's bit with certainty.
Bases differ (50% of cases): Bob gets a random, uncorrelated bit.
STEP 3 — Basis reconciliation (public classical channel):
Alice and Bob announce their BASES (not bit values) for each qubit.
They keep only the bits where bases agreed -- the 'sifted key' (~50%).
STEP 4 — Eavesdropping detection:
Publicly compare a random subset of sifted-key bits.
If QBER (quantum bit error rate) > ~11%: ABORT -- eavesdropper detected.
STEP 5 — Information reconciliation:
Apply classical error-correction to fix any small discrepancies.
STEP 6 — Privacy amplification:
Hash the reconciled key to eliminate any partial information Eve may hold.
Result: final, provably secure shared secret key.

2.3.3 Security of BB84

The security of BB84 rests on two fundamental quantum mechanical principles:
• Non-orthogonal state indistinguishability: The four BB84 states form two non-orthogonal bases.
No measurement can perfectly distinguish between non-orthogonal states without introducing
unavoidable disturbance, which Alice and Bob can detect.
• No-Cloning Theorem: Eve cannot copy an unknown qubit and forward a perfect replica. Any
interception disturbs the original qubit and introduces detectable errors.

BB84 Security Result [T1, Sec. 12.6]

If the observed quantum bit error rate (QBER) is Q, then:
Maximum information Eve can hold about the sifted key <= chi(Q) (Holevo bound).
After privacy amplification removing r bits:
I(Eve; FinalKey) <= 2^(-r) -- exponentially small.
Unconditional security: Secure against any attack by an eavesdropper with
UNLIMITED computational power AND quantum computers,
as long as QBER < threshold ~ 11% for standard BB84.
This is INFORMATION-THEORETIC security -- not based on computational hardness.

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 13
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

Exam Tip: Know the difference: information-theoretic security (BB84 — secure even against unlimited
computation) vs. computational security (RSA — secure only because factoring is believed to be
computationally hard). Exam questions often ask you to explain this distinction clearly.

2.3.4 B92 Protocol

B92 Protocol (Bennett, 1992) [T2, Sec. 9.3]

Uses only TWO non-orthogonal states (simpler than BB84's four states):
Bit 0: |0> = [1, 0]^T (vertical polarisation)
Bit 1: |+> = (1/sqrt(2)) * [1, 1]^T (diagonal -- NOT orthogonal to |0>)
Bob randomly measures in Z-basis or X-basis.
Key bit kept only when Bob gets a definitive, unambiguous result:
Z-basis result |1> --> Alice must have sent |+> (bit = 1). KEEP.
X-basis result |-> --> Alice must have sent |0> (bit = 0). KEEP.
Ambiguous result --> DISCARD.
Advantage: Uses only 2 states -- simpler hardware requirements.
Disadvantage: ~25% key generation rate compared to ~50% for BB84.

2.3.5 E91 Protocol — Entanglement-Based QKD

E91 Protocol (Ekert, 1991) [T2, Sec. 9.4]

Source generates Bell pairs: |Phi+> = (|00> + |11>) / sqrt(2).
Alice receives qubit A, Bob receives qubit B, from each pair.
Key generation: When Alice and Bob measure in the SAME randomly chosen basis,
their results are perfectly correlated. These form the shared secret key.
Security test using MISMATCHED measurements -- compute CHSH correlator S:
S = | E(a,b) - E(a,b') + E(a',b) + E(a',b') |
Quantum mechanics: S = 2*sqrt(2) ~ 2.83 (Bell inequality VIOLATED)
Classical local realism: S <= 2 (Bell inequality satisfied)
If S ~ 2*sqrt(2): No classical eavesdropper can explain the correlations.
The key is guaranteed secure by the Bell inequality violation itself.
If S ~ 2: Eve has interfered -- ABORT.
Key advantage: Device-independent security -- secure even if the measuring
devices themselves are untrusted (the Bell test certifies entanglement).

Exam Tip: Know all three QKD protocols: BB84 (4 states, 2 bases, most practical), B92 (2 non-orthogonal
states, lower efficiency), E91 (entangled pairs, Bell inequality test). All three provide information-theoretic
security via different quantum mechanical mechanisms.

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 14
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

2.4 Quantum Teleportation

2.4.1 Introduction and Motivation

Quantum teleportation [T1, Sec. 1.3.7; T2, Sec. 9.5] transmits an unknown quantum state |psi> from
Alice to Bob using only classical communication and a pre-shared entangled pair. It seems paradoxical:
an unknown quantum state containing potentially infinite information is transferred using only 2
classical bits.

Key Point: Resolution of the paradox: The 2 classical bits alone cannot recover |psi> — Bob also needs the
pre-shared entangled qubit. The entanglement 'amplifies' the 2 classical bits into full quantum state transfer.
Resource accounting: 1 ebit + 2 classical bits --> 1 qubit of channel capacity.

2.4.2 Bell States — Prerequisites

The Four Bell States [T2, Sec. 9.5]

|Phi+> = (|00> + |11>) / sqrt(2) <-- shared pair used in teleportation
|Phi-> = (|00> - |11>) / sqrt(2)
|Psi+> = (|01> + |10>) / sqrt(2)
|Psi-> = (|01> - |10>) / sqrt(2)
These four states form an orthonormal basis for C^2 (x) C^2 (the Bell basis).
Bell circuit (creates Bell states from computational basis):
|00> --> apply H on first qubit, then CNOT --> |Phi+>
|01> --> apply H on first qubit, then CNOT --> |Phi->
|10> --> apply H on first qubit, then CNOT --> |Psi+>
|11> --> apply H on first qubit, then CNOT --> |Psi->

2.4.3 Teleportation Protocol — Full Mathematical Derivation

Teleporting state |psi> = alpha|0> + beta|1> from Alice to Bob [T2, Sec. 9.5]:

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 15
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

Quantum Teleportation — Complete Derivation [T2, Sec. 9.5]

SETUP:
Qubit 1: Alice's unknown state |psi>_1 = alpha|0> + beta|1>
Qubits 2, 3: Shared Bell pair |Phi+>_23 = (|00>+|11>) / sqrt(2)
Alice holds qubits 1 and 2; Bob holds qubit 3.
Initial 3-qubit state:
|PHI_0> = |psi>_1 (x) |Phi+>_23
= (alpha|0> + beta|1>) * (|00> + |11>) / sqrt(2)
STEP 1 — Alice applies CNOT (control = qubit 1, target = qubit 2):
|PHI_1> = (1/sqrt(2)) * [alpha|0>(|00>+|11>) + beta|1>(|10>+|01>)]
STEP 2 — Alice applies Hadamard to qubit 1:
|PHI_2> = (1/2) * [|00>(alpha|0>+beta|1>) + |01>(beta|0>+alpha|1>)
+ |10>(alpha|0>-beta|1>) + |11>(-beta|0>+alpha|1>)]
STEP 3 — Alice measures qubits 1 and 2 (result: m1, m2). 4 outcomes, each prob = 1/4.
STEP 4 — Bob's qubit collapses to one of four states:
m1=0, m2=0 --> alpha|0> + beta|1> = |psi> (apply I to recover |psi>)
m1=0, m2=1 --> beta|0> + alpha|1> = X|psi> (apply X to recover |psi>)
m1=1, m2=0 --> alpha|0> - beta|1> = Z|psi> (apply Z to recover |psi>)
m1=1, m2=1 --> -beta|0> + alpha|1> = XZ|psi> (apply ZX to recover |psi>)
STEP 5 — Alice sends 2 classical bits (m1, m2) to Bob via public channel.
STEP 6 — Bob applies correction Z^{m1} * X^{m2} and recovers |psi> exactly.

2.4.4 Key Properties and Limitations

• No faster-than-light communication: Bob cannot recover |psi> until he receives the 2 classical
bits from Alice. The protocol cannot exceed the speed of light.
• No-Cloning preserved: Alice's qubit is destroyed in the measurement step. At no point do two
copies of |psi> exist simultaneously.
• Entanglement consumed: One pre-shared ebit is used per teleportation. Fresh entangled pairs
must be distributed for future teleportations.
• Experimental realisation: Quantum teleportation has been demonstrated over distances exceeding
1400 km via satellite-based quantum channels.

2.4.5 Superdense Coding — The Dual Protocol

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 16
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

Superdense Coding [T1, Sec. 2.3]

Dual of teleportation: 1 ebit + 1 qubit transmitted --> 2 classical bits.
Alice and Bob share |Phi+> = (|00>+|11>) / sqrt(2).
Alice applies one of 4 operations to HER qubit only:
Bits 00 --> apply I --> shared state remains |Phi+>
Bits 01 --> apply X --> shared state becomes |Psi+>
Bits 10 --> apply Z --> shared state becomes |Phi->
Bits 11 --> apply iY --> shared state becomes |Psi->
Alice sends her ONE qubit to Bob.
Bob applies the inverse Bell circuit and measures — recovers both bits exactly.
Resource summary: 1 ebit + 1 qubit --> 2 classical bits.

Exam Tip: Resource duality (essential exam knowledge): (a) Teleportation: 1 ebit + 2 cbits --> 1 qubit of
channel capacity. (b) Superdense Coding: 1 ebit + 1 qubit --> 2 cbits. These are the two fundamental
exchange rates between quantum and classical communication resources.

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 17
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

2.5 Comprehensive Exam Review Summary

Quick Reference: Error-Correcting Codes

Code Parameters Corrects

3-qubit bit-flip [[3, 1, 1]] Single X error on any one qubit

3-qubit phase-flip [[3, 1, 1]] Single Z error on any one qubit

Shor code [[9, 1, 3]] Any single-qubit error (X, Y, Z)

Perfect 5-qubit [[5, 1, 3]] Any single-qubit error (smallest n)

Steane code [[7, 1, 3]] Any single-qubit error; CSS structure

General [[n,k,d]] k logical in n physical qubits Up to floor((d-1)/2) arbitrary errors

Quick Reference: QKD Protocols

Protocol Key Features Security Basis

BB84 (1984) 4 states, 2 conjugate bases; error Non-orthogonality + No-Cloning

rate check; most practical

B92 (1992) 2 non-orthogonal states; ~25% key Non-orthogonality + No-Cloning

rate; simpler hardware

E91 (1991) Entangled pairs; Bell inequality test; Bell inequality violation
device-independent

Quick Reference: Classical vs. Quantum Entropy

Classical (Shannon) Quantum (Von Neumann)

H(X) = -SUM p_x * log2(p_x) S(rho) = -Tr( rho * log2(rho) )

H(X) >= 0 always S(rho) >= 0 always

H(X) <= log2(|X|) S(rho) <= log2(d) where d = Hilbert space dimension

H(Y|X) = H(X,Y) - H(X) >= 0 ALWAYS S(A|B) = S(A,B) - S(B) CAN BE NEGATIVE
(entanglement!)

Shannon noiseless coding: H(X) bits per symbol Schumacher theorem: S(rho) qubits per qubit

Shannon noisy coding: C = max I(X;Y) HSW theorem: C = max chi (Holevo quantity)

Compression via typical sequences Compression via typical subspace

Top 10 Most Frequently Tested Concepts

1. QEC Conditions: P * Ei_dagger * Ej * P = alpha_ij * P -- know what each symbol means and why this
condition enables error correction.
2. Stabiliser formalism: Define stabiliser group S, code space V_S, logical operators; identify code
dimension (2^k for n-k generators on n qubits).

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 18
QUANTUM COMPUTING LECTURE NOTES | Noise, Error Correction & Quantum Information

3. Discretisation theorem: Correcting {I, X, Y, Z} corrects ALL single-qubit errors -- explain the linear
span argument.
4. Threshold theorem: State it precisely; explain p_th, why p < p_th suffices, and how concatenated
codes achieve double-exponential suppression.
5. BB84 step-by-step: Be able to trace through a worked example and explain exactly why
eavesdropping introduces detectable errors.
6. Teleportation derivation: All 6 steps with full state evolution; know the resource count: 1 ebit + 2
cbits --> 1 qubit.
7. Von Neumann vs. Shannon: Key differences, especially that S(A|B) can be negative and what that
means physically.
8. No-Cloning implications: How it enables QKD security; why teleportation does NOT violate it (the
original state is destroyed).
9. Holevo bound: I_acc <= chi; n qubits cannot carry more than n classical bits without pre-shared
entanglement.
10. Shor code structure: Two-level construction -- why it corrects arbitrary single-qubit errors via the
Pauli basis expansion argument.

References
[T1] Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information, 10th Anniversary Edition.
Cambridge University Press, 2010.
[T2] Yanofsky, N. S. & Mannucci, M. A. Quantum Computing for Computer Scientists. Cambridge University
Press, 2008.

Ref: [T1] Nielsen & Chuang (2010) [T2] Yanofsky & Mannucci (2008) Page 19