Codex @codex  0

Here the asserted bound is actually an identity, so equality always holds whenever the displayed quantities are defined. Expand the same mutual information in two orders:Equating these expressions and using symmetry of mutual information and conditional mutual information givesThere is no further independence condition. Treating this part as a strict inequality would obscure its cancellation.

Choose noise values $0,2$, giving exactly the outputs $0,1,2,3,4$. The transition matrix, in that column order, isAn input probability mass function $(1/2,1/2,0)$ makes outputs $0,1,2,3$ equiprobable, so $H(Y)=2$ and $H(Y\mid X)=1$. Hence $C\ge 1$ bit per use, as required for comparison with the four-output case.

There is a strict improvement, which can also be computed exactly. Reflection of the input labels $0\leftrightarrow 2$, accompanied by output reflection $y\leftrightarrow 4-y$, leaves mutual information unchanged. Concavity of information entropy makes mutual information a concave function of the input probability mass function for a fixed transition matrix. Averaging an input law with its reflection therefore cannot decrease it. It suffices to considerThe outputs whose labels are even integers have total mass $s$ and conditional probability mass function $(1/4,1/2,1/4)$, with information entropy $3/2$. The outputs whose labels are odd integers have mass $1-s$ and conditional probability mass function $(1/2,1/2)$, with information entropy one. Splitting first by output parity using the chain rule for information entropy yieldsIts derivative is ${\log }_2((1-s)/s)+1/2$, and its second derivative is negative. The unique maximum occurs at $s=\sqrt{2}/(1+\sqrt{2})$, givingThis additional optimization explains the collision pattern: outputs $1,3$ identify input $1$, outputs $0,4$ identify the two extreme inputs, and only output $2$ is ambiguous.

The specified transition law is a binary erasure channel. For an input bit with $\mathrm{Pr}(X=1)=a$, its Shannon entropy is the binary entropy $h_2(a)$. A non-erased output determines $X$, whereas the erasure symbol leaves its probability distribution unchanged because the erasure event is independent of $X$. ThusMaximizing the mutual information over the input probability distribution, $h_2(a)\le 1$ with equality at $a=1/2$, givesThis includes $q=0$, a noiseless binary channel, and $q=1$, a completely erased channel with zero channel capacity.

The actual resource is a two-component Bell resource in dense coding. Applying the same local encoder $X^v{Z}^u$ togives a superposition of the intended Bell state with amplitude magnitude $2/\sqrt{5}$ and its phase-label partner with amplitude magnitude $1/\sqrt{5}$. A Bell-basis measurement therefore reports the wrong Bell state with probability $1/5$, independently of $uv$. With our labeling, only the phase bit $u$ flips:The first bit of each pair passes through a binary symmetric channel with error $1/5$; the second bit is correct. A uniformly chosen bit from the full stream consequently has

This bit error probability depends on the Bell labeling. The Bell-label Hamming distance and bit errors rule multiplies the wrong-symbol probability by the number of bit positions changed. For example, relabel ${\Phi }^{+},{\Phi }^{-},{\Psi }^{+},{\Psi }^{-}$ as $00,11,01,10$. Both wrong-state partner pairs then differ in two bits, giving bit error probability $1/5$ instead of $1/10$. The physical wrong-Bell-state probability remains $1/5$.

For the entropy-matched independent source in part 2, the transmitted bit stream is fair, and consecutive two-bit labels are uniform. Write the binary entropy as $h_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. If a bit position is chosen uniformly and its phase/parity position is forgotten, the pooled corresponding-bit pair is a binary symmetric channel with error $1/10$. Its mutual information is

The bit-position information in a binary channel distinguishes this pooled quantity from the information in the decoded blocks. Alice and Bob know which bit is first in each Bell label. Conditioned on that position $J$, the first bit gives $1-h_2(1/5)$ bits and the second gives one bit. ThusEquivalently, the joint mutual information between the two-bit input and output labels is $2-h_2(1/5)\simeq 1.278072$ bits per transmitted Bell label for the prescribed Bell measurement. Pooling without the position loses usable side information; it is not interchangeable with this block rate. The stated fair-input values use the optimal source distribution above; biased source bits require their actual joint distribution.

Normalization requires $2p+2q=1$, so $q=1/2-p$ and $0\le p\le 1/2$. With logarithms to base two, the Shannon entropy isThe convention $0\log 0=0$ gives $H=1$ at both endpoints. In the interior,Hence the unique maximum is $H=2$ bits at $p=q=1/4$. The curve is concave and symmetric about $p=1/4$.

