Definitions for Capacities of repeater-assisted quantum communications
DefinitionQAlgorithms_Papers_Independent_Support50_P47The objects the formalized statements of Capacities of repeater-assisted quantum communications (arXiv:1601.00966) are stated in. Each was checked against the paper by a blind read-back and a moderator.
WeightedNetwork: PDF pp.16,23–24: an undirected weighted network with individually labelled edges. Endpoint ordering is only a representation; routes may traverse either way. Distinct labels may have the same endpoints, retaining parallel edges. Finiteness and connectedness are imposed in the proposition, not by this data.Route: PDF pp.16,23–24: a nonempty simple route, including its actual edge labels. Injectivity forbids repeated vertices. The first and last vertices are fixed; there is no independently supplied collection that could omit legal routes.IsConnected: PDF pp.23–24: every pair of distinct vertices has a simple route. On a singleton graph this is vacuous, but the proposition requires a ≠ b.routeWeight: PDF pp.23–24, Eq.(131): minimum of the weights of the actual route edges. The finite range is nonempty by Route.positive, so real sInf is a genuine minimum.cutWeight: PDF pp.20,23–24, Eqs.(107),(131): maximum weight over labelled edges crossing A and its complement, counted once regardless of endpoint ordering. For finite connected networks and an endpoint-separating A this set is finite and nonempty. Outside that domain real sSup assigns 0 to the empty cut.
import Mathlib
/-! Pirandola, arXiv:1601.00966v4. Only the standalone graph proposition is
stated here. Operational and source-ambiguity deferrals are individually recorded
in the unit's HARD.md and GAPS.json. Compilation is pending batch handoff. -/
namespace QAlgorithms.Papers.Independent.Support50.P47
noncomputable section
universe u v
/-- PDF pp.16,23–24: an undirected weighted network with individually labelled
edges. Endpoint ordering is only a representation; routes may traverse either
way. Distinct labels may have the same endpoints, retaining parallel edges.
Finiteness and connectedness are imposed in the proposition, not by this data. -/
structure WeightedNetwork (V : Type u) (E : Type v) where
left : E → V
right : E → V
separated : ∀ e, left e ≠ right e
weight : E → ℝ
/-- PDF pp.16,23–24: a nonempty simple route, including its actual edge labels.
Injectivity forbids repeated vertices. The first and last vertices are fixed;
there is no independently supplied collection that could omit legal routes. -/
structure Route {V : Type u} {E : Type v} (G : WeightedNetwork V E) (a b : V) where
length : ℕ
positive : 0 < length
vertex : Fin (length + 1) → V
edge : Fin length → E
start : vertex ⟨0, Nat.zero_lt_succ length⟩ = a
finish : vertex (Fin.last length) = b
simple : Function.Injective vertex
follows : ∀ i : Fin length,
(G.left (edge i) = vertex i.castSucc ∧ G.right (edge i) = vertex i.succ) ∨
(G.right (edge i) = vertex i.castSucc ∧ G.left (edge i) = vertex i.succ)
/-- PDF pp.23–24: every pair of distinct vertices has a simple route.
On a singleton graph this is vacuous, but the proposition requires a ≠ b. -/
def IsConnected {V : Type u} {E : Type v} (G : WeightedNetwork V E) : Prop :=
∀ a b : V, a ≠ b → Nonempty (Route G a b)
/-- PDF pp.23–24, Eq.(131): minimum of the weights of the actual route edges.
The finite range is nonempty by Route.positive, so real sInf is a genuine minimum. -/
def routeWeight {V : Type u} {E : Type v} (G : WeightedNetwork V E)
{a b : V} (p : Route G a b) : ℝ :=
sInf (Set.range (fun i : Fin p.length => G.weight (p.edge i)))
/-- PDF pp.20,23–24, Eqs.(107),(131): maximum weight over labelled edges
crossing A and its complement, counted once regardless of endpoint ordering.
For finite connected networks and an endpoint-separating A this set is finite
and nonempty. Outside that domain real sSup assigns 0 to the empty cut. -/
def cutWeight {V : Type u} {E : Type v} (G : WeightedNetwork V E) (A : Set V) : ℝ :=
sSup {w : ℝ | ∃ e : E,
((G.left e ∈ A ∧ G.right e ∉ A) ∨ (G.right e ∈ A ∧ G.left e ∉ A)) ∧
w = G.weight e}
/-- A constant-weight nonempty route has that weight, even when it is negative. -/
example {V : Type u} {E : Type v} (G : WeightedNetwork V E)
{a b : V} (p : Route G a b) (w : ℝ) (hw : ∀ e, G.weight e = w) :
routeWeight G p = w := by
letI : Nonempty (Fin p.length) := ⟨⟨0, p.positive⟩⟩
simp [routeWeight, hw]
/-- The empty crossing set has the documented off-domain value 0. -/
example {V : Type u} {E : Type v} (G : WeightedNetwork V E) :
cutWeight G Set.univ = 0 := by
simp [cutWeight]
end
end QAlgorithms.Papers.Independent.Support50.P47
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Support50.P47.IsConnected
For arbitrary types and a network with distinct endpoints for every and arbitrary real edge weights, being connected means that for every pair with , there exists a route from to : a positive integer length , pairwise distinct vertices with and , and edges whose endpoints are in either order for every . There is no requirement to supply a route from a vertex to itself. This condition holds vacuously when is empty or has only one element.
QAlgorithms.Papers.Independent.Support50.P47.Route
Let be arbitrary types, and let be a network with endpoint functions satisfying for every edge and with weights . For vertices , a route from to consists of a natural number , vertices , and edges , such that , , all vertices are pairwise distinct, and, for every , either and , or and . Edges may therefore be traversed in either endpoint order. Length zero is excluded, and the distinctness requirement implies that no such route exists when .
QAlgorithms.Papers.Independent.Support50.P47.WeightedNetwork
For arbitrary types and , a weighted network consists of two endpoint functions , a requirement that for every , and a real weight function . Thus every edge has two distinct endpoints and an arbitrary real weight, which may be negative or zero. Different edges may have the same endpoints. No finiteness or nonemptiness requirement is imposed on either type.
QAlgorithms.Papers.Independent.Support50.P47.cutWeight
Let be arbitrary types, let have endpoint functions with for every edge and a real weight function , and let be any set. Its cut weight is defined by
Thus it takes the real supremum of the weights of edges with exactly one endpoint in , without requiring to contain or exclude any specified vertices. Under the real supremum convention used here, its value is if this set of weights is empty or unbounded above. In particular, it is for , , or any other set with no crossing edges.
QAlgorithms.Papers.Independent.Support50.P47.routeWeight
Let be arbitrary types, let assign distinct endpoints to each edge and a real weight to each , and let . Given a route from to , consisting of a positive length , pairwise distinct vertices starting at and ending at , and edges joining to in either endpoint order, its route weight is defined by
Because , this is the minimum of a finite nonempty set of real edge weights; the definition never takes an infimum of an empty set for a route.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.