Sources and References

Primary textbook — John Watrous, The Theory of Quantum Information (Cambridge University Press, 2018). The Fall 2011 lecture notes (LN2011) that formed the basis of the textbook are cited throughout.

Supplementary texts — T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. (Wiley, 2006); Michael Nielsen and Isaac Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2000); John Preskill, Lecture Notes for Physics 219: Quantum Computation, Chapter 10 (2022).

Online resources — Debbie Leung, QIC 820 / CO 486 / CS 766 course page (UWaterloo, Fall 2023): https://www.math.uwaterloo.ca/~wcleung/qic820-f2023.html; Preskill Phys 219 lecture notes at theory.caltech.edu; arXiv references cited inline for research results.

Chapter 1: Mathematical Foundations

The theory of quantum information rests on a precise algebraic framework. This chapter develops the necessary mathematical infrastructure: complex Euclidean spaces as the arena for quantum states, linear operators as the language for transformations and measurements, the vec operator as a bridge between operators and vectors, and convexity as the geometry underlying optimisation.

1.1 Complex Euclidean Spaces

Classical information is stored in a finite set of symbols. Quantum information generalises this by allowing probability amplitudes — complex numbers — in place of probabilities. The natural home for these amplitudes is a complex Euclidean space indexed by the classical symbol set.

The inner product is linear in the second argument and conjugate-linear in the first — the physics convention, opposite to the mathematics convention. We use the Dirac bra-ket notation \(|u\rangle\) for \(u \in \mathcal{X}\) and \(\langle u|\) for its dual (conjugate transpose), so \(\langle u|v\rangle = \langle u,v\rangle\).

The norms satisfy the Cauchy-Schwarz inequality \(|\langle u,v\rangle| \leq \|u\|\|v\|\), with equality iff \(u\) and \(v\) are proportional. The Euclidean norm and the 2-norm coincide on vectors. The norms are related by \(\|u\|_\infty \leq \|u\|_2 \leq \|u\|_1 \leq \sqrt{|\Sigma|}\,\|u\|_2 \leq |\Sigma|\,\|u\|_\infty\).

1.2 Linear Operators and Operator Norms

The spectral theorem allows us to define operator functions: for \(f:\mathbb{R} \to \mathbb{R}\) and Hermitian \(A = \sum_i \lambda_i \Pi_i\), set \(f(A) = \sum_i f(\lambda_i)\Pi_i\). The most important cases are \(\sqrt{A}\) (for \(A \geq 0\)) and \(\log A\) (for \(A > 0\)).

Every operator also has a singular value decomposition, which is the analogue of the spectral theorem for non-square or non-normal operators.

These norms satisfy \(\|A\|_\infty \leq \|A\|_2 \leq \|A\|_1\) and the duality \(\|A\|_1 = \max\{\langle A, B\rangle : \|B\|_\infty \leq 1\}\). The trace norm is especially important because it governs distinguishability of quantum states.

The trace norm has a direct operational meaning: for two quantum states \(\rho,\sigma\), the probability of correctly identifying the state (given uniformly random prior) equals \(\tfrac{1}{2}+\tfrac{1}{4}\|\rho-\sigma\|_1\). This is the Holevo-Helstrom theorem (Theorem 2.1). The spectral norm (operator norm) \(\|A\|_\infty = \lambda_{\max}(A^*A)^{1/2}\) is the largest singular value; for Hermitian \(A\) it is \(\max(|\lambda_{\max}(A)|,|\lambda_{\min}(A)|)\). The Frobenius norm \(\|A\|_2 = \sqrt{\operatorname{Tr}(A^*A)}\) is the Hilbert-Schmidt norm and is induced by the inner product \(\langle A,B\rangle = \operatorname{Tr}(A^*B)\).

A key inequality connecting trace norm and fidelity: \(\|\rho-\sigma\|_1^2 \leq 4(1-F(\rho,\sigma)^2)\). This is useful for bounding distinguishability from fidelity. For pure states \(\rho = |\psi\rangle\langle\psi|\) and \(\sigma = |\phi\rangle\langle\phi|\): \(\|\rho-\sigma\|_1 = 2\sqrt{1-|\langle\psi|\phi\rangle|^2}\) (the “Bures distance”) and \(F = |\langle\psi|\phi\rangle|\), giving the tight Fuchs-van de Graaf bound as an equality.

The Schatten norms also satisfy Hölder’s inequality: \(|\langle A, B\rangle| \leq \|A\|_p \|B\|_q\) for \(1/p + 1/q = 1\). For \(p = q = 2\) this is the Cauchy-Schwarz inequality for the Hilbert-Schmidt inner product. The Frobenius norm is submultiplicative: \(\|AB\|_2 \leq \|A\|_2\|B\|_2\). The spectral norm is submultiplicative: \(\|AB\|_\infty \leq \|A\|_\infty\|B\|_\infty\). An important inequality connecting the three: \(\|ABC\|_1 \leq \|A\|_2\|B\|_1\|C\|_2\).

1.3 The Vec Operator and Tensor Identities

The vec operator provides a canonical identification between operators (matrices) and vectors (column vectors in a tensor product space). This identification is essential for purification theory, the Choi isomorphism, and many duality arguments.

Two important special cases: setting \(C = I\) gives \(\operatorname{vec}(A) = (A\otimes I)\operatorname{vec}(I) = (I\otimes A^T)\operatorname{vec}(I)\). Setting \(A = I\) gives \((I\otimes B)\operatorname{vec}(C) = \operatorname{vec}(CB^T)\).

The tensor identity has a key consequence for quantum channels. If \(\Phi(M) = \sum_k A_k M B_k^*\), then the natural representation satisfies \(K(\Phi)\operatorname{vec}(M) = \operatorname{vec}(\Phi(M))\), so \(K(\Phi) = \sum_k A_k \otimes \bar{B}_k\). The Choi matrix is \(J(\Phi) = (\Phi\otimes I)(\operatorname{vec}(I)\operatorname{vec}(I)^*)\), and the tensor identity gives the reconstruction formula \(\Phi(M) = \operatorname{Tr}_\mathcal{X}[(I\otimes M^T)J(\Phi)]\).

