For a transferable utility game, the characteristic function of a coalitional game assigns a coalition $S$ its largest total attainable revenue $v(S)$, with $v(\varnothing )=0$. The core of a cooperative game consists of payoff vectors $x$ satisfying efficiency, $x(N)=v(N)$, and coalition stability, $x(S)\ge v(S)$ for every $S$. A coalition receiving less could operate alone and distribute its extra value to make each member better off.

Use thousands of pounds as the monetary unit. The physical directed arcs are $A\to B$ and $C\to D$, owned by $i$, with capacities $3,2$; $A\to C$ and $B\to D$, owned by $j$, with capacities $1,1$; and $B\to C$, owned by $k$, with capacity $2$.

The physical network is acyclic. There are exactly three $A$–$D$ graph paths and one $B$–$C$ graph path. Let $u,v,w$ be the $A$–$D$ flows on $ABD$, $ACD$, $ABCD$, respectively, and let $z$ be the direct $B$–$C$ demand. Their capacities and revenue areEvery feasible traffic pattern decomposes into these graph paths, so these inequalities are exact. The first is redundant, since $u\le 1$ and $w\le 2$ imply it.

Formulate this as a minimum-cost flow through the two-resource path packing as minimum-cost circulation reduction. Use auxiliary vertices $s,L,R,t$ and the following arcs, whose entries are (capacity, cost):The first forward graph path carries $u$, $sLt$ carries $v$, $sLRt$ carries $w$, and $sRt$ carries $z$. Conservation at $L$ imposes $v+w\le 2$, and at $R$ imposes $w+z\le 2$; the individual finite-capacity arcs give the other bounds. The return arc closes the circulation. Its cost is exactly $-R$, so this is an ordinary minimum-cost circulation with precisely the required feasible traffic set. Unlimited capacities may all be replaced by $5$, the maximum possible total graph path flow.

An linear programming optimality certificate is particularly short:The feasible choice $u=v=w=z=1$ attains equality. Thus the actual traffic is three units from $A$ to $D$ and one from $B$ to $C$, andAll four positive terms in the bound must be tight at any optimum, so these graph path amounts are unique.

The two traffic demands must retain their identities. Merely adding fictitious return arcs $D\to A$ and $C\to B$ to the physical graph can create an invalid graph cycle combining both rewards: $A\to C\to B\to D\to A$ would credit the $j$-only network with revenue even though it carries neither requested demand. The resource-flow formulation above avoids that problem.

For the characteristic function, only complete physical graph paths owned by a coalition are available. Company $i$ or $j$ alone has no requested graph path; company $k$ carries two units of $B$–$C$ traffic. The pair $\{i,j\}$ carries one unit on each of $ABD,ACD$; the pair $\{i,k\}$ sends two units on $ABCD$ rather than selling them at the lower $B$–$C$ rate; and $\{j,k\}$ has only the two direct $B$–$C$ units. ThereforeWriting payments in thousands, all stable divisions of the revenue are exactlyEquivalently, $8\le x_k\le 10$, $0\le x_j\le 10$ and $x_i=22-x_j-x_k$. This is the entire core, not just one acceptable allocation.

The nucleolus minimizes in lexicographic order the sorted decreasing excesses of a coalition $e(S,x)=v(S)-x(S)$ over imputations. Empty and grand-coalition coalition excesses are fixed zeros and can be omitted. For the six other coalitions, efficiency givesThe two $k$-related coalition excesses sum to $-2$, so their maximum is at least $-1$. This bound is attainable, and attaining it forces $x_k=9$. All six coalition excesses are then at most $-1$ precisely when $1\le x_j\le 9$ and $x_i=13-x_j$. The fixed pair of coalition excesses equals $-1$ throughout these first-stage minimizers.