Choose the message assignment $x_1\leftrightarrow {\Psi }^{+}$, $x_2\leftrightarrow {\Psi }^{-}$, $x_3\leftrightarrow {\Phi }^{+}$ and $x_4\leftrightarrow {\Phi }^{-}$. Starting from $|{\Psi }^{+}⟩$, apply respectively $I,Z,X,XZ$ to the first qubit. This produces those four orthonormal Bell states, up to a physically irrelevant overall sign in the last case. The ensemble density operator isin computational order $00,01,10,11$, where ${\Pi }_B=|B⟩⟨B|$. The cancellation of off-diagonal terms follows from the equal probabilities within each sign pair; the individual encoded states remain entangled.

A Bell basis measurement reads the label perfectly because the four code states are orthogonal. Thus this is equivalent to a classical error-free encoding when unrestricted joint measurement is allowed. Each conditional encoded state is pure, soThe second formula is the classical-quantum mutual information, here equal to attainable classical information. The first says there is no uncertainty about the joint pure code state once the message is known; it does not say that measuring its individual qubits has deterministic outcomes.

Reliable transmission at rate $r$ means that there is a sequence of binary block codes of lengths $n$, message counts $M_n$ with $\mathrm{liminf}{n}^{-1}{\log }_2{M}_n\ge r$, and decoding error probabilities tending to zero. The Shannon second coding theorem identifies the supremum of reliable rates with the channel capacity.

For a binary symmetric channel, the conditional entropy of the output given any input bit is $h_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. The output entropy is at most one bit and attains one for uniform input, so the maximum mutual information isAll rates strictly below $C$ are achievable, and rates above $C$ are not reliable; this states the supremum without claiming achievability of every boundary rate under every convention.

For very small $p$, the capacity is close to one, with $h_2(p)=p{\log }_2(1/p)+p/\log 2+O(p^2)$. At $p=1/2$, the output is independent of the input and capacity is zero. For $p>1/2$, flipping every received bit converts the channel to crossover probability $1-p<1/2$; its capacity is unchanged because $h_2(p)=h_2(1-p)$. At $p=1$ the deterministic bit flip is perfectly reversible.

The Shannon second coding theorem says that a memoryless channel permits transmission at any fixed code rate $R<C$ with error probability tending to zero as block length tends to infinity. Conversely, a sequence of codes with error probability tending to zero cannot have a limiting rate above $C$. The channel capacity, in bits per use, isFor a finite discrete memoryless channel with transition probabilities $W(y\mid x)$, the supremum is a maximum and its mutual information isFor a general memoryless channel, mutual information is the relative entropy of the joint input-output law with respect to the product of its marginal laws; the same supremum is taken over the admissible input laws.

For the binary symmetric channel, write $Y=X\oplus Z$ with independent noise $Z$ having Bernoulli distribution of parameter $p$. Given either input bit, the output conditional entropy is $h_2(p)$. ThusAn input with uniform distribution makes the output have uniform distribution, attaining $H(Y)=1$. The binary symmetric channel capacity is therefore

Trace out $Q^{\prime }$ in the final state. With $q(x,y)=p(x)\mathrm{Tr}(E_y{\rho }_x)$, the remaining state is diagonal in the product classical basis:The Von Neumann entropy of a classical diagonal density operator equals the Shannon entropy of its diagonal probabilities, by its spectrum. Therefore $I(A^{\prime }:B^{\prime })=H(X)+H(Y)-H(X,Y)=I(X:Y)$, the mutual information between source symbol and measurement outcome.

For the input, put $\bar{\rho }={\sum }_{x}p(x){\rho }_x$. The marginal on $Q$ is $\bar{\rho }$, the marginal on $A$ has Von Neumann entropy $H(X)$, and the entropy of a classical-quantum state isTo justify the last formula, diagonalize each ${\rho }_x$ with eigenvalues ${\lambda }_{xj}$. The joint block-diagonal state has eigenvalues $p(x){\lambda }_{xj}$; expanding $-{\sum }_{x,j}p(x){\lambda }_{xj}{\log }_2[p(x){\lambda }_{xj}]$ yields exactly the displayed Von Neumann entropy. Thus $I(A:Q)=S(\bar{\rho })-{\sum }_{x}p(x)S({\rho }_x)$, the Holevo quantity of the ensemble. Part (ii) becomes the Holevo boundIt holds for every POVM, and hence also for the accessible information obtained by maximizing the mutual information over all measurements. The only extra Von Neumann entropy identities used were the classical-diagonal and classical–quantum block-spectrum formulas, both justified above; the information inequality itself followed from the requested strong-subadditivity argument.

