Thilan Dissanayaka Quantum Computing June 03, 2020

The Math You Need — Linear Algebra for Quantum Computing

In the previous article, we introduced qubits, superposition, entanglement, and interference. We used some math — state vectors, probability amplitudes, the Hadamard matrix. Now it’s time to formalize all of that.

Here’s the truth about quantum computing: it’s linear algebra. Every qubit state is a vector. Every quantum gate is a matrix. Multi-qubit systems are tensor products. Measurement is projection. If you can multiply matrices and understand complex numbers, you can understand quantum computing. That’s it.

If you worked through the AES article and understood how MixColumns multiplies a vector by a matrix in GF(2^8), you already have the core intuition. Quantum computing does the same thing — but in $\mathbb{C}^{2^n}$ (complex vector spaces) instead of finite fields.

This article covers exactly the math you need — no more, no less. Every concept comes with a quantum computing example so you see immediately why it matters.

Complex Numbers — Quick Refresher

Quantum amplitudes are complex numbers, so we need to be comfortable with them.

A complex number has a real part and an imaginary part:

\[z = a + bi\]

Where $i = \sqrt{-1}$, so $i^2 = -1$.

Examples: $3 + 2i$, $-1 + 0i$ (which is just $-1$), $0 + i$ (which is just $i$).

Complex Conjugate

The complex conjugate of $z = a + bi$ is:

\[z^* = a - bi\]

Flip the sign of the imaginary part. Examples:

$(3 + 2i)^* = 3 - 2i$
$(i)^* = -i$
$(5)^* = 5$ (real numbers are their own conjugate)

Modulus (Absolute Value)

The modulus of $z = a + bi$ is:

\[|z| = \sqrt{a^2 + b^2} = \sqrt{z \cdot z^*}\]

This is the “length” of the complex number.

Why This Matters for Quantum

\[|\alpha|^2 = \alpha \cdot \alpha^*\]

If $\alpha = \frac{1+i}{2}$:

\[|\alpha|^2 = \frac{1+i}{2} \cdot \frac{1-i}{2} = \frac{(1+i)(1-i)}{4} = \frac{1 - i^2}{4} = \frac{1+1}{4} = \frac{1}{2}\]

So there’s a 50% chance of measuring 0. The complex phase ($i$) affects interference but not individual measurement probabilities.

Vectors — Qubit States

A qubit is a vector in a 2-dimensional complex vector space $\mathbb{C}^2$.

Column Vectors

\[|0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad |1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}\]

A general qubit:

\[|\psi\rangle = \alpha|0\rangle + \beta|1\rangle = \alpha\begin{pmatrix} 1 \\ 0 \end{pmatrix} + \beta\begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} \alpha \\ \beta \end{pmatrix}\]

This is a linear combination of the basis vectors. The coefficients $\alpha$ and $\beta$ are the amplitudes.

Row Vectors (Bra Vectors)

The Dirac notation has two sides:

Ket $|\psi\rangle$ — column vector (what we’ve been using)
Bra $\langle\psi|$ — row vector, the conjugate transpose of the ket

\[|\psi\rangle = \begin{pmatrix} \alpha \\ \beta \end{pmatrix} \quad \Longrightarrow \quad \langle\psi| = \begin{pmatrix} \alpha^* & \beta^* \end{pmatrix}\]

The “bra-ket” name comes from the bracket notation: $\langle\phi|\psi\rangle$ is the inner product, and it looks like a bracket split in half.

Inner Product (Bra-Ket)

The inner product of two states $|\phi\rangle$ and $|\psi\rangle$ is:

\[\langle\phi|\psi\rangle = \begin{pmatrix} \phi_1^* & \phi_2^* \end{pmatrix} \begin{pmatrix} \psi_1 \\ \psi_2 \end{pmatrix} = \phi_1^*\psi_1 + \phi_2^*\psi_2\]

This gives a scalar (a single complex number).

Orthogonality

Two states are orthogonal if their inner product is zero:

\[\langle 0|1\rangle = \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = 0\]

The basis states $|0\rangle$ and $|1\rangle$ are orthogonal — they’re completely distinguishable. Measurement can always tell them apart.

Normalization

A valid quantum state must be normalized — its inner product with itself equals 1:

This is the requirement that probabilities sum to 1.

Probability from Inner Product

The probability of measuring state $|\phi\rangle$ when the system is in state $|\psi\rangle$ is:

\[P(\phi) = |\langle\phi|\psi\rangle|^2\]

For example, the probability of measuring $|0\rangle$ in state $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$:

\[P(0) = |\langle 0|\psi\rangle|^2 = |\alpha|^2\]

