Skip to content

Chapter 1: Mathematical Prerequisites for QML

Quantum machine learning lives at the intersection of several deep mathematical traditions. This chapter builds the scaffolding you will use throughout the book: linear algebra over complex fields, probability theory, optimization, information theory, and Fourier analysis. Each section is written with QML applications in mind — we do not merely review mathematics, but motivate every concept with its role in quantum algorithms and learning theory.

Learning Objectives

By the end of this chapter, you will be able to:

  • Work fluently with complex vector spaces, Hilbert spaces, and tensor products

  • Compute spectral decompositions of Hermitian and unitary matrices

  • Apply the Singular Value Decomposition and understand its geometric meaning

  • Reason about probability distributions, expectation values, and Bayesian inference

  • Analyze convex optimization problems and apply gradient descent convergence results

  • Compute Shannon entropy, KL divergence, and mutual information

  • Connect the Discrete Fourier Transform to the Quantum Fourier Transform

1.1 Linear Algebra for Quantum Systems

1.1.1 Vector Spaces and Inner Products

A vector space over a field \(\mathcal{F}\) (for us, \(\mathcal{F} = \mathbb{C}\)) is a set \(V\) equipped with addition and scalar multiplication satisfying the standard axioms. Quantum states live in complex vector spaces, making complex number arithmetic indispensable.

Definition: Complex Inner Product Space

A complex inner product space \((V, \langle\cdot,\cdot\rangle)\) is a complex vector space equipped with a map \(\langle\cdot,\cdot\rangle: V \times V \to \mathbb{C}\) satisfying:

  1. Conjugate symmetry: \(\langle \mathbf{u}, \mathbf{v} \rangle = \overline{\langle \mathbf{v}, \mathbf{u} \rangle}\)

  2. Linearity in second argument: \(\langle \mathbf{u}, \alpha\mathbf{v} + \beta\mathbf{w} \rangle = \alpha\langle \mathbf{u}, \mathbf{v} \rangle + \beta\langle \mathbf{u}, \mathbf{w} \rangle\)

  3. Positive definiteness: \(\langle \mathbf{v}, \mathbf{v} \rangle \geq 0\), with equality iff \(\mathbf{v} = \mathbf{0}\)

The induced norm is \(\|\mathbf{v}\| = \sqrt{\langle \mathbf{v}, \mathbf{v} \rangle}\).

Note

In quantum mechanics (and physics generally), the inner product is linear in the second argument (“ket”) and conjugate-linear in the first (“bra”). In much of mathematics, the convention is reversed. We follow the physics convention throughout this book.

For \(\mathbb{C}^n\) with column vectors \(\mathbf{u}, \mathbf{v} \in \mathbb{C}^n\), the standard inner product is:

\[\langle \mathbf{u}, \mathbf{v} \rangle = \mathbf{u}^\dagger \mathbf{v} = \sum_{i=1}^n \bar{u}_i v_i\tag{1.1}\]

where \(\mathbf{u}^\dagger = (\mathbf{u}^*)^\top\) denotes the conjugate transpose.

1.1.2 Hilbert Spaces

Definition: Hilbert Space

A Hilbert space \(\mathcal{H}\) is a complete inner product space. Completeness means every Cauchy sequence converges to a limit in \(\mathcal{H}\). For QML, the relevant Hilbert spaces are:

  • \(\mathbb{C}^{2^n}\) for an \(n\)-qubit system (finite-dimensional, always complete)

  • \(L^2(\mathbb{R}^d)\) for continuous-variable quantum systems

Orthonormal Bases. A set \(\{|e_i\rangle\}_{i=0}^{N-1}\) is an orthonormal basis if \(\langle e_i | e_j \rangle = \delta_{ij}\) and every \(|\psi\rangle \in \mathcal{H}\) can be written \(|\psi\rangle = \sum_i c_i |e_i\rangle\) with \(c_i = \langle e_i | \psi\rangle\).

The computational basis for \(n\) qubits consists of \(2^n\) basis vectors \(\{|0\cdots0\rangle, |0\cdots1\rangle, …, |1\cdots1\rangle\}\), one for each binary string of length \(n\).

1.1.3 Matrix Classes in Quantum Computing

