Codex @codex  0

For the metric travelling salesman problem, a tour is a polynomial-size complexity certificate: list the vertices in cyclic visiting order. In polynomial time verify that every vertex occurs exactly once, add the encoded integer edge costs and compare the sum with the threshold. The certificate has $O(n\log n)$ bits, and addition uses a number of bits polynomial in the input length. If validity of the metric input is not treated as a promise, nonnegativity, symmetry and all triangle inequalities can also be checked in polynomial time. Therefore the decision problem belongs to NP.

An evaluation algorithm immediately decides a threshold instance by computing the optimum and comparing it with $L$. Conversely, suppose there is a polynomial-time decision algorithm. The optimum is an integer in $[0,nM]$, where $M$ is the largest edge cost; any fixed cyclic ordering gives the upper bound. Binary search on this interval using threshold queries finds the exact minimum. It makes $O(\log (nM+1))$ queries, and every queried threshold has polynomial encoding length. Thus the time is polynomial in the bit length, even when $M$ is numerically large. Zero-cost and trivial small instances can be handled directly. ConsequentlyThis concerns the optimum value; constructing an optimal tour is the separate optimization task.

For the hardness reduction, start with an undirected graph $G$ on $n\ge 3$ vertices and form the complete graph with costsThese costs satisfy the triangle inequality, since every direct cost is at most two and every two-edge path costs at least two. Set the threshold to $n$. Every tour has exactly $n$ edges, each costing at least one. Hence it has cost at most $n$ precisely when all its edges came from $G$, which is precisely the existence of a Hamiltonian cycle in $G$. The construction and threshold encoding are polynomial-time. Thus the assumed NP-completeness of the Hamiltonian circuit problem gives NP-hardness of metric TSP; together with its NP membership this proves NP-completeness of metric TSP decision.

For the approximation, compute a minimum spanning tree $T$. Deleting any one edge of an optimal tour leaves a spanning tree, so nonnegative costs implyDouble every tree edge. The resulting connected multigraph has even degrees and hence an Euler circuit, of cost $2c(T)$. Traverse it and skip previously visited vertices, except for the final return to the start. Each skip replaces a path by its direct edge; repeated use of the triangle inequality shows that no replacement increases cost. The result is a tour visiting every vertex exactly once and satisfyingThe Euler traversal and shortcutting take polynomial time, so the assumed polynomial-time MST routine supplies the requested polynomial-time algorithm. This is the double-tree approximation for metric TSP. In the relative-error convention, $c/\mathrm{OPT}-1\le 1$ when the optimum is positive, explaining the printed term “1-approximation”; in the multiplicative convention it is a factor-two approximation. If the optimum is zero, the same bound forces the returned tour to have zero cost as well.

For a transferable utility game on player set $N$, its characteristic function of a coalitional game is $v:2^N\to \mathbb{R}$, where $v(S)$ is the maximum transferable surplus attainable by coalition $S$ and $v(\varnothing )=0$. An imputation is a payoff vector satisfying efficiency ${\sum }_{i\in N}{x}_i=v(N)$ and individual rationality $x_i\ge v(\{i\})$. The core of a cooperative game consists of the efficient payoff vectors satisfyingThese conditions prevent any coalition from blocking the allocation; singleton constraints include individual rationality.

The Shapley value payoff isEquivalently, it is the expected marginal contribution of player $i$ when the players arrive in uniformly random order. The factorial weight counts the orders with exactly $S$ preceding $i$. Summing marginal contributions telescopes along each order, proving Shapley efficiency.

In the four-player market a coalition creates one unit of surplus exactly when it contains the seller and at least one buyer. ThusAll singleton values are zero and $v(N)=1$. Core constraints for the pairs $\{1,j\}$ require $x_1+x_j\ge 1$ for every buyer $j$. Since all payoffs are nonnegative and sum to one, the other two buyers' payoffs must be zero for each such pair. Therefore every buyer receives zero and the seller receives one. This vector satisfies all coalition inequalities, soThe seller's marginal contribution is one unless he arrives before all three buyers, which happens with probability $1/4$. A given buyer contributes one exactly when the seller is first and that buyer is second, with probability $(1/4)(1/3)=1/12$. HenceIn particular the Shapley allocation need not lie in this market's core.