The vec identity also makes the Choi-Kraus correspondence transparent: \(J(\Phi) = \sum_k \operatorname{vec}(A_k)\operatorname{vec}(A_k)^*\) for Kraus operators \(\{A_k\}\). This is the Gram matrix of the vectors \(\{\operatorname{vec}(A_k)\}\), and its PSD property gives the CP condition.

1.4 Matrix Inequalities and Operator Monotone Functions

Operator functions inherit an ordering structure from the Löwner order on \(\operatorname{Herm}(\mathcal{X})\), but this ordering interacts with matrix operations in subtle ways.

Key operator monotone functions: \(f(t) = t^\alpha\) for \(\alpha \in (0,1]\) is operator monotone; \(f(t) = \log t\) is operator monotone; \(f(t) = t^2\) is operator convex but not operator monotone. Crucially, \(A \geq B \geq 0\) does not imply \(A^2 \geq B^2\) in general (the square function is not operator monotone).

The Golden-Thompson inequality is used in the proof of the data processing inequality for quantum relative entropy via the Peierls-Bogoliubov inequality.

Lieb’s concavity theorem (1973) is one of the deepest results in matrix analysis. Its many corollaries include the joint convexity of quantum relative entropy (Theorem 5.8) and the strong subadditivity of von Neumann entropy (Theorem 5.10). The original proof used complex interpolation methods; Carlen-Lieb (2012) later gave a simpler proof using the operator geometric mean.

1.5 Convexity

Quantum information theory is pervaded by convexity arguments — density operators form a convex set, separable states form a convex set, and the feasible regions of SDPs are convex. We collect the key results here.

Convexity theorems are applied throughout: Carathéodory bounds the decomposition length of separable states; Krein-Milman identifies pure states as extreme points and underpins channel representations; the separating hyperplane theorem gives entanglement witnesses; Sion’s theorem underlies strong duality for SDPs.

Chapter 2: Quantum States and Channels

Quantum mechanics is a probabilistic theory, but the probabilities arise from a more fundamental description in terms of amplitudes. A quantum state is not simply a probability distribution over classical configurations — it is a positive semidefinite operator that encodes both the classical uncertainty and the quantum coherence of a system.

2.1 Registers and Density Operators

The set \(D(\mathcal{X})\) is a compact convex set. Its extreme points are precisely the pure states \(\{|u\rangle\langle u| : \|u\| = 1\}\). By Krein-Milman, every \(\rho \in D(\mathcal{X})\) is a convex combination of pure states (this is just the spectral decomposition: \(\rho = \sum_x p(x)|e_x\rangle\langle e_x|\)). The maximally mixed state \(\frac{I}{d}\) (with \(d = \dim\mathcal{X}\)) is the centroid of \(D(\mathcal{X})\).

The non-uniqueness of the pure-state decomposition is fundamental. While the spectral decomposition \(\rho = \sum_x p(x)|e_x\rangle\langle e_x|\) uses eigenstates, the same density matrix can be written as a mixture over any ensemble of pure states consistent with the eigenvalues (via the Schrödinger mixture theorem). This non-uniqueness has a crucial physical consequence: no measurement of \(\rho\) alone can determine which pure-state ensemble was prepared. The state \(\rho\) encapsulates all operationally distinguishable information about the preparation.

2.2 Measurements and POVMs

The most general quantum measurement on register \(X\) is described by a positive operator-valued measure.

A projective measurement \(\{P_a\}\) on a pure state \(|\psi\rangle\) yields outcome \(a\) with probability \(\|P_a|\psi\rangle\|^2 = \langle\psi|P_a|\psi\rangle\). After the measurement the state collapses to \(P_a|\psi\rangle/\|P_a|\psi\rangle\|\). For mixed states, the post-measurement state is \(P_a\rho P_a / \operatorname{Tr}(P_a\rho)\).

The key operational difference between a POVM and a projective measurement: a POVM can have more outcomes than the dimension of \(\mathcal{X}\), at the cost of not necessarily being a projection. Neumark’s (Naimark’s) dilation theorem states that any POVM on \(\mathcal{X}\) can be implemented as a projective measurement on a larger system \(\mathcal{X}\otimes\mathcal{Y}\): there exist projectors \(\{Q_a\}\) on \(\mathcal{X}\otimes\mathcal{Y}\) and a fixed state \(|0\rangle \in \mathcal{Y}\) such that \(\operatorname{Tr}(M(a)\rho) = \operatorname{Tr}(Q_a(\rho\otimes|0\rangle\langle 0|))\) for all \(\rho\).

2.3 Binary State Discrimination and the Holevo-Helstrom Theorem

A fundamental task is: given a register holding either state \(\rho_0\) (with prior \(p_0\)) or \(\rho_1\) (with prior \(p_1 = 1-p_0\)), find the measurement maximising the probability of correctly identifying the state. This is the quantum analogue of the classical hypothesis testing problem.

The key insight is that the optimal measurement projects onto the eigenspaces of the operator difference \(p_0\rho_0 - p_1\rho_1\). This is the quantum version of the Neyman-Pearson lemma: in classical hypothesis testing, the optimal test is the likelihood ratio test. Quantum mechanically, the eigenvectors of \(p_0\rho_0-p_1\rho_1\) play the role of the likelihood ratio threshold. States in the positive eigenspace are more likely to have come from \(\rho_0\); states in the negative eigenspace from \(\rho_1\).

The SDP formulation is illuminating. The discrimination probability is

The last equality is the Holevo-Helstrom theorem. Its dual SDP is \(\beta = \inf\operatorname{Tr}(Y)\) s.t. \(Y \geq p_0\rho_0\) and \(Y \geq p_1\rho_1\), and strong duality \(d=\beta\) follows since both are strictly feasible.

With equal priors \(p_0 = p_1 = 1/2\), the maximum success probability is \(\tfrac{1}{2}(1 + \tfrac{1}{2}\|\rho_0 - \rho_1\|_1)\), so the trace distance \(\tfrac{1}{2}\|\rho_0-\rho_1\|_1\) is the bias above guessing. This gives the SDP formulation of trace distance.

2.4 Multi-State Discrimination

