Definitions for Routing entanglement in the quantum internet

QAlgorithms.Papers.Independent.Intakethird100.P45.Edge

For every natural number $N$, an edge is defined to be any ordered pair of labels from $\{0,\ldots,N-1\}$. This type permits equal endpoints and includes both orders of every pair of distinct endpoints; it imposes no geometric or adjacency condition. For $N=0$, there are no such pairs.

QAlgorithms.Papers.Independent.Intakethird100.P45.FeasibleFamily

For every natural number $N$, every finite set $H$ of ordered pairs from $\{0,\ldots,N-1\}^2$, every $a,b\in\{0,\ldots,N-1\}$, and every finite set $F$ of encodings $(k,v)$ with $0\le k<N^2$ and entries $v_0,\ldots,v_{k+1}\in\{0,\ldots,N-1\}$, $\operatorname{FeasibleFamily}(H,a,b,F)$ holds exactly when each encoding in $F$ starts at $a$, ends at $b$, has pairwise distinct pairs $(\min(v_i,v_{i+1}),\max(v_i,v_{i+1}))$ for $0\le i<k+1$, has all these pairs in $H$, and has no intermediate entry $v_1,\ldots,v_k$ equal to either endpoint, and, in addition, the sets of these pairs for any two distinct encodings in $F$ are disjoint. Distinct encodings may share vertices. The endpoints may coincide, intermediate entries may repeat subject to the stated conditions, and the intermediate-entry condition is vacuous for $k=0$. The empty family satisfies the predicate. No additional adjacency condition is imposed, and when $N=0$, no endpoints exist.

QAlgorithms.Papers.Independent.Intakethird100.P45.GridNetwork

For every natural number $N$, a grid network consists of a position function from the labels $\{0,\ldots,N-1\}$ to $\mathbb Z^2$, together with the requirement that this function is injective: if two labels have the same position, then the labels are equal. Thus all labeled positions are distinct, with no further restriction on their coordinates. The case $N=0$ is included, with an empty position function and a vacuously satisfied injectivity condition.

QAlgorithms.Papers.Independent.Intakethird100.P45.InternalFlags

For every natural number $N$, $\operatorname{InternalFlags}(N)$ is the type of all Boolean-valued functions on pairs $(r,i)$, where $r=(k,v)$ ranges over every encoding with $0\le k<N^2$ and entries $v_0,\ldots,v_{k+1}\in\{0,\ldots,N-1\}$, and $i$ ranges over the indices $0\le i<k$. Thus a function assigns either true or false separately to each such pair, including pairs belonging to encodings that satisfy no route-validity conditions. An encoding with $k=0$ contributes no indices. For $N=0$ or $N=1$, the entire indexing domain is empty, so there is exactly one such function.

QAlgorithms.Papers.Independent.Intakethird100.P45.PortTrailEncoding

For every natural number $N$, $\operatorname{PortTrailEncoding}(N)$ is the type of pairs $(k,v)$ consisting of a natural number $k$ with $0\le k<N^2$ and a sequence $v_0,\ldots,v_{k+1}$ whose entries lie in $\{0,\ldots,N-1\}$. Thus the sequence has $k+2$ entries, and entries may repeat without restriction. No adjacency or edge conditions are imposed. When $N=0$, this type is empty.

QAlgorithms.Papers.Independent.Intakethird100.P45.ValidRoute

For every natural number $N$, every finite set $H$ of ordered pairs from $\{0,\ldots,N-1\}^2$, every $a,b\in\{0,\ldots,N-1\}$, and every encoding $r=(k,v)$ with $0\le k<N^2$ and entries $v_0,\ldots,v_{k+1}\in\{0,\ldots,N-1\}$, $\operatorname{ValidRoute}(H,a,b,r)$ holds exactly when $v_0=a$, $v_{k+1}=b$, the pairs $e_i=(\min(v_i,v_{i+1}),\max(v_i,v_{i+1}))$ are distinct for distinct indices $0\le i<k+1$, every such pair belongs to $H$, and $v_j\ne a$ and $v_j\ne b$ for every $1\le j\le k$. Intermediate entries may repeat subject to these conditions, and $a=b$ is permitted. For $k=0$, the intermediate-entry condition is vacuous and the distinct-pair condition is automatic, so validity requires precisely $v_0=a$, $v_1=b$, and $(\min(a,b),\max(a,b))\in H$. No lattice or other adjacency condition is imposed beyond membership in $H$. When $N=0$, neither endpoints nor encodings exist.