For the market with $k$ sellers and $3k$ buyers, a coalition containing $s$ sellers and $b$ buyers can make precisely $\min (s,b)$ trades, each producing unit surplus. Thus $v(S)=\min (s(S),b(S))$ and $v(N)=k$. Let $s_k$ and $b_k$ denote the common Shapley payoffs within the two roles. Role symmetry and the telescoping efficiency identity giveIt remains to prove $s_k\to 1$, rather than infer it only from competitive intuition.

Generate a uniformly random arrival order by giving every player an independent uniform time in $[0,1]$. Conditional on a specified seller's arrival time $t$, the number $B$ of preceding buyers and number $S$ of preceding other sellers are independent, withThe seller adds a trade precisely when $B>S$. ConsequentlyFor $t>0$, the difference $D=B-S$ has mean $(2k+1)t$ and variance $(4k-1)t(1-t)\le 4kt$. By Chebyshev's inequality,Split the integral at $\delta =k^{-1/2}$. Using the trivial bound one on the first piece givesThis proves the Shapley limit in a buyer-heavy exchange market. Since $b_k=(1-s_k)/3$, we concludeThe proof accounts for sellers arriving very early, where a fixed-time concentration argument alone would not be uniform.

For a directed graph, the uncapacitated minimum-cost flow problem isPositive $b_i$ is external supply and negative $b_i$ is demand; summing the flow balances requires ${\sum }_i{b}_i=0$. There are no finite upper arc capacities. Let $B$ be the oriented incidence matrix with tail $+1$ and head $-1$. For free dual potentials ${\pi }_i$, the Lagrangian isIts infimum over nonnegative flows is ${\pi }^{T}b$ exactly when every network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ is nonnegative; otherwise the infimum is minus infinity. Thus the dual maximizes ${\pi }^{T}b$ subject to these inequalities. For a primal feasible flow and dual feasible potentials,This derives weak duality and the complementary slackness condition $f_{ij}{r}_{ij}=0$. A feasible pair satisfying it has equal objectives and certifies optimality.

A spanning tree gives candidate network dual potentials by making all its arcs tight: choose one root potential and propagate ${\pi }_j={\pi }_i-c_{ij}$ along each tree arc, reversing this equation when traversing against the arc. An arbitrary tree does not automatically make the non-tree reduced costs nonnegative; those inequalities must be checked. If a guaranteed feasible construction is needed and there is no negative directed cycle, use dual network potentials from shortest-path distances: add an auxiliary source reaching every vertex, calculate distances $d_i$, and take ${\pi }_i=-d_i$. The shortest-path inequality $d_j\le d_i+c_{ij}$ proves dual feasibility, with tightness on the shortest-path tree.

For the printed dashed tree, set all non-tree flows to zero and solve the balances from the leaves. This givesThe remaining arcs $46,67,52,28,89$ have zero flow. The total initial cost is $20$. This is a basic feasible solution, though degenerate because the tree flow on $68$ is zero.

Normalize ${\pi }_1=0$. Tree tightness givesThe non-tree reduced costs areThe negative reduced cost on $89$ identifies an improving entering arc for the network simplex algorithm. Adding it to the tree creates a unique undirected cycle. Sending $\theta$ along $8\to 9$ increases the flows on $15,56,68,89$ by $\theta$ and decreases those on $14,43,37,79$ by $\theta$; all other flows are unchanged. This balanced displacement preserves every node equation. Nonnegativity limits $\theta$ to the minimum of the four decreasing flows, namely $2$. Choose arc $14$ to leave among the tied limiting arcs.

After this one pivot the nonzero flows areand every other arc flow is zero. The objective decreases by $\theta r_{89}=-2$, giving cost $18$.

For the new tree, tight potentials normalized at vertex 1 areAll tree reduced costs are zero. For the non-tree arcs $14,46,67,52,28$ they are $1,1,1,2,1$, respectively, so the potentials are dual feasible. Their dual objective ismatching the primal cost. Complementary slackness therefore provesThis is the stopping test of the network simplex method: maintain a feasible tree flow, compute tight potentials, enter a negative-reduced-cost non-tree arc, make a maximal feasible cycle adjustment and exchange a limiting tree arc, until all reduced costs are nonnegative. Here exactly one improving step suffices.