Exactly what we said in the previous article — but now we see it’s just an inner product.

Matrices — Quantum Gates

Quantum gates are matrices that transform state vectors. Applying a gate $U$ to a state $|\psi\rangle$ is matrix-vector multiplication:

\[|\psi'\rangle = U|\psi\rangle\]

The Key Quantum Gates

Pauli-X (NOT Gate)

\[X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\]

Flips $|0\rangle$ to $|1\rangle$ and vice versa:

\[X|0\rangle = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix} = |1\rangle\]

Pauli-Z (Phase Flip)

\[Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\]

Leaves $|0\rangle$ unchanged, flips the sign of $|1\rangle$:

\[Z|1\rangle = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ -1 \end{pmatrix} = -|1\rangle\]

This doesn’t change the measurement probability ($|-1|^2 = 1$), but the phase matters for interference.

Pauli-Y

\[Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}\]

Combines a bit flip and a phase flip.

Hadamard (H)

\[H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\]

Creates superposition from basis states:

\[H|0\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix} = \frac{|0\rangle + |1\rangle}{\sqrt{2}} = |+\rangle\] \[H|1\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -1 \end{pmatrix} = \frac{|0\rangle - |1\rangle}{\sqrt{2}} = |-\rangle\]

Notice: $H|0\rangle = |+\rangle$ has equal amplitudes with the same sign. $H|1\rangle = |-\rangle$ has equal amplitudes with opposite signs. The sign difference is what creates interference — and it’s the basis for almost every quantum algorithm.

Applying H twice gives you back the original state:

\[H^2 = HH = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \cdot \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I\]

$H$ is its own inverse. This property is used constantly in quantum algorithms.

Phase Gate (S) and T Gate

\[S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}, \quad T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}\]

These add phases to the $|1\rangle$ component without affecting $|0\rangle$. The $T$ gate is particularly important — the set ${H, T, \text{CNOT}}$ forms a universal gate set (any quantum computation can be approximated using just these three gates).

Unitary Matrices

All quantum gates must be unitary. A matrix $U$ is unitary if:

\[U^\dagger U = UU^\dagger = I\]

Where $U^\dagger$ is the conjugate transpose (transpose the matrix, then take the complex conjugate of every element).

Why unitary? Because unitary matrices:

Preserve normalization — If $|\psi\rangle$ is normalized, $U|\psi\rangle$ is also normalized. Probabilities still sum to 1.
Are reversible — Every unitary matrix has an inverse ($U^{-1} = U^\dagger$). Quantum computation is inherently reversible. (Measurement is the one exception.)

Let’s verify the Hadamard gate is unitary:

\[H^\dagger = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}^\dagger = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = H\]

(H is real and symmetric, so the conjugate transpose equals itself.)

\[H^\dagger H = H^2 = I \quad \checkmark\]

Matrix Composition — Sequential Gates

Applying gate $A$ then gate $B$ is:

\[|\psi'\rangle = B(A|\psi\rangle) = (BA)|\psi\rangle\]

Note the right-to-left order — $A$ is applied first, but it’s on the right in the matrix product $BA$. This is the same convention as function composition: $f(g(x))$ applies $g$ first.

Example: Apply $X$ then $H$ to $|0\rangle$:

\[HX|0\rangle = H|1\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -1 \end{pmatrix} = |-\rangle\]

Tensor Products — Multi-Qubit Systems

A single qubit lives in $\mathbb{C}^2$. Two qubits live in $\mathbb{C}^2 \otimes \mathbb{C}^2 = \mathbb{C}^4$. Three qubits live in $\mathbb{C}^8$. In general, $n$ qubits live in $\mathbb{C}^{2^n}$.

The tensor product $\otimes$ is how we combine individual qubit spaces into a multi-qubit space.

Tensor Product of Vectors

\[|0\rangle \otimes |1\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \cdot 0 \\ 1 \cdot 1 \\ 0 \cdot 0 \\ 0 \cdot 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}\]

The recipe: take each element of the first vector and multiply it by the entire second vector.

For a general vector $\begin{pmatrix} a \ b \end{pmatrix} \otimes \begin{pmatrix} c \ d \end{pmatrix}$:

\[\begin{pmatrix} a \\ b \end{pmatrix} \otimes \begin{pmatrix} c \\ d \end{pmatrix} = \begin{pmatrix} a \cdot c \\ a \cdot d \\ b \cdot c \\ b \cdot d \end{pmatrix}\]

Shorthand

The 2-Qubit Basis

The four basis states for 2 qubits:

\[|00\rangle = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \quad |01\rangle = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}, \quad |10\rangle = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \quad |11\rangle = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}\]

A general 2-qubit state:

\[|\psi\rangle = \alpha_{00}|00\rangle + \alpha_{01}|01\rangle + \alpha_{10}|10\rangle + \alpha_{11}|11\rangle = \begin{pmatrix} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{pmatrix}\]

Four amplitudes — one for each possible 2-bit string.

Tensor Product of Matrices

To apply gate $A$ to qubit 1 and gate $B$ to qubit 2 (simultaneously and independently):

\[(A \otimes B)|\psi_1\rangle \otimes |\psi_2\rangle\]

The tensor product of two $2 \times 2$ matrices gives a $4 \times 4$ matrix:

\[A \otimes B = \begin{pmatrix} a_{11}B & a_{12}B \\ a_{21}B & a_{22}B \end{pmatrix}\]

Example: Apply $H$ to the first qubit and $I$ (identity, do nothing) to the second:

\[H \otimes I = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{pmatrix}\]

Applying this to $|00\rangle$:

\[(H \otimes I)|00\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle) = |+\rangle \otimes |0\rangle\]

The first qubit is now in superposition $|+\rangle$, the second is still $|0\rangle$.

Entangled States — Not a Tensor Product

Here’s the crucial point. The Bell state:

\[|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}\]

Try to write this as $|a\rangle \otimes |b\rangle$ for some single-qubit states $|a\rangle = \begin{pmatrix} a_1 \ a_2 \end{pmatrix}$ and $|b\rangle = \begin{pmatrix} b_1 \ b_2 \end{pmatrix}$:

\[\begin{pmatrix} a_1 b_1 \\ a_1 b_2 \\ a_2 b_1 \\ a_2 b_2 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}\]

This requires $a_1 b_1 = \frac{1}{\sqrt{2}}$ and $a_1 b_2 = 0$ and $a_2 b_1 = 0$ and $a_2 b_2 = \frac{1}{\sqrt{2}}$.

From $a_1 b_2 = 0$: either $a_1 = 0$ or $b_2 = 0$. If $a_1 = 0$: then $a_1 b_1 = 0 \neq \frac{1}{\sqrt{2}}$. Contradiction. If $b_2 = 0$: then $a_2 b_2 = 0 \neq \frac{1}{\sqrt{2}}$. Contradiction.

There’s no solution. The Bell state cannot be written as a product of two single-qubit states. This is the mathematical definition of entanglement — a multi-qubit state that cannot be factored into individual qubit states. The qubits are correlated in a way that has no classical analog.

The CNOT Gate — Creating Entanglement

The CNOT (Controlled-NOT) gate is a 2-qubit gate that flips the second qubit (target) if and only if the first qubit (control) is $|1\rangle$:

\[\text{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\]

Its action on the basis states:

$\text{CNOT}|00\rangle = |00\rangle \quad \text{(control=0, target unchanged)}$ $\text{CNOT}|01\rangle = |01\rangle \quad \text{(control=0, target unchanged)}$ $\text{CNOT}|10\rangle = |11\rangle \quad \text{(control=1, target FLIPPED)}$ $\text{CNOT}|11\rangle = |10\rangle \quad \text{(control=1, target FLIPPED)}$

Creating a Bell State

Apply $H$ to the first qubit, then CNOT:

Step 1: $H \otimes I$ on $|00\rangle$:

\[(H \otimes I)|00\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle)\]

Step 2: CNOT:

\[\text{CNOT}\left[\frac{1}{\sqrt{2}}(|00\rangle + |10\rangle)\right] = \frac{1}{\sqrt{2}}(\text{CNOT}|00\rangle + \text{CNOT}|10\rangle) = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) = |\Phi^+\rangle\]

Two gates. That’s all it takes to create the “spooky” quantum entanglement that Einstein argued about. It’s just matrix multiplication.

In circuit notation (which we’ll cover in article 3):

q0: ─[H]─●─
          │
q1: ─────⊕─

The $H$ creates superposition. The CNOT creates entanglement. Together, they produce a Bell pair.

Outer Products and Projection

Outer Product

The outer product of a ket and a bra gives a matrix:

\[|0\rangle\langle 0| = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\begin{pmatrix} 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}\] \[|1\rangle\langle 1| = \begin{pmatrix} 0 \\ 0 \end{pmatrix}\begin{pmatrix} 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}\]

These are projection operators. $|0\rangle\langle 0|$ projects any state onto $|0\rangle$:

\[|0\rangle\langle 0|\psi\rangle = |0\rangle \cdot \alpha = \alpha|0\rangle\]

This is how measurement works mathematically — it projects the state onto the measured basis.

Completeness Relation

The projectors onto all basis states sum to the identity:

\[|0\rangle\langle 0| + |1\rangle\langle 1| = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I\]

This means any state can be decomposed into basis components — the foundation of measurement.

Writing Gates Using Outer Products

Any gate can be written in terms of outer products. For example:

\[X = |0\rangle\langle 1| + |1\rangle\langle 0|\] \[Z = |0\rangle\langle 0| - |1\rangle\langle 1|\] \[\text{CNOT} = |0\rangle\langle 0| \otimes I + |1\rangle\langle 1| \otimes X\]

That CNOT expression reads: “If the control qubit is $|0\rangle$, do nothing to the target. If the control is $|1\rangle$, apply $X$ to the target.” The math mirrors the logic perfectly.

Eigenvalues and Eigenvectors

A vector $|v\rangle$ is an eigenvector of matrix $U$ with eigenvalue $\lambda$ if:

\[U|v\rangle = \lambda|v\rangle\]

The matrix acts on the vector and just scales it — doesn’t change its direction.

Eigenstates of Pauli-Z

\[Z|0\rangle = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} = (+1)|0\rangle\] \[Z|1\rangle = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ -1 \end{pmatrix} = (-1)|1\rangle\]

$|0\rangle$ is an eigenvector with eigenvalue $+1$. $|1\rangle$ is an eigenvector with eigenvalue $-1$.

Why Eigenvalues Matter

In quantum mechanics, measurement results are eigenvalues, and the state after measurement is the corresponding eigenvector. When you measure a qubit in the Z-basis (the standard computational basis), you get eigenvalue $+1$ (which we call “0”) or $-1$ (which we call “1”).

Shor’s algorithm uses eigenvalue estimation (technically “phase estimation”) to find the period of a modular exponentiation function — which is equivalent to factoring. The eigenvalues encode the answer.

Putting It All Together — A Complete Example

Let’s trace through a small quantum computation step by step, showing every matrix multiplication.

Task: Create a Bell state from $|00\rangle$ and verify it’s entangled.

Step 1: Start with $|00\rangle$

\[|\psi_0\rangle = |00\rangle = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}\]

Step 2: Apply $H$ to qubit 0 (and $I$ to qubit 1)

\[|\psi_1\rangle = (H \otimes I)|\psi_0\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}\]

This is $\frac{1}{\sqrt{2}}(|00\rangle + |10\rangle)$. Qubit 0 is in superposition, qubit 1 is still $|0\rangle$.

Step 3: Apply CNOT

\[|\psi_2\rangle = \text{CNOT}|\psi_1\rangle = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}\]

This is $\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) = |\Phi^+\rangle$.

Step 4: Verify it’s entangled

As we showed earlier, this state cannot be factored into $|a\rangle \otimes |b\rangle$. Therefore it’s entangled.

Step 5: Measure

\[P(00) = \left|\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2}, \quad P(01) = 0, \quad P(10) = 0, \quad P(11) = \frac{1}{2}\]

50% chance of $|00\rangle$, 50% chance of $|11\rangle$. Both qubits always agree. That’s entanglement.

Every step was just matrix multiplication on vectors. No magic — just linear algebra.

Cheat Sheet — The Math You’ll Use Most

Concept	Formula	Quantum Meaning
State vector	$\|\psi\rangle = \begin{pmatrix} \alpha \ \beta \end{pmatrix}$	A qubit’s state
Inner product	$\langle\phi\|\psi\rangle$	Overlap / probability amplitude
Measurement probability	$P = \|\langle\phi\|\psi\rangle\|^2$	Chance of measuring $\|\phi\rangle$
Gate application	$\|\psi’\rangle = U\|\psi\rangle$	Matrix × vector
Sequential gates	$BA\|\psi\rangle$	Apply $A$ first, then $B$
Tensor product (states)	$\|\psi\rangle \otimes \|\phi\rangle$	Multi-qubit state
Tensor product (gates)	$A \otimes B$	Parallel gate application
Unitary condition	$U^\dagger U = I$	Gate is valid / reversible
Conjugate transpose	$U^\dagger = (U^T)^*$	Transpose + complex conjugate
Projection	$\|i\rangle\langle i\|$	Measurement operator
Eigenvalue equation	$U\|v\rangle = \lambda\|v\rangle$	Measurement results are eigenvalues

What’s Next

You now have all the math needed to build and analyze quantum circuits. In the next article, we’ll put these tools to work — building circuits from gates, implementing quantum teleportation, and seeing how interference creates useful computation.

The math we covered here — vectors, matrices, tensor products, inner products — will be used in every remaining article in the series. Keep this as a reference. When something looks confusing later, come back here and check the cheat sheet.

Thanks for reading!