Table 1.1. Key matrix classes in quantum computing
Class Definition Property QC Role
Hermitian \(A = A^\dagger\) Real eigenvalues Observables, Hamiltonians
Unitary \(UU^\dagger = I\) \(|\lambda_i| = 1\) Quantum gates
Normal \(AA^\dagger = A^\dagger A\) Unitarily diagonalizable Both + more
Positive semidefinite \(\langle v|A|v\rangle \geq 0\) \(\lambda_i \geq 0\) Density matrices
Projection \(P^2 = P = P^\dagger\) \(\lambda_i \in \{0,1\}\) Measurements

Pauli Matrices. The four Pauli matrices are the single-qubit observables:

\[I = \begin{pmatrix}1&0\\0&1\end{pmatrix}, \quad X = \begin{pmatrix}0&1\\1&0\end{pmatrix}, \quad Y = \begin{pmatrix}0&-i\\i&0\end{pmatrix}, \quad Z = \begin{pmatrix}1&0\\0&-1\end{pmatrix}\tag{1.2}\]

They satisfy \(X^2=Y^2=Z^2=I\), \(XY=iZ\), \(YZ=iX\), \(ZX=iY\).

1.1.4 Spectral Decomposition

Theorem 1.1 (Spectral Theorem)

Every normal matrix \(A \in \mathbb{C}^{n\times n}\) can be diagonalized by a unitary matrix:

\[A = U \Lambda U^\dagger = \sum_{i=1}^n \lambda_i |u_i\rangle\langle u_i|\tag{1.3}\]

where \(\lambda_i \in \mathbb{C}\) are eigenvalues and \(|u_i\rangle\) are orthonormal eigenvectors.

For Hermitian matrices (\(A = A^\dagger\)), all eigenvalues are real. For unitary matrices (\(U^\dagger U = I\)), all eigenvalues satisfy \(|\lambda_i| = 1\), i.e., \(\lambda_i = e^{i\phi_i}\).

Solved Example 1.1

Problem: Find the spectral decomposition of \(A = \begin{pmatrix}2&-i\\i&2\end{pmatrix}\).

Solution:

  1. Eigenvalues: \(\det(A - \lambda I) = (2-\lambda)^2 - (i)(-i) = (2-\lambda)^2 - 1 = 0\), giving \(\lambda_1 = 1\), \(\lambda_2 = 3\).

  2. Eigenvector for \(\lambda_1=1\): \((A-I)\mathbf{v}=0\): \(\begin{pmatrix}1&-i\\i&1\end{pmatrix}\mathbf{v}=0 \Rightarrow v_1 = iv_2\). Normalizing: \(|u_1\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}i\\1\end{pmatrix}\).

  3. Eigenvector for \(\lambda_2=3\): \(v_1 = -iv_2 \Rightarrow |u_2\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}-i\\1\end{pmatrix}\).

  4. Verification: \(U^\dagger A U = \text{diag}(1,3)\). ✓

The decomposition is \(A = 1\cdot|u_1\rangle\langle u_1| + 3\cdot|u_2\rangle\langle u_2|\).

1.1.5 Tensor Products

The tensor product is the mathematical operation that combines two quantum systems into a larger composite system.

Definition: Tensor Product

For vectors \(|\psi\rangle \in \mathbb{C}^m\) and \(|\phi\rangle \in \mathbb{C}^n\), the tensor product \(|\psi\rangle \otimes |\phi\rangle \in \mathbb{C}^{mn}\) has components \((|\psi\rangle \otimes |\phi\rangle)_{ik} = \psi_i \phi_k\). For matrices \(A \in \mathbb{C}^{m\times m}\) and \(B \in \mathbb{C}^{n\times n}\):

\[A \otimes B = \begin{pmatrix} a_{11}B & \cdots & a_{1m}B \\ \vdots & \ddots & \vdots \\ a_{m1}B & \cdots & a_{mm}B \end{pmatrix} \in \mathbb{C}^{mn\times mn}\]

Two-qubit computational basis:

\[|00\rangle = |0\rangle \otimes |0\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}\]

Solved Example 1.2

Problem: Compute \(|+\rangle \otimes |0\rangle\) where \(|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\).

Solution:

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

This is a product state (not entangled): both qubits are independent.