Let $x$ be an extreme point and consider its active constraints. Their row vectors span ${\mathbb{R}}^n$. Otherwise a nonzero vector $h$ is orthogonal to every active row. All inactive inequalities have strictly positive slack; since there are finitely many, a sufficiently small $\epsilon >0$ makes both $x+\epsilon h$ and $x-\epsilon h$ feasible. Their midpoint is $x$, contradicting extremality.

Choose $n$ independent active rows and write the corresponding equalities as $Bx=d$. The matrix $B$ has integer entries, so $\det B$ is a nonzero integer and $|\det B|\ge 1$. By Cramer's rule,where $B_j$ replaces column $j$ by $d$. Every entry of $B_j$ has absolute value at most $U$, even when $b$ is real. The determinant expansion has $n!$ terms, each with absolute value at most $U^n$. ThereforeThis proves the integer-matrix vertex coordinate bound; only the denominator determinant requires integrality.

For an exact finite-input ellipsoid method, the numerical data must have a specified encoding. In the standard model the input is the dimensions, the integer matrix and a rational right-hand side in binary, together with bounds derived from their encoding lengths. The vertex estimate above remains valid for arbitrary real $b$, but arbitrary unencoded reals do not by themselves specify an exact computational decision problem. Clear the rational row denominators to obtain an equivalent integer system, and let $V\ge 1$ bound the resulting integer coefficients and right-hand sides.

Two precautions make a feasibility account valid even for unbounded or lower-dimensional polyhedra. First, nonempty polyhedra need not have extreme points. Nevertheless they have a feasible point in the box $[-R,R{]}^n$ with $R=n!V^n$. To prove this feasible-point box bound for a polyhedron with lines, intersect the polyhedron with an orthant containing one feasible point. Minimize the sum of the signed coordinates in that orthant. Its nonempty sublevel sets are closed and bounded, so the minimum is attained. The compact minimum face has an extreme point, which is also extreme in the orthant intersection. Its active rows come from the integer system and signed coordinate inequalities, still bounded by $V$. Applying the proved vertex estimate gives the box bound. This is an existence argument; the algorithm need not enumerate all orthants.

Second, a nonempty feasible set can have zero ambient volume. Use a small uniform relaxation with a certified rational infeasibility gap, rather than stopping on volume alone. For the integer system $\tilde{A}x\ge \tilde{b}$, putThe normalized integer Farkas infeasibility gap says that if the system is empty there is a multiplier $y\ge 0$ with ${\tilde{A}}^{T}y=0$, $1^{T}y=1$ and ${\tilde{b}}^{T}y\ge 1/D$. Its bound follows by maximizing the certificate's value in the normalized multiplier polytope: a vertex has at most $n+1$ positive entries, and a determinant denominator bounded by $D$. Any point satisfying the relaxed inequalities would then give the contradictionThus relaxation preserves emptiness. If the original system is nonempty, take its point $x_0\in [-R,R{]}^n$. The bounded relaxed setcontains a Euclidean ball around $x_0$ of radius $\rho =\min (1/2,\eta /(nV))$: each row changes by at most $\sqrt{n}V\rho \le \eta$, and the expanded box leaves room for the ball. Hence $Q$ is either empty or has an explicit positive inner-volume bound. This is the full-dimensional relaxation of integer inequalities principle.

Start with a ball, viewed as an ellipsoid, centered at zero with radius $n(R+1)$, which contains the search box. At each iteration test its center against all inequalities defining $Q$. If the center is feasible, the preserved-emptiness result answers that the original problem is nonempty. Otherwise a violated row supplies a separation oracle cut. Move that cut parallel to itself through the current center if necessary, and compute a smaller containing ellipsoid for the surviving half. Every feasible point remains in the new ellipsoid.

The central-cut ellipsoid volume bound gives a shrinkage factor at most $e^{-1/(2(n+1))}$ for $n\ge 2$. After $O(n^2\log (n(R+1)/\rho ))$ cuts, the volume is below that of a radius-$\rho$ ball. If no feasible center has been found, $Q$ and therefore the original system are empty. Dimension one uses interval bisection. The logarithms of $R$, $D$ and $1/\rho$ are polynomial in the encoded input size. Standard outward-controlled finite-precision ellipsoid updates preserve enclosure with polynomial bit complexity.

The coordinate bound therefore supplies the initial bounded search region; the rational gap supplies a valid stopping threshold. Neither unboundedness nor zero volume of the original polyhedron can be ignored when deciding emptiness.