The binary discrimination problem extends naturally to \(n\) states. With states \(\{\rho_k\}_{k=1}^n\) prepared with priors \(\{p_k\}\), the optimal POVM satisfies the following.

Pretty-good measurement (PGM): For an ensemble \(\{p_k,|\psi_k\rangle\}\), the pretty-good measurement is \(M_k = p_k\rho^{-1/2}|\psi_k\rangle\langle\psi_k|\rho^{-1/2}\) where \(\rho = \sum_k p_k|\psi_k\rangle\langle\psi_k|\). It is not optimal in general but achieves within a constant factor of the optimal discrimination probability and is often optimal for symmetric ensembles.

2.5 Quantum Channels

The distinction between positive and CP is important. The transpose map \(T(A) = A^T\) is positive (it maps PSD operators to PSD operators) but not CP: \((T \otimes I)(|\beta\rangle\langle\beta|)\) is not PSD for the Bell state \(|\beta\rangle\). This is why complete positivity — not just positivity — is the physically meaningful condition: any quantum channel must remain valid when applied to part of a larger system.

2.5 Representations of Channels and CP/TP Characterisations

Every quantum channel has four equivalent representations, each illuminating a different physical aspect.

The adjoint \(\Phi^*: L(\mathcal{Y}) \to L(\mathcal{X})\) is defined by \(\langle B, \Phi(A)\rangle = \langle \Phi^*(B), A\rangle\). For a Kraus map \(\Phi(M) = \sum_a A_a M A_a^*\), the adjoint is \(\Phi^*(B) = \sum_a A_a^* B A_a\). The TP condition \(\sum_a A_a^*A_a = I\) is equivalent to \(\Phi^*(I) = I\) (unital adjoint, the Heisenberg picture unitality).

The adjoint has the following physical interpretation. In the Schrödinger picture, \(\Phi\) evolves states: \(\rho \mapsto \Phi(\rho)\). In the Heisenberg picture, \(\Phi^*\) evolves observables: an observable \(B\) on \(\mathcal{Y}\) is “pulled back” to \(\Phi^*(B)\) on \(\mathcal{X}\), so that the expected value is \(\operatorname{Tr}(B\Phi(\rho)) = \operatorname{Tr}(\Phi^*(B)\rho)\). The TP condition ensures that the constant observable \(I_\mathcal{Y}\) (which always has expectation 1) is preserved: \(\Phi^*(I_\mathcal{Y}) = I_\mathcal{X}\). More generally, for a measurement POVM \(\{M(a)\}_a\) on the output space, the pullback \(\{\Phi^*(M(a))\}_a\) is the effective POVM on the input space.

The four representations of a channel form a cycle: Stinespring \(\to\) Kraus (group rows of the isometry), Kraus \(\to\) Choi (apply formula), Choi \(\to\) Kraus (spectral decompose), Kraus \(\to\) natural representation (vectorise). Each representation is uniquely useful: Kraus for computation, Choi for characterising CP, Stinespring for purification arguments.

The complementary channel captures exactly the information that “leaks” to the environment during the evolution. If \(\Phi\) is a noisy communication channel, \(\hat\Phi\) models the eavesdropper’s channel. The symmetry between \(\Phi\) and \(\hat\Phi\) is not complete: while \(\hat{(\hat\Phi)}\) is isometrically equivalent to \(\Phi\) (by the fact that the Stinespring dilation is pure on \(\mathcal{Y}\otimes\mathcal{Z}\)), the dimensions of \(\mathcal{Y}\) and \(\mathcal{Z}\) can differ.

2.5b Quantum Instruments and Post-Measurement States

The Kraus representation captures the marginal statistics of a measurement but not the post-measurement states. The more complete framework is the quantum instrument.

The key relationship: every POVM \(\{M(a)\}\) arises as the marginal of a quantum instrument. Specifically, \(M(a) = (\Phi_a)^*(I_\mathcal{Y})\) where \((\Phi_a)^*\) is the adjoint of \(\Phi_a\). The simplest instrument associated with POVM element \(M(a) = K_a^*K_a\) is the Lüders instrument \(\Phi_a(\rho) = K_a\rho K_a^*\). The corresponding post-measurement state is \(K_a\rho K_a^*/\operatorname{Tr}(K_a^*K_a\rho)\).

2.5c Random Unitary Channels and Pauli Channels

A practically important class of quantum channels are the random unitary channels (also called unital channels of Pauli type), which model incoherent noise processes.

For a qubit, the most important random unitary channels are the Pauli channels:

parameterised by error probabilities \(p_x, p_y, p_z \geq 0\) with \(p_x+p_y+p_z \leq 1\). Special cases: the depolarising channel has \(p_x = p_y = p_z = p/3\); the dephasing channel has \(p_x=p_y=0\), \(p_z=p\); the bit-flip channel has \(p_x=p\), \(p_y=p_z=0\).

The Pauli channel has a particularly clean Choi matrix: since \(\{I,X,Y,Z\}/\sqrt{2}\) is an orthonormal basis for \(L(\mathbb{C}^2)\), the Choi matrix decomposes as \(J(\Phi) = \sum_P\hat\Phi_P\, P\otimes P^T\), where \(\hat\Phi_P\) are the eigenvalues of \(\Phi\) in the Pauli basis. The CP condition on \(J(\Phi)\geq 0\) gives constraints on the probabilities \((p_x,p_y,p_z)\).

2.6 Discrete Weyl Operators and Quantum Teleportation

The generalised Pauli operators form an orthonormal basis for \(L(\mathcal{X})\) and underlie the quantum one-time pad and teleportation.

Chapter 3: Purifications and Fidelity

Purification is the idea that any mixed state of a system can be regarded as part of a pure state on a larger system. This perspective converts questions about mixed states into questions about pure states, often dramatically simplifying proofs. The fidelity function, which quantifies how close two quantum states are, has its deepest characterisation through purifications via Uhlmann’s theorem.

3.1 Purifications

The connection to the vec operator is fundamental: \(|u\rangle\) purifies \(P\) iff \(|u\rangle = \operatorname{vec}(A)\) for some \(A \in L(\mathcal{Y},\mathcal{X})\) with \(AA^* = P\). This uses the identity \(\operatorname{Tr}_\mathcal{Y}(\operatorname{vec}(A)\operatorname{vec}(A)^*) = AA^*\).