QAlgorithms.Papers.Independent.Intakethird100.P45.bernoulliFlagEvent

For any finite type $I$, equipped with an enumeration of all its elements, any real number $p$, and any predicate $E$ on Boolean assignments $I\to\{\mathrm{false},\mathrm{true}\}$, define the event value to be

$$\sum_{f:I\to\{\mathrm{false},\mathrm{true}\}} \begin{cases} \displaystyle\prod_{i\in I} \begin{cases} p,&f(i)=\mathrm{true},\\ 1-p,&f(i)=\mathrm{false}, \end{cases} &E(f),\\ 0,&\text{otherwise}. \end{cases}$$

No restriction on $p$ or on the predicate $E$ is imposed. If $I$ is empty, there is exactly one assignment, and this value is $1$ if that assignment satisfies $E$, and $0$ otherwise.

QAlgorithms.Papers.Independent.Intakethird100.P45.candidateRoutes

For every natural number $N$, every finite set $H$ of ordered pairs from $\{0,\ldots,N-1\}^2$, and every $a,b\in\{0,\ldots,N-1\}$, $\operatorname{candidateRoutes}(H,a,b)$ is the finite set of all encodings $(k,v)$ with $0\le k<N^2$ and entries $v_0,\ldots,v_{k+1}\in\{0,\ldots,N-1\}$ such that $v_0=a$, $v_{k+1}=b$, the pairs $(\min(v_i,v_{i+1}),\max(v_i,v_{i+1}))$ for $0\le i<k+1$ are pairwise distinct and all belong to $H$, and every entry $v_j$ with $1\le j\le k$ differs from both $a$ and $b$. This set may be empty. The endpoints may coincide; intermediate entries may repeat subject to the stated conditions. For $k=0$, there are no intermediate entries, and the sole pair must belong to $H$. No additional adjacency condition is imposed. When $N=0$, there are no endpoints for this definition.

QAlgorithms.Papers.Independent.Intakethird100.P45.chainProbability

For any natural number $k$ and any real numbers $p,q$, define the chain value by summing over all external Boolean assignments $e$ on $\{0,\ldots,k-1\}$ and all internal Boolean assignments $u$ on $\{0,\ldots,(k-1)-1\}$, where $k-1$ is natural-number subtraction, truncated at $0$. A pair contributes $0$ unless every external and every internal flag is true; when both conditions hold, it contributes

$$\left(\prod_{i<k} \begin{cases}p,&e(i)=\mathrm{true},\\1-p,&e(i)=\mathrm{false}\end{cases}\right) \left(\prod_{j<k-1} \begin{cases}q,&u(j)=\mathrm{true},\\1-q,&u(j)=\mathrm{false}\end{cases}\right).$$

Neither $p$ nor $q$ is restricted to $[0,1]$. For $k=0$, both assignments are empty, both universal conditions hold vacuously, and the value is $1$; for $k=1$, there are no internal flags and the value is $p$.

QAlgorithms.Papers.Independent.Intakethird100.P45.conditionalOptimum

For any natural number $N$, finite set $H\subseteq V\times V$ with $V=\{0,\ldots,N-1\}$, endpoints $a,b\in V$, and real number $q$, this defines

$$\max\left(\{0\}\cup \left\{\sum_{r\in F}q^{m(r)-1}:F\text{ is a feasible family in }H\text{ from }a\text{ to }b\right\}\right).$$

