Cheat Sheet – Mathematical Foundations of Quantum Computing

Standard Qubit States

• |0⟩ =

• |1⟩ =

• Inner product $[a \; b] \begin{pmatrix} c \\ d \end{pmatrix} = a \cdot c + b \cdot d$

• Outer product examples:

  • $|0\rangle\langle0| = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$
  • $|0\rangle\langle1| = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$
  • $|1\rangle\langle0| = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$
  • $|1\rangle\langle1| = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$

Shortcut to calculating outer Products

Note that if you read the ket-bra as a binary number (e.g. $|1\rangle\langle0|$ as 2), the binary number corresponds to the index in the matrix where the 1 is. All others are 0.

Shortcut to calculating inner Products

Note that if the 2 numbers in the ket-bra are equal, the inner product returns 1, otherwise 0

• $\langle 0|0 \rangle = 1$
• $\langle 0|1 \rangle = 0$
• $\langle 1|0 \rangle = 0$
• $\langle 1|1 \rangle = 1$

Bra-ket (Inner Products)

Polar Basis States

Pauli Matrices

• X:

• Y:

• Z:

Pauli Matrices as outer Products

• X:

• Y:

• Z:

Hermitian Transpose

For $z = a + bi$, $\quad z^* = a - bi$.

Transpose Matrix and complex conjugate its elements:

• $\left( A | y \rangle \right)^\dagger = \langle y | A^\dagger$
• $\left( AB \right)^\dagger = B^\dagger A^\dagger$
• $\left( aA + bB \right)^\dagger = a^* A^\dagger + b^* B^\dagger$

Effects on the Basis States

Effects of the Pauli Matrices and the Hadamard gate on the basis states and polar basis states

Kronecker Product

• Associativity
• Distributivity
• Non-commutativity
• Mixed product property: $(W \otimes X)\,(Y \otimes Z) = (WY) \otimes (XZ)$
• Transpose and complex conjugate distribution: $(X \otimes Y)^T = X^T \otimes Y^T$ $(X \otimes Y)^* = X^* \otimes Y^*$

Hadamard Gate

(For higher dimensions: $H_n = H_2 \otimes H_{n-1}$, etc.)

Also,

$H = \frac{1}{\sqrt{2}} (X + Z)$

and

$HXH = Z$

Vector Space Axioms

$\oplus$

1. Commutativity of addition
2. Associativity of addition
3. Neutral element (existence of a zero vector)
4. Inverse elements (existence of additive inverses)

$\otimes$

5. Distributivity (over vector addition and scalar multiplication)
   • $a \cdot (x \oplus y) = a \cdot x \oplus a \cdot y$
   • $(a + b) \cdot x = a \cdot x \oplus b \cdot x$
6. Scalar associativity (compatibility of scalar multiplication)
7. Unity of scalar multiplication (existence of multiplicative identity)

Key Matrix Definitions

• Hermitian: $A = A^\dagger$

  • Hermitian matrices have real diagonal entries.
  • Eigenvalues of a Hermitian matrix are real.

• Normal: $AA^\dagger = A^\dagger A$

• Unitary: $A^\dagger A = A A^\dagger = I$

  • Eigenvalues have absolute value 1.
  • $\det(A)$ has absolute value 1.

Useful Facts

• Trace($A$) = sum of eigenvalues.

• Det($A$) = product of eigenvalues.

• Rank($A$) = maximum number of linearly independent rows (or columns).

• Exponential of a matrix:

• Log of a matrix (for suitably defined $A$):

$\sin$ and $\cos$

Series expansions (for scalar $x$):

y-intercepts:

Symmetry:

Roots:

Relation to $e^x$:

Idempotent and Projection

• Idempotent: $A^2 = A$.

  • Every idempotent matrix is a projection matrix (and vice versa).
  • Eigenvalues of an idempotent matrix are 0 or 1.
  • $\text{tr}(A) = \text{rank}(A)$ if $A$ is idempotent.
  • If $A$ and $B$ are idempotent, then $AB$ is idempotent only if $AB=BA$.
  • If $A$ and $B$ are idempotent, then $A+B$ is idempotent only if $AB=-BA$.
  • $I-A$ idempotent, if A idempotent

• Projection matrix $P$:

  • $P = \lvert u \rangle \langle u \rvert \quad \text{(if $\|u\|=1$, projects onto $\text{span}\{u\}$)}$
  • $\langle u \mid u \rangle = 1 \Rightarrow \mid u \rangle \langle u \mid$ is idempotent
  • Satisfies $P^2 = P$.