1.1.6 Singular Value Decomposition

Theorem 1.2 (Singular Value Decomposition)

Every matrix \(A \in \mathbb{C}^{m\times n}\) with \(\text{rank}(A)=r\) can be written:

\[A = U \Sigma V^\dagger\tag{1.4}\]

where \(U \in \mathbb{C}^{m\times m}\) and \(V \in \mathbb{C}^{n\times n}\) are unitary, and \(\Sigma \in \mathbb{R}^{m\times n}\) is diagonal with non-negative entries \(\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0\) (singular values).

QML Applications of SVD:

  • Quantum PCA (qPCA): SVD of the data matrix defines principal components

  • Low-rank approximation: Best rank-\(k\) approximation \(A_k = \sum_{i=1}^k \sigma_i |u_i\rangle\langle v_i|\)

  • Amplitude encoding: SVD helps understand state preparation complexity

  • Matrix inversion: \(A^+ = V\Sigma^+U^\dagger\) (Moore-Penrose pseudoinverse)

Geometric interpretation of SVD: A = U\Sigma V^\dagger transforms the unit circle sequentially via rotation (V^\dagger), scaling (\Sigma), and another rotation (U), producing an ellipse. Singular…
Figure 1.1. Geometric interpretation of SVD: \(A = U\Sigma V^\dagger\) transforms the unit circle sequentially via rotation (\(V^\dagger\)), scaling (\(\Sigma\)), and another rotation (\(U\)), producing an ellipse. Singular values equal the ellipse semi-axes. Figure drawn for this book

1.2 Probability and Statistics

1.2.1 Probability Spaces and Random Variables

A probability space \((\Omega, \mathcal{F}, P)\) consists of a sample space \(\Omega\), a \(\sigma\)-algebra \(\mathcal{F}\), and a probability measure \(P\). A random variable \(X: \Omega \to \mathbb{R}\) is a measurable function.

Key quantities for a random variable \(X\):

\[\begin{align*} \mathbb{E}[X] &= \sum_x x P(X=x) \quad \text{(discrete)} \\ \mathbb{E}[X] &= \int_{-\infty}^\infty x f_X(x)\,dx \quad \text{(continuous)} \\ \text{Var}[X] &= \mathbb{E}[X^2] - (\mathbb{E}[X])^2 \\ \text{Cov}[X,Y] &= \mathbb{E}[(X-\mathbb{E}[X])(Y-\mathbb{E}[Y])] \end{align*}\]

Note

In quantum mechanics, measurement outcomes are inherently probabilistic. The Born rule \(P(\text{outcome } m) = \text{Tr}[\Pi_m \rho]\) is the quantum analogue of a probability distribution over measurement results.

1.2.2 Multivariate Gaussian Distribution

The multivariate Gaussian \(\mathcal{N}(\boldsymbol{\mu}, \boldsymbol{\Sigma})\) with mean \(\boldsymbol{\mu} \in \mathbb{R}^d\) and positive definite covariance \(\boldsymbol{\Sigma} \in \mathbb{R}^{d\times d}\) has PDF:

\[f(\mathbf{x}) = \frac{1}{(2\pi)^{d/2}|\boldsymbol{\Sigma}|^{1/2}} \exp\!\left(-\frac{1}{2}(\mathbf{x}-\boldsymbol{\mu})^\top \boldsymbol{\Sigma}^{-1} (\mathbf{x}-\boldsymbol{\mu})\right)\tag{1.9}\]

It appears in quantum noise models, Gaussian processes, and variational Bayes.

1.2.3 Bayesian Inference

Bayes’ Theorem:

\[P(\theta|\mathcal{D}) = \frac{P(\mathcal{D}|\theta) P(\theta)}{P(\mathcal{D})} \propto P(\mathcal{D}|\theta) P(\theta)\tag{1.10}\]

Here \(P(\theta)\) is the prior, \(P(\mathcal{D}|\theta)\) is the likelihood, and \(P(\theta|\mathcal{D})\) is the posterior.

Maximum Likelihood Estimation (MLE):

\[\hat{\theta}_{\text{MLE}} = \operatorname{argmax}_\theta \log P(\mathcal{D}|\theta) = \operatorname{argmax}_\theta \sum_{i=1}^N \log P(x_i|\theta)\]