The unitary equivalence theorem (Theorem 3.2) is the quantum analogue of the fact that all probability distributions with the same marginal can be related by a coupling. Operationally: if you have access to only the \(\mathcal{X}\) part of a purification, the choice of purifying system \(\mathcal{Y}\) is irrelevant — all purifications of \(\rho\) look the same to Alice. Bob can rotate between them without affecting Alice.

The purification of a bipartite state plays a crucial role in proofs about conditional entropy, quantum channel capacity, and Uhlmann’s theorem. A key identity: for any pure tripartite state \(|\psi\rangle^{ABR}\), \(S(\rho^A) = S(\rho^{BR})\) and \(S(\rho^{AB}) = S(\rho^R)\). These follow from the Schmidt decomposition across each bipartition and the purity of the global state.

3.2 The Fidelity Function

3.3 Uhlmann’s Theorem

Uhlmann’s theorem gives the most elegant characterisation of fidelity: it is the maximal overlap between purifications. The theorem can be understood intuitively as follows: the fidelity \(F(\rho,\sigma)\) measures how “close” the two states are in terms of how much their purifications can be aligned. Since all purifications of \(\rho\) in a fixed system \(\mathcal{X}\otimes\mathcal{Y}\) are related by unitaries on \(\mathcal{Y}\), the question of maximising \(|\langle u|v\rangle|\) over purifications \(|v\rangle\) of \(\sigma\) reduces to the variational problem \(\max_V |\operatorname{Tr}(A^*BV^T)|\), which by the trace-norm variational formula equals \(\|A^*B\|_1\).

The proof of Uhlmann’s theorem via SDPs proceeds differently and more directly shows the connection between fidelity and the primal optimisation. Following Watrous (Lecture 6, LN2011) and the in-course SDP notes from Debbie Leung, the key steps are:

Uhlmann’s theorem can also be derived from the SDP formulation of fidelity. The primal SDP for \(F(P,Q)\) is

The dual is \(\beta = \inf\;\tfrac{1}{2}\langle P,Y\rangle+\tfrac{1}{2}\langle Q,Z\rangle\) s.t. \(\begin{bmatrix}Y & I \\ I & Z\end{bmatrix}\geq 0\). Strong duality (\(d=\beta\), attained) is verified using Slater’s condition. The dual with the substitution \(Z = Y^{-1}\) (optimal when \(P,Q>0\)) becomes Alberti’s theorem. The primal with the Schur complement gives \(\|V\|_\infty\leq 1\) which connects to the variational formula \(F(P,Q) = \sup_{\|V\|_\infty\leq 1}\operatorname{Re}\operatorname{Tr}(V^*\sqrt{P}\sqrt{Q}) = \|\sqrt{P}\sqrt{Q}\|_1\). This is exactly the statement of Uhlmann’s theorem with \(V = U\) a unitary (the variational formula is maximised by a unitary).

3.3b Process Fidelity and the Entanglement Fidelity

Beyond the state fidelity \(F(\rho,\sigma)\), there is a natural fidelity measure for quantum channels that compares the “distance” between two quantum processes.

The entanglement fidelity has the following key properties. First, it is independent of the choice of purification \(|u\rangle\) (by the unitary equivalence of purifications and linearity). Second, for the identity channel \(\Phi = \operatorname{id}\), \(F_e(\rho,\operatorname{id}) = 1\) for any \(\rho\). Third, the average fidelity over all pure states is related to \(F_e\) by \(\bar F(\Phi) = \int F(\Phi(|\psi\rangle\langle\psi|),|\psi\rangle\langle\psi|)d|\psi\rangle = \frac{dF_e(\rho_{\text{mm}},\Phi)+1}{d+1}\) where \(\rho_{\text{mm}} = I/d\) (Horodecki-Horodecki-Horodecki 1999).

3.4 Alberti’s Theorem

While Uhlmann characterises fidelity through purifications, Alberti’s theorem gives a variational characterisation through an optimisation over positive definite operators — the form that naturally arises as the dual of the fidelity SDP.

3.5 Fuchs-van de Graaf Inequalities

The fidelity and trace distance are the two primary distance measures for quantum states. They are related by tight inequalities.

3.6 Data Processing and Joint Concavity

Chapter 4: Semidefinite Programming

Semidefinite programming (SDP) is to quantum information what linear programming is to classical combinatorial optimisation. Many fundamental quantities — trace distance, fidelity, diamond norm, optimal state discrimination — are exactly expressible as SDPs, enabling both computation and duality-based proofs.

In quantum information, SDPs appear in two distinct roles. First, as computational tools: given the numerical data (Kraus operators, state descriptions, Hamiltonian parameters), SDPs compute exact optimal values efficiently using interior-point methods (e.g., SeDuMi, CVXPY, MOSEK in \(O(n^{3.5})\) time for an \(n\)-dimensional variable). Second, as proof techniques: the primal-dual structure gives certificates of optimality and allows compact proofs of quantum information theorems by finding explicit dual witnesses. The Holevo-Helstrom theorem, Uhlmann’s theorem, and the quantum capacity hierarchy all admit SDP-based proofs that are often more transparent than direct analytical arguments.

A key principle is that most quantum information quantities arising from optimisation over POVMs, channels, or states are SDPs because the feasible region (density matrices, POVMs, channels) is a spectrahedron — a convex set defined by linear matrix inequalities. The Choi isomorphism maps the CP condition to a PSD constraint, converting channel optimisation into standard SDP form.

The duality structure of SDPs has a direct physical interpretation in quantum information. The primal optimises over physical objects (states, measurements, channels). The dual provides witnesses: the dual feasible point certifies that the primal objective cannot exceed a certain value, and the dual optimal witnesses (entanglement witnesses, measurement witnesses) identify the physical constraints. This is why SDP duality is so powerful in quantum information: optimal protocols and impossibility proofs are two sides of the same SDP.

4.1 The Primal and Dual SDP

