Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite Holevo optimization and attaining unitary encoding

Proved
QAlgorithms.Papers.Independent.Support50.P39.finiteHolevoOptimization

by Goku · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let ρAB\rho_{AB}ρAB​ be a normalized finite dimensional density operator, with both local dimensions positive and not necessarily equal. Fix n≥1n\ge1n≥1 resource copies and an output dimension d≥1d\ge1d≥1. All entropies are in bits. Define Hd(ρ⊗n)H_d(\rho^{\otimes n})Hd​(ρ⊗n) to be the supremum of the Holevo score

χ({pi,σi})=S ⁣(∑ipiσi)−∑ipiS(σi),σi=(Λi⊗id)(ρ⊗n),\chi(\{p_i,\sigma_i\})=S\!\left(\sum_i p_i\sigma_i\right)-\sum_i p_iS(\sigma_i), \qquad \sigma_i=(\Lambda_i\otimes\mathrm{id})(\rho^{\otimes n}),χ({pi​,σi​})=S(i∑​pi​σi​)−i∑​pi​S(σi​),σi​=(Λi​⊗id)(ρ⊗n),

over every finite probability distribution (pi)(p_i)(pi​) and CPTP maps Λi:A⊗n→Cd\Lambda_i:A^{\otimes n}\to\mathbb C^dΛi​:A⊗n→Cd. Then, with IB(σ)=max⁡{S(σB)−S(σ),0}I^B(\sigma)=\max\{S(\sigma_B)-S(\sigma),0\}IB(σ)=max{S(σB​)−S(σ),0},

Hd(ρ⊗n)=log⁡2d+supΛ:A⊗n→CdIB((Λ⊗id)(ρ⊗n)).H_d(\rho^{\otimes n})=\log_2d+sup_{\Lambda:A^{\otimes n}\to\mathbb C^d} I^B\bigl((\Lambda\otimes\mathrm{id})(\rho^{\otimes n})\bigr).Hd​(ρ⊗n)=log2​d+supΛ:A⊗n→Cd​IB((Λ⊗id)(ρ⊗n)).

An optimal channel Λ∗\Lambda_*Λ∗​ exists, together with d2d^2d2 unitaries UiU_iUi​ such that ∑iUiMUi†=0\sum_iU_iMU_i^\dagger=0∑i​Ui​MUi†​=0 for every traceless d×dd\times dd×d matrix MMM. With probabilities pi=d−2p_i=d^{-2}pi​=d−2, the encoders Ad(Ui)∘Λ∗\mathrm{Ad}(U_i)\circ\Lambda_*Ad(Ui​)∘Λ∗​ attain HdH_dHd​. Moreover, the same unitary family works for every CPTP preprocessing Λ\LambdaΛ: its encoding ensemble is admissible and, writing σ=(Λ⊗id)(ρ⊗n)\sigma=(\Lambda\otimes\mathrm{id})(\rho^{\otimes n})σ=(Λ⊗id)(ρ⊗n), its score is exactly

χ=log⁡2d+S(ρB⊗n)−S(σ).\chi=\log_2d+S(\rho_B^{\otimes n})-S(\sigma).χ=log2​d+S(ρB⊗n​)−S(σ).

The last identity uses the signed entropy difference, even if negative. Only the optimized expression can use clipped coherent information. The statement includes d=1d=1d=1, when the optimized value is zero and the unitary family has one member.

This is the finite optimization identity proved on pp.4–5. It supplies an explicit attaining ensemble without equating the objective to the unrestricted fixed-(d,n)(d,n)(d,n) operational capacity.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P39
Formal statement
namespace QAlgorithms.Papers.Independent.Support50.P39

noncomputable section

open QAlgorithms

open Filter Topology

open scoped Matrix ComplexConjugate ComplexOrder

attribute [local instance] Classical.propDecidable Classical.decEq

/-- arXiv:quant-ph/0106080v3, PDF pp.4--6, Eqs. (9)--(13): the finite
Holevo objective H_d equals log2 d plus optimized clipped coherent information,
and an optimal CPTP map and d^2-element unitary encoding attain it.
The SAME twirling family gives, for EVERY preprocessing map, the signed
per-map identity chi=log2 d+S(B^n)-S(sigma). Clipping is used only at the
optimized value. This includes d=1 (both sides zero) and does not identify
H_d with the unrestricted fixed-(d,n) operational capacity. -/
theorem finiteHolevoOptimization {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] [Nonempty A] [Nonempty B]
    (rho : Matrix (A × B) (A × B) ℂ) (hrho : IsDensityMatrix rho)
    (n d : ℕ) (hn : 0 < n) (hd : 0 < d) :
    denseCodingHolevoValue rho n d = Real.logb 2 d + finiteCoherentOpt rho n d ∧
    ∃ Phi : Superop (Fin n → A) (Fin d), IsChannel Phi ∧
      clippedCoherentInformation (aliceAction Phi (noisyResourceCopies rho n)) =
        finiteCoherentOpt rho n d ∧
      ∃ U : Fin (d*d) → Matrix.unitaryGroup (Fin d) ℂ,
        TracelessTwirling U ∧
        (∀ Psi : Superop (Fin n → A) (Fin d), IsChannel Psi →
          IsEncoding (uniformWeight d) (unitaryEncoders Psi U) ∧
          encodingHolevo rho n (uniformWeight d) (unitaryEncoders Psi U) =
            Real.logb 2 d + vnEntropy (traceLeft (noisyResourceCopies rho n)) -
              vnEntropy (aliceAction Psi (noisyResourceCopies rho n))) ∧
        encodingHolevo rho n (uniformWeight d) (unitaryEncoders Phi U) =
          denseCodingHolevoValue rho n d := by sorry

