Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem A.10: For CP-unital phi:Y→X,psi:X→A and Tr phi(B)≤Tr B for positive B, H(psi∘phi)≥H(psi).

Proved
QAlgorithms.Papers.Independent.Renew46.P43.entropyIncrease

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

prove2quantum

Fix a normalized ambient state. Let ϕ:Y→X\phi:Y\to Xϕ:Y→X and ψ:X→A\psi:X\to Aψ:X→A be CP-unital Heisenberg operations, with Tr⁡ϕ(T)≤Tr⁡T\operatorname{Tr}\phi(T)\le\operatorname{Tr}TTrϕ(T)≤TrT for every positive TTT. Define H(ψ)=H(ψ∗ρ)H(\psi)=H(\psi_*\rho)H(ψ)=H(ψ∗​ρ). Composition reverses the physical state-map order; compatibility is not assumed.

H(ψ∘ϕ)≥H(ψ).H(\psi\circ\phi)\ge H(\psi).H(ψ∘ϕ)≥H(ψ).

This is the source result with its stated operational or information-theoretic domain.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Renew46_P43
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Renew46.P43

open scoped BigOperators Matrix ComplexConjugate ComplexOrder ENNReal Matrix.Norms.L2Operator

open Filter MeasureTheory

open QAlgorithms.Papers.Independent.Information100.P08 (IsPure)

open QAlgorithms.Papers.Independent.Information100.P06 (Below)

open QAlgorithms.Papers.Independent.Information100.P60 (copies relativeBits)

open QAlgorithms.Papers.Independent.Dependency50.P19 (count both)

open QAlgorithms.Papers.Independent.Information100.P22 (coherentInformation)

attribute [local instance] Classical.propDecidable Classical.decEq

open QAlgorithms.Papers.Independent.Claimed50.P40 (InBlocks)

attribute [local instance] QAlgorithms.Papers.Independent.Renew46.P43.matrixMeasurableSpace

/-- Theorem A.10, PDF pp.70-71: composition reverses state-map order. No
compatibility assumption is needed for these composable quantum operations. -/
theorem entropyIncrease {Y X A : IntrinsicSystem} (F : IntrinsicOperation Y X) (G : IntrinsicOperation X A)
    (htrace : TraceNonincreasing F) (rho : Matrix (Fin A.dim) (Fin A.dim) ℂ)
    (hrho : A.IsState rho) :
    viewedEntropy Y (G.map.comp F.map) rho ≥ viewedEntropy X G.map rho := by sorry

end QAlgorithms.Papers.Independent.Renew46.P43

end
Source
Coding Theorems of Quantum Information Theory, arXiv:quant-ph/9907077v1, PDF p. 70, Theorem A.10
Read-back

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

Let Y,X,AY,X,AY,X,A be systems with positive finite dimensions and natural number block labels on their basis indices, and call a matrix block diagonal if its entries vanish between different labels. Let FFF be a complex linear map from matrices on YYY to matrices on XXX, and GGG a complex linear map from matrices on XXX to matrices on AAA. Assume that both maps preserve the identity and block diagonality and that, at every finite amplification size r≥0r\ge0r≥0, applying the map to each matrix block preserves positive semidefiniteness for inputs whose entries vanish between different source block labels. Assume further that every positive semidefinite block diagonal matrix TTT on YYY satisfies Re⁡tr⁡F(T)≤Re⁡tr⁡T\operatorname{Re}\operatorname{tr}F(T)\le\operatorname{Re}\operatorname{tr}TRetrF(T)≤RetrT. Let ρ\rhoρ be a positive semidefinite block diagonal matrix on AAA with trace 111. Define matrices σX\sigma_XσX​ and σY\sigma_YσY​ by

(σX)ij={tr⁡ ⁣(ρ G(EjiX)),bX(i)=bX(j),0,otherwise,(σY)ij={tr⁡ ⁣(ρ G(F(EjiY))),bY(i)=bY(j),0,otherwise,(\sigma_X)_{ij}= \begin{cases} \operatorname{tr}\!\bigl(\rho\,G(E^X_{ji})\bigr),&b_X(i)=b_X(j),\\ 0,&\text{otherwise}, \end{cases} \qquad (\sigma_Y)_{ij}= \begin{cases} \operatorname{tr}\!\bigl(\rho\,G(F(E^Y_{ji}))\bigr),&b_Y(i)=b_Y(j),\\ 0,&\text{otherwise}, \end{cases}(σX​)ij​={tr(ρG(EjiX​)),0,​bX​(i)=bX​(j),otherwise,​(σY​)ij​={tr(ρG(F(EjiY​))),0,​bY​(i)=bY​(j),otherwise,​

where EjiXE^X_{ji}EjiX​ and EjiYE^Y_{ji}EjiY​ are the respective matrix units. Then

S(σY)≥S(σX),S(\sigma_Y)\ge S(\sigma_X),S(σY​)≥S(σX​),

where S(M)=−Re⁡tr⁡(f(M))S(M)=-\operatorname{Re}\operatorname{tr}(f(M))S(M)=−Retr(f(M)) and f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t is applied by continuous functional calculus.

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

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 22, 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