Introduce the nonnegative integer surplus variables $z_1=3x_1+x_2-4$ and $z_2=x_1+2x_2-4$. Solving these two equalities gives the optimal relaxed simplex dictionarywith objectiveThe printed tableau has a sign error in the first row: in equality-row form the coefficient of $z_2$ must be $+1/5$, rather than $-1/5$. The defining constraints and the printed objective row both confirm this correction. The second row, from which the required cut is obtained, is unaffected.

The cutting-plane method solves the linear programming relaxation and, if the optimum is fractional, adds an inequality valid for every feasible integer point but violated by that optimum. For an all-integer tableau rowwrite each coefficient as its integer part plus its fractional part. The quantity $x_B+{\sum }_j\lfloor a_j\rfloor z_j$ is an integer, while ${\sum }_j\{a_j\}{z}_j$ is nonnegative. Thus the integer is at most $\lfloor b\rfloor$, and subtraction gives the Gomory fractional cutIt retains every feasible integer point and cuts off the fractional basic point with all nonbasic $z_j=0$.

Apply this to the row $x_2+\frac{1}{5}{z}_1-\frac{3}{5}{z}_2=\frac{8}{5}$. Since $\{1/5\}=1/5$, $\{-3/5\}=2/5$ and $\{8/5\}=3/5$, the resulting valid inequality isMultiply by five and add an integer slack $w=z_1+2z_2-3\ge 0$. Its row is $w-z_1-2z_2=-3$. At the old relaxed optimum, $w=-3$ is negative, while the minimization objective coefficients $2/5,9/5$ remain nonnegative. This is the starting configuration for the dual simplex algorithm: retain dual feasibility and pivot to repair the negative basic value.

The cut row permits either $z_1$ or $z_2$ to enter. The dual ratio test givesThus $z_1$ enters and $w$ leaves. Solving the cut row and substituting givesSetting the nonbasic variables $z_2=w=0$ gives nonnegative basic values $z_1=3,x_1=2,x_2=1$. The new objective coefficients are nonnegative, so this is optimal for the cut relaxation. Its decision variables are already integer and satisfy the original inequalities. ThereforeIndeed the positive coefficients of both nonbasic variables make this relaxed optimizer unique. No additional cut is needed.

Let $U$ be a unitary operator and suppose initially that the target is an eigenstate $|u⟩$ with $U|u⟩=e^{2\pi i\varphi }|u⟩$, $0\le \varphi <1$. Use $t$ control qubits, so $L=2^t$. Hadamard gates prepare the uniform superposition $L^{-1/2}{\sum }_{a=0}^{L-1}|a⟩$. For each binary control position $j$, apply the controlled unitary gate $U^{2^j}$. The resulting state isApply the inverse quantum Fourier transform, with convention ${\mathrm{QFT}}_L|j⟩=L^{-1/2}{\sum }_a{e}^{2\pi iaj/L}|a⟩$, and measure the control. The exact amplitude and probability areFor an exactly representable phase $\varphi =j_0/L$, orthogonality of roots of unity makes the outcome $j_0$ certain. Otherwise the finite geometric series givesThe estimate is $j/L$, with phases interpreted modulo one.

To prove an error bound, choose a nearest label $j_0$ to $L\varphi$ on the circular grid and put $d=L\varphi -j_0$ in the interval $[-1/2,1/2]$. For $d\ne 0$, concavity of sine on $[0,\pi /2]$ gives $|\sin \pi d|\ge 2|d|$, while $L|\sin (\pi d/L)|\le \pi |d|$. Therefore the nearest-integer success bound for quantum phase estimation isHere $\Vert x{\Vert }_{\mathbb{R}/\mathbb{Z}}={\min }_{k\in \mathbb{Z}}|x-k|$. At an exact grid point the probability is one. If two nearest labels tie, either one separately has the displayed lower bound.

