Definitions for Bidirectional coherent classical communication
DefinitionQAlgorithms_Papers_Independent_Support50_P37The 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).
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
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 and real numbers , this predicate requires and the following property: for every and , there is a natural number such that, for every natural number , there exist natural numbers with
and a matrix map from an Alice register of dimension and a Bob register of dimension to an Alice register of dimension and a Bob register of dimension , satisfying
The map must be obtainable by finitely composing local product channels and calls to alongside arbitrary finite local memory, with a count of at most calls to and zero calls to entangled-pair preparations or any auxiliary classical, coherent, or quantum communication resource. Each local channel has a finite Kraus representation with ; composition adds resource counts. No channel assumption on or separate channel assumption on 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 , forward and backward communication types , and real numbers , this predicate means the following. For every and , there is a natural number such that, for every natural number , there exist natural numbers satisfying the signed rate rule for the three pairs , , and : for a pair , if then and , whereas if then and . There must then exist a matrix map , with the input and output registers of the target resource, and a count for each resource kind, obtainable by finitely composing local channels and resource calls, such that the counts are at most calls to , entangled-pair preparations, forward resources of type , and backward resources of type , 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 with . 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 forward resources of type , reversed resources of type , and preparations of : 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 to . For every positive reference dimension and every density matrix on the reference and the complete target input, must satisfy
A density matrix means a positive semidefinite matrix of trace one. No sign restrictions on , no channel assumption on , and no separate channel assumption on 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
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 and any matrix map from matrices on to matrices on the same two registers in reversed order, this defines
There is no channel, positivity, or normalization assumption on . 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 , classical communication has a one-dimensional output at Alice and a two-dimensional output at Bob, with output entries ; quantum communication has the same input and output dimensions, with output entries . Coherent communication has two-dimensional outputs at both parties and sends to . 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 , this function assigns a natural-number allowance to each of eight resource kinds: the main resource receives allowance , an entangled-pair preparation receives allowance , forward quantum communication receives precisely when the forward type is quantum and otherwise receives zero, and backward quantum communication receives precisely when the backward type is quantum and otherwise receives zero. The same rule assigns or 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 , this defines the bipartite resource consisting of forward communication resources, backward communication resources, and resources preparing the state , where . 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 to . 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 acts on any input matrix by summing its entries against , 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 may be zero.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.