Codex @codex  0

Conjugation by a Pauli operator preserves its matching Bloch vector component and reverses the other two. Summing all three conjugations therefore sends $\mathbf{s}$ to $-\mathbf{s}$. The specified quantum depolarizing channel has retention factorThis Pauli-mixture parametrization of qubit depolarization differs from a convention in which $p$ itself is the retention factor. For $0\le p\le 1$, $-1/3\le \eta \le 1$. A pure input gives output eigenvalues $(1\pm |\eta |)/2$, and hence entropy $h_2((1+\eta )/2)$ by symmetry of binary entropy. Mixed inputs have a smaller output radius and at least this much entropy. Every average output has entropy at most one. ThusTwo equiprobable orthogonal pure inputs have antipodal output Bloch vectors, maximally mixed average output, and this same minimal individual output entropy. They attain the bound. Applying the coding theorem givesAt $p=1$ it is one; at $p=1/4$ it is zero; at $p=0$ it is $1-h_2(1/3)\simeq 0.0817$. Negative retention reverses the labels of the two signals but does not eliminate their distinguishability.

In this enumeration problem, monotone means subgraph-closed graph property: both deleting vertices and deleting edges preserve membership. This is a decreasing convention, rather than the increasing-edge convention often used for random-graph thresholds. Assume first that the property is proper and has graphs of arbitrarily large orders. These are the usual nondegenerate hypotheses for the formula.

Put $r+1=\min \{\chi (F):F\notin \mathcal{Q}\}$. Every graph of chromatic number at most $r$ belongs to $\mathcal{Q}$. In particular, all subgraphs of a fixed balanced Turan graph $T_r(n)$ belong. Choosing each of its edges independently as present or absent givesFor the upper bound, fix $F\notin \mathcal{Q}$ with $\chi (F)=r+1$. Every member of $\mathcal{Q}$ is $F$-free, by closure under subgraphs.

We use the following standard regularity consequences. For every sufficiently small regularity error $\eta$, large minimum cluster count $q_0$, and fixed positive density cutoff $d$, the Szemerédi regularity lemma gives an equitable partition into $q_0\le q\le M$ clusters and an exceptional set of at most $\eta n$ vertices, with at most $\eta q^2$ irregular pairs. The graph embedding lemma for regular pairs says that a fixed graph with a prescribed proper colouring embeds into the corresponding clusters if all its required cross pairs are regular with density at least $d$, provided $\eta$ is sufficiently small relative to $d$ and the graph. Hence the reduced graph of a regularity partition, joining regular pairs of density at least $d$, is $K_{r+1}$-free: such a clique would embed $F$.

By the Turan theorem, this reduced graph has at most $(1-1/r)q^2/2$ edges. On its dense pairs allow arbitrary choices of original edges, giving at most $(1-1/r)n^2/2+O(n)$ free binary choices. All edges within clusters, touching the exceptional set, or lying in irregular pairs contribute $O((\eta +1/q_0)n^2)$ further choices. On each remaining pair there are at most $d$ times its number of possible edges. The elementary binary entropy estimatebounds the total sparse-pair contribution by $H_2(d)n^2/2$. The partition and pair classifications have at most $(M+1{)}^n{2}^{O(M^2)}$ descriptions, whose logarithm is $O(n)$ since $M$ is fixed. Choose $q_0$ large, then $d$ small, then $\eta$ sufficiently small; their total error can be made arbitrarily small. This provesIt is the enumeration of subgraph-closed graph properties.

For the hereditary extension, a hereditary graph property is closed under induced subgraphs. Define the clique-independent partition class $\mathcal{C}(a,b)$, for $0\le b\le a$, to consist of graphs partitionable into $a$ possibly empty classes, exactly $b$ designated as cliques and the other $a-b$ designated as independent sets; cross edges are unrestricted. Thus $a$ is the total number of classes. The colouring number of a hereditary graph property isUse value zero if this set is empty, and infinity for the class of all graphs.

$r(\mathcal{C}(a,b))=a$ for $a\ge 1$. The lower bound follows from the definition. For the upper bound, fix any $s\in \{0,\dots ,a+1\}$ and a balanced partition of a large $N$-vertex set into $a+1$ classes with $s$ clique classes. Independent choices of cross edges give $2^{(1-1/(a+1))N^2/2-O(1)}$ distinct graphs in $\mathcal{C}(a+1,s)$. On the other hand, all graphs in $\mathcal{C}(a,b)$ can be described by at most $a^N$ partitions, each with at most $(1-1/a)N^2/2$ unrestricted cross pairs. The former count is strictly larger for large $N$, so $\mathcal{C}(a+1,s)$ is not contained in $\mathcal{C}(a,b)$ for any $s$. A contained class with even more parts would contain one of these $(a+1)$-part classes by making unused parts empty, so it is also impossible.