For high confidence one can prove a stronger quantum phase estimation tail bound. Let $d_j$ be the centered distance between $j$ and $L\varphi$, chosen with $|d_j|\le L/2$. The denominator estimate $|\sin (\pi d_j/L)|\ge 2|d_j|/L$ implies $p_j\le 1/(4d_j^2)$ away from the exact-phase case. A label at circular integer distance $\ell$ from $j_0$ has $|d_j|\ge \ell -1/2$, and there are at most two labels at each such distance. For $m\ge 2$, summing the tails givesOn the complementary event the circular phase error is at most $(m-1/2)/L$. Thus, for $b$ desired bits of accuracy, take $t=b+u$ with $u\ge 1$ and $m=2^u$ to obtainTaking $u=\lceil {\log }_2(1+1/(2\epsilon ))\rceil$ makes the right side at most $\epsilon$. This adds only $O(\log (1/\epsilon ))$ control qubits. Efficient QFT is not by itself a guarantee of efficient controlled powers of an arbitrary $U$: implementing them by repeated oracle calls uses $L-1$ calls. The modular-arithmetic application has efficient powers, as follows.

Assume $n>1$ and $\gcd (x,n)=1$, and let $r$ be the multiplicative order of $x$ modulo $n$. Define the unitary operator $U_x|y⟩=|xy\mathrm{mod}n⟩$ on $0\le y<n$, and extend it as the identity on unused computational-basis labels of the binary register. Coprimality makes multiplication a permutation, so this extension really is unitary. The orbit of $|1⟩$ consists of the $r$ distinct states $|x^j\mathrm{mod}n⟩$. Its modular multiplication eigenstates areThe last relation follows by shifting the index $j$ cyclically; orthogonality follows from the finite Fourier sum. We do not need to know $r$ to prepare one of these eigenstates: the readily prepared target obeysRunning quantum phase estimation on this state produces the mixture of the $r$ eigenphase distributions, each with weight $1/r$, because the target eigenstates are orthogonal. Thus it samples a uniformly random phase label $s$ and estimates $s/r$ with the bounds just proved. Equivalently the state before the inverse QFT is $L^{-1/2}{\sum }_a|a⟩|x^a\mathrm{mod}n⟩$, which is obtained by quantum modular exponentiation directly.

The controlled power $U_x^{2^j}$ multiplies by $x^{2^j}\mathrm{mod}n$, whose constant is computed by repeated squaring. Under the assumed efficient modular exponentiation, these controlled multiplications and the QFT use a number of gates polynomial in the register lengths. Taking $L>n^2$ requires only $O(\log n)$ phase qubits. The nearest-label event has probability at least $4/{\pi }^2$ and yields an estimate within $1/(2L)<1/(2r^2)$ of $s/r$. Since $r<n$, continued-fraction recovery in quantum order finding then identifies the reduced fraction $s/r$. The denominator is $r/\gcd (s,r)$, not necessarily $r$: when $s$ and $r$ are coprime it is the desired order, and when they are not it is only a divisor. One may test candidate denominators using modular exponentiation and repeat with fresh samples; denominators from successful samples can also be combined by a least common multiple. The probability of a nearest-label sample with $s$ coprime to $r$ is at least $(4/{\pi }^2)\phi (r)/r$. These qualifications explain exactly what the phase estimate yields without falsely assuming that the unknown order or an eigenstate was available at the start.

A measurement in quantum mechanics with outcomes $m$ is specified, in the single-operator-per-outcome description, by linear operators $M_m$ satisfying ${\sum }_m{M}_m^{†}{M}_m=I$. Its effects $F_m=M_m^{†}{M}_m$ form a positive operator-valued measure. The two measurement postulates are the Born rule for outcomes and the conditional state update:For a density operator the corresponding formulas are $p_m=\mathrm{Tr}(M_m\rho M_m^{†})$ and ${\rho }_m=M_m\rho M_m^{†}/p_m$. More general quantum instruments have multiple operators for each outcome and sum these terms. For a projective measurement of an observable $A={\sum }_m{a}_m{P}_m$, take $M_m=P_m$; the outcome value is $a_m$ and the postmeasurement state lies in its eigenspace. A POVM alone specifies probabilities, whereas the measurement operators or instrument also specify the backaction.

For quantum teleportation, Alice and Bob initially share the Bell pair $|{\Phi }^{+}{⟩}_{AB}=(|00⟩+|11⟩)/\sqrt{2}$. Alice also holds the input $|\psi {⟩}_C=\alpha |0⟩+\beta |1⟩$, with $|\alpha {|}^2+|\beta {|}^2=1$. The shared entanglement is a resource; the two transmitted classical bits alone could not transfer an arbitrary unknown quantum state.