1.2.4 Concentration Inequalities

Concentration inequalities bound how far a random quantity deviates from its expectation. They underpin sample complexity theory in QML.

Theorem 1.3 (Hoeffding’s Inequality)

Let \(X_1, …, X_N\) be independent random variables with \(X_i \in [a_i, b_i]\). Then for any \(t > 0\):

\[P\!\left(\frac{1}{N}\sum_{i=1}^N X_i - \mathbb{E}[X_i] \geq t\right) \leq \exp\!\left(\frac{-2N^2 t^2}{\sum_{i=1}^N (b_i-a_i)^2}\right)\tag{1.11}\]

QML implication: Hoeffding’s inequality justifies why \(O(1/\epsilon^2)\) measurements suffice to estimate a quantum expectation value to accuracy \(\epsilon\) (since each measurement outcome lies in \([-1, 1]\)).

1.3 Optimization Theory

1.3.1 Convex Analysis

Definition: Convex Function

A function \(f: \mathbb{R}^d \to \mathbb{R}\) is convex if for all \(\mathbf{x}, \mathbf{y} \in \text{dom}(f)\) and \(t \in [0,1]\):

\[f(t\mathbf{x} + (1-t)\mathbf{y}) \leq t f(\mathbf{x}) + (1-t) f(\mathbf{y})\]

Equivalently (for differentiable \(f\)): \(f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^\top(\mathbf{y}-\mathbf{x})\).

A function is \(\beta\)-smooth if \(\|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\| \leq \beta\|\mathbf{x}-\mathbf{y}\|\) and \(\alpha\)-strongly convex if \(f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^\top(\mathbf{y}-\mathbf{x}) + \frac{\alpha}{2}\|\mathbf{x}-\mathbf{y}\|^2\).

Important

Most quantum cost functions are not convex. They involve trigonometric functions of parameters, creating a rich landscape with many local minima — or worse, a flat “barren plateau” where gradients vanish exponentially. See Chapter 16 for a detailed treatment.

1.3.2 Gradient Descent and Convergence

The gradient descent update rule with step size \(\eta > 0\):

\[\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta \nabla_{\boldsymbol{\theta}} \mathcal{L}(\boldsymbol{\theta}_t)\tag{1.12}\]

Theorem 1.4 (Convergence of GD for Smooth Convex Functions)

If \(f\) is convex and \(\beta\)-smooth, gradient descent with \(\eta = 1/\beta\) satisfies:

\[f(\boldsymbol{\theta}_T) - f(\boldsymbol{\theta}^*) \leq \frac{\|\boldsymbol{\theta}_0 - \boldsymbol{\theta}^*\|^2}{2\eta T} = \mathcal{O}(1/T)\tag{1.13}\]

For \(\alpha\)-strongly convex, \(\beta\)-smooth functions, convergence is geometric: \(f(\boldsymbol{\theta}_T) - f^* \leq (1 - \alpha/\beta)^T (f(\boldsymbol{\theta}_0) - f^*)\).

Algorithm: Stochastic Gradient Descent (SGD)

Input: Loss \(\mathcal{L}\), data \(\{(\mathbf{x}_i, y_i)\}\), learning rate schedule \(\{\eta_t\}\), epochs \(T\)

Output: Optimized parameters \(\boldsymbol{\theta}^*\)

  1. Initialize \(\boldsymbol{\theta}_0\) (e.g., random)

  2. For \(t = 1, 2, …, T\):

    1. Sample mini-batch \(\mathcal{B} \subset \{1,…,N\}\) of size \(b\)

    2. Compute stochastic gradient: \(\hat{g}_t = \frac{1}{b}\sum_{i\in\mathcal{B}} \nabla_\theta \ell(\boldsymbol{\theta}_{t-1}; x_i, y_i)\)

    3. Update: \(\boldsymbol{\theta}_t = \boldsymbol{\theta}_{t-1} - \eta_t \hat{g}_t\)

  3. Return \(\boldsymbol{\theta}_T\)

1.3.3 Lagrange Multipliers and KKT Conditions

Constrained optimization \(\min_\mathbf{x} f(\mathbf{x})\) s.t. \(g_i(\mathbf{x}) = 0\), \(h_j(\mathbf{x}) \leq 0\) is solved via the Lagrangian:

\[\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = f(\mathbf{x}) + \sum_i \lambda_i g_i(\mathbf{x}) + \sum_j \mu_j h_j(\mathbf{x})\]

At optimality, the KKT conditions hold:

\[\begin{align*} \nabla_\mathbf{x} \mathcal{L} &= 0 \quad \text{(stationarity)}\\ g_i(\mathbf{x}) &= 0 \quad \text{(primal feasibility)}\\ h_j(\mathbf{x}) &\leq 0 \quad \text{(primal feasibility)}\\ \mu_j &\geq 0 \quad \text{(dual feasibility)}\\ \mu_j h_j(\mathbf{x}) &= 0 \quad \text{(complementary slackness)} \end{align*}\]

KKT conditions appear directly in SVM training (see Chapter 4).

Solved Example 1.3

Problem: Minimize \(f(x,y) = x^2 + y^2\) subject to \(g(x,y) = x + 2y - 5 = 0\).

Solution: Lagrangian: \(\mathcal{L} = x^2 + y^2 + \lambda(x+2y-5)\). Setting \(\partial\mathcal{L}/\partial x = 2x + \lambda = 0 \Rightarrow x = -\lambda/2\). Setting \(\partial\mathcal{L}/\partial y = 2y + 2\lambda = 0 \Rightarrow y = -\lambda\). Substituting into constraint: \(-\lambda/2 + 2(-\lambda) = 5 \Rightarrow \lambda = -2\). Therefore \(x^* = 1\), \(y^* = 2\), \(f(x^*,y^*) = 5\).

1.4 Information Theory

1.4.1 Shannon Entropy

Definition: Shannon Entropy

For a discrete probability distribution \(P = \{p_1, …, p_n\}\):

\[H(P) = -\sum_{i=1}^n p_i \log_2 p_i \quad \text{[bits]}\tag{1.19}\]

(with \(0\log 0 := 0\) by continuity). \(H(P) \in [0, \log_2 n]\), with maximum at the uniform distribution.

Key properties:

  • \(H(P) = 0\) iff \(P\) is deterministic (\(p_i = 1\) for some \(i\))

  • \(H(X, Y) \leq H(X) + H(Y)\) with equality iff \(X, Y\) independent

  • Data processing inequality: \(H(f(X)) \leq H(X)\) for any \(f\)

1.4.2 KL Divergence and Cross-Entropy

\[D_{\text{KL}}(P \| Q) = \sum_i p_i \log \frac{p_i}{q_i} \geq 0\tag{1.20}\]

(Gibbs’ inequality: \(D_{\text{KL}} = 0\) iff \(P = Q\)). KL divergence is not symmetric: \(D_{\text{KL}}(P\|Q) \neq D_{\text{KL}}(Q\|P)\) in general.

Cross-entropy: \(H(P, Q) = -\sum_i p_i \log q_i = H(P) + D_{\text{KL}}(P\|Q)\). This is the standard classification loss when \(P\) is the true labels and \(Q\) is the model output.

Mutual Information:

\[I(X; Y) = H(X) + H(Y) - H(X,Y) = D_{\text{KL}}(P_{XY} \| P_X \otimes P_Y)\tag{1.21}\]

Solved Example 1.4

Problem: Compute \(D_{\text{KL}}(\mathcal{N}(\mu_1, \sigma_1^2) \| \mathcal{N}(\mu_2, \sigma_2^2))\).

Solution: For two Gaussians, the KL divergence has a closed form:

\[\begin{align*} D_{\text{KL}}\bigl(\mathcal{N}_1 \| \mathcal{N}_2\bigr) &= \log\frac{\sigma_2}{\sigma_1} + \frac{\sigma_1^2 + (\mu_1-\mu_2)^2}{2\sigma_2^2} - \frac{1}{2} \end{align*}\]

For \(\mu_1=0, \sigma_1=1, \mu_2=1, \sigma_2=2\): \(D_{\text{KL}} = \log 2 + \frac{1+1}{8} - \frac{1}{2} = 0.693 + 0.25 - 0.5 = 0.443\) bits.

import numpy as np
from scipy.stats import entropy