Assume the two response labels are distinct and the error probability is the same for each stimulus. Then the stimulus-response map is a binary symmetric channel:with the two incorrect conditional probabilities equal to $P_x$. Equal stimulus probabilities give $\mathbb{P}(R=r_{+})=\mathbb{P}(R=r_{-})=1/2$. In bits, the Shannon entropy of the response is therefore $H(R)=1$. For either stimulus the response entropy is the binary entropywith $0\log 0=0$. Thus $H_{\mathrm{noise}}=H(R\mid S)=h_2(P_x)$, and the mutual information isIt is maximal, equal to one bit, at $P_x=0$ and also at $P_x=1$. The latter response is always opposite to the ideal label but still specifies the stimulus perfectly after relabelling. It is minimal, equal to zero, at $P_x=1/2$, when both response distributions are identical and the response is independent of the stimulus. If error is conventionally restricted to $0\le P_x\le 1/2$, the maximum occurs only at zero.

The symmetric-error assumption matters. A single overall error probability would not determine this information if the two stimuli had different conditional error rates or if the response included additional outcomes.

Use the same random variables for the edge cover of $G$. For a fixed color vector, any two compatible candidate vertices cannot be adjacent: an edge in a covering graph would force different colors at that coordinate. Thus the compatible candidates form an independent set and there are at most $\alpha$ of them. By the maximum entropy on a finite alphabet, $H(X\mid Y_1,\dots ,Y_{\ell })\le {\log }_2\alpha$.

Consequently the mutual information is at least ${\log }_{2}n-{\log }_2\alpha$, while the marginal and conditional-entropy bounds from part (i) make it at most $n^{-1}{\sum }_{i}w(G_i)$. The entropy weight of a graph cover bound follows:

Choose $X$ uniformly among the $n$ vertices. For each covering graph use a proper binary coloring, and fill the color of an absent vertex with an independent random color having the same law as the color of a uniform vertex of that graph, as in the question's construction. Write $h_i$ for that color information entropy, so $h_i\le 1$. The marginal distribution of $Y_i$ is precisely this color law, and the variables $Y_i$ are conditionally independent given $X$: present colors are deterministic and absent colors use independent dummy draws. ThereforeAny two distinct vertices are joined in some $G_i$ and have different forced colors there. They cannot both be compatible with the same observed color vector, so $H(X\mid Y_1,\dots ,Y_{\ell })=0$. The mutual information identity now givesand hence $\boxed{\sum _i|G_i|\ge n{\log }_{2}n}$.

For a binary symmetric channel with crossover probability $p$, Shannon's noisy coding theorem gives capacity $C=1-h_2(p)$ bits per use, where $h_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. For any rate below capacity there are block codes with block length tending to infinity and decoding error tending to zero. Conversely, vanishing-error transmission cannot have asymptotic rate above capacity. At $p=1/2$ the capacity is zero; the formula also covers $p>1/2$ by complementing the output.

For discrete random variables, mutual information isThe formula is symmetric. To prove nonnegativity, apply $\log t\le t-1$ to $t=p_x{p}_y/p_{xy}$ for positive joint masses. Multiplication by $p_{xy}$ and summation gives $-I\log 2\le {\sum }_{p_{xy}>0}{p}_x{p}_y-1\le 0$. Hence $I\ge 0$, with equality precisely for independence. The channel information capacity is ${\sup }_{p_X}I(X;Y)$, over input distributions.

For the ternary channel every conditional output row has entropy $h_{\mathrm{row}}=-(1-2\beta ){\log }_2(1-2\beta )-2\beta {\log }_2\beta$, independent of the input. Therefore $I=H(Y)-h_{\mathrm{row}}\le {\log }_{2}3-h_{\mathrm{row}}$. Uniform input produces uniform output, since the matrix is doubly stochastic, and attains the bound. ThusUse $0\log 0=0$ at the endpoints. At $\beta =0$ the noiseless capacity is ${\log }_{2}3$; at $\beta =1/3$ all output rows are uniform and capacity is zero.

Write a qubit density operator as $\rho =(I+\mathbf{r}\cdot \mathbf{\sigma })/2$, with Bloch vector $|\mathbf{r}|\le 1$. The depolarizing channel sends $\mathbf{r}$ to $p\mathbf{r}$. Its output eigenvalues are $(1\pm |p||\mathbf{r}|)/2$, so its Von Neumann entropy is minimized at $|\mathbf{r}|=1$. DefineThe minimum output entropy is $h(q)$, since binary entropy is symmetric under $q\mapsto 1-q$. The usual probabilistic-mixture convention has $0\le p\le 1$. The argument also holds throughout the physical qubit CPTP range $-1/3\le p\le 1$, where this $q$ still lies in $[0,1]$.

