How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Quantum Source Compression and Classical Communication over Quantum Channels
1 · Prerequisites
- Absolute and Conditional Convergence; Rearrangement; Products
- Algebraic Closure, Embeddings, and Separability
- Algebraic Extensions, Extension Degree, and Finite Fields
- Binary Operations, Monoids, Groups and Subgroups
- Channels, Kraus, Choi, and Stinespring Representations
- Compactness in Metric Spaces
- Completeness, Completion, and Uniform Continuity
- Complex Norms and Realification
- Composition Series, the Jordan–Hölder Theorem and Solvable Groups
- Congruences, the Integers Modulo n and the Chinese Remainder Theorem
- Construction of the Natural Numbers
- Construction of the Real Numbers via Cauchy Sequences
- Construction of the Real Numbers via Dedekind Cuts
- Continuity, IVT, EVT, and Uniform Continuity
- Convexity
- Cosets, Index and Lagrange's Theorem
- Countability and Uncountability
- Cyclic Groups and Direct Products
- Determinants of Matrices over a Commutative Ring
- Diagonalisation and the Minimal Polynomial
- Divisibility, Euclidean Domains, Principal Ideal Domains and Unique Factorisation
- Divisibility, Greatest Common Divisors and Bézout's Identity
- Dual Spaces, Bilinear and Quadratic Forms, and Sylvester's Law of Inertia
- Eigenvalues, Eigenvectors and the Characteristic Polynomial
- Filters and Ultrafilters
- Finite basis projector energies and variational electronic structure
- Finite Counting, Factorials and Binomial Coefficients
- Finite Probability Spaces and Random Variables
- Finite-Alphabet Entropy and Divergence
- Finite-Dimensional Complex Inner-Product Spaces and Matrix Interfaces
- Foundations of the Real Numbers for Analysis
- Free Modules, Exact Sequences, Projective and Injective Modules
- Fundamental Trigonometric Identities
- Group Actions, Orbits, Stabilisers and Cayley's Theorem
- Group Homomorphisms and the Isomorphism Theorems
- Hilbert Space Geometry and Riesz Representation
- Ideals, Quotient Rings and the Isomorphism Theorems for Rings
- IID Lossless Source Coding and the AEP
- Improper Integrals
- Independence Borel Cantelli and Zero One Laws
- Inner Product Spaces, Gram-Schmidt, Projections and Adjoints
- Knill–Laflamme Recovery and Subsystem Codes
- Limits of Real Functions
- limsup, liminf, and Subsequential Limits
- Linear Combinations of Unitaries and Taylor Simulation
- Linear Independence, Bases and Dimension
- Linear Transformations, Rank-Nullity and Quotient Spaces
- Matrices, the Matrix of a Linear Map, and Change of Basis
- Measurable Functions and Simple Approximation
- Measurements, POVMs, and Instruments
- Measures and Their Basic Properties
- Metric Spaces
- Modes of Convergence Egorov and Lusin
- Modes of Convergence for Random Variables
- Modules, Submodules, Quotient Modules and the Isomorphism Theorems
- Monotone Functions, Discontinuities, and Continuity Sets
- Monotone Sequences, Bolzano-Weierstrass, and Cauchy Completeness
- Normal Subgroups and Quotient Groups
- Order, Zorn's Lemma, and the Axiom of Choice
- Pointwise Extended-Real Function Products
- Polynomial Rings, the Division Algorithm and Roots
- Power Series and Real-Analytic Functions
- Primes, Euclid's Lemma and the Fundamental Theorem of Arithmetic
- Probability Spaces Random Variables and Expectation
- Product Measures and the Fubini Tonelli Theorems
- Properties of the Integral and the Working FTC
- Pure and Mixed States, Ensembles, and Schmidt Decomposition
- Quantum Communication and Fingerprinting
- Quantum Information Measures
- Quantum Optimization, Semidefinite Programs, and Variational Algorithms
- Quantum Relative Entropy, Data Processing, and Strong Subadditivity
- Registers, Tensor Products, and Partial Trace
- Relations, Functions, and Quotients
- Rings, Subrings, Integral Domains and Fields
- Rⁿ as a Normed Space; Vector-Valued Functions
- Roots, Rational Powers, and Classical Inequalities
- Sequences and Limits
- Sequences and Series of Functions; Uniform Convergence
- Series: Convergence and the Nonnegative Tests
- Sigma Algebras and Borel Sets
- Simple Field Extensions and the Construction of the Complex Numbers
- Sine, Cosine, and the Definition of Pi
- Splitting Fields
- Suprema and Infima
- Sylow's Theorems, p-Groups and Nilpotent Groups
- Symmetric Groups, Cycle Decomposition and the Sign Homomorphism
- Tensor Products of Modules
- The Complex Exponential and Euler's Formula
- The Derivative and the Mean Value Theorems
- The Determinant of a Linear Operator, Cofactors and Cramer's Rule
- The Exponential Function
- The Fundamental Theorem of Algebra
- The Fundamental Theorem of Finite Abelian Groups
- The Galois Correspondence
- The Lebesgue Integral and the Convergence Theorems
- The Logarithm and General Powers
- The Lᵖ Spaces Holder Minkowski and Riesz Fischer
- The Riemann Integral: Definition and Integrability
- The Spectral Theorem, Positive Operators and Singular Value Decomposition
- The ZFC Axioms and the Basic Set Constructions
- Topological Spaces and Continuity
- Topology of ℝ
- Triangularisation, Generalised Eigenspaces and Jordan Canonical Form
- Trust region and cubic regularization methods
- Vector Spaces, Linear Subspaces, Span and Direct Sums
- Weak Laws and Series of Independent Random Variables
2 · Summary
This page proves two finite-dimensional asymptotic coding theorems. For the IID source , the Schumacher rate is nats, measured using squared entanglement fidelity of a channel that factors through the code space. For a fixed finite-input memoryless cq channel , the HSW capacity is the maximum ensemble Holevo information in nats/use, with deterministic codewords, collective output POVMs, and vanishing average block error. Bits are obtained by dividing the displayed nats rates by ; no infinite-dimensional or general quantum-input single-letter claim is made.
The source-code diagram records the untouched reference register and the two channels in the code definition. The cq diagram records the encoder word, memoryless output state, and decoder measurement. These are type-level diagrams only; the statements and proofs below use the explicit channel, state, and POVM formulas.
R\otimes A^{\otimes n} \arrow[r,"\operatorname{id}_R\otimes\mathcal E_n"] &
R\otimes C_n \arrow[r,"\operatorname{id}_R\otimes\mathcal D_n"] &
R\otimes\widehat A^{\otimes n}
[M] \arrow[r,"m\mapsto x^n(m)"] &
\mathcal X^n \arrow[r,"x^n\mapsto\bigotimes_i\rho_{x_i}"] &
\mathcal D(H_B^{\otimes n}) \arrow[r,"\{\Lambda_m\}"] &
[M]
3 · Logical flowchart
4 · Definitions, theorems and proofs
Gentle measurement bound in finite dimensions
Statement
Let be a density operator on a nonzero finite-dimensional complex inner-product space , let , and suppose for some . Then
Here is the unique nonnegative square root, and is the finite-dimensional trace norm. No normalization is applied after the operation .
Facts & Assumptions
Given: A finite-dimensional density operator , an operator , and with .
Density operator: is nonnegative with trace one.
Purifications exist and are unitarily equivalent after padding: every finite-dimensional density operator has a unit-vector purification whose partial trace is the state.
Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely: a nonnegative endomorphism has an orthonormal eigenbasis with nonnegative real eigenvalues.
A non-negative operator has a unique non-negative square root: a nonnegative endomorphism has a unique nonnegative square root.
Trace Norm: the trace norm is the sum of singular values.
Partial trace contracts the trace norm on Hermitian operators: partial trace does not increase trace norm on Hermitian operators.
Proof
Choose a purification of using [F2]. Let , , and . By [F3]–[F4], the eigenvalues of lie in and , so is nonnegative. Diagonalizing by [F3], is a sum of nonnegative eigenvalues of times nonnegative quadratic forms; hence . Also because and .
The Hermitian operator is zero off the span of . If is not a scalar multiple of , write with ; in the orthonormal basis , its matrix has trace and determinant . By [F7], , so the eigenvalues have opposite signs or one is zero. Its trace norm is the square root of the characteristic discriminant, . If is a scalar multiple of , the same formula reduces to the one-dimensional trace norm .
Since and , step 2.1 gives Taking the partial trace over gives the claimed bound by [F6], because the partial trace of the first rank-one state is and that of the second is .
The finite positive square root preserves operator order
Statement
If are nonnegative endomorphisms of a nonzero finite-dimensional complex inner-product space and , then their nonnegative square roots satisfy .
Facts & Assumptions
Given: Nonnegative on a nonzero finite-dimensional complex inner-product space with .
Non-negative and positive operators: means is nonnegative, and positive definite operators have positive quadratic form on nonzero vectors.
Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely: finite-dimensional Hermitian operators have orthonormal eigenbases.
A non-negative operator has a unique non-negative square root: the nonnegative square root is defined spectrally with eigenvalues .
Continuity and derivatives of positive-base real powers and The second fundamental theorem: if is differentiable on with and is integrable, then : the positive powers and have their ordinary derivatives, and a continuous derivative integrates to its endpoint difference on each compact positive interval.
The integral with oriented limits: and and For : is integrable on if and only if it is integrable on and on , and then ; with the oriented form for arbitrary : oriented compact-interval integrals reverse sign and add over adjacent intervals.
Monotone change of variable for Riemann-integrable functions: a differentiable monotone change of variable transforms a Riemann integral by its derivative.
The adjoint is characterised by and Adjoints satisfy , , , and : adjoints satisfy the inner-product identity and reverse products, so a congruence by a self-adjoint endomorphism is self-adjoint and preserves nonnegativity by its quadratic-form calculation.
If on and both are integrable then ; and : pointwise inequalities between integrable functions on a compact interval imply the same inequality for their integrals.
A monotone sequence converges if and only if it is bounded: every bounded monotone sequence of real numbers converges.
A continuous function on is Riemann integrable, by Heine-Cantor and Riemann's criterion: a continuous real function on a compact interval is Riemann integrable.
Proof
First suppose are positive definite and . By [F2], their eigenvalues are strictly positive: applying the positive quadratic form to an eigenvector gives . Define spectrally by replacing each eigenvalue with , and set ; multiplication in the eigenbasis shows these are the inverse square root and inverse of . Put . By the adjoint product rule in [F7], is self-adjoint, and [F7] gives for , so is positive definite. Also by the same quadratic-form identity and [F1]. Hence every eigenvalue of is at least one by [F2]; define spectrally by reciprocating its positive eigenvalues, giving . Since , multiplying this factorization by on either side gives the identity, so . Congruence of by now yields .
For and nonzero , , and likewise for , so and are positive definite and ordered. Step 1.1 gives . Multiplying the order by and subtracting from yields
Set for . It is continuous, hence integrable on every compact interval in its domain by [F10]. For , ; for , . For each integer , the sequence is nondecreasing by positivity and additivity, and is bounded above by . For this evaluation follows from the primitive , whose derivative is by [F4], and the fundamental theorem in [F4]; for both sides are zero by the equal-endpoint convention in [F5]. The sequence is likewise nondecreasing and bounded above by , using the primitive and [F4] when , and [F5] when . Both sequences therefore converge by [F9]. By additivity [F5], converges to a finite . For every , monotonicity [F8] and on give , so . For each fixed , define . If is fixed and is large enough that and , additivity and monotonicity of the integral with the two displayed tail bounds give Since and , this proves for each fixed . Now [F6] with in the coefficient integral over the fixed interval gives for the coefficient is identically zero. For a nonnegative , let be its spectral projection at eigenvalue and define The coefficient depends only on , so this definition is independent of choices of eigenvectors within eigenspaces. The coefficient convergence and finite spectral sum imply for every vector . For , this quadratic form is also the integral of the continuous scalar function on , as follows from the finite spectral sum. By step 2.1 these functions for and are pointwise ordered; [F8] therefore gives . Taking limits and using yields for every , which is .
Finite Hayashi–Nagaoka operator inequality
Statement
Let be nonnegative endomorphisms of a finite-dimensional complex inner-product space , with . Define spectrally on and set it to zero on . Then
Facts & Assumptions
Given: Nonnegative on finite-dimensional with .
Non-negative and positive operators: means is nonnegative.
Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely and A non-negative operator has a unique non-negative square root: nonnegative endomorphisms have finite orthonormal eigenbases and their square roots are defined by taking nonnegative square roots of eigenvalues.
Proof
If , every endomorphism, including , is zero, so the asserted inequality is . Henceforth assume , as required by [F2]. Set , , and . For and endomorphisms , expanding and dividing by gives . Apply this with and . Since , expansion of and the preceding inequality give Now , so congruence by gives ; the last equality follows because commutes with . Since , substitution and collection of the two terms yield By [F2], ; [F3] and give by diagonalizing . Therefore . Taking in the last display proves
Let be the orthogonal projection onto . If , then ; both terms are nonnegative, so each is zero. By [F3], these terms are and , hence . Since are self-adjoint, they preserve the orthogonal complement of as well. Thus both sides of the desired inequality are block diagonal for . On , congruence of step 1.1 by the inverse of the restriction of gives . On this block, , so its left side is . On , the desired inequality is , since there. Combining these two block inequalities proves the Statement, including when either block is zero-dimensional.
Finite IID quantum source and compression code
Definition
Let be a nonzero finite-dimensional complex inner-product space and let be a density operator (Density operator) on . The finite IID quantum source with state emits the block state on at blocklength .
An quantum compression code for consists of a finite-dimensional code space with , a quantum channel (Finite-dimensional quantum channel) , and a quantum channel . Its squared entanglement fidelity is
where is any finite-dimensional reference space supporting the chosen unit-vector purification of on . The value is independent of the chosen finite purification by the isometric equivalence of Purifications exist and are unitarily equivalent after padding. A sequence of codes is reliable when . The code's rate is nats per source letter, equivalently qubits per source letter. The entropy threshold in these units is nats or qubits, where is the entropy of Finite-dimensional von Neumann entropy.
Continuity of finite-dimensional quantum entropy
Statement
For each fixed finite dimension , von Neumann entropy is continuous on density operators (Density operator) on in operator norm (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||). Thus, if in operator norm, then .
Facts & Assumptions
Given: A fixed finite dimension and density operators on .
Finite-dimensional von Neumann entropy: , with .
Ordered eigenvalues of Hermitian matrices are operator-norm Lipschitz: each ordered eigenvalue of Hermitian matrices changes by at most the operator norm of the matrix difference.
Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: is continuous, strictly increasing, and onto . By The natural logarithm as the inverse of the exponential function, and for .
Density operator: a density operator is nonnegative with trace one, so its eigenvalues lie in .
Proof
Define for and . It is continuous for positive by [F3]. Since is increasing and onto, as . Put ; then by the inverse and reciprocal identities in [F3]. Hence by [F4] with , so is continuous on .
Let and similarly for . By [F5], density eigenvalues lie in ; [F2] gives for every . For any , continuity of at the finitely many gives one positive radius such that makes for all .
Sum the inequalities in step 2.1 and use [F1]. This gives whenever , proving continuity. The zero-eigenvalue boundary is covered by step 1.1, so no full-rank assumption is used.
Finite square-root measurement packing bound for cq states
Statement
Let be a finite nonempty set, let be a probability vector, and let be density operators on a finite-dimensional . Let . Suppose that for every in the support of , projections satisfy and , where and . For , draw independently with law . Then the square-root POVM built from has expected average error at most
Facts & Assumptions
Given: A finite ensemble of states, projectors obeying the displayed bounds, and independent random codewords.
Density operator: each is nonnegative with trace one.
Gentle measurement bound in finite dimensions: acceptance at least implies trace-norm disturbance at most .
Finite Hayashi–Nagaoka operator inequality: if and , then , with the inverse on support.
Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely and A non-negative operator has a unique non-negative square root: positive operators have spectral square roots and inverse square roots on their supports.
Trace Norm Duality And Norm Properties: for an effect , when is Hermitian.
Trace of a product of positive semidefinite matrices is nonnegative: the trace of a product of two nonnegative operators is nonnegative.
For and , : trace is cyclic for compatible finite-dimensional factors.
Trace is a linear functional on : trace is linear over finite sums and scalar multiples.
Proof
For a realized codebook, set and . Since each factor is a projection, . Define on and zero on its kernel; add . By [F4], all are nonnegative and is the support projection of , so is a POVM.
For , independence of and gives The first equality factors the finite independent expectation into the product of its two means and distributes the finite trace sum using [F8]; the second uses [F7] and the support of the first factor. For the first inequality, is nonnegative, so [F6] applied to its product with the nonnegative first factor gives the trace bound. For the last inequality, is nonnegative and [F6]–[F7] give .
For the transmitted codeword , [F3] applied with and gives the operator inequality . Since is nonnegative by [F1], [F6] applied to its product with the nonnegative difference of the right and left sides preserves the order after taking trace, and trace linearity [F8] expands the resulting right side to The gentle bound [F2] for the global projection gives . Since , trace-norm duality [F5], cyclicity [F7], and then give
Average step 2.1 over all messages and codebooks. Its first term is at most by the acceptance estimate there, and each of the competing terms is at most by step 1.2. Thus the expected average error has the claimed bound. Because the codebook sample space is finite, at least one realization has error no greater than its expectation.
Compression dimension bounds entanglement fidelity
Statement
Let have decreasing eigenvalues , padded by zeros, and let an compression code have intermediate dimension as in Finite IID quantum source and compression code. Then
Facts & Assumptions
Given: A finite-dimensional density operator , a purification of , and encoder and decoder channels factoring through a code space of dimension .
Finite IID quantum source and compression code: the squared entanglement fidelity is the overlap of the purified source with the recovered joint state, and the encoder and decoder are quantum channels.
Kraus and Choi characterizations of complete positivity: every finite-dimensional completely positive map has a finite Kraus representation.
Trace preservation is Kraus normalization: a trace-preserving Kraus family satisfies .
Schmidt decomposition: a finite bipartite vector has an expansion with , both factor families orthonormal, and squared norm .
Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely: a finite-dimensional Hermitian operator has an orthonormal eigenbasis.
Partial trace over a finite tensor factor: partial trace contracts the repeated factor index in an orthonormal product basis. The trace-pairing identity and basis independence are given by The partial trace is characterized by the trace pairing and is basis-independent.
Proof
Choose Kraus families and for the encoder and decoder from [F2]. The composite channel has Kraus operators , each of rank at most because it factors through the -dimensional code space. By [F3],
By [F4], write , ordering the decreasingly. Expanding and contracting either orthonormal factor family by [F7] gives Indeed each cross term with indices contracts with coefficient , or , respectively. Thus both reduced operators have exactly the positive eigenvalues , with any remaining eigenvalues zero. Complete by an orthonormal basis of , available from [F5] applied to the zero operator there. On this full reference basis, has eigenvalues , with the Statement's zero padding; in particular .
For each let , and let be the projection onto its reference-side Schmidt support (zero if ). Since , apply [F4] on these two factors: there are at most orthonormal second-factor vectors. Thus and . Cauchy–Schwarz and the trace-pairing identity in [F7] give
Put . Then , and the full reference basis from step 1.2 gives . If , then , since the source has at most positive eigenvalues. Otherwise, ordering the eigenvalues gives Thus the overlap in step 2.1 is bounded by .
Expanding the recovered state in the composite Kraus family from step 1.1 gives . By step 3.1 this is at most . Step 1.1 gives , proving the bound.
Finite-input memoryless cq channel
Definition
Let be a finite nonempty input alphabet and let be a nonzero finite-dimensional complex inner-product space. A finite-input cq channel is a map assigning a density operator (Density operator) on to each . Its -use memoryless extension sends a word to the product state For an input probability vector , write and ; this is the Holevo information of the ensemble in Finite classical-quantum states and Holevo information, in nats.
Finite cq block codes, average error, and capacity
Definition
Fix a finite-input cq channel as in Finite-input memoryless cq channel. For integers , an cq block code consists of a deterministic encoder for and a finite POVM (Finite POVMs and their outcome law) on . Under a uniform message, its average block error is Its rate is nats per channel use, using the natural-log unit convention of Finite-dimensional von Neumann entropy. A sequence of such codes is reliable if . The classical capacity is the supremum of over reliable sequences.
For each transmitted state, the POVM outcome weights sum to one by POVM outcome weights are probabilities, so is the uniform-message block error probability.
Typical-projector bounds for finite quantum sources and cq ensembles
Statement
All logarithms are natural. First, for every density operator on a nonzero finite-dimensional space and every , there are spectral projectors for such that, as ,
Second, let be a finite nonempty set, let be a probability vector, and let be density operators on a nonzero finite-dimensional output space. Put and . For every , there are sets with , global spectral projectors for , and conditional spectral projectors for , such that one sequence satisfies, for every sufficiently large and every , Zero eigenvalues are omitted from surprisal sums. No identical-distribution assumption is made for the conditional eigenbasis measurements.
Facts & Assumptions
Given: The finite states, ensemble, and from the Statement.
Finite-alphabet IID information AEP with a variance bound: for a finite IID law, the average surprisal converges in probability to its entropy, with an explicit variance-over- tail bound.
Finite-dimensional von Neumann entropy: , with zero terms set to zero and units nats.
Finite classical-quantum states and Holevo information: is the finite ensemble average state.
Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely: each finite-dimensional density operator has an orthonormal eigenbasis with nonnegative eigenvalues.
A non-negative operator is equivalently self-adjoint with nonnegative eigenvalues, a positive semidefinite matrix in an orthonormal basis, or an operator of the form S^*S: a nonnegative operator with zero quadratic form at a vector annihilates that vector.
Chebyshev's inequality on a finite probability space and Variance, standard deviation, and covariance on a finite probability space: a finite random variable satisfies , and variance is the expected squared centered value.
Trace is a linear functional on : trace is linear over finite sums and scalar multiples.
Basic identities for a probability measure: the probability of a finite union is at most the sum of its event probabilities.
Density operator: every and is nonnegative with trace one.
Proof
Diagonalize by [F4], and sample with law . The surprisal is a finite-alphabet random variable of mean by [F2]. For a product eigenvector with coordinates , its eigenvalue is and its surprisal is by [F7]. Let project onto product eigenvectors whose total surprisal lies in . The probability of this set tends to one by [F1]. Every selected product eigenvalue is at most and at least ; the first bound gives the operator inequality, and the second together with total mass at most one gives the rank bound.
For an input word , let count its occurrences of . Define by when and for every . The coordinate indicators are independent under and have variance at most ; [F6]–[F9] give . For each with , by [F3] and [F10]; a vector in therefore has zero quadratic form for , so [F5] gives . The spectral logarithm on the latter positive support is bounded in finite dimension by [F4], making finite for every such . Define this family only for ; the zero-probability symbols never occur in . Choose small enough that the empirical averages of each of the two finite families and , restricted to , differ from their -averages by at most on . These choices are possible because both restricted families are finite and their entries are finite.
For each , diagonalize and, conditional on a fixed , measure each tensor factor in its chosen eigenbasis. The resulting surprisal variables are independent, finite, and uniformly bounded over the finite family of positive eigenvalues. By [F7], the product eigenvalue surprisal is their sum. Their means sum to , which is within of by step 1.2. Their sum has variance at most for a fixed finite bound ; independence makes cross-covariances zero. Chebyshev [F6] shows that the probability of leaving the window tends to zero uniformly over . Project onto the product eigenvectors whose surprisal lies in this window. Each selected eigenvalue is at most and at least , proving conditional acceptance, the operator bound, and the rank bound as in step 1.1.
By [F10], is a state and . Any has when , so [F5] gives . Hence . On that support, the variable obtained by measuring in an eigenbasis of is finite and uniformly bounded over with and positive eigenvalue index. Its mean is . The -average of these means is by [F2], [F3], and [F8].
For fixed , measuring the product state in the product eigenbasis of gives independent surprisal variables with means and a common finite bound on their absolute values. By [F7], each product eigenvalue surprisal is the sum of the coordinate surprisals. Their means sum to within of by step 1.2, and their sum has variance at most for a finite . Chebyshev [F6] therefore bounds uniformly by a quantity tending to zero the probability of leaving the -window around . The spectral projector of for that window accepts every such conditional product state with probability at least . Its rank and compressed-operator bounds follow from its eigenvalue window exactly as in step 1.1.
Take to be the maximum of the uniform failure bounds in steps 2.1 and 3.1; both tend to zero, so . The global state acceptance follows from step 1.1 applied to ; all conditional and operator/rank assertions are those proved in steps 2.1 and 3.1. The constructions use only finite spectra, finite sums, and finite probability spaces, so no choice axiom is invoked.
Finite-dimensional Schumacher quantum source coding theorem
Statement
Let be a density operator on a nonzero finite-dimensional source space, and use the squared entanglement-fidelity code model of Finite IID quantum source and compression code. Write in nats.
- For every there is a sequence of compression codes with and .
- If a sequence of codes satisfies , then .
Thus the asymptotic reliable compression rate is exactly nats per source letter, or qubits per source letter.
Facts & Assumptions
Given: A nonzero finite-dimensional source space, a density operator , and the compression-code convention of the Statement.
Finite IID quantum source and compression code: an code factors through an -dimensional code space, and its squared entanglement fidelity is the overlap of a purification with the recovered state.
Typical-projector bounds for finite quantum sources and cq ensembles: the spectral typical projector for has mass tending to one, rank at most , and every included eigenvalue is at most .
Compression dimension bounds entanglement fidelity: any code factoring through dimension has entanglement fidelity at most the sum of the largest eigenvalues of .
Finite-dimensional quantum channel: a quantum channel is completely positive and trace preserving.
Kraus and Choi characterizations of complete positivity and Trace preservation is Kraus normalization: finite channels have finite Kraus families, and a trace-preserving family satisfies .
Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely: finite-dimensional states have finite spectral decompositions in orthonormal eigenbases.
Proof
Fix , choose an ordered eigenbasis of once, and take the spectral typical projector from [F2]. Order its finitely many product eigenvectors lexicographically; the resulting map to the first standard code basis vectors defines a partial isometry with , where . Let the code space have dimension and let be its extra flag, orthogonal to . Define The encoder Kraus family consists of and over an orthonormal basis of ; its Kraus squares sum to . The decoder Kraus family consists of and from a spectral decomposition ; its Kraus squares sum to . Thus both maps are channels by [F4]–[F6]. If is the finite composite Kraus family, substituting its action into [F1] gives . The branch contributes , and every other branch contributes a nonnegative squared modulus. Therefore . The basis order makes the sequence of codes explicit and uses no choice axiom.
Suppose . Choose and so that for . Let be the typical projector from [F2], and let . Each eigenvalue in its range is at most . Therefore the sum of any eigenvalues of is at most : the part outside the typical range contributes at most its total mass, and each selected eigenvalue inside contributes at most the displayed maximum.
Since and , . Hence . Given , choose to obtain the direct assertion.
Apply [F3] to each -block code with intermediate dimension . Step 1.2 shows that its fidelity is at most a quantity tending to zero, hence . The argument includes zero eigenvalues and requires no full-rank source assumption.
Holevo–Schumacher–Westmoreland capacity theorem for finite cq channels
Statement
Let be a finite-input, finite-output memoryless cq channel as in Finite-input memoryless cq channel. With the average-error code convention of Finite cq block codes, average error, and capacity, its classical capacity in nats per use is For every a sequence of codes with rate tending to has average error tending to zero, and every reliable sequence has limiting upper rate at most . This theorem concerns a fixed finite classical input alphabet and does not assert a single-letter formula for general quantum-input channels.
Facts & Assumptions
Given: A finite nonempty alphabet , nonzero finite-dimensional output space , and one density operator for each input symbol.
Finite cq block codes, average error, and capacity: codes use a uniform finite message, deterministic input words, a finite decoding POVM, average block error, and rate nats/use.
The finite Holevo measurement bound: for any finite ensemble of states and any finite POVM, the classical mutual information of the input and the measurement outcome is at most the ensemble Holevo information.
Typical-projector bounds for finite quantum sources and cq ensembles: for a finite ensemble, a high-probability input typical set has conditional and global output projectors with exponentially controlled rank and operator bounds, and uniform acceptance error tending to zero.
Finite square-root measurement packing bound for cq states: projectors satisfying those four bounds give expected average decoding error at most .
Strong subadditivity of finite-dimensional quantum entropy: for every finite tripartite state, .
Continuity of finite-dimensional quantum entropy: entropy is continuous in operator norm on finite-dimensional state spaces, including at zero eigenvalues.
Finite-alphabet Fano inequality: for a finite message estimated from a finite observation with error probability , .
Finite entropy and mutual-information chain rules: for finite variables, .
Partial trace over a finite tensor factor and The partial trace is characterized by the trace pairing and is basis-independent: tracing tensor factors gives the usual marginals, is linear, and is independent of the chosen orthonormal basis.
Ordered tensor registers, their inner product, and wire permutations: the product basis is ordered factorwise and product operators act on their corresponding tensor factors.
Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely: finite-dimensional Hermitian states have orthonormal eigenbases.
Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: the natural logarithm is additive on finite products of positive numbers.
Heine-Borel in : with the Euclidean metric a subset of is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line and A continuous real-valued function on a nonempty compact metric space is bounded and attains a greatest and a least value: the closed probability simplex in finite-dimensional Euclidean space is compact, and a continuous real function on it attains a maximum.
The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: the operator norm is the maximum of over unit vectors .
Density operator: each output state is nonnegative and has trace one.
The partial trace is characterized by the trace pairing and is basis-independent and Trace is a linear functional on : product-state marginals and finite mixture marginals are computed by partial trace and finite linearity.
Proof
Write . The simplex is nonempty, closed, and bounded. For each state , [F12] diagonalizes it with nonnegative eigenvalues summing to one by [F16], so its action on a unit vector has norm at most one and [F15] gives . Therefore . Fix an orthonormal basis identifying unitarily with ; this preserves spectra and operator norm, so [F7] applies. Thus the first entropy term in is continuous in ; the second is a finite linear sum. Thus [F14] shows the supremum is attained, so . A point-mass input law gives by [F2], hence .
Fix and . Choose with . Let be the input typical set from [F4], with excluded probability . Since , for all sufficiently large ; for each earlier blocklength choose a fixed and use the one-message code with word and decoding POVM . Draw each large- codeword independently from conditioned on . Its mean output state is The global typical projector from [F4] therefore obeys . Each conditional projector has acceptance at least , rank at most , and the global projector accepts every conditioned codeword with at least , where and .
Consider any code with , uniform message , output states , decoding outcome , and average error . The Holevo measurement bound [F3] gives . Applying Fano [F8] and the finite mutual-information identity [F9], with , yields . For , [F2] gives , so the inequality is .
Since , choose large enough that and for every . For the finite prefix , set and use the one-message code from step 1.2. For , set and apply the packing lemma [F5] to the conditional input law on , with and . It gives expected average error at most Since for and , this tends to zero. Merge the packing POVM's failure effect into message 1: put and for . These effects are positive and sum to ; message 1's success increases by , while every other success is unchanged. Thus their average error obeys the same expectation bound, including . The codebook space is finite; order once and choose its lexicographically first codebook whose average error is at most this expectation. This defines a deterministic code for each without any choice axiom, and the finite one-message prefix does not affect .
Let and . By [F17], its th marginal is , which is a state by [F16]. For any bipartite state , tensor it with the unique state on a one-dimensional middle register : the four entropies in [F6] become , because tensoring with this factor leaves the spectrum unchanged. Thus [F6] implies ; iterating gives . Product entropy is additive: diagonalize each by [F12], so every positive product eigenvalue has logarithm equal to the sum of its coordinate logarithms by [F13]; zero eigenvalues contribute zero by [F2]. Summing these finite terms gives . Therefore
The selected codes have average error tending to zero and . If , the single-message code has zero error. When , taking a maximizing from step 1.1 proves achievability of every . When , the single-message code shows that rate zero is reliable.
Combining steps 1.3 and 2.2 gives . For any reliable sequence, divide by and let ; since , its limiting upper rate is at most . Together with step 3.1 and the capacity definition [F1], this proves the theorem.
5 · Examples, counterexamples and false statements
None yet.
Sources
- Mark M. Wilde, From Classical to Quantum Shannon Theory, second-edition prepublication v8, Lemma 9.4.2
- John Watrous, The Theory of Quantum Information, §3.1.2 and §3.2.3
- Mark M. Wilde, From Classical to Quantum Shannon Theory, second-edition prepublication v8, Appendix B
- John Watrous, The Theory of Quantum Information, Appendix B and §8.1.2
- Mark M. Wilde, From Classical to Quantum Shannon Theory, second-edition prepublication v8, Lemma 16.4.1
- John Watrous, The Theory of Quantum Information, §8.1.2
- Mark M. Wilde, From Classical to Quantum Shannon Theory, second-edition prepublication v8, Chapter 18 §§18.1–18.2
- John Watrous, The Theory of Quantum Information, §5.3.2
- Mark M. Wilde, From Classical to Quantum Shannon Theory, second-edition prepublication v8, §11.10
- John Watrous, The Theory of Quantum Information, §5.2.4
- Mark M. Wilde, From Classical to Quantum Shannon Theory, second-edition prepublication v8, Chapter 16
- John Watrous, The Theory of Quantum Information, Theorem 5.44 proof
- Mark M. Wilde, From Classical to Quantum Shannon Theory, second-edition prepublication v8, Chapter 18 §18.2.1
- Mark M. Wilde, From Classical to Quantum Shannon Theory, second-edition prepublication v8, Chapters 16 and 20
- Mark M. Wilde, From Classical to Quantum Shannon Theory, second-edition prepublication v8, §§16.2 and 20.3.1
- Mark M. Wilde, From Classical to Quantum Shannon Theory, second-edition prepublication v8, Chapter 15
- Mark M. Wilde, From Classical to Quantum Shannon Theory, second-edition prepublication v8, Chapter 18
- John Watrous, The Theory of Quantum Information, Theorem 5.44, §5.3.2