The dual is derived via Lagrange multipliers. Associate dual variable \(Y \in \operatorname{Herm}(\mathcal{Y})\) to the equality constraint \(\Phi(X)=B\) and \(S \in \operatorname{Pos}(\mathcal{X})\) to the inequality \(X \geq 0\). The Lagrangian is \(\langle A,X\rangle + \langle B-\Phi(X),Y\rangle + \langle X,S\rangle = \langle B,Y\rangle + \langle X, A - \Phi^*(Y) + S\rangle\). For this to be bounded as \(X\) varies over \(\operatorname{Pos}(\mathcal{X})\), we need \(A - \Phi^*(Y) + S = 0\), giving the dual constraint.

The sign convention: the dual variable \(Y\) for the equality constraint is free (unconstrained as a Hermitian matrix, since the constraint is an equality). The dual variable \(S\) for the inequality \(X \geq 0\) is positive semidefinite (since \(-S\) is the Lagrange multiplier for \(X \geq 0\), and positivity of \(-S\) would mean \(S \leq 0\), but we choose the sign so that \(S \geq 0\) pairs with \(\langle X,S\rangle \geq 0\)).

The notation \(\Phi^*\) for the adjoint of the constraint map should not be confused with the adjoint (Heisenberg-picture) channel. In the SDP context, \(\Phi: L(\mathcal{X})\to L(\mathcal{Y})\) is any Hermiticity-preserving linear map, and its adjoint \(\Phi^*: L(\mathcal{Y})\to L(\mathcal{X})\) satisfies \(\langle Y, \Phi(X)\rangle = \langle\Phi^*(Y), X\rangle\). When \(\Phi = \Phi_{\text{ch}}\) is a quantum channel, the adjoint of the constraint map and the adjoint of the channel coincide, but for general SDP constraint maps they differ.

4.2 Weak and Strong Duality

The duality gap \(\beta - d\) can be strictly positive. Closing the gap requires a regularity condition. Example 4.1 shows a gap exists between attainment (not between the values \(d=\beta=0\)), but Example 4.4 below shows what happens when Slater’s condition fails: the primal optimal is approached but not attained. This is analogous to the LP degeneracy situation, but for matrix variables.

A useful test: if the SDP arises from a quantum information problem with a natural “maximally noisy” or “identity” solution, strict feasibility usually holds for both primal and dual — precisely the regime of most quantum information SDPs.

4.3 Complementary Slackness

Complementary slackness provides necessary and sufficient conditions for optimality when strong duality holds — it is the quantum analogue of complementary slackness in LP.

The complementary slackness conditions can be interpreted geometrically: \(XS = 0\) means the support of \(X\) is orthogonal to the support of \(S\). Since \(S = \Phi^*(Y) - A\), this says “the primal optimal \(X\) is supported only on the subspace where the dual inequality \(\Phi^*(Y) \geq A\) is tight (equality holds).” This is exactly analogous to the classical LP condition that a basic feasible solution has nonzero variables only where the corresponding dual constraints are active.

4.4 Computing Adjoint Maps

To use any specific SDP, one must compute the adjoint \(\Phi^*\) of the constraint map \(\Phi\). Two methods are available.

4.4b Application: Quantum State Tomography as Semidefinite Program

Quantum state tomography (QST) is the process of estimating a quantum state \(\rho\) from the outcomes of multiple measurements. The key computational step — fitting the experimental frequencies to a valid density matrix — is naturally an SDP.

The regularised QST problem can also be formulated as a semidefinite program: \(\min_\rho \lambda\operatorname{Tr}(\rho^2) - \sum_k f_k\log\operatorname{Tr}(M_k\rho)\) s.t. \(\rho\geq 0\), \(\operatorname{Tr}(\rho)=1\). The Tikhonov regularisation term \(\lambda\operatorname{Tr}(\rho^2) = \lambda\|\rho\|_2^2\) penalises pure states and encourages mixed solutions, acting as a prior for the maximum entropy principle. The resulting SDP has unique solution when the measurement is informationally complete (i.e., the POVM spans \(\operatorname{Herm}(\mathcal{X})\)).

4.5 Application: Optimal State Discrimination

4.6 Application: Fidelity as an SDP

4.7 The Diamond Norm

When two channels \(\Phi_0,\Phi_1\) are given uniformly at random, the optimal probability of correctly identifying which was applied equals \(\tfrac{1}{2} + \tfrac{1}{4}\|\Phi_0-\Phi_1\|_\diamond\). The auxiliary system \(\mathcal{Z}\) is essential: without it (using only \(\|\cdot\|_1\)), the discrimination probability may be strictly lower.

4.8 Application: Quantum Channel Simulation and the Reverse Shannon Theorem

A natural question arising from the diamond norm is: when can one channel \(\Phi\) simulate another channel \(\Psi\) using shared entanglement and classical communication? The reverse Shannon theorem answers this question and provides a unified framework connecting channel simulation, classical capacity, and entanglement consumption.

The reverse Shannon theorem gives a duality between the forward problem (maximise communication rate given a channel) and the reverse problem (minimise the resources needed to simulate a channel). Together with the HSW theorem, it implies that the classical capacity equals the channel simulation cost in the entanglement-assisted regime.

Chapter 5: Quantum Entropy and Information

Shannon’s information theory and quantum mechanics meet in the study of entropy. The classical Shannon entropy governs the compression of classical data; its quantum generalisation, the von Neumann entropy, governs quantum data compression and lies at the heart of every capacity theorem for quantum channels.

5.1 Shannon Entropy and the Asymptotic Equipartition Property

The AEP is the rigorous form of the intuitive statement that “most sequences from a source look the same.” More precisely: the typical sequences each have probability roughly \(2^{-nH}\), and there are roughly \(2^{nH}\) of them. The remaining \(|\Omega|^n - 2^{nH}\) atypical sequences collectively have negligible probability.

The AEP is the foundational tool in both classical and quantum Shannon theory. Conceptually, it says that a source with entropy \(H\) behaves, asymptotically, like a uniform distribution over a set of size \(2^{nH}\). All compression, channel coding, and capacity theorems follow from this: the source can be compressed to \(nH\) bits with negligible error (Shannon’s source coding theorem), and a channel with capacity \(C\) can transmit at rate \(R < C\) by identifying the \(2^{nR}\) messages with codewords in the typical set of the output (Shannon’s noisy channel theorem).