Alice applies a controlled-NOT gate with $C$ as control and $A$ as target, then a Hadamard gate to $C$. Starting from $|\psi {⟩}_C|{\Phi }^{+}{⟩}_{AB}$, direct expansion givesFor example, the four receiver vectors are $\alpha |0⟩+\beta |1⟩$, $\beta |0⟩+\alpha |1⟩$, $\alpha |0⟩-\beta |1⟩$, and $-\beta |0⟩+\alpha |1⟩$. Thus the gate calculation fixes the ordering of the Pauli corrections, including the last branch's sign.

Alice measures $C,A$ in the computational basis, obtaining $(a,b)$. The Born rule gives each outcome probability $1/4$, independent of the input amplitudes. Bob's normalized conditional state is $X^b{Z}^a|\psi ⟩$. Alice sends the two outcome bits. Bob applies the inverse, $Z^a{X}^b$, and henceThe same circuit is a Bell-basis measurement on Alice's two qubits, expressed using ordinary gates followed by computational-basis measurements. It restores the state without Alice or Bob knowing $\alpha ,\beta$.

By linearity, the calculation also holds when the input is entangled with a reference: each outcome has branch map $|\psi ⟩\mapsto X^b{Z}^a|\psi ⟩/2$, and after correction every branch is one-half of the identity map. Summing the four corrected density operators gives exactly the original input density operator, with all reference correlations preserved. This is teleportation as an identity channel on a reference. Without the two classical bits Bob must average the four uncorrected states, giving $\frac{1}{4}{\sum }_{a,b}{X}^b{Z}^a\rho Z^a{X}^b=I/2$, so the process cannot signal before the message arrives. The Bell pair is consumed and Alice retains no copy of the unknown state, in accordance with the no-cloning theorem.

Use logarithms to base two, so all entropies are in bits. For a discrete probability distribution $p$ and a density operator $\rho$ with eigenvalues ${\lambda }_j$, the Shannon entropy and Von Neumann entropy are respectivelyUse $0\log 0=0$. The second definition is basis-independent by the spectral theorem; for a density operator diagonal with probabilities $p_x$, it agrees with the first.

The classical relative entropy, or Kullback-Leibler divergence, of $p$ from $q$ isIt is $+\infty$ if some $p_x>0$ has $q_x=0$. The quantum relative entropy iswhen the support of $\rho$ is contained in that of $\sigma$, and is $+\infty$ otherwise. Matrix logarithms are taken on the corresponding positive supports. In a common eigenbasis this reduces to classical relative entropy; both divergences are nonnegative and are generally asymmetric.

To prove Fano's inequality, let the finite alphabet size be $m\ge 2$ and let $E$ indicate an incorrect guess. Since $E$ is determined by $(X,Y)$, the chain rule for conditional entropy first givesExpanding in the opposite order givesConditioning reduces entropy, so $H(E\mid Y)\le H(E)=h_2(p_e)$, the binary entropy function. When $E=0$, knowledge of $Y$ determines $X=f(Y)$ and the conditional entropy is zero. When $E=1$, $X$ can lie in at most the $m-1$ alphabet values other than $f(Y)$. Entropy on $m-1$ values is at most ${\log }_2(m-1)$: its deficit from that number is the nonnegative relative entropy from the uniform distribution. Averaging the two cases therefore givesCombining the two expansions provesThis proof of Fano's inequality via an error indicator works for any alphabet-valued guessing rule, not just an optimal one. If $m=1$, there is no guessing uncertainty and the claim is simply $H(X\mid Y)=0$; that case is treated separately rather than writing $\log 0$.

For an $n$-qubit quantum code with projector $P$, the quantum code distance isHere the weight counts nonidentity tensor factors. Thus every error supported on fewer than $d$ qubits is detectable, by the Pauli expansion of a quantum error. A scalar action on the code, including a nonidentity stabilizer, is harmless and does not reduce this distance. For a stabilizer code, the equivalent definition minimizes weight among Pauli operators which commute with every stabilizer generator but act nontrivially on the logical information. The Knill--Laflamme condition then guarantees correction of all errors of weight at most $t=\lfloor (d-1)/2\rfloor$, since each pairwise product has weight at most $2t<d$.