Involutory Matrices

• Involutory: $A^2 = I$.
  • Eigenvalues are $\pm 1$.
  • $\det(A) = \pm 1$.
  • $A$ is idempotent $\Leftrightarrow \frac{I + A}{2}$ is idempotent.
  • $A$ is idempotent $\Leftrightarrow \frac{I - A}{2}$ is idempotent.
  • Powers of $A$ alternate between $I$ and $A$.
  • $A, B$ involutory $\Rightarrow$ $A, B$ only involutory if $AB=BA$

Permutation Matrices

• Permutation matrix $P$:
  • Square, entries in $\{0,1\}$.
  • Exactly one "1" in each row and column, others 0.
  • Sums of each row and each column are 1.
  • Orthogonal, unitary, and invertible.
  • If you multiply a permutation matrix by itself often enough, you eventually get the identity.
  • Product of two permutation matrices is another permutation matrix.

Eigenvectors and Eigenvalues

• For matrix $A$, an eigenvector $\mathbf{x}$ and eigenvalue $\lambda$ satisfy

• For a Hermitian $A$, $\lambda$ is real.
• For a Hermitian Matrix, its Eigenvectors are orthogonal
• For a unitary $A$, $\lvert \lambda \rvert = 1$.
• For an idempotent $A$, $\lambda \in \{0, 1\}$.
• For an involutory $A$, $\lambda \in \{\pm 1\}$.

Permutation Matrices

• Permutation matrix $P$:
  • Square, entries in $\{0,1\}$.
  • Exactly one "1" in each row and column, others 0.
  • Sums of each row and each column are 1.
  • Orthogonal, unitary, and invertible.
  • If you multiply a permutation matrix by itself often enough, you eventually get the identity.
  • Product of two permutation matrices is another permutation matrix.

More or less relevant linear algebra concepts

Eigenvectors and Eigenvalues

• For matrix $A$, an eigenvector $\mathbf{x}$ and eigenvalue $\lambda$ satisfy

Determinant of a Matrix

For a 2x2 Matrix

For a 2x2 matrix

the determinant is given by:

Using Cofactor Expansion

For an $n \times n$ matrix, the determinant can be calculated using cofactor expansion along any row or column. For example, expanding along the first row:

where $A_{1j}$ is the $(n-1) \times (n-1)$ submatrix obtained by removing the first row and $j$-th column of $A$.

For example, for a 3x3 matrix

the determinant is given by:

Properties of Determinants

• Multiplicative Property: $\det(AB) = \det(A) \det(B)$
• Transpose: $\det(A^T) = \det(A)$
• Inverse: If $A$ is invertible, $\det(A^{-1}) = \frac{1}{\det(A)}$
• Determinant of Identity Matrix: $\det(I) = 1$
• Row Operations:
  • Swapping two rows multiplies the determinant by $-1$.
  • Multiplying a row by a scalar $k$ multiplies the determinant by $k$.
  • Adding a multiple of one row to another row does not change the determinant.

Kernel, Image, and Related Concepts

Kernel (Null Space)

The kernel (or null space) of a matrix $A$, denoted as $\ker(A)$ or $\text{null}(A)$, is the set of all vectors $\mathbf{x}$ such that $A\mathbf{x} = \mathbf{0}$. In other words, it is the set of solutions to the homogeneous equation $A\mathbf{x} = \mathbf{0}$.

Image (Column Space)

The image (or column space) of a matrix $A$, denoted as $\text{im}(A)$ or $\text{col}(A)$, is the set of all vectors that can be expressed as $A\mathbf{x}$ for some vector $\mathbf{x}$. It is the span of the columns of $A$.

Rank

The rank of a matrix $A$, denoted as $\text{rank}(A)$, is the dimension of the image (column space) of $A$. It represents the maximum number of linearly independent columns of $A$.

Nullity

The nullity of a matrix $A$, denoted as $\text{nullity}(A)$, is the dimension of the kernel (null space) of $A$. It represents the number of linearly independent solutions to the homogeneous equation $A\mathbf{x} = \mathbf{0}$.

Rank-Nullity Theorem

The rank-nullity theorem states that for any $m \times n$ matrix $A$:

where $n$ is the number of columns of $A$.

Worksheets

General Bit Manipulation

• Calculate required bits for a binary number: $\lfloor\log_2(n)\rfloor+1$
• Convert a decimal number to binary: $\text{mod}(n,2),\text{div}(n,2)$
• Convert a decimal number to binary grey code: $base2(n^{(n>>1)})$*
  • Bitshift right by 1: equivalent to dividing by 2