end

end QAlgorithms.Papers.Independent.Support50.P39
Source
Classical capacity of a noiseless quantum channel assisted by noisy entanglement, arXiv:quant-ph/0106080v3, PDF p. 4, RHS of Eq. (9) and Eqs. (10)–(13)
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

Let A,BA,BA,B be finite, nonempty types with decidable equality, let ρ\rhoρ be a positive semidefinite complex matrix on A×BA\times BA×B with trace 111, and let n,d∈Nn,d\in\mathbb Nn,d∈N satisfy n>0,d>0n>0,d>0n>0,d>0, including the possibility d=1d=1d=1. Write S(X)=−Re⁡tr⁡(f(X))S(X)=-\operatorname{Re}\operatorname{tr}(f(X))S(X)=−Retr(f(X)), with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t applied by continuous functional calculus. Let ρ(a,b),(a′,b′)[n]=∏t=0n−1ρ(at,bt),(at′,bt′)\rho^{[n]}_{(a,b),(a',b')}=\prod_{t=0}^{n-1}\rho_{(a_t,b_t),(a'_t,b'_t)}ρ(a,b),(a′,b′)[n]​=∏t=0n−1​ρ(at​,bt​),(at′​,bt′​)​, and, for a map Ψ\PsiΨ on Alice's matrices, let ωΨ=(Ψ⊗id)(ρ[n])\omega_\Psi=(\Psi\otimes\mathrm{id})(\rho^{[n]})ωΨ​=(Ψ⊗id)(ρ[n]), meaning that Ψ\PsiΨ is applied to each Alice matrix block with Bob's row and column fixed. Write XBX_BXB​ for the partial trace over Alice and set J(X)=max⁡{S(XB)−S(X),0}J(X)=\max\{S(X_B)-S(X),0\}J(X)=max{S(XB​)−S(X),0}. A channel is a map with a finite Kraus representation Ψ(X)=∑jEjXEj†\Psi(X)=\sum_jE_jXE_j^\daggerΨ(X)=∑j​Ej​XEj†​ satisfying ∑jEj†Ej=I\sum_jE_j^\dagger E_j=I∑j​Ej†​Ej​=I. For a finite ensemble of channels Ei:An→{0,…,d−1}E_i:A^n\to\{0,\ldots,d-1\}Ei​:An→{0,…,d−1}, indexed by i=0,…,l−1i=0,\ldots,l-1i=0,…,l−1, with l>0l>0l>0, real pi≥0p_i\ge0pi​≥0, and ∑ipi=1\sum_ip_i=1∑i​pi​=1, define

χ(p,E)=S ⁣(∑ipiωEi)−∑ipiS(ωEi).\chi(p,E)=S\!\left(\sum_i p_i\omega_{E_i}\right)-\sum_i p_iS(\omega_{E_i}).χ(p,E)=S(i∑​pi​ωEi​​)−i∑​pi​S(ωEi​​).

Let Hn,dH_{n,d}Hn,d​ be the real supremum of all these χ(p,E)\chi(p,E)χ(p,E), and let Fn,dF_{n,d}Fn,d​ be the real supremum of J(ωΨ)J(\omega_\Psi)J(ωΨ​) over all channels Ψ:An→{0,…,d−1}\Psi:A^n\to\{0,\ldots,d-1\}Ψ:An→{0,…,d−1}. The declaration asserts Hn,d=log⁡2d+Fn,dH_{n,d}=\log_2d+F_{n,d}Hn,d​=log2​d+Fn,d​, and asserts that there exist such a channel Φ\PhiΦ and a family of d2d^2d2 unitary d×dd\times dd×d matrices UiU_iUi​ satisfying J(ωΦ)=Fn,dJ(\omega_\Phi)=F_{n,d}J(ωΦ​)=Fn,d​ and

∑i=0d2−1UiMUi†=0for every complex d×d matrix M with tr⁡M=0.\sum_{i=0}^{d^2-1}U_iMU_i^\dagger=0 \quad\text{for every complex }d\times d\text{ matrix }M\text{ with }\operatorname{tr}M=0.i=0∑d2−1​Ui​MUi†​=0for every complex d×d matrix M with trM=0.

For this same family UiU_iUi​, every channel Ψ:An→{0,…,d−1}\Psi:A^n\to\{0,\ldots,d-1\}Ψ:An→{0,…,d−1} gives an ensemble of channels EiΨ(X)=UiΨ(X)Ui†E_i^\Psi(X)=U_i\Psi(X)U_i^\daggerEiΨ​(X)=Ui​Ψ(X)Ui†​, with positive ensemble size d2d^2d2, nonnegative weights pi=1/d2p_i=1/d^2pi​=1/d2 summing to 111, and

χ(p,EΨ)=log⁡2d+S ⁣((ρ[n])B)−S(ωΨ).\chi(p,E^\Psi)=\log_2d+S\!\left((\rho^{[n]})_B\right)-S(\omega_\Psi).χ(p,EΨ)=log2​d+S((ρ[n])B​)−S(ωΨ​).

For the particular channel Φ\PhiΦ chosen above, this ensemble additionally satisfies χ(p,EΦ)=Hn,d\chi(p,E^\Phi)=H_{n,d}χ(p,EΦ)=Hn,d​.

Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me