Minimize the largest of the remaining coalition excesses. They become $x_j-13,-x_j,x_j-10,-1-x_j$, whose maximum is $\max (-x_j,x_j-10)$. Its unique minimum is $-5$ at $x_j=5$. Hence $x_i=8$ and $x_k=9$. The sorted proper coalition excesses there are $(-1,-1,-5,-5,-6,-8)$, and

For a connected undirected weighted graph, a spanning tree connects all vertices without a graph cycle. A minimum spanning tree minimizes the sum of its edge weights. Disconnected input has no spanning tree, although the same methods produce a minimum spanning forest. Negative edge weights and ties cause no difficulty; a tree always contains exactly $|V|-1$ edges.

The central exchange argument is the minimum spanning tree cut property. Suppose a forest $F$ is contained in some minimum spanning tree $T$, and consider a cut with no edge of $F$ crossing it. Let $e$ be a lightest crossing edge. If $e\notin T$, adding it creates a graph cycle; the graph path in $T$ between its endpoints contains a crossing edge $f$. That $f$ is not in $F$, and $w(e)\le w(f)$. Thus $T-f+e$ is another spanning tree with no larger weight and still contains $F$. It is also minimum and contains $F\cup \{e\}$. This proves that the chosen edge is safe, rather than merely asserting a greedy choice.

Kruskal's algorithm sorts all edges by increasing weight, starts with the empty forest, and adds an edge precisely when its endpoints are in different components. Each added edge is lightest across a component cut respected by the current forest. The exchange proof inductively keeps the forest inside a minimum spanning tree; connectedness makes the final forest a spanning tree, hence an optimum. Sorting takes $O(|E|\log |E|)$ comparisons, and even a simple component-merging implementation takes only polynomial additional work. Efficient component tracking improves that overhead further.

Prim's algorithm instead grows a single tree, repeatedly adding a lightest edge from its vertex set to the outside. The same cut argument proves correctness. A dense implementation using an array runs in $O(|V{|}^2)$ comparisons. The dual minimum spanning tree cycle property says a uniquely heaviest edge of a graph cycle belongs to no minimum spanning tree: exchanging it for a lighter crossing edge strictly improves any tree containing it. Ties must be handled carefully; a merely nonunique heaviest edge can occur in an optimum.

Complexity classes are formally classes of decision problems, so use the version asking whether a graph has a spanning tree of total weight at most a supplied threshold $K$. Assume integer or rational weights and threshold are encoded in binary. The input length includes all these bits, not only the numbers of vertices and edges. P consists of decision problems decidable by a deterministic algorithm in time polynomial in that input length. NP consists of those with polynomial-size complexity certificates verified in deterministic polynomial time, equivalently decidable in polynomial time by a nondeterministic machine.

Kruskal's algorithm constructs the optimum and compares its weight with $K$. Binary integer comparisons and sums are polynomial-time operations. Rational comparisons can be made by cross multiplication, and their summed numerator and denominator have polynomially bounded bit length: a product of input denominators has bit length no greater than the sum of their bit lengths. The combinatorial algorithm makes polynomially many such operations. Hence the minimum-spanning-tree decision problem is in P; the optimization version likewise has a polynomial-time algorithm.

For membership in NP, the complexity certificate is a list of $|V|-1$ selected edges. Check that every edge is present, that the edges connect all vertices and contain no graph cycle, and that their total weight is at most $K$. A graph search and binary arithmetic do this in polynomial time. A successful complexity certificate need not establish that its tree is minimum: it proves the threshold question's yes-answer. Conversely, a yes-instance has such a tree as a complexity certificate. ThereforeMembership in NP does not arithmetic mean NP-hardness; here the explicit greedy algorithm provides the stronger tractability result.

Given a feasible network flow $f$, an original directed edge $(u,v)$ has forward residual capacity $c_{uv}-f_{uv}$ and a reverse residual arc of capacity $f_{uv}$. A source–sink graph path in this residual network permits an augmentation by the minimum residual capacity along it: increase forward flows and decrease the corresponding reversed flows. Capacities and flow conservation are preserved, and the flow value increases by that amount.