Here a route $r$ consists of a length $m(r)$ with $1\le m(r)\le N^2$ and a vertex sequence $(v_0,\ldots,v_{m(r)})$. It is admissible when it starts at $a$, ends at $b$, its canonical edge pairs $(\min(v_i,v_{i+1}),\max(v_i,v_{i+1}))$ are distinct members of $H$, and none of its intermediate vertices equals either endpoint; other vertex repetitions are permitted. A feasible family is a finite set of admissible encoded routes whose edge sets are disjoint for every two distinct members. The empty family is feasible and contributes $0$. The maximum includes an explicit baseline of $0$, and $q$ is unrestricted, so it may be negative or outside $[0,1]$. A length-one route contributes $q^0=1$, including when $q=0$. There is no assumption that $a\ne b$ or that $H$ is a grid edge set; for $N=0$, there are no endpoint inputs.

QAlgorithms.Papers.Independent.Intakethird100.P45.conditionalYield

For every natural number $N$, every real number $q$, and every finite set $F$ of encodings $r=(k_r,v)$ with $0\le k_r<N^2$ and entries $v_0,\ldots,v_{k_r+1}\in\{0,\ldots,N-1\}$, $\operatorname{conditionalYield}(q,F)$ is the real number $\sum_{r\in F}q^{k_r}$. There are no restrictions on $q$ and no route-validity or disjointness requirements on $F$. Each encoding with $k_r=0$ contributes $1$, including when $q=0$, since $0^0=1$ under this power convention. The empty sum is zero, and when $N=0$, $F$ must be empty.

QAlgorithms.Papers.Independent.Intakethird100.P45.deliveredCount

For every natural number $N$, every finite set $F$ of encodings $r=(k,v)$ with $0\le k<N^2$ and entries $v_0,\ldots,v_{k+1}\in\{0,\ldots,N-1\}$, and every Boolean-valued function $\mathrm{flags}$ defined on all pairs $(r,i)$ of any such encoding and an index $0\le i<k$, $\operatorname{deliveredCount}(F,\mathrm{flags})$ is the natural number of encodings $r=(k,v)$ in $F$ for which $\mathrm{flags}(r,i)$ is true for every $0\le i<k$. No route-validity, disjointness, or probabilistic assumptions are required. Every encoding in $F$ with $k=0$ is counted because its condition has no indices to check. An empty $F$ gives count zero; when $N=0$, $F$ must be empty.

QAlgorithms.Papers.Independent.Intakethird100.P45.edgeKey

For every natural number $N$ and any labels $a,b\in\{0,\ldots,N-1\}$, define their edge key to be the ordered pair

$$(\min(a,b),\max(a,b)).$$

Equal labels are allowed and produce $(a,a)$. If $N=0$, there are no labels $a,b$ to supply.

QAlgorithms.Papers.Independent.Intakethird100.P45.endpointDegree

For every natural number $N$, every grid network given by an injective position map $x:\{0,\ldots,N-1\}\to\mathbb Z^2$, and every label $a\in\{0,\ldots,N-1\}$, define the endpoint degree of $a$ to be the number of pairs $(u,v)$ satisfying $u<v$, $|x_1(u)-x_1(v)|+|x_2(u)-x_2(v)|=1$, and $u=a$ or $v=a$. This number is $0$ if no such pair exists. For $N=0$, there is no label $a$ to supply.

QAlgorithms.Papers.Independent.Intakethird100.P45.externalMass

For any natural number $N$, a grid network $G$ assigning distinct positions $x_i\in\mathbb Z^2$ to the vertices $i\in V=\{0,\ldots,N-1\}$, any real number $p$, and any finite set $H\subseteq V\times V$, let

$$E_G=\{(i,j)\in V\times V:i<j,\ |x_{i,1}-x_{j,1}|+|x_{i,2}-x_{j,2}|=1\}.$$

The definition assigns the real number

$$p^{|H|}(1-p)^{\max(|E_G|-|H|,\,0)}.$$

There is no requirement that $H\subseteq E_G$, and the subtraction in the second exponent is natural-number subtraction, so that exponent is $0$ whenever $|H|>|E_G|$. There is also no restriction on $p$. Every zeroth power is $1$, including $0^0$; in particular, when $N=0$, both edge sets are empty and the value is $1$.

QAlgorithms.Papers.Independent.Intakethird100.P45.feasibleFamilies

