Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Bidirectional coherent classical communication

Definition
QAlgorithms_Papers_Independent_Support50_P37

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

prove2quantum

The objects the formalized statements of Bidirectional coherent classical communication (arXiv:quant-ph/0412126) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • Communication: PDF p.2: the three distinct communication resources; direction is specified separately.
  • communicationResource: PDF p.2: a single forward bit, coherent bit, or qubit, with the source's channel action.
  • outputTask: PDF p.2, Eq.(1): independent forward/backward output blocks and output EPR pairs. The tensor ordering groups registers by owner. A zero-copy block has singleton ports.
  • inputBudget: PDF p.2: the complete consumed-resource budget. Only the selected communication kind in each direction is available; EPR pairs and every use of U are separately counted.
  • AchievesBidirectional: PDF p.2, Eq.(1) and signed-rate paragraph: simultaneous signed achievability. Negative rates supply calls, nonnegative rates require outputs, with no external input of a zero-rate resource. The accepted rateConstraint bounds inputs by n*(-rate+delta) or outputs below by n*(rate-delta). All resource counts and the actual sequential protocol precede every normalized input and reference in ErrorOn. Local CPTP operations include free local ancillas and discarding; no shared state, feedback, or catalyst is free. The same error bound applies jointly to both outputs and the produced EPR pairs.
  • averageSuccess: PDF pp.3,5, Eq.(4) and note [14] on p.12: uniform average joint decoding success. Inputs are normalized computational-basis projectors. Alice's decoded output is b, Bob's is a; the mean runs over all 2^(mf+mb) independent, equiprobable message pairs.
  • AchievesAverageClassical: PDF pp.3–7 and note [14] on p.12: the E=0 input hypothesis with average error. The finite protocol uses only U and free local operations, with no supplied EPR pair, side communication, shared random seed, or catalyst. Its schedule and maps are fixed before both messages. Local measurements are included in the final local CPTP maps; these maps can be purified, retaining their local environments, as in Eq.(5). Message lengths approach the two nonnegative rates as in the paragraph above Eq.(4).
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Papers_Independent_Support21_P19
import Definitions.Def_QAlgorithms_Papers_Independent_Renew46_P34

/-! Harrow–Leung, quant-ph/0412126v3. The six stated nodes use actual finite
sequential protocols. The signed RSP-region claim is deferred in HARD.md.
Compilation is pending the batch mechanical handoff. -/

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.2: the three distinct communication resources; direction is specified separately. -/
inductive Communication where
  | classical | coherent | quantum
  deriving DecidableEq

/-- PDF p.2: a single forward bit, coherent bit, or qubit, with the source's channel action. -/
def communicationResource : Communication → Resource
  | .classical => cbitChannel 2
  | .coherent => cobitChannel 2
  | .quantum => qubitChannel 2

/-- PDF p.2, Eq.(1): independent forward/backward output blocks and output EPR pairs.
The tensor ordering groups registers by owner. A zero-copy block has singleton ports. -/
def outputTask (forward backward : Communication) (mf mb eo : ℕ) : Resource :=
  tensorResources
    (tensorResources (resourceTensorCopies (communicationResource forward) mf)
      (resourceTensorCopies (reverse (communicationResource backward)) mb))
    (resourceTensorCopies (entangled 2) eo)

/-- PDF p.2: the complete consumed-resource budget. Only the selected communication
kind in each direction is available; EPR pairs and every use of U are separately counted. -/
def inputBudget (forward backward : Communication) (n ei fi bi : ℕ) : Kind → ℕ
  | .main => n
  | .ebit => ei
  | .qubitF => if forward = .quantum then fi else 0
  | .qubitB => if backward = .quantum then bi else 0
  | .cobitF => if forward = .coherent then fi else 0
  | .cobitB => if backward = .coherent then bi else 0
  | .cbitF => if forward = .classical then fi else 0
  | .cbitB => if backward = .classical then bi else 0