Boolean Fourier Transform

Every pseudo-boolean function can be represented as a polynomial in the form of a sum of products of boolean variables: $f(x) = \sum_{S \subseteq [n]} \omega _S \prod_{i \in S} x_i$ $= \sum_{S \subseteq [n]} \omega _S \varphi_S(x)$ $= \omega^T \varphi_S(x)$

Example:

TODO task 1.6

Hadamard

Hadamard Matrix Definition

• Hadamard Matrix: $H_1 = \frac{1}{\sqrt{2}}\begin{bmatrix}1 & 1 \\ 1 & -1\end{bmatrix}$
• $H_0 = [1]$
• For higher dimensions: $H_n = H_2 \otimes H_{n-1}$
• $H_2 = \frac{1}{2}\begin{bmatrix}1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1\end{bmatrix}$

Hadamard Transform

Because the Hadamard matrix is unitary, it is involutory. If we want to solve $f = H_n \cdot w$ for $w$, we can calculate it directly: $w = H_n \cdot f$

Fourier

Fourier Matrix Definition

• Fourier Matrix: $F_n = \frac{1}{\sqrt{2^n}}\begin{bmatrix}1 & 1 & 1 & 1 & \cdots \\ 1 & \omega & \omega^2 & \omega^3 & \cdots \\ 1 & \omega^2 & \omega^4 & \omega^6 & \cdots \\ 1 & \omega^3 & \omega^6 & \omega^9 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots\end{bmatrix}$
• $\omega = \exp{\frac{2\pi i}{2^n}}$
• $\omega$ is a primitive $2^n$-th root of unity

Fourier Transform

Because the Fourier matrix is unitary, it is involutory. If we want to solve $f = F_n \cdot w$ for $w$, we can calculate it directly: $w = F_n \cdot f$

TODO task 2.3 b)

Bool-Möbius Transform

Sierpinski Matrix

• Sierpinski Matrix:
  • $S_1 = \begin{bmatrix}1 & 0 \\ 1 & 1\end{bmatrix}$
  • $S_n = S_1 \otimes S_{n-1}$
  • $S_2 = \begin{bmatrix}1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1\end{bmatrix}$

Bool-Möbius Transform

Because $S_n\times S_n = I$, the Sierpinski matrix is involutory. If we want to solve $f = S_n \cdot w$ for $w$, we can calculate it directly: $w = S_n \cdot f$

Yet another Feature Transform

Compared to our original

we now have

Recursive definition: $\phi([]) = [1]$ $\phi([x_1, x_2, \ldots, x_n]) = \begin{bmatrix} 1 \\ x_n \end{bmatrix} \otimes \phi([x_1, x_2, \ldots, x_{n-1}])$

Pauli Matrices

• The Pauli Matrices are unitary and involutory.
• They can easily be written as linear combinations of outer products:
• $I = |0\rangle\langle0| + |1\rangle\langle1| = \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}$
• $X = |0\rangle\langle1| + |1\rangle\langle0| = \begin{pmatrix}0 & 1 \\ 1 & 0\end{pmatrix}$
• $Y = -i|0\rangle\langle1| + i|1\rangle\langle0| = \begin{pmatrix}0 & -i \\ i & 0\end{pmatrix}$
• $Z = |0\rangle\langle0| - |1\rangle\langle1| = \begin{pmatrix}1 & 0 \\ 0 & -1\end{pmatrix}$
• Because they are unitary, their Eigenvalues are of norm 1. Because they are Hermitian, their Eigenvalues are real. Therefore, the Eigenvalues of the Pauli Matrices are $\pm 1$.
• Because they are Hermitian, their Eigenvectors are orthogonal.
• Their Eigenvectors are:
  • $I$: $\begin{pmatrix}1 \\ 0\end{pmatrix}$ and $\begin{pmatrix}0 \\ 1\end{pmatrix}$
  • $X$: $\begin{pmatrix}1 \\ 1\end{pmatrix}$ and $\begin{pmatrix}1 \\ -1\end{pmatrix}$
  • $Z$: $\begin{pmatrix}1 \\ 0\end{pmatrix}$ and $\begin{pmatrix}0 \\ 1\end{pmatrix}$
  • $Y$: $\begin{pmatrix}1 \\ i\end{pmatrix}$ and $\begin{pmatrix}1 \\ -i\end{pmatrix}$

Matrix Exponential

$e^{i\theta X} = \cos(\theta)I + i\sin(\theta)X$