For every natural number $N$, every finite set $H$ of ordered pairs from $\{0,\ldots,N-1\}^2$, and every $a,b\in\{0,\ldots,N-1\}$, $\operatorname{feasibleFamilies}(H,a,b)$ is the finite set of all finite sets $F$ of encodings $(k,v)$ with $0\le k<N^2$ and entries $v_0,\ldots,v_{k+1}\in\{0,\ldots,N-1\}$ satisfying the following conditions: every encoding in $F$ starts at $a$, ends at $b$, has pairwise distinct pairs $(\min(v_i,v_{i+1}),\max(v_i,v_{i+1}))$ for $0\le i<k+1$, has every such pair in $H$, and has each intermediate entry $v_1,\ldots,v_k$ different from both endpoints; furthermore, any two distinct encodings in $F$ have disjoint sets of these pairs. The empty family is included, so this set of families is nonempty whenever its endpoint arguments exist. The endpoints may coincide, shared vertices between encodings are permitted, and for $k=0$ the intermediate-entry condition is vacuous. No additional adjacency condition is imposed. When $N=0$, no endpoints exist.

QAlgorithms.Papers.Independent.Intakethird100.P45.greedyFamily

For any natural number $N$, finite set $H\subseteq V\times V$ with $V=\{0,\ldots,N-1\}$, and endpoints $a,b\in V$, this defines a finite set of routes by running the following procedure for at most $|H|$ steps, starting with $H$. A route is encoded by a length $m$ with $1\le m\le N^2$ and vertices $(v_0,\ldots,v_m)$; it is admissible in a remaining edge set $J$ when $v_0=a$, $v_m=b$, the canonical pairs $(\min(v_i,v_{i+1}),\max(v_i,v_{i+1}))$ for $0\le i<m$ are distinct members of $J$, and every intermediate vertex differs from both endpoints. Other vertex repetitions are allowed. If no steps remain, or no admissible route exists, the procedure returns the empty set. Otherwise, it selects an admissible route of minimum length by a fixed classical choice, removes all its canonical edge pairs from $J$, recursively continues with one fewer step, and inserts the selected route into the resulting finite set. Thus the initial step allowance is exactly the number of pairs in $H$, including any pairs that cannot occur in an admissible route. Empty $H$ gives an empty family. No grid structure or inequality $a\ne b$ is assumed; for $N=0$, there are no endpoint inputs.

QAlgorithms.Papers.Independent.Intakethird100.P45.greedyRate

For any natural number $N$, an injective assignment $i\mapsto x_i\in\mathbb Z^2$ on $V=\{0,\ldots,N-1\}$ defining a grid network $G$, endpoints $a,b\in V$, and arbitrary real numbers $p,q$, let $E_G$ consist of the pairs $(i,j)$ with $i<j$ whose positions have Manhattan distance $1$. This defines

$$\sum_{H\subseteq E_G} p^{|H|}(1-p)^{|E_G|-|H|} \sum_{r\in F_H}q^{m(r)-1}.$$

A route $r$ is encoded by a length $1\le m(r)\le N^2$ and vertices $(v_0,\ldots,v_{m(r)})$. It is admissible in an edge set $J$ when $v_0=a$, $v_{m(r)}=b$, its canonical edge pairs $(\min(v_i,v_{i+1}),\max(v_i,v_{i+1}))$ are all distinct and belong to $J$, and every intermediate vertex differs from both endpoints; other vertex repetitions are allowed. The finite set $F_H$ is constructed starting with $J=H$ and $|H|$ available steps: with zero steps or no admissible route, return the empty set; otherwise select an admissible route of minimum length by a fixed classical choice, remove its edge set, recursively continue with one fewer step, and insert the selected route into the resulting set. The outer sum includes every subset of $E_G$, including the empty set, and all exponents are nonnegative integers. Empty inner sums are $0$, and zeroth powers are $1$, including $0^0$. Neither $p,q\in[0,1]$ nor $a\ne b$ is assumed; when $N=0$, no endpoint inputs exist.

QAlgorithms.Papers.Independent.Intakethird100.P45.greedySteps