/-- PDF p.2, Eq.(1) and signed-rate paragraph: simultaneous signed achievability.
Negative rates supply calls, nonnegative rates require outputs, with no external input
of a zero-rate resource. The accepted rateConstraint bounds inputs by n*(-rate+delta)
or outputs below by n*(rate-delta). All resource counts and the actual sequential
protocol precede every normalized input and reference in ErrorOn. Local CPTP operations
include free local ancillas and discarding; no shared state, feedback, or catalyst is free.
The same error bound applies jointly to both outputs and the produced EPR pairs. -/
def AchievesBidirectional (U : Resource) (forward backward : Communication)
    (C1 C2 E : ℝ) : Prop :=
  ∀ eps > (0 : ℝ), ∀ delta > (0 : ℝ), ∃ n0 : ℕ, 1 ≤ n0 ∧ ∀ n ≥ n0,
    ∃ fi bi ei mf mb eo : ℕ,
      rateConstraint fi mf n C1 delta ∧ rateConstraint bi mb n C2 delta ∧
      rateConstraint ei eo n E delta ∧
      let target := outputTask forward backward mf mb eo
      ∃ v : Kind → ℕ, (∀ k, v k ≤ inputBudget forward backward n ei fi bi k) ∧
      ∃ F : Superop (Fin target.ai × Fin target.bi) (Fin target.ao × Fin target.bo),
        Sequential (D := Unit) (library U) target.ai target.bi target.ao target.bo v
          (fun _ => F) ∧ ErrorOn F target.map (fun _ => True) eps

/-- PDF pp.3,5, Eq.(4) and note [14] on p.12: uniform average joint decoding success.
Inputs are normalized computational-basis projectors. Alice's decoded output is b,
Bob's is a; the mean runs over all 2^(mf+mb) independent, equiprobable message pairs. -/
def averageSuccess {mf mb : ℕ}
    (F : Superop (Fin (2^mf) × Fin (2^mb)) (Fin (2^mb) × Fin (2^mf))) : ℝ :=
  (∑ a : Fin (2^mf), ∑ b : Fin (2^mb),
    (F (Matrix.single (a,b) (a,b) 1) (b,a) (b,a)).re) /
      ((2 : ℝ)^mf * (2 : ℝ)^mb)

/-- PDF pp.3–7 and note [14] on p.12: the E=0 input hypothesis with average error.
The finite protocol uses only U and free local operations, with no supplied EPR pair,
side communication, shared random seed, or catalyst. Its schedule and maps are fixed
before both messages. Local measurements are included in the final local CPTP maps;
these maps can be purified, retaining their local environments, as in Eq.(5).
Message lengths approach the two nonnegative rates as in the paragraph above Eq.(4). -/
def AchievesAverageClassical (U : Resource) (C1 C2 : ℝ) : Prop :=
  0 ≤ C1 ∧ 0 ≤ C2 ∧
    ∀ eps > (0 : ℝ), ∀ delta > (0 : ℝ), ∃ n0 : ℕ, 1 ≤ n0 ∧ ∀ n ≥ n0,
      ∃ mf mb : ℕ,
        (n : ℝ)*(C1-delta) ≤ mf ∧ (mf : ℝ) ≤ n*C1 ∧
        (n : ℝ)*(C2-delta) ≤ mb ∧ (mb : ℝ) ≤ n*C2 ∧
        ∃ v : Kind → ℕ, (∀ k, v k ≤ budget n 0 0 0 0 0 0 0 k) ∧
        ∃ F : Superop (Fin (2^mf) × Fin (2^mb)) (Fin (2^mb) × Fin (2^mf)),
          Sequential (D := Unit) (library U) (2^mf) (2^mb) (2^mb) (2^mf) v
            (fun _ => F) ∧ 1-eps ≤ averageSuccess F

/-- PDF p.2: the zero-copy target still has nonempty physical ports. -/
example : (outputTask .coherent .quantum 0 0 0).ai = 1 ∧
    (outputTask .coherent .quantum 0 0 0).bo = 1 := by
  constructor <;> rfl