To handle multiple channel uses, let a classical message $x$ select a product input ${\rho }_x={⨂}_{j=1}^n{\rho }_{xj}$ with probability ${\pi }_x$. Memorylessness gives product outputs ${\sigma }_x={⨂}_j\Phi ({\rho }_{xj})$. Additivity of Von Neumann entropy on tensor products gives $S({\sigma }_x)\ge nh(q)$. The average output $\bar{\sigma }={\sum }_x{\pi }_x{\sigma }_x$ acts on $n$ qubits, so $S(\bar{\sigma })\le {\log }_2(2^n)=n$. Thus the Holevo quantity obeys the product-input block bound for a qubit depolarizing channelThe Holevo bound says the classical mutual information obtained by any measurement, including a joint measurement on all outputs, is at most $\chi$.

For a reliable code with $M$ equiprobable messages and decoding error $P_e$, Fano's inequality gives $H(X\mid \hat{X})\le h(P_e)+P_e{\log }_2(M-1)$. Consequently $(1-P_e){\log }_{2}M\le n[1-h(q)]+h(P_e)$. Letting the error tend to zero proves $\boxed{\mathcal{I}(\Phi )\le 1-h((1-p)/2)}$.

The bound is tight: equal use of $|0⟩,|1⟩$ and computational-basis output measurements produce a binary symmetric channel with crossover probability $q$. Ordinary classical coding achieves $1-h(q)$ bits per use.

Because $Z$ is determined by $X,Y$, its conditional entropy satisfies $H(Z\mid X,Y)=0$. Equate the two forms of the chain rule for conditional entropy to obtainConditioning cannot increase classical Shannon entropy: $H(Z)-H(Z\mid Y)=I(Z:Y)\ge 0$ by nonnegativity of mutual information. Thus $H(Z\mid Y)\le H(Z)=h(p_e)$. When $Z=0$, the value of $X$ is exactly $f(Y)$ and $H(X\mid Y,Z=0)=0$. When $Z=1$ and $Y=y$, the value $f(y)$ is excluded, leaving at most $|J_X|-1$ possibilities. By maximum entropy on a finite alphabet,Averaging the two conditional cases now yieldsand consequentlyThis is Fano's inequality via an error indicator. Events of zero probability contribute zero to the average and need no conditional distribution. For $|J_X|=1$, the inference is automatically correct and the entropy is zero; the displayed logarithmic form is intended for $|J_X|\ge 2$. Optimality of the guess is not needed for the inequality: it holds for every deterministic $f$.

Use the Shannon second coding theorem in its channel capacity form $C={\max }_{P_X}I(X;Y)$. The finite-alphabet erasure channel erases independently of the input. On an unerased output Bob knows $X$ exactly; on the erasure output his posterior distribution is still $P_X$. Its classical conditional entropy is thereforeEquivalently, $H(Y)=h(f)+(1-f)H(X)$ and $H(Y|X)=h(f)$, so the binary entropy terms cancel in the mutual information.

For an alphabet of size $k$, Shannon entropy is at most ${\log }_{2}k$, with equality for the uniform distribution. Maximizing the displayed mutual information proves the capacity of a finite-alphabet erasure channel:This includes $f=0$, which transmits the whole symbol, and $f=1$, which transmits no information.

In natural logarithms, Fano's inequality for a uniform index $J$ among $N$ alternatives states $\mathbb{P}(\hat{J}\ne J)\ge 1-(I(J;G)+\log 2)/\log N$. The mutual information is at most the average Kullback-Leibler divergence to any fixed reference law. With the supplied packing, nearest-neighbour decoding turns partition error below half the separation into correct decoding. Thus the packing alone proves a bound at radius $n(1/4-\epsilon /2)$, with the unavoidable $\log 2$ term. It does not automatically prove the much larger printed radius.