If no residual source–sink graph path exists, let $S$ be the vertices reachable from the source. The sink is outside $S$. Every original arc from $S$ to its complement is saturated, and every original arc back into $S$ has zero flow, since a positive reverse residual arc would make its tail reachable. Conservation therefore givesThe flow equals this cut capacity, so the max-flow min-cut theorem proves it is maximum.

Termination needs a capacity or path-selection assumption. For integer capacities, starting from zero, every residual capacity and augmentation is integral; each augmentation increases the value by at least one, and the value is bounded by the total source-outgoing capacity. The algorithm therefore terminates. Rational capacities can be scaled to integers. With arbitrary real capacities, unrestricted graph path choices do not guarantee finite termination. A valid uniformly terminating implementation is the Edmonds–Karp algorithm, choosing a shortest residual graph path each time.

Here is why that choice works independently of numerical capacity sizes. Residual distances from the source cannot decrease after augmenting along a shortest graph path. Every newly created residual arc is the reverse of a graph path arc; if it could cause the first distance decrease, its previous distance relation would contradict that decrease. When an arc $(u,v)$ is saturated on a shortest graph path, $d(v)=d(u)+1$. Before the same direction can be saturated again, it must have been restored by a reverse augmentation on a shortest graph path, at which time $d^{\prime }(u)=d^{\prime }(v)+1\ge d(v)+1=d(u)+2$. Each arc is consequently critical only $O(|N|)$ times. There are $O(|A|)$ arcs and each augmentation saturates at least one, giving $O(|N||A|)$ augmentations, each found by breadth-first search in $O(|A|)$ time. Thus the shortest-path Ford–Fulkerson implementation terminates and finds a maximum flow in $O(|N||A{|}^2)$ arithmetic operations.

For sports elimination by maximum flow, first give the target team all its remaining wins. This cannot hurt its chance to finish strictly ahead: changing a result to favour it also removes a rival's win. Let $w^{\ast }$ be its resulting win count. If any rival already has at least $w^{\ast }$ wins, strict victory is impossible. Otherwise give each unordered pair of rivals $i<j<n$ one game node. Its incoming capacity is $g_{ij}$, and its two outgoing arcs go to the participating team nodes. Their capacities may be replaced by the finite numbersince no arc can need more than the total number of remaining rival games. Team $i$ has sink capacity $w^{\ast }-w_i-1$.

An integral flow of value $G$ saturates all game-node incoming arcs. Its two outgoing amounts allocate exactly $g_{ij}$ wins to the two teams; the team-sink caps keep each rival strictly below $w^{\ast }$. Conversely any successful completion of the league specifies such a flow. Integral capacities and augmentation give an integral maximum flow, soafter the initial negative-capacity rejection. Each actual game is counted once: making independent nodes for both ordered pairs would double-count it.

The network has $O(n^2)$ nodes and arcs. If each input integer has at most $k$ bits, its derived capacities have $O(k+\log n)$ bits. The shortest-path algorithm above uses $O(n^6)$ arithmetic operations, each on integers of polynomial bit length. Therefore the decision problem belongs to P, even with $k$ part of the input. If $k$ is fixed, even the basic integral-augmentation bound $O(G|A|)=O(n^4{2}^k)$ is polynomial in $n$. If $k$ varies, that particular bound is only pseudopolynomial; it is the shortest-path implementation that establishes polynomial bit complexity.

Fix the noise convention explicitly: $p$ is the total probability of a nonidentity Pauli error. The memoryless qubit quantum depolarizing channel iswith independent identical use on successive qubits, namely ${\mathcal{D}}_p^{\otimes n}$ on an $n$-qubit block. Its normalized Kraus operators are $\sqrt{1-p}I,\sqrt{p/3}X,\sqrt{p/3}Y,\sqrt{p/3}Z$.