/-- PDF p.2: an unassisted budget forbids both backward communication and supplied EPR pairs. -/
example (n : ℕ) : inputBudget .classical .coherent n 0 0 0 .cbitB = 0 ∧
    inputBudget .classical .coherent n 0 0 0 .ebit = 0 := by
  simp [inputBudget]

/-- PDF p.2: zero rate cannot borrow an external input, including at zero block length. -/
example (used produced : ℕ) (delta : ℝ) :
    rateConstraint used produced 0 0 delta ↔ used = 0 := by
  simp [rateConstraint]

/-- PDF p.2: coherent transmission retains off-diagonal terms, unlike a dephasing cbit. -/
example : communicationResource .coherent = cobitChannel 2 ∧
    communicationResource .classical = cbitChannel 2 := by
  constructor <;> rfl

/-- PDF pp.3,5: the empty message pair is a singleton, with success one under identity. -/
example : averageSuccess (mf := 0) (mb := 0) (fun M => M) = 1 := by
  simp [averageSuccess, Matrix.single_apply]

end QAlgorithms.Papers.Independent.Support50.P37
Source
Bidirectional coherent classical communication, arXiv:quant-ph/0412126v3, https://arxiv.org/abs/quant-ph/0412126v3
Read-back

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

QAlgorithms.Papers.Independent.Support50.P37.AchievesAverageClassical

For any bipartite resource UUU and real numbers C1,C2C_1,C_2C1​,C2​, this predicate requires C1,C2≥0C_1,C_2\ge0C1​,C2​≥0 and the following property: for every ε>0\varepsilon>0ε>0 and δ>0\delta>0δ>0, there is a natural number n0≥1n_0\ge1n0​≥1 such that, for every natural number n≥n0n\ge n_0n≥n0​, there exist natural numbers mf,mbm_f,m_bmf​,mb​ with

n(C1−δ)≤mf≤nC1,n(C2−δ)≤mb≤nC2,n(C_1-\delta)\le m_f\le nC_1, \qquad n(C_2-\delta)\le m_b\le nC_2,n(C1​−δ)≤mf​≤nC1​,n(C2​−δ)≤mb​≤nC2​,

and a matrix map FFF from an Alice register of dimension 2mf2^{m_f}2mf​ and a Bob register of dimension 2mb2^{m_b}2mb​ to an Alice register of dimension 2mb2^{m_b}2mb​ and a Bob register of dimension 2mf2^{m_f}2mf​, satisfying

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]\ge1-\varepsilon.2mf​2mb​1​a=0∑2mf​−1​b=0∑2mb​−1​Re[F(∣a,b⟩⟨a,b∣)(b,a),(b,a)​]≥1−ε.

The map FFF must be obtainable by finitely composing local product channels and calls to UUU alongside arbitrary finite local memory, with a count of at most nnn calls to UUU and zero calls to entangled-pair preparations or any auxiliary classical, coherent, or quantum communication resource. Each local channel has a finite Kraus representation X↦∑jKjXKj†X\mapsto\sum_jK_jXK_j^\daggerX↦∑j​Kj​XKj†​ with ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I; composition adds resource counts. No channel assumption on UUU or separate channel assumption on FFF is imposed. Message lengths zero are allowed, and a zero rate forces the corresponding message length to be zero.

QAlgorithms.Papers.Independent.Support50.P37.AchievesBidirectional