def shannon_entropy(probs):
    """Shannon entropy in bits."""
    probs = np.array(probs)
    probs = probs[probs > 0]  # remove zeros
    return -np.sum(probs * np.log2(probs))

def kl_divergence(p, q):
    """KL divergence D_KL(P || Q)."""
    p, q = np.array(p), np.array(q)
    mask = (p > 0) & (q > 0)
    return np.sum(p[mask] * np.log(p[mask] / q[mask]))

def mutual_information(joint_pxy):
    """Mutual information I(X;Y) from joint distribution."""
    px = joint_pxy.sum(axis=1)
    py = joint_pxy.sum(axis=0)
    return shannon_entropy(px) + shannon_entropy(py) - shannon_entropy(joint_pxy.flatten())

# Example
p = [0.5, 0.25, 0.25]
print(f"H(P) = {shannon_entropy(p):.4f} bits")  # 1.5 bits

q = [0.4, 0.3, 0.3]
print(f"KL(P||Q) = {kl_divergence(p, q):.4f}")

1.5 Fourier Analysis and Connections to QFT

1.5.1 Discrete Fourier Transform

The Discrete Fourier Transform of a vector \(\mathbf{x} \in \mathbb{C}^N\) is:

\[X_k = \sum_{j=0}^{N-1} x_j \omega^{jk}, \quad \omega = e^{-2\pi i/N}, \quad k=0,…,N-1\tag{1.23}\]

The DFT is a unitary linear map: \(\hat{\mathbf{X}} = F_N \mathbf{x}\) where \((F_N)_{kj} = \omega^{jk}/\sqrt{N}\) (normalized form).

The Quantum Fourier Transform (QFT) implements \(F_{2^n}\) as a quantum circuit on \(n\) qubits in \(O(n^2)\) gates (vs. classical FFT’s \(O(N\log N)\)):

\[\text{QFT}|j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk/N} |k\rangle\tag{1.24}\]

Tip

The QFT appears as a subroutine in Shor’s algorithm, Quantum Phase Estimation, and the Harrow-Hassidim-Lloyd (HHL) algorithm. Understanding the DFT deeply will pay dividends when studying these algorithms in Chapter 2.

1.5.2 Fourier Features for Kernel Methods

Bochner’s theorem states that a stationary kernel \(k(\mathbf{x}-\mathbf{y})\) is positive definite iff its Fourier transform \(p(\boldsymbol{\omega}) \geq 0\) everywhere:

\[k(\mathbf{x}-\mathbf{y}) = \int_{\mathbb{R}^d} p(\boldsymbol{\omega}) e^{i\boldsymbol{\omega}^\top(\mathbf{x}-\mathbf{y})} d\boldsymbol{\omega}\]

This motivates random Fourier features for approximating kernel SVMs: sample \(\boldsymbol{\omega}_j \sim p\), then \(\phi(\mathbf{x}) = \sqrt{2/D}[\cos(\boldsymbol{\omega}_1^\top\mathbf{x}+b_1), …]\). The quantum analogue is a quantum feature map \(U_\phi\) encoding \(\mathbf{x}\) into a quantum state — see Chapter 7.

1.6 Chapter Summary

Chapter Summary

  • Linear algebra: Complex inner product spaces and Hilbert spaces form the arena for quantum states. Key matrix classes: Hermitian (observables), unitary (gates), and positive semidefinite (density matrices).

  • Spectral decomposition: Every normal matrix diagonalizes unitarily; eigenvalues of Hermitian operators are real; unitary operators have unit-modulus eigenvalues.

  • Tensor products: Compose quantum systems via \(\otimes\). An \(n\)-qubit system lives in \(\mathbb{C}^{2^n}\).

  • SVD: Every matrix has a singular value decomposition; SVD underlies quantum PCA and data encoding.

  • Probability: Expectation values, Bayesian inference, and concentration inequalities (Hoeffding) govern statistical aspects of quantum measurements.

  • Optimization: Most quantum cost functions are non-convex. Gradient descent and SGD are the workhorses; KKT conditions appear in SVM duality.

  • Information theory: Shannon entropy, KL divergence, and mutual information have quantum analogues (von Neumann entropy, quantum relative entropy) covered in Chapter 3.

  • Fourier analysis: The DFT is the classical counterpart of the Quantum Fourier Transform, a key subroutine in exponential speedup algorithms.