Write the Bloch sphere representation of a density matrix as $\rho =(I+\mathbf{r}\cdot \mathbf{\sigma })/2$, with $|\mathbf{r}|\le 1$. Its eigenvalues are $(1\pm |\mathbf{r}|)/2$, proving exactly this positivity condition. Conjugation by one Pauli operator preserves that coordinate of the Bloch vector and reverses the other two. Summing the three conjugations givessoThe Bloch ball contracts isotropically, collapses to the maximally mixed state at $p=3/4$, and contracts with reversal for $p>3/4$. That last interval still represents a physical Pauli mixture. If instead $q$ is the probability of replacing the state by $I/2$, then $\mathcal{D}(\rho )=(1-q)\rho +qI/2$, with $p=3q/4$ and $\eta =1-q$; the usual replacement-probability range $0\le q\le 1$ stops at complete depolarization.

Let $h_2(x)=-x{\log }_{2}x-(1-x){\log }_2(1-x)$, with endpoint limits. In bits per use, the unassisted product-state classical capacity and the entanglement-assisted capacity of a qubit depolarizing channel arewhere $H_4$ is Shannon entropy of the listed four probabilities. Equivalently $C_E=2+(1-p){\log }_2(1-p)+p{\log }_2(p/3)$. The first quantity is a classical capacity with product quantum inputs and potentially collective output measurements, not the quantum capacity. These are the requested capacity formulae; a proof of their coding theorems is not needed here. The maximally entangled input gives a Bell-diagonal joint state with those four probabilities, explaining the entropy appearing in $C_E$. The original entanglement-assisted capacity calculation gives the depolarizing-channel expression.

At $p=0$ the capacities are one and two. Both vanish at $p=3/4$. On the full Pauli-error interval they increase again beyond that point, reaching $1-h_2(2/3)$ and $2-{\log }_{2}3$ at $p=1$; on the replacement-probability plot both decrease to zero at $q=1$. The two panels make this convention distinction explicit.

For the high-noise capacity ratio for qubit depolarization, put $\eta =1-4p/3\to 0$. Taylor expansion of binary entropy around one half givesThe four probabilities for $C_E$ are $1/4+3\eta /4$ and three copies of $1/4-\eta /4$. For a perturbation ${\delta }_i$ of the uniform four-outcome distribution, with ${\sum }_i{\delta }_i=0$, entropy expansion givesHere ${\sum }_i{\delta }_i^2=3{\eta }^2/4$, hence $C_E=3{\eta }^2/(2\ln 2)+O({\eta }^3)$. ThereforeThe reciprocal ratio is $1/3$, and the same enhancement factor occurs as $q\to 1$ in the replacement convention.

The Schumacher compression theorem concerns a memoryless quantum information source with average density matrix $\rho$ on a finite-dimensional Hilbert space. For $n$ uses the average state is ${\rho }_n={\rho }^{\otimes n}$. Compression consists of an encoding quantum channel into a space of dimension $D_n$ and a decoding channel back to the original block space, with asymptotic rate $n^{-1}{\log }_2{D}_n$ qubits per source use. The optimal reliable rate is $S(\rho )$: every larger rate is achievable, and no smaller rate is reliable. This holds for average pure-source fidelity; the direct construction also preserves a purification reference, and the converse for that stronger entanglement fidelity criterion holds with fidelity tending to zero below the threshold. The encoding and decoding are deterministic channels; no free classical transmission of the source label is allowed.

Diagonalize $\rho ={\sum }_j{\lambda }_j|j⟩⟨j|$ and omit zero-probability eigenvalues when sampling. Define the quantum typical subspace projector $P_{n,\delta }$ by retaining product eigenvectors withThe sampled random variable $-{\log }_2{\lambda }_j$ has expectation $S=S(\rho )$. The weak law of large numbers gives $w_n=\mathrm{Tr}({\rho }_n{P}_{n,\delta })\to 1$. Every retained eigenvalue is at least $2^{-n(S+\delta )}$, and the total probability is at most one, soThis proves the two typical subspace theorem estimates used in the direct part.