For any bipartite resource UUU, forward and backward communication types s,ts,ts,t, and real numbers C1,C2,EC_1,C_2,EC1​,C2​,E, this predicate means the following. For every ε>0\varepsilon>0ε>0 and δ>0\delta>0δ>0, there is a natural number n0≥1n_0\ge1n0​≥1 such that, for every natural number n≥n0n\ge n_0n≥n0​, there exist natural numbers fi,bi,ei,mf,mb,eof_i,b_i,e_i,m_f,m_b,e_ofi​,bi​,ei​,mf​,mb​,eo​ satisfying the signed rate rule for the three pairs (fi,mf,C1)(f_i,m_f,C_1)(fi​,mf​,C1​), (bi,mb,C2)(b_i,m_b,C_2)(bi​,mb​,C2​), and (ei,eo,E)(e_i,e_o,E)(ei​,eo​,E): for a pair (u,v,r)(u,v,r)(u,v,r), if r<0r<0r<0 then v=0v=0v=0 and u≤n(−r+δ)u\le n(-r+\delta)u≤n(−r+δ), whereas if r≥0r\ge0r≥0 then u=0u=0u=0 and n(r−δ)≤vn(r-\delta)\le vn(r−δ)≤v. There must then exist a matrix map FFF, with the input and output registers of the target resource, and a count vkv_kvk​ for each resource kind, obtainable by finitely composing local channels and resource calls, such that the counts are at most nnn calls to UUU, eie_iei​ entangled-pair preparations, fif_ifi​ forward resources of type sss, and bib_ibi​ backward resources of type ttt, with no calls to the other communication kinds. A local step is a product of an Alice channel and a Bob channel; a channel here has a finite Kraus representation X↦∑jKjXKj†X\mapsto\sum_jK_jXK_j^\daggerX↦∑j​Kj​XKj†​ with ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I. A resource call may act alongside arbitrary finite local memory, leaving that memory unchanged, and composition adds the call counts. The target is the tensor product of mfm_fmf​ forward resources of type sss, mbm_bmb​ reversed resources of type ttt, and eoe_oeo​ preparations of (∣00⟩+∣11⟩)/2(|00\rangle+|11\rangle)/\sqrt2(∣00⟩+∣11⟩)/2​: a classical resource deletes off-diagonal entries and transfers the input to the other party, a quantum resource transfers it unchanged, and a coherent resource maps ∣i⟩⟨j∣|i\rangle\langle j|∣i⟩⟨j∣ to ∣i,i⟩⟨j,j∣|i,i\rangle\langle j,j|∣i,i⟩⟨j,j∣. For every positive reference dimension and every density matrix MMM on the reference and the complete target input, FFF must satisfy

12Re⁡tr⁡D†D≤ε,D=(id⁡⊗F)(M)−(id⁡⊗target)(M).\frac12\operatorname{Re}\operatorname{tr}\sqrt{D^\dagger D}\le\varepsilon, \qquad D=(\operatorname{id}\otimes F)(M) -(\operatorname{id}\otimes\mathrm{target})(M).21​RetrD†D​≤ε,D=(id⊗F)(M)−(id⊗target)(M).

A density matrix means a positive semidefinite matrix of trace one. No sign restrictions on C1,C2,EC_1,C_2,EC1​,C2​,E, no channel assumption on UUU, and no separate channel assumption on FFF are included; zero rates use the nonnegative branch of the rate rule, and the production counts have no upper bounds imposed by that rule.

QAlgorithms.Papers.Independent.Support50.P37.Communication

Communication\mathrm{Communication}Communication is a type with exactly three distinct values, called classical, coherent, and quantum, and equality between its values is decidable.

QAlgorithms.Papers.Independent.Support50.P37.averageSuccess

For arbitrary natural numbers mf,mbm_f,m_bmf​,mb​ and any matrix map FFF from matrices on {0,…,2mf−1}×{0,…,2mb−1}\{0,\ldots,2^{m_f}-1\}\times\{0,\ldots,2^{m_b}-1\}{0,…,2mf​−1}×{0,…,2mb​−1} to matrices on the same two registers in reversed order, this defines

averageSuccess⁡(F)=12mf2mb∑a=02mf−1∑b=02mb−1Re⁡ ⁣[F(∣a,b⟩⟨a,b∣)(b,a),(b,a)].\operatorname{averageSuccess}(F) = \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\bigl(|a,b\rangle\langle a,b|\bigr)_{(b,a),(b,a)} \right].averageSuccess(F)=2mf​2mb​1​a=0∑2mf​−1​b=0∑2mb​−1​Re[F(∣a,b⟩⟨a,b∣)(b,a),(b,a)​].