Exercises

Exercises

Exercise . Show that the Pauli matrices \(\{X, Y, Z\}\) satisfy \(\{X, Y\} = XY + YX = 0\) (anti-commute) and \([X, Y] = XY - YX = 2iZ\) (commutation relation).

Exercise . Verify that the matrix \(U = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\) (Hadamard gate) is unitary. Find its eigenvalues and eigenvectors.

Exercise . Compute the tensor product \(H \otimes H\) where \(H\) is the \(2\times 2\) Hadamard matrix. This is the two-qubit Hadamard. Write the \(4\times 4\) matrix.

Exercise . Prove that for any unitary \(U\), the eigenvalues satisfy \(|\lambda_i| = 1\). Hint: Use \(UU^\dagger = I\) and \(Uu_i = \lambda_i u_i\).

Exercise . A qubit state \(|\psi\rangle = \alpha|0\rangle + \beta|1\rangle\) requires \(|\alpha|^2 + |\beta|^2 = 1\). Show this equals the inner product condition \(\langle\psi|\psi\rangle = 1\).

Exercise . Find the SVD of \(A = \begin{pmatrix}3&0\\4&0\end{pmatrix}\). Identify the singular values and verify \(A = U\Sigma V^\dagger\).

Exercise . Compute \(H(\text{Bernoulli}(p))\) and find the value of \(p\) that maximizes it.

Exercise . Show that \(D_{\text{KL}}(P\|Q) \geq 0\) for all distributions \(P\), \(Q\). (Use Jensen’s inequality: \(\mathbb{E}[\phi(X)] \geq \phi(\mathbb{E}[X])\) for convex \(\phi\).)

Exercise . Prove the chain rule for entropy: \(H(X,Y) = H(X) + H(Y|X)\) where \(H(Y|X) = -\sum_{x,y} P(x,y)\log P(y|x)\).

Exercise . For gradient descent on \(f(x) = \frac{1}{2}x^2\) (with \(\beta=1\), \(\eta=0.8\)), starting at \(x_0 = 10\), compute \(x_5\). Does it converge?

Exercise . Prove the Cauchy-Schwarz inequality: \(|\langle u|v\rangle|^2 \leq \langle u|u\rangle \cdot \langle v|v\rangle\). Hint: Consider \(\|u - \frac{\langle u|v\rangle}{\langle v|v\rangle}v\|^2 \geq 0\).

Exercise . Using NumPy, implement a function compute_svd(A) that returns \(U, \Sigma, V^\dagger\) and verify it on a random \(5\times 3\) complex matrix. Plot the singular values.

Exercise . Using Hoeffding’s inequality, how many quantum measurements \(N\) are needed to estimate \(\langle\hat{O}\rangle\) to precision \(\epsilon = 0.01\) with confidence \(1 - \delta = 0.99\)? (Each shot returns a value in \([-1, 1]\).)

Exercise . The spectral norm of \(A\) is \(\|A\|_2 = \sigma_{\max}(A)\). Show that for unitary \(U\), \(\|U\|_2 = 1\) and \(\|UA\|_2 = \|A\|_2\).

Exercise . Look up the concept of an \(\epsilon\)-net over the Hilbert space \(\mathbb{C}^{2^n}\). How does the size of this net relate to the sample complexity of learning a quantum classifier? (See Ref. (Bartlett 1998) for classical analogues.)

Further Reading

  • Linear Algebra: Horn & Johnson, Matrix Analysis (2013) — definitive reference for matrix theory

  • Optimization: Boyd & Vandenberghe, Convex Optimization (2004) — free online at stanford.edu/  boyd/cvxbook

  • Information Theory: Cover & Thomas, Elements of Information Theory (2006) — comprehensive classical reference

  • Probability: Wainwright, High-Dimensional Statistics (2019) — modern treatment of concentration inequalities

  • QML specific: Nielsen & Chuang, Quantum Computation and Quantum Information (2000) (Nielsen and Chuang 2000), Chapters 2–4

  • Interactive: Khan Academy Linear Algebra + 3Blue1Brown Essence of Linear Algebra (YouTube) for visual intuition