For any natural number $N$ and vertices $a,b$ in $V=\{0,\ldots,N-1\}$, this defines a function $T(f,H)$ taking a natural number of steps $f$ and a finite set $H\subseteq V\times V$ to a finite set of encoded routes. An encoded route consists of an integer $m$ with $1\le m\le N^2$ and a vertex sequence $(v_0,\ldots,v_m)$; its length is $m$, and its edge set is $E(r)=\{(\min(v_i,v_{i+1}),\max(v_i,v_{i+1})):0\le i<m\}$. Such a route is admissible in $H$ from $a$ to $b$ when $v_0=a$, $v_m=b$, its $m$ canonical edge pairs are all distinct and belong to $H$, and every intermediate vertex differs from both $a$ and $b$. Other repetitions of vertices are permitted. The definition is

$$T(0,H)=\varnothing,\qquad T(f+1,H)= \begin{cases} \varnothing,&\text{if no admissible route exists in }H,\\ \{r\}\cup T(f,H\setminus E(r)),&\text{otherwise}, \end{cases}$$

where $r$ is the route selected by a fixed classical choice from the admissible routes of minimum length; the definition supplies no further rule for resolving ties. The union is a set union, so repeated encodings would be counted only once. There is no assumption that $a\ne b$ or that $H$ comes from a grid, and zero steps always returns the empty set. For $N=0$, there are no choices of endpoints $a,b$.

QAlgorithms.Papers.Independent.Intakethird100.P45.iidMass

For any finite type $I$, equipped with an enumeration of all its elements, any real number $p$, and any Boolean assignment $f:I\to\{\mathrm{false},\mathrm{true}\}$, define its mass to be

$$\prod_{i\in I} \begin{cases} p,&f(i)=\mathrm{true},\\ 1-p,&f(i)=\mathrm{false}. \end{cases}$$

There is no assumption that $p\in[0,1]$. If $I$ is empty, the product equals $1$.

QAlgorithms.Papers.Independent.Intakethird100.P45.latticeDistance

For any two integer-coordinate points $a=(a_1,a_2)$ and $b=(b_1,b_2)$, define their lattice distance to be the natural number

$$|a_1-b_1|+|a_2-b_2|,$$

where each absolute value is regarded as a natural number. Coincident points are allowed and have distance $0$.

QAlgorithms.Papers.Independent.Intakethird100.P45.optimalGlobalRate

For any natural number $N$, a grid network $G$ given by an injective assignment of positions $x_i\in\mathbb Z^2$ to $V=\{0,\ldots,N-1\}$, endpoints $a,b\in V$, and arbitrary real numbers $p,q$, let $E_G$ be the set of pairs $(i,j)$ with $i<j$ and Manhattan distance $1$ between $x_i$ and $x_j$. This defines

$$\sum_{H\subseteq E_G} p^{|H|}(1-p)^{|E_G|-|H|} \max\left(\{0\}\cup \left\{\sum_{r\in F}q^{m(r)-1}:F\text{ is feasible in }H\text{ from }a\text{ to }b\right\}\right).$$

An encoded route $r$ consists of a length $1\le m(r)\le N^2$ and a vertex sequence $(v_0,\ldots,v_{m(r)})$. It is admissible when it starts at $a$, ends at $b$, its canonical edge pairs $(\min(v_i,v_{i+1}),\max(v_i,v_{i+1}))$ are distinct members of $H$, and all intermediate vertices differ from both endpoints; other vertex repetitions are permitted. A feasible family $F$ is a finite set of such routes with disjoint edge sets for every two distinct members. The empty family is feasible and has sum $0$, and each maximum also explicitly includes $0$. The outer sum includes the empty subset. The parameters $p$ and $q$ need not lie in $[0,1]$, and the endpoints need not be distinct. All zeroth powers, including $0^0$, equal $1$, so a length-one route contributes $1$. For $N=0$, there are no endpoint inputs.

QAlgorithms.Papers.Independent.Intakethird100.P45.physicalEdges