Therefore,

• $R_X(\theta) = e^{-i\theta X} = \cos(\theta)I - i\sin(\theta)X$
• $R_Y(\theta) = e^{-i\theta Y} = \cos(\theta)I - i\sin(\theta)Y$
• $R_Z(\theta) = e^{-i\theta Z} = \cos(\theta)I - i\sin(\theta)Z$

Linear Combinations of Pauli Matrices

Every matrix $A \in \mathbb{C}^{2\times 2}$ can be written as a linear combination of the Pauli Matrices.

This is because we can write the standard basis as a linear combination of the Pauli Matrices:

$|0\rangle \langle 0| = \frac{1}{2}(I + Z)$ $|1\rangle \langle 1| = \frac{1}{2}(I - Z)$ $|0\rangle \langle 1| = \frac{1}{2}(X + iY)$ $|1\rangle \langle 0| = \frac{1}{2}(X - iY)$

$A = \frac{1}{2}\left(\text{Tr}(A)I + \text{Tr}(AX)X + \text{Tr}(AY)Y + \text{Tr}(AZ)Z\right)$

Example

The Matrix $V = \frac{1}{\sqrt{2}} \begin{bmatrix} i & -i \\ 1 & 1 \end{bmatrix}$

Beam Splitter

$B=\frac{1}{\sqrt{2}}\begin{bmatrix}1 & i \\ i & 1\end{bmatrix}$

Wiederholt sich beim Quadrieren.

Bivariate Functions as 2x2 Matrices

Every bivariate function can be represented as a 2x2 matrix.

With $x=\begin{bmatrix}1\\x\end{bmatrix}$ and $y=\begin{bmatrix}1\\y\end{bmatrix}$, we can write the function $f$ as

$x^T \begin{bmatrix}a & b \\ c & d\end{bmatrix} y = a + by + cx + dxy$

3D Vectors as Matrices

Every 3D vector can be represented as a matrix.

$X(\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}) = \begin{bmatrix} x_3 & x_1 - ix_2 \\ x_1 + ix_2 & -x_3 \end{bmatrix}$

$X(\begin{pmatrix}1\\0\\0\end{pmatrix}) = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = X$ $X(\begin{pmatrix}0\\1\\0\end{pmatrix}) = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} = Y$ $X(\begin{pmatrix}0\\0\\1\end{pmatrix}) = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} = Z$

Note the following:

$x^Ty = \frac{1}{2}\text{Tr}(XY)$

And for square matrices: $\text{Tr}(AB) = \text{Tr}(BA)$

Therefore, the inner product of 2 real vectors is symmetric

Born Rule

the spatial component of the wave function of a 1D particle trapped in a 1D well is given by

$\text{for } 0 \leq x \leq w \text{ and by}$

elsewhere.

Inner Product is 0 when orthogonal, i.e., when two different eigenvectors are multiplied, the result is 0.

If we have two identical eigenvectors:

4th roots of unity

Rotations in the complex plane

To rotate a complex number by an angle, we multiply it by $i^x = e^{x\times\ln(i)}$

What is $\ln(i)$?

$e^{ix} = i\,\sin(x) + \cos(x)$

$e^{\ln(i)} = i \quad\Longrightarrow\quad e^{\frac{\ln(i)}{i}} = i$

Phase Gate

$S = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix}$

It is the generator of:

$G= \{\begin{bmatrix} 1 & 0 \\ 0 & e^{i2\pi /n} \end{bmatrix}^k | k \in \Z \}$

Quaternions

Quaternions are a non-commutative extension of complex numbers.

Quaternions as Matrices

The matrices for (i), (j), and (k) are given as:

The product (ijk) gives:

Finally, multiplying further:

This aligns with (ijk = -1).

TODO 4.9

Vector Logic

Example

Given a matrix

$C = n[n\otimes n]^T + n[n\otimes s]^T + n[s \otimes n]^T + s[s \otimes s]^T$ $= \begin{bmatrix} 1 & 1&1&0 \\ 0&0&0&1 \end{bmatrix}$

multiplying it with, say, $\begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}$ gives you the first column of the matrix, which is $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$.

You can also write C as:

$C = F \otimes n^T + I \otimes s^T$

because the kronecker product is linear.

Bilinearity of the Kronecker Product

We start with:

Distributing the terms:

Which simplifies to:

Tensor Products and the Born Rule

If we have two states $|a\rangle$ and $|b\rangle$ that obey the Born rule, then the tensor product of these states also obeys the Born rule.