Write $P=P_{n,\delta }$. Encode its range isometrically into a compressed space and reserve one orthogonal failure flag. Decode the range back isometrically and the failure flag to a fixed pure state $|\phi ⟩$. This typical-subspace compression with a failure flag is a physical channel whose composite action isIndeed its Kraus operators are $P$ and $|\phi ⟩⟨e_a|$, where the $e_a$ form an orthonormal basis of $\ker P$, and their adjoint products sum to $I$. The Kraus formula for entanglement fidelity givesFor any pure-state ensemble of ${\rho }_n$, the average squared quantum fidelity is at least this number: apply convexity of $|z{|}^2$ separately to the amplitudes $⟨{\psi }_x|K_{\alpha }|{\psi }_x⟩$ with their source probabilities. Thus average fidelity also tends to one. The compressed dimension is at most $2^{n(S+\delta )}+1$, and its rate is at most $S+\delta +o(1)$. Choose $\delta <R-S$ for any prescribed $R>S$. One may also take ${\delta }_n=n^{-1/4}$: the finite spectral information variance and Chebyshev's inequality still give $w_n\to 1$, with rate tending to $S$. A pure source, $S=0$, can simply be re-prepared exactly without sending any qubits.

For the coherent converse, we prove the finite-dimensional quantum compression converse. If the compressed space has dimension $D$, the state of reference plus compressed system has a pure-state decomposition with Schmidt rank at most $D$. Applying decoder Kraus operators locally cannot increase the Schmidt rank of those vectors, so the final reference–output state has Schmidt number at most $D$. Let $|{\Psi }_{{\rho }_n}⟩$ purify the source, with squared Schmidt coefficients equal to the decreasing eigenvalues ${\mu }_1\ge {\mu }_2\ge \cdots$ of ${\rho }_n$. For any normalized vector $|v⟩$ of Schmidt rank at most $D$, its reference support lies in a rank-at-most-$D$ projector $Q$. HenceThe last bound follows by maximizing ${\sum }_j{\mu }_j⟨j|Q|j⟩$ subject to $0\le ⟨j|Q|j⟩\le 1$ and their sum at most $D$. Average over a Schmidt-rank-bounded decomposition of the final state to obtain $F_e\le {\sum }_{j=1}^D{\mu }_j$.

At rate $R<S$, choose $0<\delta <S-R$. The total source probability outside the quantum typical subspace tends to zero, while every eigenvalue inside it is at most $2^{-n(S-\delta )}$. Therefore for $D_n\le 2^{nR}$,This argument allows arbitrary encoding and decoding channels, not only subspace projection.

For completeness, average pure-source reliability also forces the same rate, even though it is a weaker criterion than entanglement fidelity. Here is a separate converse for that formulation. Let the emitted block pure states be ${\psi }_x$, with probabilities $p_x$, and let ${\sigma }_x$ be the decoded states. If their mean squared fidelity tends to one, then their mean trace distance ${\bar{\delta }}_n$ tends to zero, since $\frac{1}{2}\Vert {\sigma }_x-{\psi }_x{\Vert }_1\le \sqrt{1-⟨{\psi }_x|{\sigma }_x|{\psi }_x⟩}$. This inequality follows by choosing a purification with that overlap and using contraction of trace distance under a partial trace.