5.2 Shannon’s Noiseless Coding Theorem

5.3 Von Neumann Entropy

The von Neumann entropy has a maximum entropy interpretation: among all states \(\rho\) satisfying linear constraints \(\operatorname{Tr}(O_k\rho) = c_k\), the one maximising \(S(\rho)\) is the thermal (Gibbs) state \(\rho = Z^{-1}e^{-\sum_k\beta_k O_k}\), where \(Z = \operatorname{Tr}(e^{-\sum_k\beta_k O_k})\) and \(\{\beta_k\}\) are Lagrange multipliers. For a single energy constraint \(\operatorname{Tr}(H\rho) = E\): the maximum entropy state is the Boltzmann-Gibbs state \(\rho_\beta = e^{-\beta H}/\operatorname{Tr}(e^{-\beta H})\) with temperature \(T = 1/(k_B\beta)\). This is the quantum statistical mechanics principle of maximum entropy (Jaynes 1957).

The Araki-Lieb inequality shows that quantum conditional entropy \(S(A|B) = S(AB)-S(B)\) satisfies \(S(A|B) \geq -S(A)\). This is remarkable: while classically \(H(A|B) \geq 0\) always, quantum conditional entropy can be as negative as \(-S(A)\), achieved when \(\rho^{AB}\) is pure (so \(S(AB)=0\) and \(S(A|B) = -S(A)\)).

5.3b Concavity of Entropy and the Subadditivity Chain

The concavity of von Neumann entropy \(S(\sum_k p_k\rho_k) \geq \sum_k p_k S(\rho_k)\) has a clean proof via quantum relative entropy: \(S(\bar\rho\|\bar\rho) - \sum_k p_k S(\rho_k\|\bar\rho) = S(\bar\rho)\cdot\sum_k p_k - \sum_k p_k S(\rho_k) = -\sum_k p_k[S(\rho_k)-S(\bar\rho)+D(\rho_k\|\bar\rho)]\). Since \(D\geq 0\) and \(S(\bar\rho) = S(\sum_kp_k\rho_k)\), this gives concavity.

More precisely, the concavity identity is:

The right side is the Holevo information \(\chi\) of the ensemble \(\{(p_k,\rho_k)\}\) with average state \(\bar\rho = \sum_k p_k\rho_k\). This connects the concavity of entropy directly to the Holevo bound on accessible information (Theorem 5.11): the information gap between “knowing which \(\rho_k\)” and “having \(\bar\rho\)” exactly equals the Holevo information, which upper-bounds how much Alice can communicate to Bob through the ensemble.

5.4 Quantum Data Compression

The proof uses the typical subspace: the eigenspace of \(\rho^{\otimes n}\) spanned by eigenvectors with eigenvalue close to \(2^{-nS(\rho)}\). Projecting onto this subspace and transmitting the projection succeeds with high fidelity by the quantum AEP, using only \(n(S(\rho)+\delta)\) qubits. The converse uses Fannes’ inequality and Winter’s argument.

To make this precise: let \(\rho = \sum_x p(x)|e_x\rangle\langle e_x|\) be the spectral decomposition. The eigenvectors of \(\rho^{\otimes n}\) are \(|e_{x_1}\rangle\otimes\cdots\otimes|e_{x_n}\rangle\) with eigenvalue \(\prod_i p(x_i) = p(x^n)\). The \(\delta\)-typical subspace is

and the typical projector \(\Pi_{n,\delta}\) projects onto \(\mathcal{S}_{n,\delta}\).

The TTS (typical subspace transmission) protocol uses an isometry \(V: \mathcal{S}_{n,\delta}\to\mathbb{C}^{\lceil 2^{n(S+\delta)}\rceil}\) to compress into \(n(S+\delta)\) qubits. The decoder applies \(V^\dagger\) followed by replacement of the discarded part with a fixed state \(|0\rangle\). The fidelity with the input (referenced against a purification) is shown to be \(\geq 1-O(\varepsilon)\) by the quantum AEP.

5.5 Entanglement Concentration and Dilution

For bipartite pure state \(|\psi\rangle_{AB} = \sum_v\sqrt{p(v)}|v\rangle_A|v\rangle_B\) in Schmidt form, define the entropy of entanglement \(E(|\psi\rangle) = S(\operatorname{Tr}_B|\psi\rangle\langle\psi|) = H(p)\).

The equality of concentration and dilution rates means the entropy of entanglement is the unique entanglement measure for bipartite pure states under asymptotic LOCC. If classical communication is charged, dilution costs only \(O(\sqrt{n})\) extra cbits — savings quantified by the entanglement spread \(\Delta(|\psi\rangle) = \log\operatorname{rank}(\rho_A) - \log(1/\|\rho_A\|_\infty)\).

5.6 Quantum Relative Entropy

An immediate application: \(S(\rho\|I/d) = \log d - S(\rho) \geq 0\), giving the upper bound \(S(\rho) \leq \log d\).

The quantum relative entropy also satisfies the data processing inequality: for any channel \(\Phi\), \(S(\Phi(\rho)\|\Phi(\sigma))\leq S(\rho\|\sigma)\). This is one of the most fundamental results in quantum information — it says that processing quantum information cannot increase the distinguishability of two states. The classical analogue is the data processing inequality for classical divergences.

A natural question is: when does equality hold? The answer is given by the Petz recovery map, which provides a universal sufficient condition for equality and connects data processing to approximate quantum error correction.

This characterisation has deep implications for approximate quantum error correction. If a channel \(\Phi\) only slightly decreases \(S(\rho\|\sigma)\), then there exists a near-perfect recovery map — and quantitatively, the Fawzi-Renner theorem (2015) shows that \(S(\rho\|\sigma) - S(\Phi(\rho)\|\Phi(\sigma)) \geq -2\log F(\rho, \mathcal{P}_{\sigma,\Phi}\circ\Phi(\rho))\), giving a recovery fidelity bound purely from the relative entropy decrease.

5.6b Quantum Hypothesis Testing and Stein’s Lemma

A fundamental task in statistics is hypothesis testing: given many copies of an unknown state, decide whether it is \(\rho\) (null hypothesis) or \(\sigma\) (alternative). The quantum relative entropy governs the optimal error exponents.