For every natural number $N$ and every grid network given by an injective position map $x:\{0,\ldots,N-1\}\to\mathbb Z^2$, define its physical edges to be the finite set of all ordered label pairs $(u,v)$ satisfying

$$u<v \quad\text{and}\quad |x_1(u)-x_1(v)|+|x_2(u)-x_2(v)|=1.$$

Thus each included pair has distinct endpoints and is recorded with its smaller label first. The set may be empty, and is empty when $N=0$ or $N=1$.

QAlgorithms.Papers.Independent.Intakethird100.P45.retainedLinkProbability

For any natural number $S$, including $0$, and any real number $p_0$, define the retained-link value by summing over all Boolean assignments $f$ on $\{0,\ldots,S-1\}$: an assignment contributes $\prod_{i=0}^{S-1}w_i$ if at least one $f(i)$ is true, and contributes $0$ otherwise, where $w_i=p_0$ when $f(i)$ is true and $w_i=1-p_0$ when it is false. There is no assumption that $p_0\in[0,1]$. For $S=0$, the existential condition is false for the unique empty assignment, so the value is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P45.routeEdge

For every natural number $N$, every encoding $r=(k,v)$ with $0\le k<N^2$ and entries $v_0,\ldots,v_{k+1}\in\{0,\ldots,N-1\}$, and every integer index $i$ with $0\le i<k+1$, the value $\operatorname{routeEdge}(r,i)$ is the ordered pair $(\min(v_i,v_{i+1}),\max(v_i,v_{i+1}))$, whose two coordinates lie in $\{0,\ldots,N-1\}$. Equal consecutive entries give the pair $(v_i,v_i)$, and different indices may give the same pair; no adjacency requirement is imposed. When $N=0$, there is no such encoding.

QAlgorithms.Papers.Independent.Intakethird100.P45.routeEdges

For every natural number $N$ and every encoding $r=(k,v)$ with $0\le k<N^2$ and entries $v_0,\ldots,v_{k+1}\in\{0,\ldots,N-1\}$, $\operatorname{routeEdges}(r)$ is the finite set $\{(\min(v_i,v_{i+1}),\max(v_i,v_{i+1})) : 0\le i<k+1\}$. Repeated pairs appear only once in this set. The set is nonempty because $k+1\ge1$, and it may contain pairs with equal coordinates; no adjacency condition is imposed. When $N=0$, there is no encoding to which this definition can be applied.

QAlgorithms.Papers.Independent.Intakethird100.P45.routeLength

For every natural number $N$ and every encoding $r=(k,v)$, where $0\le k<N^2$ and $v_0,\ldots,v_{k+1}\in\{0,\ldots,N-1\}$, $\operatorname{routeLength}(r)$ is the natural number $k+1$. Consequently, every encoding has length between $1$ and $N^2$, inclusive; length zero is excluded. When $N=0$, there is no encoding to which this definition can be applied.

QAlgorithms.Papers.Independent.Intakethird100.P45.shortestRoute

For every natural number $N$, every finite set $H$ of ordered pairs from $\{0,\ldots,N-1\}^2$, and every $a,b\in\{0,\ldots,N-1\}$, consider all encodings $r=(k,v)$ with $0\le k<N^2$ and entries $v_0,\ldots,v_{k+1}\in\{0,\ldots,N-1\}$ such that $v_0=a$, $v_{k+1}=b$, the pairs $(\min(v_i,v_{i+1}),\max(v_i,v_{i+1}))$ for $0\le i<k+1$ are pairwise distinct and all belong to $H$, and every intermediate entry $v_1,\ldots,v_k$ differs from both $a$ and $b$. If there are no such encodings, $\operatorname{shortestRoute}(H,a,b)$ returns no encoding; otherwise, it returns one chosen encoding whose length $k+1$ is less than or equal to the length of every encoding satisfying these conditions. No tie-breaking rule is specified beyond the classical choice of a minimizing encoding. The endpoints may coincide, intermediate entries may repeat subject to the stated conditions, and $k=0$ has no intermediate-entry restriction and gives length $1$. No additional adjacency condition is imposed. When $N=0$, no endpoints exist.