We need only an elementary entropy continuity from Jordan decomposition bound, derivable from Question 4. If $\delta =\frac{1}{2}\Vert \sigma -\tau {\Vert }_1$, write the positive and negative parts of $\sigma -\tau$ as $\delta {\omega }_{+},\delta {\omega }_{-}$. The common density matrixand the two mixture bounds giveHere $g$ is increasing and concave, $g(0)=0$. Apply this in block dimension $d^n$, both to the average states and to individual outputs, using convexity of trace distance and concavity of $g$. Since the original ensemble is pure, its Holevo quantity is $S({\rho }_n)=nS$. The decoded ensemble hasThe Holevo quantity under a quantum channel cannot increase. To specify the entropy ingredient, Strong subadditivity of Von Neumann entropy states $S(XB)+S(BE)\ge S(B)+S(XBE)$. Attach the classical source label $X$, dilate the decoder isometrically to $BE$, and trace out $E$. The displayed inequality says $I(X:B)\le I(X:BE)$; the isometry preserves the input mutual information. Since $I(X:B)$ of a labelled ensemble is its Holevo quantity, this proves the needed decoder monotonicity. Before decoding, the system has dimension $D_n$, so its Holevo quantity is at most ${\log }_2{D}_n$. Thus ${\log }_2{D}_n\ge nS-o(n)$ and the rate cannot be below $S$. Both operational fidelity formulations therefore have the claimed noiseless coding threshold.

For a density matrix $\rho$ on a $d$-dimensional Hilbert space, its Von Neumann entropy, in bits, iswhere the ${\lambda }_a$ are its eigenvalues and $0{\log }_{2}0=0$. Each summand is nonnegative, proving $S\ge 0$, with equality exactly when one eigenvalue is one and the rest zero, namely for a pure state.

We first prove the nonnegativity of quantum relative entropy needed below. Diagonalize $\rho$ with eigenvalues ${\lambda }_a$ and eigenvectors $u_a$, and $\sigma$ with eigenvalues ${\mu }_b$ and eigenvectors $v_b$. Put $B_{ab}=|⟨u_a,v_b⟩{|}^2$ and $q_a=⟨u_a|\sigma |u_a⟩={\sum }_b{B}_{ab}{\mu }_b$. Each row of $B$ sums to one. Concavity of the ordinary logarithm gives ${\sum }_b{B}_{ab}{\log }_2{\mu }_b\le {\log }_2{q}_a$. ConsequentlyThe final Gibbs inequality follows directly from ${\sum }_{{\lambda }_a>0}{\lambda }_a\log (q_a/{\lambda }_a)\le \log {\sum }_{{\lambda }_a>0}{q}_a\le 0$. Support failure gives $D=+\infty$; zero eigenvalues can otherwise be handled by restriction or regularization. Equality requires $q_a={\lambda }_a$ and equality in the logarithm inequality on every positive-weight row. Thus $u_a$ is a $\sigma$ eigenvector of eigenvalue ${\lambda }_a$ wherever ${\lambda }_a>0$. The remaining diagonal entries of $\sigma$ vanish and positivity makes the remaining rows and columns zero. Hence equality holds exactly when $\rho =\sigma$.

Taking $\sigma =I/d$ gives $D(\rho \Vert I/d)={\log }_{2}d-S(\rho )$, provingThe lower equality is attained exactly by pure states and the upper exactly by the maximally mixed state $I/d$.

For $\bar{\rho }={\sum }_i{p}_i{\rho }_i$, each positive-weight state has support contained in that of $\bar{\rho }$. Expanding the quantum relative entropy givesThis proves Concavity of Von Neumann entropy, with equality precisely when every positive-weight ${\rho }_i$ is the same state.

For the upper entropy bound for a quantum mixture, diagonalize each component, ${\rho }_i={\sum }_a{\lambda }_{ia}|v_{ia}⟩⟨v_{ia}|$, and set $q_{ia}=p_i{\lambda }_{ia}$. Form the rectangular matrix $B$ whose columns are $\sqrt{q_{ia}}{v}_{ia}$. Then $B{B}^{†}=\bar{\rho }$, while the Gram matrix $\Gamma =B^{†}B$ has diagonal $q_{ia}$. The two matrices have the same nonzero eigenvalues: $B$ and $B^{†}$ map corresponding positive-eigenvalue eigenspaces isomorphically. Thus $S(\Gamma )=S(\bar{\rho })$.