The quantum Stein’s lemma establishes the quantum relative entropy as the fundamental distinguishability measure in the asymptotic hypothesis testing regime. Its classical analogue (Stein’s lemma for classical distributions) uses the KL divergence. The proof of the quantum version is substantially harder and uses the operator inequality techniques developed for quantum entropy — specifically, Lemma 3.17 of Hiai-Petz which is equivalent to the data processing inequality.

5.7 Strong Subadditivity

5.8 Holevo’s Theorem

Fano’s inequality lower-bounds the error rate in any decoding scheme. Combined with Holevo’s theorem, it implies the quantum Holevo bound: transmitting \(n\) classical bits reliably requires at least \(n\) qubits in the channel, even with optimal encoding and measurement.

The HSW (Holevo-Schumacher-Westmoreland) theorem (1997) establishes that the classical capacity of a quantum channel \(\Phi: L(\mathcal{X})\to L(\mathcal{Y})\) is

where the max is over all ensembles on \(\mathcal{X}^{\otimes n}\). The regularisation over \(n\) is generally necessary (Hastings 2008 showed strict superadditivity of \(\chi\) for some channels), making the classical capacity uncomputable in general.

Chapter 6: Separability and Entanglement Theory

Entanglement is the defining resource of quantum information. This chapter develops the mathematical theory of entanglement: how to characterise it, how to detect it, and how it behaves under local operations and classical communication.

The distinction between separable and entangled states is not merely a mathematical curiosity — it has profound operational consequences. Entangled states violate Bell inequalities, which are constraints that any classically correlated (separable) state must satisfy. Detecting this violation operationally certifies entanglement without any characterisation of the measurement devices (device-independent certification).

The mathematical theory of entanglement is rich and still not fully understood. The separability problem is NP-hard; the connection between PPT and separability breaks down above \(2\times 3\) dimensions; the quantum capacities remain uncomputable in general; and the relationship between entanglement measures is complex. The framework of SDP relaxations (§6.3b) and convex optimisation over quantum states (§6.7, §6.8) provides the best current tools for these problems, and many of the key results in this chapter are proved using the SDP duality machinery of Chapter 4.

6.1 Separable Operators

6.2 The Horodecki Criterion and Entanglement Witnesses

Before developing the algebraic theory of separability, it is worth understanding the operational test that motivated the field: the CHSH inequality.

Deciding separability is NP-hard in general (Gurvits 2003). However, necessary conditions give powerful tests that suffice to detect most entangled states in practice.

The separating hyperplane theorem applied to the convex set \(\operatorname{Sep}\) gives the abstract existence of a witness for every entangled state. The constructive challenge is to find explicit witnesses that are practically measurable in the lab. An entanglement witness \(H\) must be measurable (i.e., expressible as a sum of local observables \(H = \sum_i a_i\otimes b_i\)) and satisfy \(\langle H,P\otimes Q\rangle \geq 0\) for all products \(P,Q\geq 0\).

A common construction: given a linear map \(\Lambda\) that is positive but not CP, define \(H = (I\otimes\Lambda^*)(\Pi^+)\) where \(\Pi^+ = |\beta\rangle\langle\beta|\) is the maximally entangled projector. Then \(\langle H,\rho\rangle = \langle\Pi^+,(I\otimes\Lambda)\rho\rangle = F(\Lambda(\rho)) \geq 0\) for separable \(\rho\) (since \(\Lambda\) is positive and \(\rho^A\geq 0\) for product states), but \(\langle H,|\beta\rangle\langle\beta|\rangle = \operatorname{Tr}(\Pi^+ (I\otimes\Lambda)(|\beta\rangle\langle\beta|)) < 0\) when \(\Lambda\) is not CP.

6.3 The Ball of Separable States

Theorem 6.3 says there is a Frobenius-norm ball of radius 1 around the identity operator \(I\) that lies entirely within \(\operatorname{Sep}\), after normalisation. This gives a concrete sufficient condition for separability and is used in the theory of quantum error correction (highly mixed states near the maximally mixed state are separable).

6.3b SDP Relaxations of Separability

Since exact separability testing is NP-hard, one uses SDP-based relaxations. The basic relaxation is the PPT test (Def. 6.3), which is an SDP feasibility check. More powerful is the DPS (Doherty-Parrilo-Spedalieri) hierarchy of SDP relaxations.

The DPS hierarchy satisfies \(\operatorname{Sep} \subset \cdots \subset \operatorname{Sep}^{(k+1)} \subset \operatorname{Sep}^{(k)} \subset \cdots \subset \operatorname{Sep}^{(1)} = \operatorname{PPT}\). The remarkable result (Brandão-Harrow 2013) is that for any \(\varepsilon > 0\), there exists \(k = O(\log(d)/\varepsilon^2)\) such that \(\operatorname{Sep}^{(k)} \subseteq \{\rho : \min_{\sigma\in\operatorname{Sep}}\tfrac{1}{2}\|\rho-\sigma\|_1 \leq \varepsilon\}\). This gives an efficient algorithm for approximating separability to within trace-norm precision, establishing that the separability problem has a quasipolynomial-time algorithm in fixed precision.

6.4 Separable Maps and Schmidt Rank

6.5 LOCC

The chain of inclusions is: \(\text{LO} \subset \text{LOCC}_1 \subset \text{LOCC}_N \subset \text{LOCC}^\infty \subset \text{LOCC} \subsetneq \text{SEP} \subset \text{PPT-preserving}\).

6.6 Nielsen’s Theorem

6.7 Entanglement Measures

6.8 PPT States and Bound Entanglement

6.9 Monogamy of Entanglement

One of the most counterintuitive features of quantum entanglement is that it is monogamous: if Alice and Bob share a maximally entangled state, then Alice cannot be entangled with any third party Charlie. This contrasts sharply with classical correlations, which can be shared freely among many parties.

The CKW inequality is the quantitative version of monogamy: Alice’s entanglement with Bob plus Alice’s entanglement with Charlie cannot exceed Alice’s entanglement with the joint system \(BC\). The slack \(\tau(A:BC) - \tau(A:B) - \tau(A:C)\) is called the residual tangle or 3-tangle, a genuine tripartite entanglement measure.