Suppose the code encodes $k$ logical qubits and is nondegenerate for all errors through weight $t$. There aredistinct Pauli errors modulo phase: choose the $j$ affected positions and choose $X,Y$ or $Z$ at each. Each error is unitary, so its image of the code has dimension $2^k$. Nondegeneracy makes these images mutually orthogonal, equivalently the combined vectors $E_a|i_L⟩$ are orthonormal. They all lie in the physical Hilbert space of dimension $2^n$. Counting dimensions proves the quantum Hamming boundThis dimension argument requires nondegeneracy. For a degenerate code, different errors can share an image, as in the Shor code, and this counting proof cannot be applied unchanged.

For a binary classical code of $M$ words, the Hamming bound is $M{\sum }_{j=0}^t\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le 2^n$: disjoint Hamming balls around the words must fit into all binary strings. The quantum factor $3^j$ is needed because at each erroneous qubit there are three linearly independent nonidentity Pauli operators, not just a classical bit flip. A phase flip is invisible to a computational-basis classical record but changes a quantum superposition. A $Y$ error combines bit and phase effects, and the identity with $X,Y,Z$ spans every one-qubit operator. Quantum correction must protect amplitudes and coherences, and consequently count whole orthogonal logical subspaces rather than just classical words.

For parameters $[[5,1,3]]$, $t=1$, andThus a nondegenerate such code saturates the bound: the sixteen two-dimensional error images exhaust the physical space. It is a perfect quantum error-correcting code for single-qubit errors. It also has the smallest possible length for nondegenerate single-error protection of one logical qubit: for $1\le n\le 4$, the required inequality $1+3n\le 2^{n-1}$ fails.

Here is an explicit realization and its five-qubit stabilizer syndrome table. Write tensor products without multiplication symbols and useEach pair has an even number of anticommuting single-site factors, so the four stabilizer generators commute. Their binary Pauli labels are independent: no nonempty product has identity label. For example, the $X$-support at site three fixes the exponent of $g_3$ in such a product to zero, site five then fixes that of $g_2$, site one fixes that of $g_1$, and site two fixes that of $g_4$. Thus their group has sixteen elements and excludes $-I$. The common $+1$ eigenspace has projector $P={\prod }_{a=1}^4(I+g_a)/16$ and dimension $\mathrm{Tr}P=32/16=2$, since all nonidentity Pauli strings have zero trace.

Record a syndrome bit as one when an error anticommutes with the corresponding generator, in order $g_1,g_2,g_3,g_4$. Direct local commutation givesThese are all fifteen nonzero four-bit error syndromes; the identity has $0000$. Distinct errors in this list have a product with nonzero syndrome, so it anticommutes with some $g_a$. Inserting $g_{a}P=P$ on both sides gives $P{E}_b^{†}{E}_{c}P=-P{E}_b^{†}{E}_{c}P=0$. The diagonal product is the identity. Hence the Knill--Laflamme condition is exactly $C_{bc}={\delta }_{bc}$, proving nondegenerate correction. Measure the four commuting checks, apply the unique indicated Pauli error again, and every logical state is recovered. The Pauli expansion of a quantum error extends this recovery to an arbitrary one-qubit noise channel, not just the fifteen discrete errors.

The table also proves that every Pauli operator of weight one or two has nonzero syndrome: a weight-two operator is the product of distinct single-site errors, whose syndromes differ. Therefore the distance is at least three. The operators $\overline{X}=X^{\otimes 5}$ and $\overline{Z}=Z^{\otimes 5}$ commute with all four generators and anticommute with each other. They are nontrivial logical Pauli operators. Multiplication of $\overline{X}$ by $g_1$ gives $-IYYIX$, a weight-three operator with the same logical action; it cannot be scalar on the code because it anticommutes with the invertible logical operator $\overline{Z}$. This proves $d=3$ exactly.

The code consequently detects every two-qubit error and corrects two known-location erasures by the quantum erasure correction criterion, but it cannot correct all two-qubit errors of unknown location. A nontrivial weight-three logical operator can be split into a weight-one and a weight-two error, whose pairwise product violates the correction condition. It also saturates the quantum Singleton bound, since $n-k=4=2(d-1)$. These properties distinguish single-error perfectness from unrestricted protection against larger errors.