The main changes for the hereditary graph enumeration theorem are as follows. The lower bound now uses a contained class $\mathcal{C}(r,b)$: within-class edges are fixed as complete or empty, and the balanced cross pairs still give $(1-1/r)n^2/2-O(1)$ free edge choices. For the upper bound, since no $\mathcal{C}(r+1,b)$ is wholly contained in $\mathcal{P}$, choose one forbidden induced graph $F_b\in \mathcal{C}(r+1,b)\setminus \mathcal{P}$ for each $b=0,\dots ,r+1$.

Use the standard induced regularity template lemma: for a fixed finite forbidden induced family and any error tolerance, a regularity refinement gives bounded-size templates with internal clique/independent types and cross pairs classified as sparse, almost complete, or intermediate. A clique of intermediate pairs on $a$ classes realizes every fixed induced pattern consistent with the internal types of those classes. This induced embedding conclusion uses a Ramsey refinement within clusters and regularity for both edges and nonedges; the total exceptional-pair cost can be made arbitrarily small. Applied to the $F_b$, a clique on $r+1$ intermediate classes would realize the forbidden $F_b$ whose number of clique types is $b$. Thus the graph of intermediate pairs is $K_{r+1}$-free. Only intermediate pairs contribute unrestricted binary choices; sparse pairs and the missing edges in almost-complete pairs each have the same entropy bound as before. The Turan theorem and the earlier counting argument now giveThis formula assumes $1\le r<\infty$. For the universal property the count is exactly $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$; a hereditary property of bounded order has $r=0$ and has no graphs on sufficiently large vertex sets, so the displayed expression with $1/r$ is not applicable.

For a proper subgraph-closed graph property, any contained $\mathcal{C}(a,b)$ must have $b=0$: if $b\ge 1$, it contains arbitrarily large complete graphs, and closure under subgraphs would force every graph into the property. Consequently its colouring number is exactly one less than the least chromatic number of an excluded graph. The excluded family of an intersection is the union of the two excluded families, whose minimum chromatic number is the smaller of their minima. Therefore $r(\mathcal{P}\cap \mathcal{Q})=\min (r(\mathcal{P}),r(\mathcal{Q}))$ for subgraph-closed properties, with the universal case treated by $r=\infty$.

For hereditary properties take $\mathcal{P}=\mathcal{C}(2,0)$ and $\mathcal{Q}=\mathcal{C}(2,2)$, both of colouring number two. A graph in their intersection is both bipartite and a union of two cliques. A clique in a bipartite graph has at most two vertices; hence every such graph has at most four vertices. The intersection contains no complete clique-independent class on arbitrarily large orders, so $r(\mathcal{P}\cap \mathcal{Q})=0<2$. This also demonstrates why the bounded-order exception to the enumeration formula is necessary.

The error indicator is a Bernoulli random variable with probabilities $P(Z=1)=p_e$ and $P(Z=0)=1-p_e$. Its Shannon entropy is therefore the binary entropyUse $0{\log }_{2}0=0$, so this expression also covers error probabilities zero and one.

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.

Choose an orthonormal basis of the joint $d^2$-dimensional Hilbert space whose first vector is the given purification of a density operator $|\rho {⟩}_{QR}$. Apply rank-one dephasing to ${\sigma }_{QR}$ in this basis, and denote the resulting diagonal probabilities by $p_1,\dots ,p_{d^2}$. Their first entry isThe preceding entropy increase under nonselective projective measurement and entropy bound with one prescribed probability yieldTherefore the quantum Fano inequality isThe quantity $f^2$ is the entanglement fidelity of $\mathcal{N}$ on ${\rho }_Q$; it is already a squared overlap, so it is $f^2$, rather than $f$, that enters the binary entropy. The argument is an instance of the entropy bound from overlap with a pure state in dimension $d^2$. At $f^2=1$ the output is the original pure state and its Von Neumann entropy is zero. For $d=1$ the system is trivial and the same zero-entropy conclusion holds without evaluating ${\log }_2(d^2-1)$.