If there are $L$ columns, let $W=\mathrm{diag}(1,\omega ,\dots ,{\omega }^{L-1})$, with $\omega =e^{2\pi i/L}$. ThenAll the summands have the same Von Neumann entropy. The just-proved concavity therefore implies $S(\bar{\rho })=S(\Gamma )\le S(\mathrm{diag}\Gamma )=H(q)$. Finally,We have proved both requested bounds:For the upper equality, strictness in the concavity argument forces $\Gamma$ to be diagonal. Its entries between two positive-weight component eigenvectors then force those vectors to be orthogonal. Thus upper equality holds exactly when the supports of the positive-weight component states are mutually orthogonal. In that case their classical label is perfectly distinguishable, explaining the extra $H(p)$ bits.

A quantum operation is a linear, completely positive, trace-nonincreasing map on operators; its output trace records the probability of a selected outcome. A deterministic process that sends every density matrix to another normalized density matrix is a quantum channel, satisfying linearity, complete positivity and trace preservation. Linearity preserves probabilistic mixtures. Complete positivity means that ${\mathrm{id}}_R\otimes \mathcal{E}$ remains positive for every finite-dimensional reference system $R$, so the process also acts consistently on entangled inputs. Trace preservation maintains total probability. Conditioning a selected branch by dividing by its output trace is generally nonlinear; it is a separate state-update step.

The Stinespring dilation of a deterministic operation on a system $A$ iswhere $U$ is unitary on system plus environment, the initial environment is fixed and independent of the input, and the environment is discarded. A mixed environment can be purified by adding an extra environment system. For different input and output dimensions, use an isometry $V:A\to B\otimes E$ instead of this same-system unitary form.

Choose an orthonormal environment basis $\{|\alpha ⟩\}$. Taking the partial trace gives the Kraus representationUnitarity and completeness of the environment basis giveConversely, suppose the Kraus operators obey this completeness condition. Define $V|\psi ⟩={\sum }_{\alpha }{K}_{\alpha }|\psi ⟩\otimes |\alpha ⟩$. Then $V^{†}V=I$, so $V$ is an isometry. For equal input/output system dimensions, extend the orthonormal images of the subspace $A\otimes |0⟩$ to an orthonormal basis of $A\otimes E$. Mapping a completed input basis to that output basis supplies a unitary $U$ with $U(|\psi ⟩|0⟩)=V|\psi ⟩$. Tracing the environment recovers the given operator sum. This proves both directions of the equivalence.

It also follows directly that every completely positive map in finite dimensions has an operator sum. Form its unnormalized Choi matrix $J=(\mathrm{id}\otimes \mathcal{E})|\Omega ⟩⟨\Omega |$, with $|\Omega ⟩={\sum }_i|i⟩|i⟩$. Complete positivity makes $J\ge 0$. Resolve $J={\sum }_{\alpha }|v_{\alpha }⟩⟨v_{\alpha }|$ and reshape each vector as $|v_{\alpha }⟩={\sum }_i|i⟩K_{\alpha }|i⟩$. Comparing the coefficients of $|i⟩⟨j|$ gives $\mathcal{E}(|i⟩⟨j|)={\sum }_{\alpha }{K}_{\alpha }|i⟩⟨j|K_{\alpha }^{†}$, hence the same formula for every operator by linearity. Trace preservation imposes the completeness condition just derived.

Finally, linearity of the operator sum is immediate from matrix multiplication. For any positive operator $B$ on reference plus system,because each summand is a positive congruence. This proves complete positivity for every reference dimension. Cyclicity of the trace givesKraus form is trace preserving exactly when ${\sum }_{\alpha }{K}_{\alpha }^{†}{K}_{\alpha }=I$. Without this normalization, the final printed assertion would be false: a single operator $K=I/2$ gives output trace one quarter on every input density matrix. Thus the completeness condition is an essential part of the physical Kraus representation.

