Here is a tripartite Schmidt projection entanglement concentration protocol. For , set . Regrouping the local qubits of each party gives
where counts ones. Alice performs a projective measurement of that count, without learning the individual string. The orthogonal projector for outcome is . By the Born rule, its probability and conditional pure state are
Alice sends by classical communication; all three parties use local unitary operations to relabel the same ordered type class as . There are now equal common-label amplitudes. Measuring the individual qubits instead would have destroyed precisely this coherence.
To obtain an integer number of target GHZ states, choose . The following exact LOCC step handles type classes whose sizes are not powers of two. For every -element subset , Alice uses the Kraus operator
Every label occurs in such subsets, proving on the occupied subspace. Thus this is a complete measurement in quantum mechanics. Each outcome has probability , and leaves the normalized pure state . After Alice communicates , all parties relabel its elements in the same order. Binary expansion of the labels then factors the state into exactly independent copies of the target GHZ state. Local extensions of these operations handle unused basis vectors and do not affect the protocol.
For example, taking gives an outcome-dependent yield without any failure branch. Since has a binomial distribution with parameters , the weak law of large numbers gives in probability. Stirling's formula, uniformly when stays away from zero and one, gives
By continuity of the binary entropy, in probability. The integer rounding and logarithmic correction have no first-order effect.
A fixed yield with success probability tending to one is also explicit. For sufficiently large , take
On , the bounded derivative of the binary entropy in a neighborhood of the fixed and Stirling's formula give . Chebyshev's inequality bounds the complementary probability by . Abort there if necessary, and otherwise use the subset measurement in quantum mechanics with . Thus
This matches the first-order rate in part (i), with exact outputs on every successful forward branch. If , simply retain the original target copies; if is an endpoint, output zero target copies.
Use base-two logarithms, so entanglement entropy is measured in bits. Write for the binary entropy, with . Taking a partial trace over any two parties removes the off-diagonal terms: the two traced strings are orthogonal. Consequently all three one-party reduced density matrices of the first pure state are
Each division into two groups is one party versus the other two. The Schmidt coefficients are and , so the entanglement entropy across each of , and is . For the second pure state, set : every one-party reduced density matrix is , and all three entanglement entropies are one bit.
For every pair , the first pure state instead gives the reduced density matrix
This is a separable quantum state, explicitly a convex combination of two product states. Its relative entropy of entanglement is therefore zero: in , choose to attain zero, while nonnegativity of quantum relative entropy excludes a negative value. The same argument with equal weights applies to the second pure state. Thus
The pairwise density matrices contain classical correlations, despite the entanglement of the global pure state; discarding a party loses the coherence between its two branches.
The entanglement entropy of independent source copies across any cut is , whereas copies of the target GHZ state have entanglement entropy . Average monotonicity of pure-state entanglement entropy under LOCC gives for exact successful forward branches. In a reversible asymptotic conversion the reverse direction similarly prevents a first-order deficit, since . For asymptotically faithful outputs, a continuity bound for quantum conditional entropy with trivial conditioning changes these inequalities only by . Hence the reversible leading-order rate is
The zero pairwise relative entropies of entanglement are consistent with this conversion: no independent pairwise resource has to be supplied or removed.
There is a qualification to the literal finite-block formulation in the source. For , the Schmidt rank of the exact state of source copies is , whereas target GHZ states have Schmidt rank . Every refined LOCC branch acts by a product of local linear operators and cannot increase this Schmidt rank. For , the displayed rate has for sufficiently large blocks when , so an exact successful reverse conversion is impossible, irrespective of its claimed probability. The exact dilution obstruction from Schmidt rank is avoided in the usual asymptotic formulation by allowing outputs approaching the desired pure state. The leading-order rate above and the exact forward protocol below remain valid; neither establishes the source's stronger exact round-trip claim. At the two states are identical. At or , the source is a known product state, the rate is zero, and local preparation supplies any desired number of source copies.
Use base-two logarithms throughout, so classical rates are measured in bits and quantum compression rates in qubits. A memoryless classical information source is a sequence of independent and identically distributed random variables on a finite alphabet , with fixed probability mass function . A length- word has probability , and the one-symbol Shannon entropy is , with .
For , the typical set is
This is weak typicality: it constrains the normalized self-information, not each empirical symbol count separately.
The typical sequence theorem gives the following three facts for fixed . The probability tends to one; each word in the set has probability between and ; and, once the set has probability at least ,
The concentration assertion follows from the weak law of large numbers applied to the iid information variables , whose finite-alphabet mean is . The probability bounds are the definition of typicality exponentiated. Summing the lower bound over the typical words and using total probability at most one proves the cardinality upper bound; summing the upper bound and using total typical probability at least proves the lower bound.
Fix and choose . Enumerate all words in and assign a distinct fixed-length binary index to each. Reserve one more index as a failure symbol for every atypical input. For all sufficiently large ,
so these indices can be transmitted using bits. The decoder inverts the typical-word enumeration; on the failure index it returns any fixed word. This describes both the compressor and decompressor, and its block error probability obeys
Its rate tends to bits per symbol. Thus every permits reliable fixed-rate compression, with no claim that atypical words are reconstructed correctly.
For the memoryless quantum information source, the average one-use density matrix is
Its trace is one and determinant , so its two eigenvalues are
The source-coding limit in Schumacher compression is the Von Neumann entropy of this average state: every larger qubit rate allows asymptotically faithful recovery of the emitted states, and a smaller rate cannot do so. Applying that limit gives
where is the binary entropy. The quantum typical subspace of has dimension about and carries asymptotically all source weight, which explains the compression rate. The entropy of the classical emission label is one bit; it is not the quantum rate because the two emitted pure states are nonorthogonal.
Use the usual asymptotic convention: the output approaches the desired -copy pure target in trace distance, and any recorded failure probability tends to zero. Define the binary entropy
The entanglement entropies per source and target are and . The asymptotic pure-state entanglement conversion rate is
Both achievability and the upper bound matter here.
For entanglement concentration, expand sources in their correlated computational basis. Every pair of strings of Hamming weight has the same amplitude . Alice measures only this weight, without resolving the individual string. Bob's string has the same weight automatically. Conditional on , the normalized state is maximally entangled on correlated strings. Its outcome probability is , a binomial distribution. By the weak law of large numbers, in probability; Stirling's formula then gives . A uniform Schmidt vector on entries is majorized by a uniform vector on entries padded with zeros. Thus Nielsen's pure-state conversion theorem converts the conditional state into that many Bell pairs exactly. For any fixed , one obtains at least Bell pairs with probability tending to one.
For entanglement dilution, consider the Schmidt strings of targets with probabilities . The quantum typical subspace retains strings satisfying
The retained probability tends to one by the weak law applied to the independent variables . The number of retained strings is at most , because their probabilities sum to at most one. Normalize the target after truncation to those strings. Its squared overlap with the full target is . A uniform Schmidt vector of dimension , with , is majorized by the truncated target's Schmidt vector padded with zeros: the sum of its largest entries is at least . Hence Bell pairs prepare the truncated target exactly by LOCC. Its trace distance from the true target is . Combining concentration and dilution achieves any rate . Choosing margins tending sufficiently slowly to zero attains the ratio as a limiting rate.
For the converse, average monotonicity of pure-state entanglement entropy follows from Concavity of Von Neumann entropy: a measurement by one party leaves the other party's reduction unchanged on average, so its average conditional entropy cannot increase. Refine local measurement records, including local discarded systems, to obtain pure output branches on the output qubits of each party. Iterating the concavity argument gives
Let and let the squared-overlap error of the average output be . Define , the pure-state trace distance. Concavity of the square root gives . Partial trace cannot increase trace distance, so the reduced states are also within . The continuity bound for quantum conditional entropy, with trivial conditioning and local dimension , implies
Consequently
which excludes a limiting rate exceeding .
The vanishing-error convention is essential. If exact deterministic conversion were required for every finite block, majorization would also require the largest squared Schmidt coefficient to satisfy , hence
This can be strictly smaller than the entropy ratio: at , the two bounds are approximately and . Thus the boxed rate answers the standard asymptotic task, rather than imposing unmentioned exact zero-error conditions on every finite block.
Applying the optimal single-copy filter independently gives a random number of exact successful targets with binomial distribution
The weak law of large numbers gives in probability. In contrast, collective entanglement concentration and entanglement dilution yield asymptotically targets with vanishing output error. The improvement is strict, not just nonnegative. Differentiating binary entropy gives
Since , it follows that
This is collective advantage over independent two-qubit filtering. Independent filtering discards the entanglement in product-state failure branches; the collective reversible asymptotic procedure avoids that extensive loss. The separately filtered targets are exact conditional on success, whereas the collective statement uses the vanishing-error convention from the previous part. Here the counted outputs are target states ; that is also the notation in the original printed question.
Conjugation by a Pauli operator preserves its matching Bloch vector component and reverses the other two. Summing all three conjugations therefore sends to . The specified quantum depolarizing channel has retention factor
This Pauli-mixture parametrization of qubit depolarization differs from a convention in which itself is the retention factor. For , . A pure input gives output eigenvalues , and hence entropy 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. Thus
Two 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 gives
At it is one; at it is zero; at it is . 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 . Every graph of chromatic number at most belongs to . In particular, all subgraphs of a fixed balanced Turán graph belong. Choosing each of its edges independently as present or absent gives
For the upper bound, fix with . Every member of is -free, by closure under subgraphs.
We use the following standard regularity consequences. For every sufficiently small regularity error , large minimum cluster count , and fixed positive density cutoff , the Szemerédi regularity lemma gives an equitable partition into clusters and an exceptional set of at most vertices, with at most 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 , provided is sufficiently small relative to and the graph. Hence the reduced graph of a regularity partition, joining regular pairs of density at least , is -free: such a clique would embed .
By the Turan theorem, this reduced graph has at most edges. On its dense pairs allow arbitrary choices of original edges, giving at most free binary choices. All edges within clusters, touching the exceptional set, or lying in irregular pairs contribute further choices. On each remaining pair there are at most times its number of possible edges. The elementary binary entropy estimate
bounds the total sparse-pair contribution by . The partition and pair classifications have at most descriptions, whose logarithm is since is fixed. Choose large, then small, then sufficiently small; their total error can be made arbitrarily small. This proves
It 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 , for , to consist of graphs partitionable into possibly empty classes, exactly designated as cliques and the other designated as independent sets; cross edges are unrestricted. Thus is the total number of classes. The colouring number of a hereditary graph property is
Use value zero if this set is empty, and infinity for the class of all graphs.
for . The lower bound follows from the definition. For the upper bound, fix any and a balanced partition of a large -vertex set into classes with clique classes. Independent choices of cross edges give distinct graphs in . On the other hand, all graphs in can be described by at most partitions, each with at most unrestricted cross pairs. The former count is strictly larger for large , so is not contained in for any . A contained class with even more parts would contain one of these -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 : within-class edges are fixed as complete or empty, and the balanced cross pairs still give free edge choices. For the upper bound, since no is wholly contained in , choose one forbidden induced graph for each .
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 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 , a clique on intermediate classes would realize the forbidden whose number of clique types is . Thus the graph of intermediate pairs is -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 give
This formula assumes . For the universal property the count is exactly ; a hereditary property of bounded order has and has no graphs on sufficiently large vertex sets, so the displayed expression with is not applicable.
For a proper subgraph-closed graph property, any contained must have : if , 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 for subgraph-closed properties, with the universal case treated by .
For hereditary properties take and , 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 . This also demonstrates why the bounded-order exception to the enumeration formula is necessary.
The error indicator is a Bernoulli random variable with probabilities and . Its Shannon entropy is therefore the binary entropy
Use , so this expression also covers error probabilities zero and one.
Use the Shannon second coding theorem in its channel capacity form . The finite-alphabet erasure channel erases independently of the input. On an unerased output Bob knows exactly; on the erasure output his posterior distribution is still . Its classical conditional entropy is therefore
Equivalently, and , so the binary entropy terms cancel in the mutual information.
For an alphabet of size , Shannon entropy is at most , with equality for the uniform distribution. Maximizing the displayed mutual information proves the capacity of a finite-alphabet erasure channel:
This includes , which transmits the whole symbol, and , which transmits no information.
Choose an orthonormal basis of the joint -dimensional Hilbert space whose first vector is the given purification of a density operator . Apply rank-one dephasing to in this basis, and denote the resulting diagonal probabilities by . Their first entry is
The preceding entropy increase under nonselective projective measurement and entropy bound with one prescribed probability yield
Therefore the quantum Fano inequality is
The quantity is the entanglement fidelity of on ; it is already a squared overlap, so it is , rather than , that enters the binary entropy. The argument is an instance of the entropy bound from overlap with a pure state in dimension . At the output is the original pure state and its Von Neumann entropy is zero. For the system is trivial and the same zero-entropy conclusion holds without evaluating .
For , normalize the remaining probabilities by , . Directly splitting the Shannon entropy sum gives
Here is the binary entropy. The Shannon entropy of a distribution on points is at most . For example, nonnegativity of its Kullback-Leibler divergence from the uniform distribution gives . Thus the entropy bound with one prescribed probability is
For , equality holds precisely when the remaining probabilities are all . For , the distribution is deterministic and both sides are zero. The displayed formula is for ; 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 ,
The quantum relative entropy formula applies when the support of a positive operator is contained in that of ; otherwise . Use in the Von Neumann entropy formula.
The binary density operator is diagonal with eigenvalues . Its Von Neumann entropy is the binary entropy:
The two diagonal density operators commute, so their quantum relative entropy is
A term with zero numerator has value zero; a positive numerator and zero denominator give . In particular, , whereas or gives .
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 ,
The last step uses for the binary entropy and . If , rearrangement and then the supremum over give the one-shot classical-quantum coding converse:
For , the sole POVM effect is , forcing , and the bound is trivial. For , division by is undefined: the undivided inequality remains valid and gives no size restriction. The displayed coding bound is therefore understood for , or with a vacuous right-hand side at .
An alternative uses the original decoder directly. Let be the uniform message and its measured estimate. For , Fano's inequality bounds the conditional entropy by . The Holevo bound gives
Thus 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 and put
All sigma-algebras are interpreted modulo null sets. We will prove that every finite partition measurable with respect to this tail sigma-algebra of a measurable partition has . 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 . The infinite-future entropy formula and the backwards chain rule for information entropy give, for every , the block conditional entropy given the infinite future identity
Each term equals 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 . Since is -measurable and finite, the martingale convergence theorem and continuity of finite-partition conditional entropy allow an with
To see the continuity explicitly, for each partition atom of the conditional probabilities tend to almost everywhere; apply dominated convergence theorem to the bounded continuous function on and sum over the finitely many partition atoms.
For set , , and . The conditional entropy of finite measurable partitions satisfies
The second inequality uses conditioning reduces entropy, since refines each block ; the final equality uses measure preservation.
Moreover is -measurable. For each , tail measurability gives measurable with respect to , hence measurable with respect to . Thus conditioning reduces entropy and the displayed block identity imply
Use the symmetric entropy identity to obtain
The fraction on the right tends to zero: is fixed and by the definition of entropy rate of a measurable partition. Taking and then gives
Now let and take . If , its binary entropy is , while its entropy rate is zero, contradicting completely positive entropy. Therefore
Since was arbitrary, every finite-partition tail is trivial. The argument needs only that 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 , the capacity is
where is the binary entropy. Shannon second coding theorem says that for every transmission rate and every , sufficiently long block codes exist with rate at least and decoding-error probability below ; conversely, a sequence of codes whose error tends to zero cannot have limiting rate above .
For the general channel let and be its input and output. Every conditional output distribution is a permutation of , hence
for every input distribution. Since ,
The uniform input makes every output probability equal to : the column-permutation assumption and the total sum imply that all column sums are equal to one. It therefore attains , proving
In the displayed four-output channel each row is a permutation of
With base-two logarithms,
Choose with
A greedy packing construction gives binary length- codes of minimum distance greater than and size at least
Their asymptotic rate is at least
where is binary Binary entropy. Minimum-distance decoding corrects every error pattern of weight at most . Since a channel error count is , the law of large numbers gives
Thus 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 and are orthogonal projections, the flagged state is block diagonal. If denotes the binary entropy, then
and
Its unflagged marginals are and . Substitution in Strong subadditivity of Von Neumann entropy cancels the two binary-entropy terms and gives
This 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 . Since is determined by ,
Setting this to zero gives
Equivalently, each ciphertext symbol supplies the source redundancy bits toward identifying the key.
For the stated cipher, the original formula uses , so , while . Split first according to whether . This event and its complement each have probability , and conditional on the probabilities are . Hence
If , then
so, using ,
Therefore
Binary entropy is symmetric about probability and increases up to that point. Since equality holds at , it also holds at . Thus
and all requested values are
Finally let , so the source is uniform on . Use one uniform key bit and encrypt each symbol by
Thus the second key swaps and . Every ciphertext has two possible plaintexts, a binary string and its complement, with equal source probability. No amount of ciphertext distinguishes the keys: for every . This cipher has infinite unicity distance.
Set , so and . For every state , the entropy bound for a binary mixture gives
Taking the minimum over and using the variational characterization of quantum conditional entropy on each term gives
Since binary entropy satisfies , this is
Rate-distortion function Created 2026-09-24 Updated 2026-10-14
Fix a finite source alphabet , a probability mass function , a finite reconstruction alphabet , and a nonnegative distortion measure . The information rate-distortion function is
The source probability distribution stays fixed; the conditional distribution of the reconstruction is what we optimize. Each feasible test channel must keep expected distortion at most . The objective is mutual information, measured in bits when the logarithms have base two. If no test channel satisfies the constraint, the infimum is .[ref]
Consider independent and identically distributed fair bits and Hamming distortion, which charges one for an incorrect bit. At zero expected distortion, every bit must be reconstructed correctly, and . If an average fraction of incorrect bits is allowed, the binary rate-distortion function gives
Here is binary entropy. This is an asymptotic limit for long block codes, rather than a claim that a single bit can be stored in physical bits. The three-bit lossy Hamming code gives a small, fully explicit version of the same tradeoff, with rate and expected distortion .
Figure 1.
Allowing more incorrect fair bits lowers the asymptotic information rate
. The curve is the exact binary rate-distortion function. The marked three-symbol code has rate at expected distortion ; its gap above the curve shows that a small explicit block code need not attain the asymptotic bound. Rates count bits per original source symbol. Details.
Rate-distortion theory separates the question of what is possible from the design of a practical encoder and decoder. It also forces the fidelity criterion to be explicit. Hamming distortion treats all symbol mismatches alike; mean squared error instead penalizes larger numerical errors more strongly. Those objectives can favor different reconstructions of the same data. An average error criterion does not by itself control the error on every individual input.
Claude Shannon's Coding Theorems for a Discrete Source With a Fidelity Criterion by Claude Shannon was published in 1959. Its formulation fixes a cost for replacing one source letter by another and studies the communication rate compatible with the allowed average cost. The important shift is to quantify which distinctions may be discarded, rather than requiring exact recovery of every letter.[ref]