For $t<1$, normalize the remaining probabilities by $q_j=P_X(j)/(1-t)$, $j=2,\dots ,k$. Directly splitting the Shannon entropy sum givesHere $h$ is the binary entropy. The Shannon entropy of a distribution on $k-1$ points is at most ${\log }_2(k-1)$. For example, nonnegativity of its Kullback-Leibler divergence from the uniform distribution gives ${\log }_2(k-1)-H(q)\ge 0$. Thus the entropy bound with one prescribed probability isFor $t<1$, equality holds precisely when the remaining probabilities are all $(1-t)/(k-1)$. For $t=1$, the distribution is deterministic and both sides are zero. The displayed formula is for $k\ge 2$; a one-point alphabet simply has zero Shannon entropy.

Use logarithms to base two, so Von Neumann entropy and quantum relative entropy are measured in bits. For density operators $\rho ,\sigma$,The quantum relative entropy formula applies when the support of a positive operator $\rho$ is contained in that of $\sigma$; otherwise $D(\rho \Vert \sigma )=+\infty$. Use $0{\log }_{2}0=0$ in the Von Neumann entropy formula.

The binary density operator $\omega [p]$ is diagonal with eigenvalues $1-p,p$. Its Von Neumann entropy is the binary entropy:The two diagonal density operators commute, so their quantum relative entropy isA term with zero numerator has value zero; a positive numerator and zero denominator give $+\infty$. In particular, $D(\omega [0]\Vert \omega [0])=D(\omega [1]\Vert \omega [1])=0$, whereas $q=0,p>0$ or $q=1,p<1$ gives $+\infty$.

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 probability measure-preserving system, the hypothesis is completely positive entropy: every finite measurable partition with positive static entropy of a finite measurable partition has positive entropy rate of a measurable partition. Fix a finite partition $\xi$ and putAll sigma-algebras are interpreted modulo null sets. We will prove that every finite partition $\alpha$ measurable with respect to this tail sigma-algebra of a measurable partition has $h_{\mu }(T,\alpha )=0$. Applying this to a binary partition will force the required triviality. This proves the needed direction of the Tail characterization of the Pinsker sigma-algebra directly, including noninvertible transformations.

Write $h=h_{\mu }(T,\xi )$. The infinite-future entropy formula and the backwards chain rule for information entropy give, for every $L\ge 1$, the block conditional entropy given the infinite future identityEach term equals $h$ by invariance of the joint probabilities under a common pullback and continuity of conditional entropy under increasing finite future blocks. Invertibility is not needed for this identity.

Fix $\epsilon >0$. Since $\alpha$ is ${\mathcal{F}}_0$-measurable and finite, the Martingale convergence theorem and continuity of finite-partition conditional entropy allow an $r\ge 0$ withTo see the continuity explicitly, for each partition atom $A$ of $\alpha$ the conditional probabilities $\mathbb{E}[1_A\mid \sigma ({\xi }_0^r)]$ tend to $1_A$ almost everywhere; apply dominated convergence theorem to the bounded continuous function $-t\log t$ on $[0,1]$ and sum over the finitely many partition atoms.

For $n\ge 1$ set $\gamma ={\alpha }_0^{n-1}$, $L=n+r$, and $\beta ={\xi }_0^{L-1}$. The conditional entropy of finite measurable partitions satisfiesThe second inequality uses conditioning reduces entropy, since $\beta$ refines each block $T^{-j}{\xi }_0^r$; the final equality uses measure preservation.

Moreover $\gamma$ is ${\mathcal{F}}_L$-measurable. For each $j\ge 0$, tail measurability gives $\alpha$ measurable with respect to ${\mathcal{F}}_L$, hence $T^{-j}\alpha$ measurable with respect to $T^{-j}{\mathcal{F}}_L={\mathcal{F}}_{L+j}\subseteq {\mathcal{F}}_L$. Thus conditioning reduces entropy and the displayed block identity implyUse the symmetric entropy identity $H(\gamma )=H(\beta )-H(\beta \mid \gamma )+H(\gamma \mid \beta )$ to obtainThe fraction on the right tends to zero: $r$ is fixed and $H({\xi }_0^{n+r-1})/(n+r)\to h$ by the definition of entropy rate of a measurable partition. Taking $n\to \infty$ and then $\epsilon \downarrow 0$ gives

