Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Uniform average error suffices for E=0 coherification

Open
QAlgorithms.Papers.Independent.Support50.P37.average_error_coherification

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

prove2quantum

Let UUU be a fixed bipartite unitary or isometry between nonzero finite-dimensional registers, and let c1,c2≥0c_1,c_2\ge0c1​,c2​≥0. Suppose finite protocols PnP_nPn​, using at most nnn calls to UUU and free local operations only, transmit independent uniform classical messages of lengths m1(n)m_1(n)m1​(n) and m2(n)m_2(n)m2​(n), with mi(n)≤ncim_i(n)\le n c_imi​(n)≤nci​ and mi(n)/n→cim_i(n)/n\to c_imi​(n)/n→ci​. Neither the protocol, its schedule, nor its register dimensions depends on the message pair. No external entanglement, shared random seed, side communication, or catalyst is supplied.

If the uniform average joint decoding success tends to one, then the same rates are achievable coherently:

12m1(n)+m2(n)∑a,bPr⁡[Pn(a,b)=(b,a)]⟶1⟹U⪰c1 cobits(→)+c2 cobits(←).\frac{1}{2^{m_1(n)+m_2(n)}}\sum_{a,b} \Pr[P_n(a,b)=(b,a)]\longrightarrow1 \quad\Longrightarrow\quad U\succeq c_1\ \mathrm{cobits}(\rightarrow)+c_2\ \mathrm{cobits}(\leftarrow).2m1​(n)+m2​(n)1​a,b∑​Pr[Pn​(a,b)=(b,a)]⟶1⟹U⪰c1​ cobits(→)+c2​ cobits(←).

Here aaa and bbb range over all respective bit strings, and (b,a)(b,a)(b,a) specifies Alice's and Bob's decoded outputs. The coherent conclusion has vanishing joint trace-distance error uniformly over normalized quantum inputs and untouched references, without supplied entanglement. This states the e=0e=0e=0 strengthening actually used in the construction, rather than an unspecified resource-assisted generalization.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P37
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Support50.P37

open QAlgorithms.Papers.Independent.Support21.P19

open QAlgorithms.Papers.Independent.Renew46.P34 (rateConstraint)

open scoped Matrix ComplexConjugate

attribute [local instance] Classical.propDecidable Classical.decEq

/-- PDF p.5, norm-squared identity for Gamma_00, and note [14] on p.12.
In the E=0 construction, a vanishing uniform average classical error suffices for
reference-uniform coherent transmission at the same rates, without an external seed. -/
theorem average_error_coherification (U : Resource) (hU : IsIsometricResource U)
    (C1 C2 : ℝ) (h : AchievesAverageClassical U C1 C2) :
    AchievesBidirectional U .coherent .coherent C1 C2 0 := by sorry

end QAlgorithms.Papers.Independent.Support50.P37

end
Source
Bidirectional coherent classical communication, arXiv:quant-ph/0412126v3, PDF p. 12, Note [14], with §III p.5
Read-back

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

Let UUU be a bipartite resource with positive finite input dimensions ai,bia_i,b_iai​,bi​, positive finite output dimensions ao,boa_o,b_oao​,bo​, and map X↦VXV†X\mapsto VXV^\daggerX↦VXV†, where V:Cai⊗Cbi→Cao⊗CboV:\mathbb C^{a_i}\otimes\mathbb C^{b_i}\to\mathbb C^{a_o}\otimes\mathbb C^{b_o}V:Cai​⊗Cbi​→Cao​⊗Cbo​ satisfies V†V=IV^\dagger V=IV†V=I. Here an allowed protocol is a finite composition of local channels and resource calls extended by local memory registers; a channel means a map X↦∑jKjXKj†X\mapsto\sum_j K_jXK_j^\daggerX↦∑j​Kj​XKj†​ with a finite Kraus family satisfying ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I. Suppose the real numbers C1,C2C_1,C_2C1​,C2​ are nonnegative and have the following property: for every ε,δ>0\varepsilon,\delta>0ε,δ>0, there is an integer n0≥1n_0\ge1n0​≥1 such that for every integer n≥n0n\ge n_0n≥n0​, there are nonnegative integers mf,mbm_f,m_bmf​,mb​ satisfying n(C1−δ)≤mf≤nC1n(C_1-\delta)\le m_f\le nC_1n(C1​−δ)≤mf​≤nC1​ and n(C2−δ)≤mb≤nC2n(C_2-\delta)\le m_b\le nC_2n(C2​−δ)≤mb​≤nC2​, and an allowed protocol FFF using at most nnn calls to UUU and no calls to supplied entangled-state, quantum-communication, coherent-communication, or classical-communication resources, whose input registers have dimensions 2mf,2mb2^{m_f},2^{m_b}2mf​,2mb​, whose output registers have dimensions 2mb,2mf2^{m_b},2^{m_f}2mb​,2mf​, and for which