There is no channel, positivity, or normalization assumption on FFF. Either message length may be zero, in which case its register has one basis value; the denominator is always positive.

QAlgorithms.Papers.Independent.Support50.P37.communicationResource

This function assigns a bipartite resource to each communication type. Each resource has a two-dimensional input at Alice and a one-dimensional input at Bob. Writing its input matrix as X=(Xij)i,j=0,1X=(X_{ij})_{i,j=0,1}X=(Xij​)i,j=0,1​, classical communication has a one-dimensional output at Alice and a two-dimensional output at Bob, with output entries δijXij\delta_{ij}X_{ij}δij​Xij​; quantum communication has the same input and output dimensions, with output entries XijX_{ij}Xij​. Coherent communication has two-dimensional outputs at both parties and sends XXX to ∑i,j=01Xij∣i,i⟩⟨j,j∣\sum_{i,j=0}^{1}X_{ij}|i,i\rangle\langle j,j|∑i,j=01​Xij​∣i,i⟩⟨j,j∣. Thus these are particular matrix maps, with no further parameters.

QAlgorithms.Papers.Independent.Support50.P37.inputBudget

For any forward and backward communication types and natural numbers n,ei,fi,bin,e_i,f_i,b_in,ei​,fi​,bi​, this function assigns a natural-number allowance to each of eight resource kinds: the main resource receives allowance nnn, an entangled-pair preparation receives allowance eie_iei​, forward quantum communication receives fif_ifi​ precisely when the forward type is quantum and otherwise receives zero, and backward quantum communication receives bib_ibi​ precisely when the backward type is quantum and otherwise receives zero. The same rule assigns fif_ifi​ or bib_ibi​ to the corresponding coherent communication kind when that direction’s type is coherent, and to the corresponding classical communication kind when that direction’s type is classical. Thus exactly one forward communication kind and one backward communication kind receive their respective specified allowances; all four numbers may be zero.

QAlgorithms.Papers.Independent.Support50.P37.outputTask

For any forward and backward communication types and any natural numbers mf,mb,eom_f,m_b,e_omf​,mb​,eo​, this defines the bipartite resource consisting of mfm_fmf​ forward communication resources, mbm_bmb​ backward communication resources, and eoe_oeo​ resources preparing the state ∣Φ2⟩⟨Φ2∣|\Phi_2\rangle\langle\Phi_2|∣Φ2​⟩⟨Φ2​∣, where ∣Φ2⟩=(∣0,0⟩+∣1,1⟩)/2|\Phi_2\rangle=(|0,0\rangle+|1,1\rangle)/\sqrt2∣Φ2​⟩=(∣0,0⟩+∣1,1⟩)/2​. A classical resource transfers Alice’s two-dimensional input to Bob after deleting its off-diagonal entries; a quantum resource transfers that input unchanged; a coherent resource sends each matrix unit ∣i⟩⟨j∣|i\rangle\langle j|∣i⟩⟨j∣ to ∣i,i⟩⟨j,j∣|i,i\rangle\langle j,j|∣i,i⟩⟨j,j∣. A backward resource is obtained by exchanging Alice’s and Bob’s input and output registers in the corresponding forward resource. The resources are combined by tensor products, first combining the forward and backward factors and then the entangled-state factors, grouping each party’s registers using the finite-product indexing equivalences. More explicitly, combining resources R,SR,SR,S acts on any input matrix XXX by summing its entries against R(∣x⟩⟨y∣)⊗S(∣u⟩⟨v∣)R(|x\rangle\langle y|)\otimes S(|u\rangle\langle v|)R(∣x⟩⟨y∣)⊗S(∣u⟩⟨v∣), with the input and output registers regrouped by party. Zero copies of any resource mean the identity resource on one-dimensional registers at both parties, so any or all of mf,mb,eom_f,m_b,e_omf​,mb​,eo​ may be zero.

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