Chapter 7: Quantum Channel Capacities

The capacity theory for quantum channels is the quantum analogue of Shannon’s channel coding theorems, but far richer due to the multiplicity of resources (classical bits, qubits, entanglement) that can be transmitted and consumed.

7.1 Classical Capacity

The regularisation over \(n\) in the HSW theorem is necessary in general (Hastings 2008 proved that \(\chi\) is not additive), which makes \(C(\Phi)\) uncomputable. However, for degradable channels (channels \(\Phi\) for which there exists a map \(\mathcal{N}\) with \(\Phi_E = \mathcal{N}\circ\Phi\), where \(\Phi_E\) is the complementary channel), the Holevo information is additive and \(C = \chi(\Phi)\).

The relationship between the HSW capacity and the classical capacity of the quantum measurement channel is important. If one is restricted to product input states (no entanglement between uses), the maximum rate is \(\chi^{(1)}(\Phi) = \max_{\{p_k,\rho_k\}}\chi(\Phi(\mathcal{E}))\). The full classical capacity may be larger because entangled codewords across multiple uses can increase the Holevo information. Concretely: for the qubit depolarising channel \(\Omega_p\), entangled codewords provide no advantage (\(\chi\) is additive) and \(C(\Omega_p) = 1 - h(p) - p\log 3\). For the qubit erasure channel, no entanglement advantage either. The Hastings channel requires a specific carefully constructed channel where entanglement increases the Holevo information by a constant factor.

7.2 Quantum Capacity and the LSD Theorem

The single-letter lower bound is the coherent information \(I_c(\rho,\Phi) = S(\Phi(\rho)) - S_e(\rho,\Phi)\), where \(S_e\) is the entropy exchange (equal to \(S(AE)_{\rho^{AE}}\)). SSA implies \(I_c \leq S(\Phi(\rho)) \leq \log\dim\mathcal{Y}\), and the LSD theorem says \(Q \geq \max_\rho I_c(\rho,\Phi)\), with equality for degradable channels.

7.3 Entanglement-Assisted Capacity

7.4 Private Classical Capacity

Classical information can be transmitted through a quantum channel not only reliably, but also privately — so that an eavesdropper (who holds the channel environment) obtains negligible information. This is the quantum-mechanical basis for quantum key distribution.

The inequality \(P \geq Q\) has a beautiful physical interpretation: any rate at which quantum information can be reliably transmitted implies the same rate of private classical communication (encode the classical message in a qubit state). The deeper result is that \(P = Q\) for many natural channels — the quantum capacity of transmitting qubits is exactly the same as the private classical capacity. This connection was made precise by the Devetak-Shor (2005) equivalence: private codes can be converted to quantum codes and vice versa.

7.5 Quantum Key Distribution and the BB84 Protocol

Quantum key distribution (QKD) is the application of quantum information theory to cryptography. It allows two parties to establish a shared secret key whose security is guaranteed by the laws of physics, not computational hardness assumptions.

Chapter 8: Quantum Error Correction

Quantum error correction (QEC) is the theory of protecting quantum information against noise. The key insight — that quantum information can be encoded in larger Hilbert spaces in ways that allow errors to be detected and corrected without disturbing the encoded information — is the foundation of fault-tolerant quantum computation.

The existence of quantum error correction is perhaps the most surprising fact in quantum information theory: despite the no-cloning theorem (Theorem 2.4) and the no-broadcasting theorem for mixed states, it is still possible to protect quantum information against a restricted class of errors. The resolution of this apparent contradiction is that QEC does not copy the quantum information — it spreads it across many qubits in a highly entangled way, so that no single qubit carries enough information for the no-cloning argument to apply. The Knill-Laflamme conditions (Definition 8.2) make this precise: the error must leave no information about the logical codeword in the error syndrome.

The entropy connection is deep: correcting errors is dual to erasing entropy, and the channel capacity framework of Chapter 7 and the QEC framework of this chapter are two sides of the same coin — the quantum capacity \(Q(\Phi)\) equals the maximum code rate for which QEC is possible through \(\Phi\).

8.1 The Error Correction Framework

8.2 Entropy and Error Correction

The connection between quantum error correction and quantum entropy is deep: the coherent information \(I_c\) is exactly the rate at which information survives a noisy channel, and the Knill-Laflamme conditions can be rephrased in terms of conditional entropy. Specifically: a code \(\mathcal{C}\) is exactly correctable for \(\Phi\) if and only if \(S(A|B)_\omega = -S(A)_\omega\) where \(\omega^{AB}\) is the state after sending half of the maximally entangled state on \(\mathcal{C}\otimes\mathcal{C}\) through \(\Phi\). This entropy formulation is equivalent to the Knill-Laflamme conditions and connects error correction directly to the negative conditional entropy criterion for entanglement (§5.3). Specifically, \(\{E_j\}\) are correctable for \(\mathcal{C}\) if and only if the “error syndrome” (which Kraus operator applied) is statistically independent of the logical information in \(\mathcal{C}\). This is the quantum analogue of the classical separation between parity check bits and message bits in linear codes.

8.3 CSS Codes and Fault Tolerance

The most practically important class of stabiliser codes are the CSS (Calderbank-Shor-Steane) codes, built from two classical linear codes with a nested structure. Their special form separates bit-flip and phase-flip error correction, making fault-tolerant gate implementation much simpler.

The threshold theorem is the foundational result of fault-tolerant quantum computation. It says that if hardware errors are below a threshold (roughly \(10^{-3}\) to \(10^{-2}\) for modern codes), quantum computations of arbitrary length can be performed reliably by using quantum error correction with only a polylogarithmic overhead. The exponential suppression \((p/p_{\text{th}})^{2^L}\) comes from concatenation: at each level of the code hierarchy, the logical error rate squares, driving it towards zero.

8.4 Approximate Quantum Error Correction and the Knill-Laflamme Conditions Revisited

The exact Knill-Laflamme conditions require the error syndrome to carry zero information about the logical codeword. In practice, this is often relaxed to approximate error correction — tolerating a small fidelity loss.

Key Formulas Summary