Why Quantum Computing?
Classical computers have served us extraordinarily well for decades, following Moore's Law in doubling transistor density roughly every 18–24 months. But as transistors approach the atomic scale, quantum mechanical effects — once a nuisance — become dominant. Quantum computing is not simply "faster classical computing"; it is a fundamentally different computational paradigm that exploits quantum phenomena to perform certain computations that are provably intractable on classical hardware.
A classical bit is either 0 or 1. A qubit can exist in a superposition of both simultaneously. Crucially, $n$ qubits can encode $2^n$ amplitudes simultaneously — an exponential advantage in state-space representation.
The State Space Argument
To describe the state of $n$ classical bits, you need $n$ numbers (each 0 or 1). To describe the state of $n$ qubits, you generally need $2^n$ complex amplitudes.
Explore the mathematics of the $2^n$ state space
For $n = 300$, this is $2^{300}$ — far more than the estimated number of atoms in the observable universe ($\approx 10^{80}$). Classical computers cannot even store a general 300-qubit state, let alone simulate its evolution.
This exponential state space is precisely what quantum algorithms harness. By carefully engineering interference — amplifying paths leading to correct answers and cancelling paths leading to wrong ones — quantum algorithms can solve specific problems with dramatically fewer operations.
Landmark Quantum Speedups
| Problem | Classical Best | Quantum Best | Speedup |
|---|---|---|---|
| Integer Factoring | $O(e^{n^{1/3}})$ (sub-exp) | $O(n^3)$ (Shor) | Exponential |
| Unstructured Search | $O(N)$ | $O(\sqrt{N})$ (Grover) | Quadratic |
| Simulating Quantum Systems | Exponential | Polynomial | Exponential |
| Discrete Log | $O(e^{n^{1/3}})$ | $O(n^3)$ (Shor) | Exponential |
| Linear Systems (HHL) | $O(N \log N)$ | $O(\text{polylog}(N))$ | Exponential (conditional) |
These are not all equivalent speedups — Grover's is "merely" quadratic, while Shor's factoring is exponential. But in practice, factoring large numbers is the basis of RSA encryption; a scalable quantum computer running Shor's algorithm would break much of modern public-key cryptography.
Physical Implementations
Qubits can be physically realized in many systems, each with trade-offs:
-
SUPERCONDUCTING
IBM, Google — fast gates, short coherence (~100μs) -
TRAPPED ION
IonQ, Quantinuum — long coherence, slower gates -
PHOTONIC
PsiQuantum — room-temp, hard multi-photon gates -
SPIN (SILICON)
Intel — fab-compatible, longer coherence potential
Linear Algebra & Dirac Notation
Quantum mechanics is formulated in the language of linear algebra over the complex numbers. Before we can speak of qubits and gates, we must build fluency with this mathematical language — especially Paul Dirac's elegant bra-ket notation, which makes quantum calculations remarkably compact.
Hilbert Spaces, Vectors, and Inner Products
A Hilbert space $\mathcal{H}$ is a complete inner product space over $\mathbb{C}$. For a single qubit, $\mathcal{H} = \mathbb{C}^2$. For $n$ qubits, $\mathcal{H} = \mathbb{C}^{2^n}$.
A ket $\ket{\psi}$ denotes a column vector in $\mathcal{H}$:
The computational basis for a single qubit consists of two orthonormal vectors:
A general qubit state is a linear combination (superposition) of these basis states: $\ket{\psi} = \alpha\ket{0} + \beta\ket{1}$ where $\alpha, \beta \in \mathbb{C}$.
The Inner Product
The bra $\bra{\psi}$ is the conjugate-transpose (Hermitian conjugate / "dagger") of the ket:
The inner product of $\ket{\phi}$ and $\ket{\psi}$ is the bra-ket:
Key properties of the inner product:
- Conjugate symmetry: $\braket{\phi|\psi} = \braket{\psi|\phi}^*$
- Linearity: $\bra{\phi}(\alpha\ket{\psi_1}+\beta\ket{\psi_2}) = \alpha\braket{\phi|\psi_1}+\beta\braket{\phi|\psi_2}$
- Positive definiteness: $\braket{\psi|\psi} \geq 0$, with equality iff $\ket{\psi} = 0$
- Orthonormality: $\braket{0|0} = \braket{1|1} = 1$, $\braket{0|1} = \braket{1|0} = 0$
The Outer Product and Projection Operators
The outer product $\ket{\psi}\bra{\phi}$ is an operator (matrix) mapping $\mathcal{H} \to \mathcal{H}$:
Notice the key difference from the inner product: a bra times ket $\braket{\phi|\psi}$ produces a scalar (a complex number), while a ket times bra $\ket{\psi}\bra{\phi}$ produces a matrix (an operator). The ordering matters! The outer product $\ket{0}\bra{0}$ is the projection operator onto $\ket{0}$ — it "filters out" the $\ket{0}$-component of any state it acts on. Let's see it in action:
Apply $\ket{0}\bra{0}$ to the state $\ket{+} = \frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$: $$\ket{0}\bra{0}\ket{+} = \ket{0}\braket{0|+} = \ket{0} \cdot \frac{1}{\sqrt{2}} = \frac{1}{\sqrt{2}}\ket{0}$$ The projection extracted only the $\ket{0}$ part of $\ket{+}$ and discarded the $\ket{1}$ part — exactly what "projection" means geometrically (dropping a vector onto an axis and keeping only that component). In matrix form: $$\begin{pmatrix}1&0\\0&0\end{pmatrix}\frac{1}{\sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\0\end{pmatrix} \checkmark$$
The completeness relation states that for any orthonormal basis $\{\ket{i}\}$:
Let's verify this for the computational basis by explicitly summing the two projection matrices:
This identity is perhaps the single most frequently used tool in quantum calculations. Any operator or state can be expanded using it: $\ket{\psi} = \mathbb{I}\ket{\psi} = \sum_i \ket{i}\braket{i|\psi}$, recovering the fact that $\braket{i|\psi}$ is the component of $\ket{\psi}$ along $\ket{i}$.
Operators and Matrices
A linear operator $A: \mathcal{H} \to \mathcal{H}$ is represented as a matrix once we fix a basis. The adjoint (Hermitian conjugate) $A^\dagger$ is defined by $\bra{\phi}A\ket{\psi} = \braket{A^\dagger\phi|\psi}$, i.e., $(A^\dagger)_{ij} = A_{ji}^*$.
Real eigenvalues → physical observables
Preserves norm → quantum gates
Diagonalizable; includes both above
Used in measurement theory
Tensor Products
For a system composed of two subsystems with Hilbert spaces $\mathcal{H}_A$ and $\mathcal{H}_B$, the combined space is the tensor product $\mathcal{H}_A \otimes \mathcal{H}_B$. Concretely, for column vectors:
For operators, the Kronecker product: $(A \otimes B)$ acts as $A$ on the first subsystem and $B$ on the second. The dimension multiplies: $\dim(\mathcal{H}_A \otimes \mathcal{H}_B) = \dim(\mathcal{H}_A) \cdot \dim(\mathcal{H}_B)$. So $n$ qubits live in $(\mathbb{C}^2)^{\otimes n} = \mathbb{C}^{2^n}$.
Dirac Notation Quick Reference
| Notation | Name | Meaning |
|---|---|---|
| $\ket{\psi}$ | Ket | Column vector (state vector) |
| $\bra{\psi}$ | Bra | Row vector = $\ket{\psi}^\dagger$ (conjugate transpose) |
| $\braket{\phi|\psi}$ | Bra-ket (bracket) | Inner product — a complex number |
| $\ket{\psi}\bra{\phi}$ | Ket-bra | Outer product — an operator (matrix) |
| $\bra{\phi}A\ket{\psi}$ | Matrix element | $\braket{\phi|A|\psi}$ — a complex number |
| $\ket{\psi} \otimes \ket{\phi}$ | Tensor product | Joint state, often written $\ket{\psi\phi}$ or $\ket{\psi}\ket{\phi}$ |
Qubits
The quantum bit, or qubit, is the fundamental unit of quantum information. Unlike a classical bit which is definitively 0 or 1, a qubit can exist in any superposition of the two computational basis states $\ket{0}$ and $\ket{1}$.
A qubit state is any unit vector in $\mathbb{C}^2$: $$\ket{\psi} = \alpha\ket{0} + \beta\ket{1}, \quad \alpha, \beta \in \mathbb{C}, \quad |\alpha|^2 + |\beta|^2 = 1$$ The coefficients $\alpha$ and $\beta$ are called probability amplitudes. Upon measurement in the computational basis, the qubit collapses to $\ket{0}$ with probability $|\alpha|^2$ and to $\ket{1}$ with probability $|\beta|^2$.
The constraint $|\alpha|^2 + |\beta|^2 = 1$ means the state must be normalized — probabilities must sum to one. Notice that while $\alpha$ and $\beta$ are complex, the probabilities $|\alpha|^2$ and $|\beta|^2$ are real. The complex phases are not directly observable (a global phase $e^{i\theta}$ has no physical meaning) but relative phases between $\alpha$ and $\beta$ critically matter and drive interference.
The Bloch Sphere
Since an overall global phase is unphysical, we can always write any qubit state as:
where $\theta \in [0, \pi]$ and $\phi \in [0, 2\pi)$. This maps every pure qubit state bijectively to a point on the surface of a unit sphere — the Bloch sphere.
Key special states on the Bloch sphere:
| State | $\theta$ | $\phi$ | Location | Description |
|---|---|---|---|---|
| $\ket{0}$ | $0$ | — | North Pole | Computational basis $\ket{0}$ |
| $\ket{1}$ | $\pi$ | — | South Pole | Computational basis $\ket{1}$ |
| $\ket{+} = \frac{\ket{0}+\ket{1}}{\sqrt{2}}$ | $\pi/2$ | $0$ | +x axis | Equal superposition, phase 0 |
| $\ket{-} = \frac{\ket{0}-\ket{1}}{\sqrt{2}}$ | $\pi/2$ | $\pi$ | -x axis | Equal superposition, phase $\pi$ |
| $\ket{i} = \frac{\ket{0}+i\ket{1}}{\sqrt{2}}$ | $\pi/2$ | $\pi/2$ | +y axis | Equal superposition, phase $\pi/2$ |
| $\ket{-i} = \frac{\ket{0}-i\ket{1}}{\sqrt{2}}$ | $\pi/2$ | $-\pi/2$ | -y axis | Equal superposition, phase $-\pi/2$ |
$\ket{\psi} = \alpha\ket{0} + \beta\ket{1}$ has 4 real degrees of freedom (real and imaginary parts of $\alpha$ and $\beta$). Normalization removes one, and global phase invariance removes another, leaving 2 real degrees of freedom — enough to parameterise a sphere ($S^2$).
More formally: the physical state space is not $\mathbb{C}^2$ but the projective Hilbert space $\mathbb{C}P^1$ (the space of complex lines through the origin in $\mathbb{C}^2$, i.e. rays), which is topologically a 2-sphere. The Bloch sphere is precisely this projective space — every point on $S^2$ corresponds to a unique physical state.
There is a subtle but important factor of 2 in the Bloch sphere parametrisation. The state $\ket{0}$ sits at the north pole ($\theta=0$) and $\ket{1}$ at the south pole ($\theta=\pi$) — they are antipodal (180° apart on the sphere). Yet geometrically, two antipodal points are not "perpendicular" — they are opposite. Meanwhile, quantum mechanically, $\braket{0|1}=0$ means they are orthogonal (perpendicular as vectors in $\mathbb{C}^2$).
This is because the Bloch parametrisation uses $\cos(\theta/2)$ and $\sin(\theta/2)$, not $\cos\theta$ and $\sin\theta$. A rotation of $\theta=\pi$ (pole to pole, 180° on the sphere) corresponds to a rotation by $\theta/2 = \pi/2$ in the Hilbert space — exactly what it takes to go from $\ket{0}$ to $i\ket{1}$ (which is $\ket{1}$ up to a global phase). Two states are orthogonal iff they are antipodal on the Bloch sphere. To go from one pole to the opposite takes a half-turn in Hilbert space but a full-turn (180°) on the sphere. A full turn in Hilbert space ($\theta = 2\pi$) brings you back to the same state with a sign: $e^{i\pi}\ket{0} = -\ket{0}$ (a global phase, unphysical). You need a $4\pi$ rotation in physical space to return to the identical quantum state — this is the spinor nature of qubits.
Bloch Sphere ↔ Cartesian Coordinates
The Bloch sphere is, geometrically, just a unit sphere in 3D. Any point on a unit sphere can be described by either polar angles $(\theta, \phi)$ or Cartesian coordinates $(x, y, z)$. The conversion is the standard spherical-to-Cartesian mapping:
The triple $(x, y, z)$ is called the Bloch vector. It points from the origin to the state's position on the sphere, and relates directly to the expectation values of the Pauli operators:
This equivalence is powerful: the Bloch vector is physically observable — each component is the expected outcome of a Pauli measurement. Let's verify with a worked example:
| State | $\theta$ | $\phi$ | $x = \sin\theta\cos\phi$ | $y = \sin\theta\sin\phi$ | $z = \cos\theta$ | Location |
|---|---|---|---|---|---|---|
| $\ket{0}$ | $0$ | — | $0$ | $0$ | $+1$ | North pole |
| $\ket{1}$ | $\pi$ | — | $0$ | $0$ | $-1$ | South pole |
| $\ket{+}$ | $\pi/2$ | $0$ | $+1$ | $0$ | $0$ | +x axis |
| $\ket{-}$ | $\pi/2$ | $\pi$ | $-1$ | $0$ | $0$ | −x axis |
| $\ket{i}$ | $\pi/2$ | $\pi/2$ | $0$ | $+1$ | $0$ | +y axis |
| $\ket{-i}$ | $\pi/2$ | $-\pi/2$ | $0$ | $-1$ | $0$ | −y axis |
Notice the pattern: each axis state has $|\text{component}| = 1$ along its axis and $0$ elsewhere — exactly what you'd expect from a unit vector along that axis.
The Three Standard Qubit Bases
While the computational ($z$) basis is most natural, any pair of antipodal Bloch sphere points forms a valid orthonormal basis. The three axis-aligned bases arise naturally from the three Pauli operators:
| Basis name | Axis | States | Measurement operator |
|---|---|---|---|
| Computational ($Z$-basis) | $\hat{z}$ | $\ket{0},\,\ket{1}$ | $Z = \ket{0}\bra{0} - \ket{1}\bra{1}$ |
| Hadamard ($X$-basis) | $\hat{x}$ | $\ket{+} = \frac{\ket{0}+\ket{1}}{\sqrt{2}},\; \ket{-} = \frac{\ket{0}-\ket{1}}{\sqrt{2}}$ | $X = \ket{+}\bra{+} - \ket{-}\bra{-}$ |
| Circular ($Y$-basis) | $\hat{y}$ | $\ket{i} = \frac{\ket{0}+i\ket{1}}{\sqrt{2}},\; \ket{-i} = \frac{\ket{0}-i\ket{1}}{\sqrt{2}}$ | $Y = \ket{i}\bra{i} - \ket{-i}\bra{-i}$ |
The bases are related by explicit conversion formulas — each basis can be expressed in terms of any other:
These conversions are crucial for understanding measurement basis choice: measuring in the $X$-basis means applying $H$ first (to rotate $X$-eigenstates to $Z$-eigenstates) then measuring in the computational basis. This is precisely how IBM quantum hardware executes measurements in non-standard bases.
The Hadamard as a Basis Change
The Hadamard gate $H$ maps the $z$-basis ($\ket{0}, \ket{1}$) to the $x$-basis ($\ket{+}, \ket{-}$): geometrically, it is a $180°$ rotation about the axis midway between $x$ and $z$. This makes the Hadamard a fundamental tool for creating superpositions — applying $H$ to $\ket{0}$ creates a perfect equal superposition: $H\ket{0} = \ket{+} = \frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$.
Postulate 1 — State Space
Associated with any isolated physical system is a complex vector space with inner product (a Hilbert space $\mathcal{H}$), known as the state space of the system. The system is completely described at any time by its state vector, a unit vector $\ket{\psi} \in \mathcal{H}$.
For a qubit, $\mathcal{H} = \mathbb{C}^2$. The state space of $n$ qubits is $\mathbb{C}^{2^n}$. This postulate tells us where quantum states live, but not yet what they mean physically or how they evolve.
Physical Realizations of a Qubit
Any two-level quantum system can serve as a qubit. The mathematical structure $\mathbb{C}^2$ maps onto physics as follows:
| System | $\ket{0}$ Physical State | $\ket{1}$ Physical State |
|---|---|---|
| Photon polarization | Horizontal $|\leftrightarrow\rangle$ | Vertical $|\updownarrow\rangle$ |
| Electron spin | Spin-up $|\uparrow\rangle$ | Spin-down $|\downarrow\rangle$ |
| Two-level atom | Ground state $|g\rangle$ | Excited state $|e\rangle$ |
| Superconducting circuit | Cooper pair absent $|0\rangle$ | Cooper pair present $|1\rangle$ |
| Trapped ion (electronic) | Hyperfine ground state | Excited hyperfine state |
Regardless of the physical realization, the abstract mathematics of $\mathbb{C}^2$ captures all behaviour. This universality is the power of the abstract formalism.
Postulate 2 — Observables
Every physically measurable quantity (observable) corresponds to a Hermitian operator $A = A^\dagger$ on the state space. The possible measurement outcomes are the eigenvalues of $A$. Hermitian operators always have real eigenvalues, consistent with real measurement results.
The Pauli Matrices
The three Pauli matrices are the central observables of a two-level system. They represent spin angular momentum along each axis (in units of $\hbar/2$):
Each Pauli matrix has eigenvalues $\pm 1$, and they satisfy the algebra:
The $Z$ operator has eigenvectors $\ket{0}$ (eigenvalue $+1$) and $\ket{1}$ (eigenvalue $-1$): $$Z\ket{0} = \begin{pmatrix}1&0\\0&-1\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix} = \begin{pmatrix}1\\0\end{pmatrix} = +1\cdot\ket{0}$$ $$Z\ket{1} = \begin{pmatrix}1&0\\0&-1\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix} = \begin{pmatrix}0\\-1\end{pmatrix} = -1\cdot\ket{1}$$ So measuring $Z$ on a qubit in state $\ket{0}$ always gives $+1$; measuring on $\ket{1}$ always gives $-1$.
X Eigenstates: The ±x Basis
The Pauli $X$ matrix has eigenstates: $$\ket{+} = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix}, \quad \ket{-} = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\-1\end{pmatrix}$$ with eigenvalues $+1$ and $-1$ respectively. These are precisely the states reached from the computational basis by applying the Hadamard gate. This illustrates that the choice of measurement basis is physically significant.
Postulate 3 — Unitary Evolution
The evolution of a closed quantum system is described by a unitary transformation: $$\ket{\psi(t)} = U(t, t_0)\ket{\psi(t_0)}, \quad U^\dagger U = \mathbb{I}$$ Equivalently (in continuous time), the state evolves according to the Schrödinger equation: $$i\hbar \frac{d}{dt}\ket{\psi(t)} = H\ket{\psi(t)}$$ where $H = H^\dagger$ is the Hamiltonian (energy operator) of the system.
The connection between the Schrödinger equation and unitarity: if $H$ is time-independent, the solution is $\ket{\psi(t)} = e^{-iHt/\hbar}\ket{\psi(0)}$. Since $H$ is Hermitian, $e^{-iHt/\hbar}$ is unitary. This ensures that probabilities are conserved: $|\braket{\psi(t)|\psi(t)}| = 1$ at all times.
The family of time-evolution operators $\{U(t,t_0)\}$ has an important algebraic structure — they form a group under composition, satisfying three properties:
- Identity: $U(t_0,t_0) = \mathbb{I}$ — no evolution in zero time
- Composition: $U(t,t_0) = U(t,t_1)\,U(t_1,t_0)$ for any intermediate $t_1$ — two consecutive evolutions compose correctly
- Inverse: $U(t_0,t) = U(t,t_0)^\dagger$ — time reversal is just taking the adjoint
The composition property is the quantum statement that the laws of physics don't change with time. A gate sequence $G_1 G_2 G_3$ applied to a qubit is physically the same as computing a single unitary $U = G_3 G_2 G_1$ and applying it once. This is why quantum circuits — which are just compositions of unitaries — correctly model sequential quantum operations.
Because $U^\dagger U = \mathbb{I}$, the inverse of any quantum gate is $U^\dagger$. This means quantum computation is inherently reversible — no information is ever destroyed by a quantum gate (only by measurement). This is in sharp contrast to classical irreversible gates like NAND or AND, and has implications for fault-tolerant computing.
Hamiltonian Evolution on the Bloch Sphere
For a spin-$\frac{1}{2}$ particle in a magnetic field $\mathbf{B} = B\hat{z}$, the Hamiltonian is $H = -\gamma B \hat{S}_z = -\frac{\hbar\omega_0}{2}Z$ (where $\omega_0 = \gamma B$ is the Larmor frequency). The solution $e^{-iHt/\hbar} = e^{i\omega_0 t Z/2}$ represents a rotation around the $z$-axis of the Bloch sphere at angular frequency $\omega_0$.
This "Larmor precession" is the physical foundation of NMR (nuclear magnetic resonance), and directly analogous to how quantum gates rotate the Bloch sphere state vector.
Postulate 4 — Measurement (Born Rule)
Quantum measurements are described by a collection of measurement operators $\{M_m\}$ satisfying $\sum_m M_m^\dagger M_m = \mathbb{I}$. For a system in state $\ket{\psi}$, the probability of outcome $m$ is: $$p(m) = \bra{\psi} M_m^\dagger M_m \ket{\psi}$$ After obtaining outcome $m$, the post-measurement state is: $$\ket{\psi'} = \frac{M_m\ket{\psi}}{\sqrt{p(m)}}$$ For a projective measurement onto the orthonormal basis $\{\ket{a_i}\}$, $M_i = \ket{a_i}\bra{a_i}$, and the probability of obtaining eigenvalue $a_i$ is: $$\boxed{p(a_i) = |\braket{a_i|\psi}|^2}$$
This is the Born Rule — the probability of observing outcome $a_i$ equals the squared modulus of the corresponding amplitude. It is one of the most empirically well-tested laws in physics, verified to extraordinary precision in countless experiments.
Derivation: connecting the general formula to the Born rule
How does the general formula $p(m) = \bra{\psi}M_m^\dagger M_m\ket{\psi}$ simplify to $p(a_i) = |\braket{a_i|\psi}|^2$? Let's work through it step by step.
For a projective measurement in the basis $\{\ket{a_i}\}$, the measurement operators are the projectors $M_i = \ket{a_i}\bra{a_i}$. First, compute $M_i^\dagger$: $$M_i^\dagger = (\ket{a_i}\bra{a_i})^\dagger = \ket{a_i}\bra{a_i} = M_i$$ (projectors are Hermitian). Now compute $M_i^\dagger M_i$: $$M_i^\dagger M_i = \ket{a_i}\bra{a_i}\ket{a_i}\bra{a_i} = \ket{a_i}\underbrace{\braket{a_i|a_i}}_{=\,1}\bra{a_i} = \ket{a_i}\bra{a_i}$$ (we used orthonormality: $\braket{a_i|a_i} = 1$). Substituting into the probability formula: $$p(a_i) = \bra{\psi}\ket{a_i}\bra{a_i}\ket{\psi} = \underbrace{\braket{\psi|a_i}}_{=\,\braket{a_i|\psi}^*} \cdot \braket{a_i|\psi} = |\braket{a_i|\psi}|^2$$
Concrete example: Measure $\ket{+} = \frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$ in the $Z$-basis. The probability of outcome $\ket{0}$: $$p(0) = |\braket{0|+}|^2 = \left|\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2}$$ As expected — a 50/50 outcome.
The Stern-Gerlach Experiment
The canonical demonstration of quantum measurement. Silver atoms (with spin-$\frac{1}{2}$) pass through an inhomogeneous magnetic field oriented along $z$. The force $F_z \propto \partial B/\partial z$ deflects atoms based on their $z$-spin projection. Classically, we expect a continuous smear of deflections. Quantum mechanically — and confirmed by experiment — only two discrete spots appear, corresponding to $m_s = +\frac{1}{2}$ (spin-up) and $m_s = -\frac{1}{2}$ (spin-down).
The remarkable finding: if you then pass spin-up atoms through a second Stern-Gerlach apparatus oriented along $x$ instead of $z$, you again get two outcomes with equal probability — demonstrating that the $x$-spin is maximally uncertain when the $z$-spin is known, a manifestation of the Heisenberg Uncertainty Principle.
Sequential Measurements
A beautiful and counterintuitive consequence of the measurement postulate: measuring a spin-up state $\ket{\uparrow_z}$ in the $x$-direction collapses it to either $\ket{+}$ or $\ket{-}$ with equal probability $\frac{1}{2}$. If you then re-measure in the $z$-direction, you again get up or down with equal probability — the original $z$-information has been destroyed by the intermediate $x$-measurement.
Mathematically: measuring $X$ on $\ket{\uparrow_z} = \ket{0}$ collapses it to $\ket{+}$ or $\ket{-}$. Both of these have equal $Z$-components: $|\braket{0|+}|^2 = |\braket{0|-}|^2 = \frac{1}{2}$.
The Heisenberg Uncertainty Principle
For any two observables $A$ and $B$, and any state $\ket{\psi}$: $$\sigma_A \sigma_B \geq \frac{1}{2}|\braket{[A,B]}|$$ where $\sigma_A = \sqrt{\braket{A^2} - \braket{A}^2}$ is the standard deviation, and $[A,B] = AB - BA$ is the commutator.
For spin operators, $[S_z, S_x] = i\hbar S_y$, so: $$\sigma_{S_z}\,\sigma_{S_x} \geq \frac{\hbar}{2}|\braket{S_y}|$$
The more famous position-momentum version: $[x, p] = i\hbar$ gives: $$\sigma_x \sigma_p \geq \frac{\hbar}{2}$$ This is not about experimental clumsiness — it is a fundamental feature of the universe. A quantum particle simply does not have a simultaneously sharp position and momentum.
If $[A, B] = 0$ (they commute), it means $AB = BA$. You can measure them at the same time. Think of measuring a box's Width and then its Length. The order doesn't matter, and you can know both perfectly.
However, if $[A, B] \neq 0$, they do not commute. Measuring one fundamentally scrambles the other. Think of trying to know a car's exact position (requiring a hyper-fast, sharp photo) and its exact velocity (requiring a slow-shutter video). The two properties are incompatible by nature. This is why $Z$ and $X$ measurements cannot both be sharp: $[Z, X] = 2iY \neq 0$.
Single-Qubit Gates
A quantum gate is a unitary operator $U$ applied to one or more qubits. Single-qubit gates are $2 \times 2$ unitary matrices. Every single-qubit gate corresponds to a rotation of the Bloch sphere — an elegant geometric interpretation.
The Fundamental Single-Qubit Gates
Pauli Gates
$X$ is the quantum analogue of a classical NOT gate. $Z$ adds a phase flip: $Z\ket{0} = \ket{0}$, $Z\ket{1} = -\ket{1}$. These $\pm 1$ phase differences have no classical analogue and are crucial for quantum interference.
Pauli Algebra — Multiplication Rules
The Pauli matrices form a closed algebra under multiplication. These rules are essential for simplifying circuits and propagating errors through gates:
Notice the cyclic pattern: $X \to Y \to Z \to X$ (clockwise) gives $+i$, and reversing the order gives $-i$. The Pauli matrices anti-commute: $\{\sigma_j, \sigma_k\} = \sigma_j\sigma_k + \sigma_k\sigma_j = 0$ for $j \neq k$. This means swapping the order flips the sign.
The 16-element set $\{\pm I, \pm iI, \pm X, \pm iX, \pm Y, \pm iY, \pm Z, \pm iZ\}$ forms the single-qubit Pauli group. It is closed under multiplication — the product of any two Paulis is always another Pauli (possibly with a phase $\pm 1$ or $\pm i$). This algebraic closure is why Pauli gates are so fundamental: you can track errors through a circuit by simply multiplying Pauli labels, without ever touching matrices.
Using the algebra: $XYZYX = X \cdot (YZ) \cdot (YX) = X \cdot (iX) \cdot (-iZ) = X \cdot X \cdot Z = I \cdot Z = Z$.
Every intermediate step used either the squaring rule or the multiplication table. No matrix math needed!
The Hadamard Gate
The Hadamard is arguably the most important single-qubit gate. Its key actions: $$H\ket{0} = \frac{\ket{0}+\ket{1}}{\sqrt{2}} = \ket{+}, \qquad H\ket{1} = \frac{\ket{0}-\ket{1}}{\sqrt{2}} = \ket{-}$$ $$H\ket{+} = \ket{0}, \qquad H\ket{-} = \ket{1}$$ It maps between the $z$ and $x$ bases. Geometrically: 180° rotation about the axis $\frac{1}{\sqrt{2}}(\hat{x}+\hat{z})$ on the Bloch sphere. Note $H = H^\dagger$ and $H^2 = \mathbb{I}$ (self-inverse).
S and T Phase Gates
Both leave $\ket{0}$ unchanged and add a phase to $\ket{1}$: $S$ adds phase $i = e^{i\pi/2}$ (quarter turn around $z$-axis), $T$ adds $e^{i\pi/4}$ (eighth turn). Note $S = T^2$ and $Z = S^2 = T^4$. The set $\{H, T, \text{CNOT}\}$ is universal for quantum computation.
The Phase Gate $P(\lambda)$ — Unifying Z, S, and T
$Z$, $S$, and $T$ are all special cases of a single parameterised gate called the Phase gate (sometimes written as $U_1(\lambda)$ in older Qiskit notation):
Its action is simple: it leaves $\ket{0}$ alone and rotates the phase of $\ket{1}$:
This is not quite the same as $R_z(\theta)$. The difference is a global phase: $P(\lambda) = e^{i\lambda/2} R_z(\lambda)$ (equivalently, $R_z(\theta) = e^{-i\theta/2} P(\theta)$). Since global phases are unphysical, $P(\lambda)$ and $R_z(\lambda)$ produce identical measurement outcomes, but the distinction matters in controlled gates (where the global phase becomes a relative phase).
| Gate | Phase $\lambda$ | $P(\lambda)$ form | As $R_z$ | Relation |
|---|---|---|---|---|
| $I$ | $0$ | $P(0) = I$ | $R_z(0) = I$ | Identity |
| $T$ | $\pi/4$ | $P(\pi/4)$ | $e^{i\pi/8} R_z(\pi/4)$ | $T^2 = S$ |
| $S$ | $\pi/2$ | $P(\pi/2)$ | $e^{i\pi/4} R_z(\pi/2)$ | $S^2 = Z$ |
| $Z$ | $\pi$ | $P(\pi)$ | $e^{i\pi/2} R_z(\pi)$ | $Z^2 = I$ |
| $S^\dagger$ | $-\pi/2$ | $P(-\pi/2)$ | $e^{-i\pi/4} R_z(-\pi/2)$ | $SS^\dagger = I$ |
| $T^\dagger$ | $-\pi/4$ | $P(-\pi/4)$ | $e^{-i\pi/8} R_z(-\pi/4)$ | $TT^\dagger = I$ |
Every $Z$-axis gate is just $P(\lambda)$ at a different angle. This is why they all commute with each other — they rotate about the same axis. $S^4 = Z^2 = I$ and $T^8 = S^4 = Z^2 = I$ follow directly from the angle doubling.
General Rotation Gates
Any $2\times 2$ unitary can be decomposed as a rotation around some axis $\hat{n}$ by angle $\alpha$:
In particular, the rotation gates around the three cardinal axes:
Note that $R_y$ is the only rotation gate with purely real matrix entries — it rotates amplitude between $\ket{0}$ and $\ket{1}$ without introducing any complex phase. For this reason, $R_y$ is heavily used in variational quantum circuits (Week 4's hardware-efficient ansätze).
Each cardinal rotation gate is simply the general rotation formula $R_{\hat{n}}(\theta) = \cos(\theta/2)\,\mathbb{I} - i\sin(\theta/2)\,(\hat{n}\cdot\boldsymbol{\sigma})$ applied to $\hat{n} = \hat{x}, \hat{y}$, or $\hat{z}$. Since the Pauli matrix for each axis plays the role of the generator of rotation about that axis, we can write:
Or more compactly: $R_K(\theta) = \cos(\theta/2)\,I - i\sin(\theta/2)\,K$ for $K \in \{X, Y, Z\}$. This is the master equation connecting rotations to Pauli gates.
Sanity check: at $\theta = \pi$, $\cos(\pi/2) = 0$ and $\sin(\pi/2) = 1$, so $R_K(\pi) = -iK$. Since $-i$ is a global phase, this means a $\pi$-rotation about the $K$-axis is the Pauli gate $K$ itself (up to global phase). This is why the Pauli matrices are described as "180° rotations" — they literally are $R_x(\pi)$, $R_y(\pi)$, and $R_z(\pi)$.
From the master equation: $R_z(\pi) = \cos(\pi/2)\,I - i\sin(\pi/2)\,Z = 0 \cdot I - i \cdot 1 \cdot Z = -iZ$.
From the matrix: $R_z(\pi) = \begin{pmatrix}e^{-i\pi/2}&0\\0&e^{i\pi/2}\end{pmatrix}
= \begin{pmatrix}-i&0\\0&i\end{pmatrix} = -i\begin{pmatrix}1&0\\0&-1\end{pmatrix} = -iZ \;\checkmark$
The global phase $-i$ is unphysical, so $R_z(\pi) \equiv Z$ as a gate.
The Euler Angle Decomposition (ZXZ)
A fundamental result in quantum computing is that any single-qubit gate (any $2\times2$ unitary) can be decomposed into just three rotation gates and a global phase:
The four real parameters $(\alpha, \beta, \gamma, \delta)$ uniquely determine any single-qubit gate. This is the quantum analogue of Euler angles in classical mechanics. Alternative decompositions (ZYZ, XYX, etc.) are also valid — all you need is rotations around two non-parallel axes.
We want to write $H = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ in the form $e^{i\alpha}\,R_z(\beta)\,R_x(\gamma)\,R_z(\delta)$.
Step 1: Recognize H as a rotation.
The Hadamard is a 180° rotation about the axis $\hat{n} = \frac{\hat{x}+\hat{z}}{\sqrt{2}}$
(the axis midway between $x$ and $z$). Using $R_{\hat{n}}(\pi) = -i(n_x X + n_z Z)/\sqrt{...}$,
we can write:
$$H = \frac{1}{\sqrt{2}}(X + Z)$$
Let's verify: $\frac{1}{\sqrt{2}}\left(\begin{pmatrix}0&1\\1&0\end{pmatrix} + \begin{pmatrix}1&0\\0&-1\end{pmatrix}\right) = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix} = H \;\checkmark$
Step 2: Find the Euler angles.
We can express $H$ as a product of $R_z$ and $R_x$ rotations. One valid decomposition is:
$$H = e^{i\pi/2}\, R_z(0)\, R_x(\pi/2)\, R_z(\pi)$$
Let's verify by multiplying out. Start from the right:
$R_z(\pi) = \begin{pmatrix}e^{-i\pi/2}&0\\0&e^{i\pi/2}\end{pmatrix} = \begin{pmatrix}-i&0\\0&i\end{pmatrix}$
$R_x(\pi/2) = \begin{pmatrix}\cos\frac{\pi}{4}&-i\sin\frac{\pi}{4}\\-i\sin\frac{\pi}{4}&\cos\frac{\pi}{4}\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1&-i\\-i&1\end{pmatrix}$
$R_x(\pi/2)\cdot R_z(\pi) = \frac{1}{\sqrt{2}}\begin{pmatrix}1&-i\\-i&1\end{pmatrix}\begin{pmatrix}-i&0\\0&i\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}-i&-i^2\\-i(-i)&i\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}-i&1\\-1&i\end{pmatrix}$
Multiply by $R_z(0) = I$ (identity, no change), then by $e^{i\pi/2} = i$: $$i \cdot \frac{1}{\sqrt{2}}\begin{pmatrix}-i&1\\-1&i\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1&i\\-i&-1\end{pmatrix}$$
Hmm — that gives $H$ up to some column phases! A cleaner decomposition uses the $R_z$-$R_y$-$R_z$ form: $$H = R_z(\pi)\,R_y(\pi/2)$$ Let's verify this simpler form:
$R_y(\pi/2) = \frac{1}{\sqrt{2}}\begin{pmatrix}1&-1\\1&1\end{pmatrix}$
$R_z(\pi) \cdot R_y(\pi/2) = \begin{pmatrix}-i&0\\0&i\end{pmatrix} \cdot \frac{1}{\sqrt{2}}\begin{pmatrix}1&-1\\1&1\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}-i&i\\i&i\end{pmatrix} = \frac{i}{\sqrt{2}}\begin{pmatrix}-1&1\\1&1\end{pmatrix}$
This equals $i \cdot \frac{1}{\sqrt{2}}\begin{pmatrix}-1&1\\1&1\end{pmatrix}$, which is $H$ multiplied by a global phase $e^{i3\pi/2}$. Since global phases are unphysical: $$\boxed{H \equiv R_z(\pi) \cdot R_y(\pi/2) \text{ (up to global phase)}}$$
Key takeaway: The Hadamard is a $90°$ rotation about $y$ (which creates the superposition) followed by a $180°$ rotation about $z$ (which fixes the signs). This decomposition explains why $H\ket{0} = \ket{+}$ and $H\ket{1} = \ket{-}$.
Multi-Qubit Systems
When we combine $n$ qubits, the state space grows exponentially. Two qubits have basis states $\ket{00}, \ket{01}, \ket{10}, \ket{11}$, forming the computational basis of $\mathbb{C}^4 = \mathbb{C}^2 \otimes \mathbb{C}^2$:
with normalization $\sum_{x \in \{00,01,10,11\}} |\alpha_x|^2 = 1$. For $n$ qubits:
Product vs. Entangled States
A state $\ket{\psi} \in \mathcal{H}_A \otimes \mathcal{H}_B$ is a product state if it can be written as $\ket{\psi} = \ket{\phi}_A \otimes \ket{\chi}_B$ for some $\ket{\phi}_A \in \mathcal{H}_A$ and $\ket{\chi}_B \in \mathcal{H}_B$. Otherwise, it is entangled.
Product state (Independent Coins):
Suppose I have two normal coins. I flip one, you flip the other. The outcome of my coin
has absolutely no effect on yours. Mathematically, the overall state can be factored
into "My Coin" $\otimes$ "Your Coin".
Example: $\ket{+}\ket{0} = \frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\otimes\ket{0} = \frac{1}{\sqrt{2}}(\ket{00}+\ket{10})$
Entangled state (Magic Coins):
Now suppose we have two "magic" coins that always land on the same face, even if we are
light-years apart. If I get Heads ($\ket{0}$), you instantly get Heads ($\ket{0}$).
If I get Tails ($\ket{1}$), you get Tails ($\ket{1}$).
Example: $\ket{\Phi^+} = \frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$
The Mathematical Proof of Entanglement: Why can't we just factor $\ket{\Phi^+}$ into two independent coins? Let's try to force it. Suppose: $$\ket{\Phi^+} = (\alpha\ket{0}+\beta\ket{1})\otimes(\gamma\ket{0}+\delta\ket{1})$$
If we multiply this out, we get four terms: $\alpha\gamma\ket{00} + \alpha\delta\ket{01} + \beta\gamma\ket{10} + \beta\delta\ket{11}$.
For this to equal our magic state $\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$, the mixed terms must vanish: we need $\alpha\delta = 0$ and $\beta\gamma = 0$. This means either $\alpha=0$, $\delta=0$, $\beta=0$, or $\gamma=0$. But if any of those are zero, it's impossible to get $\alpha\gamma = \frac{1}{\sqrt{2}}$ and $\beta\delta = \frac{1}{\sqrt{2}}$.
This is a mathematical contradiction. The state cannot be factored. The two qubits don't have individual states anymore; they only have a shared, collective state.
The Q-Sphere (Visualizing Many Qubits)
The Bloch sphere is perfect for a single qubit, but it fails completely for multi-qubit entangled states. For systems up to 5 qubits, we use the Q-sphere, which maps all $2^n$ basis states onto the surface of a globe simultaneously.
Think of the Q-sphere as a planet where every basis state is a city:
- Latitude (Hamming Weight): The North Pole is the "all zeros" state ($\ket{000}$). The South Pole is the "all ones" state ($\ket{111}$). States with an equal number of 1s sit on the same latitude ring.
- City Size (Probability): A state's probability $|\alpha_x|^2$ is represented by the size of the sphere at that location. Bigger = more likely.
- Color (Phase): The phase $\phi$ is mapped to a color wheel (red → green → blue → red). Phase determines how states will interfere when gates are applied — it's the hidden variable that makes quantum computing powerful.
For an $n$-qubit state $\ket{\psi} = \sum_{x \in \{0,1\}^n} \alpha_x \ket{x}$, each basis state $\ket{x}$ is placed at:
- Polar angle: $\theta_x = \frac{\pi \cdot w(x)}{n}$, where $w(x) = \sum_i x_i$ is the Hamming weight (number of 1-bits).
- Azimuthal angle: $\phi_x$ is assigned by distributing all states of the same weight evenly around the circle at that latitude.
- Dot radius: $r_x \propto |\alpha_x|$ (proportional to the amplitude magnitude).
- Dot color: $\text{Hue} = \frac{\arg(\alpha_x) + \pi}{2\pi}$ (phase mapped to the color wheel).
- Uniform (|+⟩³): All 8 states have equal-sized dots and the same color (phase 0). This is the state after applying $H^{\otimes 3}$ to $\ket{000}$.
- GHZ State: Only 2 dots — at the North and South Poles ($\ket{000}$ and $\ket{111}$). Maximum entanglement, like the "magic coins" analogy.
- W State: 3 dots at the same latitude (weight 1). The entanglement here is more "robust" than GHZ — losing one qubit doesn't destroy it.
- QFT: All states equal-sized, but with different colors. The phases form a spiral pattern — this is what the Quantum Fourier Transform looks like.
Multi-Qubit Gates & Universality
The CNOT Gate
The Controlled-NOT (CNOT) is the fundamental two-qubit gate. It flips the target qubit if and only if the control qubit is $\ket{1}$:
where $\oplus$ denotes XOR (addition mod 2). Its action on basis states: $\ket{00}\to\ket{00}$, $\ket{01}\to\ket{01}$, $\ket{10}\to\ket{11}$, $\ket{11}\to\ket{10}$.
Applying CNOT with control on qubit 1 to $\ket{+}\ket{0} = \frac{1}{\sqrt{2}}(\ket{00}+\ket{10})$. Let's apply CNOT to each basis state individually (this is how linearity works — we handle each term in the superposition separately):
- $\text{CNOT}\ket{00} = \ket{00}$ — control is $\ket{0}$, so the target is left alone
- $\text{CNOT}\ket{10} = \ket{11}$ — control is $\ket{1}$, so the target qubit is flipped: $\ket{0} \to \ket{1}$
Now by linearity of quantum mechanics (gates act on each term independently): $$\text{CNOT}\cdot\frac{1}{\sqrt{2}}(\ket{00}+\ket{10}) = \frac{1}{\sqrt{2}}(\underbrace{\text{CNOT}\ket{00}}_{\ket{00}}+\underbrace{\text{CNOT}\ket{10}}_{\ket{11}}) = \frac{1}{\sqrt{2}}(\ket{00}+\ket{11}) = \ket{\Phi^+}$$ One Hadamard plus one CNOT creates a maximally entangled Bell state — the most fundamental entangling circuit.
Other Multi-Qubit Gates
CZ (Controlled-Z)
CZ adds a phase of $-1$ if and only if both qubits are $\ket{1}$. Unlike CNOT, CZ is symmetric — control and target play equal roles. Circuit identity: CZ = (H on target) CNOT (H on target).
SWAP Gate
SWAP can be decomposed into three CNOTs:
Toffoli (CCX) Gate
A three-qubit gate with two controls and one target: $\text{Toffoli}\ket{c_1, c_2, t} = \ket{c_1, c_2, t \oplus (c_1 \text{ AND } c_2)}$. The Toffoli gate is universal for classical reversible computation — it can implement any classical logic gate reversibly. Combined with the Hadamard, $\{H, \text{Toffoli}\}$ is universal for quantum computation.
Universality
A set of gates is universal if any unitary operation on any number of qubits can be approximated to arbitrary precision using only those gates.
- • $\{H, T, \text{CNOT}\}$ — Most common universal set for quantum computing
- • $\{H, \text{Toffoli}\}$ — Universal for quantum computation
- • $\{\text{Toffoli}\}$ alone — Universal for classical (reversible) computation
The Solovay-Kitaev theorem guarantees that any unitary can be approximated with $O(\log^c(1/\epsilon))$ gates from a universal set, to accuracy $\epsilon$.
Circuit Identities
Several important circuit identities for simplification and compilation:
These identities allow us to change the "direction" of a controlled gate or switch between controlled-$X$ and controlled-$Z$ using only Hadamard gates — very useful in practice when hardware only natively supports certain gate types.
Pauli Propagation Through CNOT ($UPU^\dagger$ Rules)
When we push a Pauli error (or gate) through a CNOT, the CNOT can transform it — sometimes causing the error to spread to the other qubit. These rules are fundamental to quantum error correction, circuit simplification, and understanding how noise propagates. The key identity is:
We want to know: if a Pauli $P$ acts on the control qubit or the target qubit, what happens when we "conjugate" it through a CNOT (i.e., compute $\text{CNOT}\,(P \otimes I)\,\text{CNOT}$ or $\text{CNOT}\,(I \otimes P)\,\text{CNOT}$)?
| Error / Gate | Before CNOT | After CNOT | What happened |
|---|---|---|---|
| X ERRORS (bit flips) | |||
| $X$ on control | $X \otimes I$ | $X \otimes X$ | Spreads! $X$ propagates from control → target |
| $X$ on target | $I \otimes X$ | $I \otimes X$ | Stays. $X$ on target does not propagate |
| Z ERRORS (phase flips) | |||
| $Z$ on control | $Z \otimes I$ | $Z \otimes I$ | Stays. $Z$ on control does not propagate |
| $Z$ on target | $I \otimes Z$ | $Z \otimes Z$ | Spreads! $Z$ propagates from target → control |
| Y ERRORS (bit + phase flips, since $Y = iXZ$) | |||
| $Y$ on control | $Y \otimes I$ | $Y \otimes X$ | The $X$ part of $Y$ spreads to target; $Z$ part stays |
| $Y$ on target | $I \otimes Y$ | $Z \otimes Y$ | The $Z$ part of $Y$ spreads to control; $X$ part stays |
The pattern above has a beautiful asymmetry: $X$ errors flow forward (control → target), while $Z$ errors flow backward (target → control). This happens because CNOT copies the computational basis (the $Z$-eigenstates), so a bit-flip on the control also flips the target. But in the conjugate basis ($X$-eigenstates, i.e., $\ket{+}/\ket{-}$), the roles reverse: the CNOT effectively copies from target to control.
Formally, this follows from the identity: $$\text{CNOT} = \ket{0}\bra{0} \otimes I + \ket{1}\bra{1} \otimes X$$ The control projects and the target conditionally flips — hence $X$ on control ripples to target. The reverse direction for $Z$ follows from the Hadamard conjugation: $\text{CNOT}_{1\to2} = (H \otimes H)\,\text{CNOT}_{2\to1}\,(H \otimes H)$, which swaps the roles of $X$ and $Z$.
Proof: $X$ on control propagates
We compute $\text{CNOT}\,(X \otimes I)\,\text{CNOT}$ on each basis state:
$\ket{00} \xrightarrow{\text{CNOT}} \ket{00} \xrightarrow{X \otimes I} \ket{10} \xrightarrow{\text{CNOT}} \ket{11}$
$\ket{01} \xrightarrow{\text{CNOT}} \ket{01} \xrightarrow{X \otimes I} \ket{11} \xrightarrow{\text{CNOT}} \ket{10}$
$\ket{10} \xrightarrow{\text{CNOT}} \ket{11} \xrightarrow{X \otimes I} \ket{01} \xrightarrow{\text{CNOT}} \ket{01}$
$\ket{11} \xrightarrow{\text{CNOT}} \ket{10} \xrightarrow{X \otimes I} \ket{00} \xrightarrow{\text{CNOT}} \ket{00}$
In every case, both qubits are flipped — the same as applying $X \otimes X$. Therefore $\text{CNOT}\,(X \otimes I)\,\text{CNOT} = X \otimes X$. $\square$
Proof: $Z$ on target propagates
We compute $\text{CNOT}\,(I \otimes Z)\,\text{CNOT}$ on each basis state:
$\ket{00} \xrightarrow{\text{CNOT}} \ket{00} \xrightarrow{I \otimes Z} \ket{00} \xrightarrow{\text{CNOT}} \ket{00}$ (phase $+1$)
$\ket{01} \xrightarrow{\text{CNOT}} \ket{01} \xrightarrow{I \otimes Z} -\ket{01} \xrightarrow{\text{CNOT}} -\ket{01}$ (phase $-1$)
$\ket{10} \xrightarrow{\text{CNOT}} \ket{11} \xrightarrow{I \otimes Z} -\ket{11} \xrightarrow{\text{CNOT}} -\ket{10}$ (phase $-1$)
$\ket{11} \xrightarrow{\text{CNOT}} \ket{10} \xrightarrow{I \otimes Z} \ket{10} \xrightarrow{\text{CNOT}} \ket{11}$ (phase $+1$)
The phase pattern is: $+1$ when qubits agree ($00, 11$), $-1$ when they disagree ($01, 10$). This is exactly $Z \otimes Z$. Therefore $\text{CNOT}\,(I \otimes Z)\,\text{CNOT} = Z \otimes Z$. $\square$