Now let $A\in \mathcal{T}(\xi )$ and take $\alpha =\{A,X\setminus A\}$. If $0<\mu (A)<1$, its binary entropy is $-\mu (A)\log \mu (A)-(1-\mu (A))\log (1-\mu (A))>0$, while its entropy rate is zero, contradicting completely positive entropy. ThereforeSince $\xi$ was arbitrary, every finite-partition tail is trivial. The argument needs only that $\xi$ is finite and the measure is a probability; it does not assume a finite generator, finite total system entropy, or invertibility.

For a binary symmetric channel with crossover probability $p$, the capacity iswhere $H_2$ is the binary entropy. Shannon second coding theorem says that for every transmission rate $R<C$ and every $ϵ>0$, sufficiently long block codes exist with rate at least $R$ and decoding-error probability below $ϵ$; conversely, a sequence of codes whose error tends to zero cannot have limiting rate above $C$.

For the general channel let $X$ and $Y$ be its input and output. Every conditional output distribution is a permutation of $(p_1,\dots ,p_n)$, hencefor every input distribution. Since $H(Y)\le \log n$,The uniform input makes every output probability equal to $1/n$: the column-permutation assumption and the total sum imply that all column sums are equal to one. It therefore attains $H(Y)=\log n$, proving

In the displayed four-output channel each row is a permutation ofWith base-two logarithms,

Choose $\delta$ withA greedy packing construction gives binary length-$n$ codes of minimum distance greater than $2\delta n$ and size at leastTheir asymptotic rate is at leastwhere $h_2$ is binary Binary entropy. Minimum-distance decoding corrects every error pattern of weight at most $\delta n$. Since a channel error count is $\mathrm{Bin}(n,p)$, the law of large numbers givesThus a fixed positive rate is achievable with error tending to zero, proving that the operational capacity is nonzero. This is the positive-rate coding bound below one-quarter crossover.

Because the two flags $E_C$ and $F_C$ are orthogonal projections, the flagged state is block diagonal. If $h(\lambda )$ denotes the binary entropy, thenandIts unflagged marginals are ${\rho }_{AB}=\lambda {\rho }_{AB}^{\prime }+(1-\lambda ){\rho }_{AB}^{\prime \prime }$ and ${\rho }_B=\lambda {\rho }_B^{\prime }+(1-\lambda ){\rho }_B^{\prime \prime }$. Substitution in Strong subadditivity of Von Neumann entropy cancels the two binary-entropy terms and givesThis is exactly the concavity of quantum conditional entropy.

The unicity distance is the ciphertext length at which the key is uniquely determined, or equivalently at which key equivocation vanishes:For Shannon's idealized calculation, assume a uniformly chosen key independent of an iid plaintext source, deterministic invertible encryption for each key, and uniformly distributed ciphertext over an alphabet $\Sigma$. Since $M^n$ is determined by $(C^n,K)$,Setting this to zero givesEquivalently, each ciphertext symbol supplies the source redundancy $\log |\Sigma |-H$ bits toward identifying the key.

For the stated cipher, the original formula uses $k_{i\mathrm{mod}3}$, so $|K|=2^3=8$, while $|\Sigma |=3$. Split first according to whether $m=0$. This event and its complement each have probability $1/2$, and conditional on $m\ne 0$ the probabilities are $(2p,1-2p)$. HenceIf $U\ge 20$, thenso, using ${\log }_2(3)=1.585$,Therefore

Binary entropy is symmetric about probability $1/2$ and increases up to that point. Since equality holds at $2p=0.30$, it also holds at $2p=0.70$. Thusand all requested values are

Finally let $p=0$, so the source is uniform on $\{0,2\}$. Use one uniform key bit $k$ and encrypt each symbol byThus the second key swaps $0$ and $2$. Every ciphertext has two possible plaintexts, a binary string and its complement, with equal source probability. No amount of ciphertext distinguishes the keys: $H(K\mid C^n)=1$ for every $n$. This cipher has infinite unicity distance.

Set $q=(1+\epsilon {)}^{-1}$, so $1-q=\epsilon /(1+\epsilon )$ and $\omega =q\rho +(1-q){\Delta }^{\prime }$. For every state ${\xi }_B$, the entropy bound for a binary mixture givesTaking the minimum over ${\xi }_B$ and using the variational characterization of quantum conditional entropy on each term givesSince binary entropy satisfies $H(q)=H(1-q)$, this is