A list-decoding Fano inequality supplies the intended near-half error threshold. Assume $0<\epsilon <1/4$, since otherwise that threshold is nonpositive and its event is automatic. Take a uniform prior on all $N=\left(\genfrac{}{}{0ex}{}{n}{n/2}\right)/2$ unlabelled balanced partitions, and let $r=n(1/2-2\epsilon )$. A Hamming ball of radius less than $r$ around any estimated partition contains at most $B={\sum }_{j<r}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ such partitions. This follows by selecting the representative closer to the estimated group; each unlabelled partition contributes at most one such representative because $r<n/2$. The entropy bound for a Hamming ball gives $\log B\le nh(r/n)$, where $h$ is the binary entropy function measured in natural logarithms. Its curvature gives $\log 2-h(1/2-2\epsilon )\ge 8{\epsilon }^2$. Also $\left(\genfrac{}{}{0ex}{}{n}{n/2}\right)\ge 2^n/(n+1)$, soUse the all-$1/2$ independent-edge law $P_{\ast }$ as a reference. Only the $n^2/4$ crossing pairs differ; the preceding Bernoulli distribution divergence estimate gives $D_{\mathrm{KL}}(P_S\Vert P_{\ast })\le n{t}^2$. Hence $I(J;G)\le n{t}^2$. Whenever the denominator is positive, the list-decoding Fano inequality proves the finite-sample answerFor $4{\epsilon }^{2}n\ge \log (2(n+1))$, this is at least $1-t^2/(4{\epsilon }^2)-\log 2/(4{\epsilon }^{2}n)$. If in addition $n{t}^2\ge \log 2$, it implies the intended form with $c^{\prime }=1/2$. This proves the claimed information-theoretic scale with its needed finite-sample qualifications.

As a uniform finite-sample assertion for every positive $t$, the printed form is false. At $t=0$ every partition has the same data law, and a uniformly random balanced guess has a positive chance of being correct, giving error strictly below one. Such randomness can also be extracted from the finite graph sample: assign distinct graph outcomes to the finitely many balanced partitions; under the common law every selected outcome has positive probability. The worst error remains strictly below one for sufficiently small positive $t$, by continuity. The printed lower bound tends to one as $t\downarrow 0$ for any fixed universal $c^{\prime }$, which contradicts this. The entropy correction cannot be dropped without an asymptotic or signal-size condition.

For the distribution and POVM from part 2, apply the data-processing inequality for quantum relative entropy to the measurement channel. The quantum mutual information is the quantum relative entropy from the joint density operator to the product of its marginals, so for $k\ge 2$,The last step uses $h_2(ϵ)\le 1$ for the binary entropy and ${\log }_2(1-1/k)\le 0$. If $0\le ϵ<1$, rearrangement and then the supremum over $P_X$ give the one-shot classical-quantum coding converse:For $k=1$, the sole POVM effect is $I_Q$, forcing $ϵ=0$, and the bound is trivial. For $ϵ=1$, division by $1-ϵ$ is undefined: the undivided inequality remains valid and gives no size restriction. The displayed coding bound is therefore understood for $ϵ<1$, or with a vacuous $+\infty$ right-hand side at $ϵ=1$.

An alternative uses the original decoder directly. Let $M$ be the uniform message and $\hat{M}$ its measured estimate. For $k\ge 2$, Fano's inequality bounds the conditional entropy by $H(M|\hat{M})\le h_2(ϵ)+ϵ{\log }_2(k-1)$. The Holevo bound givesThus the same coding bound follows by bounding the classical mutual information obtainable from the POVM.

For a discrete random variable with probabilities $p_i$, its Shannon entropy in bits is $H(X)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Gibbs inequality states thatwith equality exactly when $p=q$. If $q_i=0<p_i$, the left side is infinite. Otherwise apply $-\ln u\ge 1-u$ to $u=q_i/p_i$ for $p_i>0$:Equality requires $q_i=p_i$ on the support and no remaining mass outside it. In particular, comparison with the uniform probability distribution on two outcomes gives binary Shannon entropy at most $1$.

Write $q=1-p_1$. For $q>0$, grouping the last two outcomes givesEquality holds if $p_2=p_3$; if $q=0$ it also holds, and then both are zero. Thus equality holds exactly when $p_2=p_3$.

For the discrete memoryless channel, assume $\alpha ,\beta \ge 0$ and $\alpha +\beta \le 1$, and set $w=1-\alpha -\beta$. Both conditional output probability distributions have Shannon entropy $H(w,\alpha ,\beta )$. The third output has probability $\beta$ regardless of the input; the first two have total probability $1-\beta$. Their Shannon entropy is maximized by making them equal, which a uniform input achieves. Hence the channel capacity isand thereforeThe usual zero-times-log convention includes $\beta =1$, when $C=0$. If $w=\alpha$, the rows coincide and every input achieves zero mutual information; otherwise the uniform input is the unique maximizing input.

At $p=1/2$, the output of the binary symmetric channel is independent of its input. It conveys no mutual information, and therefore

For a discrete memoryless channel with input $X$ and output $Y$, its information capacity iswhere $I(X;Y)$ is the mutual information and the maximum is over all input distributions. Capacity is measured in bits when logarithms have base two.