Over a finite field ${\mathbb{F}}_q$, a linear code of length $N$ and dimension $k$ is a $k$-dimensional subspace $C\subseteq {\mathbb{F}}_q^N$. A full-row-rank generator matrix $G\in {\mathbb{F}}_q^{k\times N}$ gives $C=\{mG:m\in {\mathbb{F}}_q^k\}$, using row-vector messages. A full-row-rank parity-check matrix $H\in {\mathbb{F}}_q^{(N-k)\times N}$ gives $C=\{x:H{x}^T=0\}$. The dual code is $C^{\perp }=\{y:x\cdot y=0\text{ for all }x\in C\}$, of dimension $N-k$. Thus the rows of $H$ span $C^{\perp }$, andConversely the rank conditions and $H{G}^T=0$ imply that the row space of $G$ equals the kernel of $H$, by inclusion and equality of dimensions.

For a CSS code, specialize to binary linear codes $C_2\subseteq C_1\subseteq {\mathbb{F}}_2^N$, of dimensions $k_2,k_1$. Define orthonormal encoded statesDifferent cosets have disjoint computational-basis support. Their span has dimension $2^{k_1-k_2}$, so it encodes $K=k_1-k_2$ logical qubits. For binary vectors write $X(u)={⨂}_j{X}_j^{u_j}$ and $Z(v)={⨂}_j{Z}_j^{v_j}$. The stabilizer generators are $X(u)$ for a basis of $C_2$, and $Z(v)$ for a basis of $C_1^{\perp }$. They fix each encoded state: the former permute its coset terms and the latter contribute phases $(-1{)}^{v\cdot (x+y)}=1$. Their commutation relation is $X(u)Z(v)=(-1{)}^{u\cdot v}Z(v)X(u)$, so the classical dual inclusion $C_1^{\perp }\subseteq C_2^{\perp }$ makes them commute. There are $k_2+N-k_1=N-K$ independent checks, giving precisely this encoded space.

For a Pauli error $X(e)Z(f)$, the Z checks give bit-error syndrome $H_1{e}^T$, where $H_1$ checks $C_1$, and the X checks give phase-error syndrome $G_2{f}^T$, where $G_2$ generates $C_2$ and hence checks $C_2^{\perp }$. Classical decoders therefore correct up to $t_X$ bit flips and $t_Z$ phase flips if $d(C_1)>2t_X$ and $d(C_2^{\perp })>2t_Z$. A Y error has both components; it is not omitted from this correction scheme.

For the precise quantum code distance, harmless stabilizer errors must be excluded. A pure-X error preserves the code exactly when $e\in C_1$, and is a stabilizer when $e\in C_2$; a pure-Z error preserves it when $f\in C_2^{\perp }$, and is a stabilizer when $f\in C_1^{\perp }$. Consequently, for $K>0$,A mixed Pauli error has weight equal to the size of the union of its X and Z supports. If it is a nontrivial logical operator, at least one component is nontrivial, so its weight is at least $\min (d_X,d_Z)$; pure-X or pure-Z operators attain that minimum. Thus $t=\lfloor (d-1)/2\rfloor$ arbitrary-qubit errors are correctable: products of two such Pauli errors have weight below $d$ and act scalarly on the code, or take it to an orthogonal syndrome sector. This is the Knill--Laflamme condition. Expanding arbitrary errors in the Pauli basis extends correction to their coherent linear span.

An explicit example is the Steane code. Take $C_1$ to be the binary Hamming code withThe distinct nonzero columns show that $C_1$ has no weight-one or weight-two word, while three dependent columns give a weight-three word. Hence its classical distance is three. Direct multiplication gives $H{H}^T=0$, proving $C_2\subseteq C_1$. Every nonzero word of $C_2$ has weight four, so the logical X and Z distances are both three. Its six stabilizer checks are the X and Z strings given by the three rows of $H$. A logical basis is the uniform superposition over $C_2$ and over $1+C_2$, since $1=(1,\dots ,1)\in C_1\setminus C_2$. The resulting $[[7,1,3]]$ CSS code corrects every single-qubit error.