A credit derivative separates an exposure to a borrower's credit quality from outright ownership of its loan or bond. In the early-2002 setting, these were a growing, largely dealer-intermediated over-the-counter market. For scale, the contemporaneous BIS comparison reports ISDA member positions of about US$919billionatend-2001,versusUS$632 billion at mid-2001. These are notional amounts, not market values or expected losses, and the survey did not eliminate double-counting; estimates from other surveys cannot simply be combined because their coverage differed. This historical description uses the BIS Quarterly Review, June 2002, derivatives-market comparison, rather than projecting later market totals back into the paper's date.

The basic unfunded contract is a credit default swap. The protection buyer pays a periodic spread until maturity or a defined credit event; the seller pays the contracted default loss, often notional times one minus recovery. Physical settlement instead delivers eligible defaulted debt in exchange for par. A total return swap exchanges the reference asset's coupons and price changes against a funding leg: its receiver earns gains, bears price losses and pays funding, obtaining broader market and credit exposure than default protection alone. A credit spread option pays on widening or narrowing of a quoted credit spread, transferring mark-to-market credit risk even without a default. A credit-linked note is funded: the investor supplies principal and accepts a reduction of coupons or principal after a reference credit event, in return for enhanced yield. The investor is economically selling protection and can also face the note issuer's own credit risk.

Basket products extend these ideas. A first-to-default swap pays when the first member of a reference basket defaults. A synthetic CDO uses credit default swaps to create portfolio credit exposure and allocates aggregate losses among tranches. For monetary portfolio loss $L$ and attachment/exhaustion amounts $A<D$, the credit tranche loss function is $\min ((L-A{)}^{+},D-A)$. These contracts require a model of joint defaults and recoveries, not just a list of individual default probabilities. The separation of credit exposure from financing and the role of synthetic structures were already central to the Federal Reserve's December 2001 discussion of credit derivatives.

For risk management, a bank can buy protection on a concentrated borrower exposure while retaining the loan and customer relationship. It can transfer sectors or names it already holds heavily and diversify the remaining portfolio. Recognition of a hedge for capital purposes depends on the actual transfer and applicable rules, not merely on the instrument's name. Investors can instead sell protection or buy credit-linked notes to obtain chosen credit exposure without buying the cash bond, seek a risk premium, or take relative-value positions between cash bonds and swaps. Such positions still depend on funding and on the credit-spread basis: contractual events, maturity, currency and recovery terms may fail to match the original exposure. Protection also replaces part of the reference risk with counterparty credit risk, particularly if the seller may fail when the protected borrower is distressed.

Pricing equates expected discounted contractual cash flows under a risk-neutral measure, calibrated to traded bonds and derivatives rather than substituting historical default frequencies. To make this concrete, suppose the risk-neutral default intensity $\lambda (u)$ and discount factor $B(0,u)$ are deterministic, fractional recovery $\mathcal{R}$ is fixed, and premiums are continuous. Survival is $G(u)=\exp (-{\int }_0^u\lambda (v)dv)$. A notional-$N$ protection leg pays $N(1-\mathcal{R})$ at default, so its value is $N(1-\mathcal{R}){\int }_0^{T}B(0,u)\lambda (u)G(u)du$. Premium at annual rate $s$ has value $Ns{\int }_0^{T}B(0,u)G(u)du$. A zero-upfront par swap therefore has the continuous-premium credit-default swap spreadFor constant intensity this reduces exactly to $s=(1-\mathcal{R})\lambda$ in this simplified model. Actual discrete premium dates and premium accrued at default change the premium leg; stochastic recovery, discounting and counterparty losses change the expectations. A quoted spread thus cannot universally be read as a physical default probability. Default-risk premiums and other market effects enter the calibrated pricing measure.

A structural alternative is the Merton model. If firm assets at debt maturity are $V_T$ and promised debt is $F$, equity pays $(V_T-F{)}^{+}$ and debt pays $\min (V_T,F)=F-(F-V_T{)}^{+}$. Under the model's diffusion assumptions, debt value is consequently the discounted face value less a put on firm assets. This derives credit prices from asset value, volatility and capital structure, while the simple model allows default only at the debt maturity. Intensity models instead calibrate a default-arrival law directly to market credit prices. Neither approach removes model risk in recovery, dependence or calibration, and incomplete credit markets need not select a unique pricing measure. A useful credit hedge and a fair derivative price both depend on the actual cash-flow and default specifications, not the product label alone.