12mf2mb∑a=02mf−1∑b=02mb−1Re⁡ ⁣[F(∣a,b⟩⟨a,b∣)(b,a),(b,a)]≥1−ε.\frac{1}{2^{m_f}2^{m_b}} \sum_{a=0}^{2^{m_f}-1}\sum_{b=0}^{2^{m_b}-1} \operatorname{Re}\!\left[F(|a,b\rangle\langle a,b|)_{(b,a),(b,a)}\right] \ge 1-\varepsilon.2mf​2mb​1​a=0∑2mf​−1​b=0∑2mb​−1​Re[F(∣a,b⟩⟨a,b∣)(b,a),(b,a)​]≥1−ε.

Then, for every ε,δ>0\varepsilon,\delta>0ε,δ>0, there is an integer n0≥1n_0\ge1n0​≥1 such that for every integer n≥n0n\ge n_0n≥n0​, there are nonnegative integers mf,mb,eom_f,m_b,e_omf​,mb​,eo​, with n(C1−δ)≤mfn(C_1-\delta)\le m_fn(C1​−δ)≤mf​ and n(C2−δ)≤mbn(C_2-\delta)\le m_bn(C2​−δ)≤mb​, and an allowed protocol using at most nnn calls to UUU and no supplied entanglement or additional communication resources, which approximates the tensor product of mfm_fmf​ forward coherent-bit channels, mbm_bmb​ backward coherent-bit channels, and preparation of eoe_oeo​ Bell pairs. A forward coherent-bit channel maps ∣x⟩⟨y∣|x\rangle\langle y|∣x⟩⟨y∣ to ∣x,x⟩⟨y,y∣|x,x\rangle\langle y,y|∣x,x⟩⟨y,y∣, retaining one copy of the basis label at Alice and placing the other at Bob; the backward channel reverses the parties, and each Bell pair is (∣00⟩+∣11⟩)/2(|00\rangle+|11\rangle)/\sqrt2(∣00⟩+∣11⟩)/2​. More precisely, writing TTT for this target map, the protocol map FFF has the same input and output registers as TTT, and for every positive integer rrr and every positive semidefinite, trace-one matrix ρ\rhoρ on an rrr-dimensional reference register together with the entire target input,

12∥(id⁡r⊗F)(ρ)−(id⁡r⊗T)(ρ)∥1≤ε,∥X∥1=Re⁡Tr⁡X†X.\frac12\left\|(\operatorname{id}_r\otimes F)(\rho) -(\operatorname{id}_r\otimes T)(\rho)\right\|_1\le\varepsilon, \qquad \|X\|_1=\operatorname{Re}\operatorname{Tr}\sqrt{X^\dagger X}.21​∥(idr​⊗F)(ρ)−(idr​⊗T)(ρ)∥1​≤ε,∥X∥1​=ReTrX†X​.

The conclusion places no upper bounds on mf,mbm_f,m_bmf​,mb​, and its entanglement rate 000 requires zero supplied Bell pairs while allowing any eo≥0e_o\ge0eo​≥0, without requiring positive entanglement production. Zero communication rates and zero output counts are included; zero tensor copies mean the identity resource on one-dimensional registers.

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