Definitions for On rounds in quantum communication

QAlgorithms.Papers.Independent.Intakethird100.P81.AliceConfig

For any natural number $N$ and any ownership assignment $\mathrm{own}:\{0,\ldots,N-1\}\to\{\mathrm{Alice},\mathrm{Bob}\}$, an Alice configuration is a Boolean-valued function on the subset of wires $q$ satisfying $\mathrm{own}(q)=\mathrm{Alice}$. It assigns one bit to each such wire, with no further conditions. If Alice owns no wires, including when $N=0$, there is exactly one Alice configuration: the empty function.

QAlgorithms.Papers.Independent.Intakethird100.P81.BlankExtension

For arbitrary types $X,Y,O$, a channel protocol $P$, and a quantum protocol $Q$ with the same input and outcome types, the blank-extension property means that there exists an injection $e$ from $P$'s wires into $Q$'s wires preserving their initial owners, such that for every bit string $z$ on $Q$'s wires,

$$Q.\mathrm{initial}(z)= \begin{cases} P.\mathrm{initial}(z\circ e),& z(q)=\mathrm{false}\text{ for every }q\notin\operatorname{im}e,\\ 0,&\text{otherwise}. \end{cases}$$

Thus the initial vector is $P$'s initial vector placed on the embedded wires with all additional wires fixed to false. Owners of additional wires are unrestricted. This property places no conditions on either protocol's rounds, measurements, output party, or validity. Either wire count may be zero whenever such an injection exists, and if there are no additional wires the condition outside the image is vacuous.

QAlgorithms.Papers.Independent.Intakethird100.P81.BobConfig

For any natural number $N$ and any ownership assignment $\mathrm{own}:\{0,\ldots,N-1\}\to\{\mathrm{Alice},\mathrm{Bob}\}$, a Bob configuration is a Boolean-valued function on the subset of wires $q$ satisfying $\mathrm{own}(q)\ne\mathrm{Alice}$, which here is exactly the subset owned by Bob. It assigns one bit to each such wire, with no further conditions. If this subset is empty, including when $N=0$, there is exactly one Bob configuration: the empty function.

QAlgorithms.Papers.Independent.Intakethird100.P81.ChannelProtocol.cost

For arbitrary types $X,Y,O$ and a channel protocol $P$, its cost is the natural number $\sum_{r\in P.\mathrm{rounds}}|S_r|$, where $S_r$ is the finite set of wires marked as sent in round $r$, and the sum follows the round list with repetitions of rounds counted separately. A wire sent in several rounds contributes once in each such round. Empty sent sets contribute zero, and an empty round list has cost zero. This definition requires no legality or validity assumption and includes protocols with zero wires.

QAlgorithms.Papers.Independent.Intakethird100.P81.ChannelProtocol.finalOwner

For arbitrary types $X,Y,O$ and a channel protocol $P$, its final ownership assignment is obtained by starting with its initial assignment and processing its round list in order: at each round, every wire in that round's sent set is assigned to the other party from its speaker, and all remaining owners are retained. This calculation does not require the round list to be legal and does not depend on either input or the round operations. For an empty round list the final ownership equals the initial ownership; zero wires are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P81.ChannelProtocol.finalState

For arbitrary types $X,Y,O$, a channel protocol $P$, and inputs $x\in X,y\in Y$, form the initial matrix $\rho_0$ with entries $(\rho_0)_{u,v}=\psi(u)\overline{\psi(v)}$, where $\psi$ is $P$'s initial vector and $u,v$ range over its $N$-bit strings. The final matrix is obtained by processing the rounds in list order, replacing the current matrix by $r_{\mathrm A}(x)$ applied to it for an Alice round and by $r_{\mathrm B}(y)$ applied to it for a Bob round. Ownership updates and sent-wire sets play no role in this calculation. With no rounds the result is $\rho_0$; zero wires are allowed. No validity assumption is required, so the definition does not assert that the resulting matrix is a density matrix.

QAlgorithms.Papers.Independent.Intakethird100.P81.ChannelProtocol

For arbitrary types $X,Y,O$, a channel protocol is a record containing a natural number $N$; a complex vector indexed by all $N$-bit strings, called its initial vector; an initial assignment of Alice or Bob to each wire; a finite list of rounds, each specifying a speaker, a finite sent-wire set, and maps on complex matrices indexed separately by Alice's input in $X$ and Bob's input in $Y$; an output party; and two families of complex matrices, one indexed by $X\times O$ and one by $Y\times O$, each matrix indexed by $N$-bit strings. The record imposes no normalization on the initial vector, no channel or locality conditions on round maps, no scheduling conditions, and no measurement conditions on the matrix families. The types may be empty, $N$ may be zero, and the round list may be empty.

QAlgorithms.Papers.Independent.Intakethird100.P81.ChannelProtocol.measurement

For arbitrary types $X,Y,O$, a channel protocol $P$, and inputs $x\in X$, $y\in Y$, the selected outcome-indexed matrix family is $P$'s Alice family at $x$ if its output party is Alice, and its Bob family at $y$ if its output party is Bob. Each matrix is indexed by the $N$-bit strings, where $N$ is $P$'s wire count. This selection alone asserts no positivity, completeness, or locality of the matrices, and applies also to zero wires or an empty outcome type.

QAlgorithms.Papers.Independent.Intakethird100.P81.ChannelProtocol.probability

For arbitrary types $X,Y,O$, a channel protocol $P$, inputs $x\in X,y\in Y$, and an outcome $o\in O$, the defined real number is

$$\operatorname{Re}\operatorname{tr}(M_o\rho_{\mathrm{final}}).$$

Here $M_o$ is the outcome-$o$ matrix from Alice's family at $x$ if Alice is the output party, and from Bob's family at $y$ otherwise; $\rho_{\mathrm{final}}$ starts with entries $\psi(u)\overline{\psi(v)}$ from the initial vector and is transformed through the round list in order, using each speaker's input-indexed map. The definition requires no validity assumption and therefore does not itself assert that this number lies in $[0,1]$ or that the outcome values sum to one. Zero wires and an empty round list are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P81.ChannelProtocol.valid

For arbitrary types $X,Y$, a finite type $O$ with a specified finite enumeration, a channel protocol $P$, a starting party $s$, and a natural number $k$, validity means the conjunction of the following conditions: its initial vector has Euclidean norm one; its round list has exactly $k$ entries; that list is legal from its initial ownership; its round at every index $i$ has speaker $s$ when $i$ is even and the other party when $i$ is odd; and, for every $x\in X,y\in Y$, its selected outcome matrices $M_o$ are positive semidefinite, satisfy $\sum_{o\in O}M_o=I$, and each act within the wires finally owned by its output party. The selected round operation uses the speaker's own input, and the selected measurement uses the output party's own input. Legality requires, successively, that each sent wire belongs to the current speaker, that every selected operation has a finite Kraus representation $F(\rho)=\sum_jE_j\rho E_j^\dagger$ with $\sum_jE_j^\dagger E_j=I$ and every $E_j$ acting within that speaker's currently owned wires, and that ownership is then updated by assigning sent wires to the other party. A matrix acts within a wire set $S$ when it is the extension of some matrix $A$ on an injectively selected list $w$ of wires contained in $S$: its entry at strings $u,v$ is $A_{u\circ w,v\circ w}$ if they agree outside those wires, and zero otherwise. Final ownership is obtained by all these updates. Zero rounds and zero wires are allowed, and sent sets need not be nonempty. If either input type is empty, the universally quantified operation and measurement conditions have no instances; if both have elements and $O$ is empty, measurement completeness is impossible.

QAlgorithms.Papers.Independent.Intakethird100.P81.ChannelRound

For arbitrary input types $X,Y$ and any natural number $N$, a channel round is a record containing a speaker chosen from Alice and Bob, a finite set of sent wires contained in $\{0,\ldots,N-1\}$, a function assigning to every $x\in X$ a map from complex matrices on $N$-bit strings to matrices of the same size, and another such function indexed by $y\in Y$. These two families are called the Alice and Bob operations. The structure itself imposes no linearity, positivity, trace preservation, locality, ownership, or compatibility conditions on these maps or on the sent wires. Empty input types, an empty sent set, and $N=0$ are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P81.ChannelRound.operation

For arbitrary types $X,Y$, a natural number $N$, a round $r$ consisting of a speaker (Alice or Bob), a finite set of sent wires, and input-indexed maps $r_{\mathrm A}(x)$ and $r_{\mathrm B}(y)$ on complex matrices indexed by $N$-bit strings, and inputs $x\in X$, $y\in Y$, the selected operation is $r_{\mathrm A}(x)$ if Alice speaks and $r_{\mathrm B}(y)$ if Bob speaks. The result is simply a function from such matrices to such matrices; this definition imposes no linearity, positivity, normalization, or locality condition. The sent wires do not affect this selection, and $N=0$ is allowed.

QAlgorithms.Papers.Independent.Intakethird100.P81.ChannelRound.update

For arbitrary types $X,Y$, a natural number $N$, a round $r$ with speaker Alice or Bob and sent-wire set $S_r\subseteq\{0,\ldots,N-1\}$, and an ownership assignment $\operatorname{own}$ assigning Alice or Bob to every wire, the updated owner of wire $q$ is the other party from $r$'s speaker if $q\in S_r$, and is $\operatorname{own}(q)$ otherwise. Thus every listed sent wire is assigned to the speaker's other party, regardless of its previous owner; the definition itself does not require the speaker to own it. An empty sent set leaves ownership unchanged, including when $N=0$.

QAlgorithms.Papers.Independent.Intakethird100.P81.ClassicalTree.changes

For arbitrary types $X,Y,O$, a classical tree has output leaves carrying a function $X\to O$ or $Y\to O$, and internal nodes labelled Alice or Bob, each carrying a Boolean function of that party’s input and two subtrees. Given such a tree $T$ and a previous party $p\in\{\mathrm{Alice},\mathrm{Bob}\}$, $\operatorname{changes}(T,p)$ is defined recursively: either kind of output leaf has value $0$; an Alice node with subtrees $T_0,T_1$ has value $\mathbf 1_{p\ne\mathrm{Alice}}+\max\{\operatorname{changes}(T_0,\mathrm{Alice}),\operatorname{changes}(T_1,\mathrm{Alice})\}$; and a Bob node has the corresponding value with Bob in place of Alice. Thus it is the maximum number of party changes along a structural path of internal nodes, counting a change from the supplied previous party to the first node when they differ. Both branches enter the maximum even if their Boolean tests make a path impossible for any input; the party named by an output leaf contributes no change.

QAlgorithms.Papers.Independent.Intakethird100.P81.ClassicalTree.cost

For arbitrary types $X,Y,O$, assign a natural-number cost to each finite binary tree whose Alice and Bob leaves carry functions $X\to O$ and $Y\to O$, respectively, and whose internal nodes carry Boolean functions on the corresponding input type. Either kind of output leaf has cost $0$, and either kind of internal node with children $T_0,T_1$ has cost $1+\max\{\operatorname{cost}(T_0),\operatorname{cost}(T_1)\}$. This counts the maximum number of internal nodes on a structural path to a leaf, including branches that no input can follow; it requires no finiteness or nonemptiness assumption on $X,Y,O$.

QAlgorithms.Papers.Independent.Intakethird100.P81.ClassicalTree

For arbitrary types $X$, $Y$, and $O$, with no finiteness or nonemptiness assumptions, a classical tree is a finite inductively constructed binary tree of four possible forms: an Alice output leaf carrying a function $f:X\to O$; a Bob output leaf carrying a function $f:Y\to O$; an Alice internal node carrying a Boolean function $\beta:X\to\{\mathrm{false},\mathrm{true}\}$ and two child trees called zero and one; or a Bob internal node carrying a Boolean function $\beta:Y\to\{\mathrm{false},\mathrm{true}\}$ and two such child trees.

QAlgorithms.Papers.Independent.Intakethird100.P81.ClassicalTree.rounds

For arbitrary types $X,Y,O$, a classical tree $T$ whose internal nodes test Boolean functions of Alice’s input in $X$ or Bob’s input in $Y$, and a designated starting party $p$, $\operatorname{rounds}(T,p)$ is $0$ for either kind of output leaf. If the root belongs to party $a$ and has subtrees $T_0,T_1$, its value is $1$ when $p=a$, or $2$ when $p\ne a$, plus the maximum number of subsequent party changes in either subtree, taking $a$ as the previous party. Here subsequent changes are counted recursively by adding $1$ whenever an internal node’s party differs from the preceding party and taking the maximum over both branches; output leaves add nothing. All structural branches enter these maxima, including paths unrealizable by any input.

QAlgorithms.Papers.Independent.Intakethird100.P81.ClassicalTree.run

For arbitrary types $X,Y,O$, a finite binary tree whose leaves carry output functions on $X$ or $Y$ and whose internal nodes carry Boolean functions on $X$ or $Y$, and inputs $x\in X$ and $y\in Y$, execution is defined recursively as follows: an Alice output leaf carrying $f:X\to O$ returns $f(x)$; a Bob output leaf carrying $f:Y\to O$ returns $f(y)$; an Alice internal node evaluates its Boolean function at $x$ and executes its one child if true and its zero child if false; a Bob internal node does the same using $y$. Every recursive execution uses the same inputs $x,y$. No finiteness or nonemptiness assumption is imposed on the types.

QAlgorithms.Papers.Independent.Intakethird100.P81.LocalChannel

For any natural number $N$, finite wire subset $S\subseteq\{0,\ldots,N-1\}$, and function $F$ from complex matrices on $N$-bit strings to matrices of the same size, this predicate means that there exist a natural number $d$ and matrices $E_0,\ldots,E_{d-1}$ such that

$$\sum_{j=0}^{d-1}E_j^\dagger E_j=I, \qquad F(\rho)=\sum_{j=0}^{d-1}E_j\rho E_j^\dagger \quad\text{for every complex matrix }\rho,$$

and each $E_j$ acts within $S$ in the following precise sense: there exist a natural number $h_j$, an injection $w_j:\{0,\ldots,h_j-1\}\hookrightarrow\{0,\ldots,N-1\}$ with image contained in $S$, and a complex matrix $M_j$ on $h_j$-bit strings, such that $E_j(y,z)=M_j(y\circ w_j,z\circ w_j)$ when $y,z$ agree on all wires outside that image, and $E_j(y,z)=0$ otherwise. The quantification over $\rho$ is not restricted to density matrices. Zero-wire embeddings, empty $S$, and $N=0$ are included; a zero-wire embedding is a scalar multiple of the identity. Although $d$ ranges over all natural numbers, $d=0$ cannot satisfy the completeness equation because the $N$-bit-string space is nonempty.

QAlgorithms.Papers.Independent.Intakethird100.P81.MeasurementPattern

For each natural number $N$, a measurement pattern is a record containing two Booleans, called $\mathrm{aliceInput}$ and $\mathrm{bobInput}$, and a finite subset $\mathrm{wires}\subseteq\{0,\ldots,N-1\}$. These fields have no additional constraints. In particular, the wire subset may be empty, and when $N=0$ it must be empty.

QAlgorithms.Papers.Independent.Intakethird100.P81.PointerMap

For each natural number $n$, a pointer map is an arbitrary function $\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}$, with no injectivity or surjectivity requirement. When $n=0$, this is the unique function from the empty set to itself.

QAlgorithms.Papers.Independent.Intakethird100.P81.PublicProtocol.bounded

For arbitrary types $X,Y,O$, a public protocol $P$ with finitely many nonnegative seed weights summing to $1$ and associated classical trees, a starting party $p$, and natural numbers $k,c$, the boundedness predicate means that every seed of strictly positive weight has a tree with at most $k$ rounds from $p$ and cost at most $c$. Cost is $0$ at an output leaf and $1$ plus the maximum child cost at a test node, so it counts the maximum number of test nodes on a structural path. Rounds are $0$ at an output leaf; otherwise they count $1$ for the first test node, an additional $1$ if its party differs from $p$, and all subsequent changes of testing party, maximized over structural paths. Unrealizable branches still enter these maxima, output-leaf parties add nothing, and seeds of weight $0$ impose no bounds. Both $k=0$ and $c=0$ are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P81.PublicProtocol.computes

For arbitrary types $X,Y,O$ with decidable equality on $O$, a public protocol $P$ with seed weights $w_i\ge0$ summing to $1$ and classical trees $T_i$, a function $f:X\times Y\to O$, and any real number $\varepsilon$, the computation predicate means that for every $x\in X$ and $y\in Y$,

$$1-\varepsilon\le \sum_i w_i\,\mathbf 1_{\operatorname{run}(T_i,x,y)=f(x,y)}.$$

Running a tree follows the false or true subtree according to the current party’s Boolean test on its own input; an Alice output leaf returns its function evaluated at $x$, and a Bob output leaf returns its function evaluated at $y$. There is no separate restriction on $\varepsilon$: if $\varepsilon\ge1$, the inequality is automatic; if $\varepsilon<0$ and both input types are nonempty, it cannot hold. If either input type is empty, the condition on input pairs is vacuous.

QAlgorithms.Papers.Independent.Intakethird100.P81.PublicProtocol

For arbitrary types $X,Y,O$, a public protocol consists of a natural number $s$ of seeds, a real weight $w_i$ for each $0\le i<s$, proofs that every $w_i\ge0$ and $\sum_{i=0}^{s-1}w_i=1$, and one classical tree $T_i$ for each seed. Each tree has Alice nodes testing functions $X\to\{\mathrm{false},\mathrm{true}\}$, Bob nodes testing functions $Y\to\{\mathrm{false},\mathrm{true}\}$, two subtrees at every test node, and output leaves carrying either a function $X\to O$ or a function $Y\to O$. Zero weights are permitted. Although the seed count is specified as a natural number, $s=0$ cannot satisfy the normalization requirement.

QAlgorithms.Papers.Independent.Intakethird100.P81.QuantumProtocol.computes

For arbitrary types $X,Y,O$, a quantum protocol $P$, a function $f:X\times Y\to O$, and a real number $\varepsilon$, this predicate means that for every $x\in X,y\in Y$,

$$1-\varepsilon\leq \operatorname{Re}\operatorname{Tr}\!\left( M_{x,y,f(x,y)}\,\psi_{x,y}\psi_{x,y}^{\dagger} \right).$$

The vector $\psi_{x,y}$ is the initial vector after all round unitaries have been applied in order, with each round using its speaker's input-dependent unitary. The outcome matrix is taken from Alice's $x$-dependent family if Alice is the designated output party and from Bob's $y$-dependent family otherwise. This predicate does not itself require the protocol to be valid or $\varepsilon$ to lie in any specified interval; it is vacuous if either input type is empty.

QAlgorithms.Papers.Independent.Intakethird100.P81.QuantumProtocol.cost

For arbitrary types $X,Y,O$ and a quantum protocol $P$, this defines its cost to be the natural number

$$\sum_{r\text{ in the round list of }P}|r.\mathrm{sent}|.$$

Thus each round contributes the cardinality of its designated sent-wire set; a wire designated as sent in several rounds is counted once in each such round. An empty round list has cost $0$. No validity assumption is required.

QAlgorithms.Papers.Independent.Intakethird100.P81.QuantumProtocol

For arbitrary types $X,Y,O$, a quantum protocol consists of a natural number $N$; an initial complex vector indexed by the $N$-bit strings $\{0,1\}^N$, equipped with the Euclidean norm; an initial assignment of each of the $N$ wires to Alice or Bob; a list of quantum rounds; an output party; and two matrix families, one assigning a complex matrix on $\{0,1\}^N$ to each pair $(x,o)\in X\times O$, and the other assigning such a matrix to each $(y,o)\in Y\times O$. Each round contains a speaker, a finite set of wires, and Alice and Bob input-indexed families of unitary matrices on the full $N$-bit space. The structure imposes no normalization on the initial vector, no legality or alternation condition on the rounds, and no positivity, completeness, or ownership-support condition on the output matrix families. Both output families are included regardless of the output party; $N=0$ and an empty round list are permitted.

QAlgorithms.Papers.Independent.Intakethird100.P81.QuantumProtocol.measurement

For arbitrary types $X,Y,O$, a quantum protocol $P$ with $N=P.N$ qubits, and inputs $x\in X$, $y\in Y$, this defines an $O$-indexed family of complex matrices on the basis of $N$-bit strings. If $P$'s designated output party is Alice, the family is $P.\mathrm{measureAlice}(x)$; otherwise it is $P.\mathrm{measureBob}(y)$. The definition itself requires neither positivity nor that these matrices sum to the identity, and imposes no restriction on which wires they act on.

QAlgorithms.Papers.Independent.Intakethird100.P81.QuantumProtocol.ownerAt

For arbitrary types $X,Y,O$, a quantum protocol $P$ with $N=P.N$ qubits, and any natural number $t$, this defines an ownership assignment on the wires $\{0,\ldots,N-1\}$. Start with $P$'s initial ownership assignment and process the first $\min(t,\ell)$ rounds in order, where $\ell$ is the length of its round list. In each processed round, assign every wire in that round's designated sent set to the party other than the round's speaker, and leave every other wire's ownership unchanged. Thus $t=0$ gives the initial assignment, and $t\geq\ell$ gives the assignment after all listed rounds. This definition imposes no legality condition: a designated sent wire is reassigned in this way even if the speaker did not previously own it.

QAlgorithms.Papers.Independent.Intakethird100.P81.QuantumProtocol.probability

For arbitrary types $X,Y,O$, a quantum protocol $P$ on $N=P.N$ qubits, inputs $x\in X,y\in Y$, and an outcome $o\in O$, this defines the real number

$$\operatorname{Re}\operatorname{Tr}\!\left(M_{x,y,o}\,\psi_{x,y}\psi_{x,y}^{\dagger}\right).$$

Here $\psi_{x,y}$ is obtained from the initial vector by applying every listed round's unitary in order, using the round's Alice unitary at $x$ when Alice speaks and its Bob unitary at $y$ otherwise; $M_{x,y,o}$ is Alice's outcome matrix at $x$ if Alice is the output party and Bob's outcome matrix at $y$ otherwise. The matrix $\psi_{x,y}\psi_{x,y}^{\dagger}$ has entry $\psi_{x,y}(u)\overline{\psi_{x,y}(v)}$. No validity, normalization, positivity, or measurement-completeness assumption is part of this definition.

QAlgorithms.Papers.Independent.Intakethird100.P81.QuantumProtocol.stateAt

For arbitrary types $X,Y,O$, a quantum protocol $P$ on $N=P.N$ qubits, inputs $x\in X,y\in Y$, and a natural number $t$, this defines a complex vector indexed by $N$-bit strings by starting with $P$'s initial vector and applying, in list order, the unitary matrices from the first $\min(t,\ell)$ rounds, where $\ell$ is the round-list length. A round uses its Alice unitary evaluated at $x$ if its speaker is Alice, and its Bob unitary evaluated at $y$ otherwise. Explicitly, writing these matrices as $U_0(x,y),\ldots,U_{\ell-1}(x,y)$ and $r=\min(t,\ell)$, the vector is

$$U_{r-1}(x,y)\cdots U_0(x,y)\,\psi_{\mathrm{initial}},$$

with the empty product giving $\psi_{\mathrm{initial}}$. Sending wires has no separate effect on this vector. No validity or normalization assumption is imposed, $t=0$ returns the initial vector, and $t\geq\ell$ applies all listed rounds.

QAlgorithms.Papers.Independent.Intakethird100.P81.QuantumProtocol.valid

For arbitrary input types $X,Y$, a finite outcome type $O$, a quantum protocol $P$ on $N=P.N$ qubits, a starting party $\mathrm{start}\in\{\mathrm{Alice},\mathrm{Bob}\}$, and a natural number $k$, this predicate means the conjunction of the following conditions. The initial vector, indexed by $N$-bit strings, has Euclidean norm $1$, and the round list has length exactly $k$. Starting from the initial ownership assignment and processing rounds in order, every wire designated as sent must currently belong to the speaker, and, for every input pair $x\in X,y\in Y$, the round's unitary must act within the speaker's currently owned wires; after the round, all sent wires are assigned to the other party and the remaining ownership assignments stay unchanged. Here the round's unitary is its Alice unitary at $x$ when Alice speaks and its Bob unitary at $y$ when Bob speaks. The speaker of round $i$, numbered from $0$, must be $\mathrm{start}$ for even $i$ and the other party for odd $i$. Finally, for every $x,y$, select Alice's $x$-dependent measurement family if Alice is the output party and Bob's $y$-dependent family otherwise: every outcome matrix must be positive semidefinite, their sum over $O$ must equal the identity, and every outcome matrix must act within the output party's wires after all rounds. Precisely, “acts within” a wire set $F$ means that there exist a natural number $h$, an injection $w:\{0,\ldots,h-1\}\hookrightarrow\{0,\ldots,N-1\}$ with image contained in $F$, and a complex matrix $M$ on $h$-bit strings such that the full matrix has entry $M(u\circ w,v\circ w)$ when $u$ and $v$ agree outside the image of $w$, and entry $0$ otherwise. The value $h=0$ is allowed. The definition also allows $k=0$ and empty sent sets; requirements quantified over input pairs are vacuous if either input type is empty.

QAlgorithms.Papers.Independent.Intakethird100.P81.QuantumRound.matrix

For arbitrary types $X,Y$, any natural number $N$, a quantum round $r$ containing a speaker, a selected wire set, an Alice input-indexed family of unitary matrices, and a Bob input-indexed family of unitary matrices on $\{0,1\}^N$, and inputs $x\in X,y\in Y$, the selected matrix is Alice’s matrix at $x$ if the speaker is Alice, and Bob’s matrix at $y$ otherwise. It is returned as a complex matrix indexed by $N$-bit strings. The wire set does not enter this selection, and $N=0$ is included.

QAlgorithms.Papers.Independent.Intakethird100.P81.QuantumRound

For arbitrary types $X,Y$ and any natural number $N$, a quantum round consists of a speaker, either Alice or Bob; a finite set of wire indices from $\{0,\ldots,N-1\}$; a function assigning to every $x\in X$ a complex unitary matrix indexed by the $N$-bit strings $\{0,1\}^N$; and another such function assigning a unitary matrix to every $y\in Y$. Both families are included regardless of the speaker. This structure places no ownership or support conditions on the matrices or the selected wires. For $N=0$, the wire set is empty and the matrices are indexed by the single empty bit string.

QAlgorithms.Papers.Independent.Intakethird100.P81.QuantumRound.update

For arbitrary types $X,Y$, any natural number $N$, a quantum round $r$, and an ownership assignment $o:\{0,\ldots,N-1\}\to\{\mathrm{Alice},\mathrm{Bob}\}$, the updated assignment gives every wire in $r$’s selected set to the party opposite $r$’s speaker and leaves every other wire’s owner equal to $o(q)$. The opposite of Alice is Bob and the opposite of Bob is Alice. This rule applies regardless of who previously owned a selected wire; an empty selected set leaves the assignment unchanged, including when $N=0$.

QAlgorithms.Papers.Independent.Intakethird100.P81.Vertex

For each natural number $n$, the vertex type is the disjoint union of two copies of $\{0,\ldots,n-1\}$. Write their elements as $L(v)$ and $R(v)$; these are distinct even when their indices agree. When $n=0$, there are no vertices.

QAlgorithms.Papers.Independent.Intakethird100.P81.agreement

For any finite type $A$, any pair of complex matrices $M_{\mathrm{false}},M_{\mathrm{true}}$ on $A$, and any complex matrix $\rho$ on $A\times\{\mathrm{false},\mathrm{true}\}$, this defines the real number

$$\sum_{b\in\{\mathrm{false},\mathrm{true}\}} \operatorname{Re}\left( \sum_{a\in A}\sum_{a'\in A} (M_b)_{a,a'}\,\rho_{(a',b),(a,b)} \right).$$

There is no assumption that the matrices $M_b$ form a measurement or that $\rho$ is a density matrix. If $A$ is empty, the value is zero.

QAlgorithms.Papers.Independent.Intakethird100.P81.aliceInputJoint

For arbitrary types $X,Y$, any natural number $N$, ownership assignment $\mathrm{own}:\{0,\ldots,N-1\}\to\{\mathrm{Alice},\mathrm{Bob}\}$, and any complex matrix $\rho$ indexed by $(X\times Y)\times\{0,1\}^{N}$, this definition gives a matrix indexed by $(X\times A_{\mathrm{own}})\times Y$, where $A_{\mathrm{own}}$ is the set of Boolean assignments to Alice’s wires. Writing $B_{\mathrm{own}}$ for the Boolean assignments to all remaining wires and $\operatorname{merge}(a,b)$ for the full string using $a$ on Alice’s wires and $b$ elsewhere, its entries are

$$J((x,a),y;\,(x',a'),y') = \sum_{b\in B_{\mathrm{own}}} \rho((x,y),\operatorname{merge}(a,b);\,(x',y'),\operatorname{merge}(a',b)).$$

No finiteness assumption on $X,Y$, or positivity or normalization assumption on $\rho$, is imposed. The sum is finite because the work register has finitely many wires. If Bob has no wires, the sum has one term indexed by the empty assignment; this includes $N=0$.

QAlgorithms.Papers.Independent.Intakethird100.P81.channelRoundsLegal

For arbitrary types $X,Y$, a natural number $N$, an ownership assignment on the $N$ wires, and a finite list of rounds, legality is defined recursively: the empty list is legal for every ownership assignment; a list beginning with round $r$ is legal exactly when every wire in $r$'s sent set is currently owned by its speaker, for every $x\in X$ and $y\in Y$ its selected matrix map is a local channel on that speaker's currently owned wires, and the remaining rounds are legal after assigning every sent wire to the other party. Here the selected map is $r_{\mathrm A}(x)$ for an Alice round and $r_{\mathrm B}(y)$ for a Bob round. A map $F$ is a local channel on a wire set $S$ precisely when there exist a natural number $d$ and matrices $E_0,\ldots,E_{d-1}$, indexed by $N$-bit strings, such that

$$\sum_{j=0}^{d-1}E_j^\dagger E_j=I,\qquad F(\rho)=\sum_{j=0}^{d-1}E_j\rho E_j^\dagger \quad\text{for every complex matrix }\rho,$$

and each $E_j$ acts within $S$. Acting within $S$ means that for some natural number $t$, injection $w:\{0,\ldots,t-1\}\hookrightarrow\{0,\ldots,N-1\}$ with image contained in $S$, and matrix $M$ indexed by $t$-bit strings, its entry at strings $u,v$ equals $M_{u\circ w,v\circ w}$ when $u,v$ agree outside the image of $w$, and equals zero otherwise. Zero wires, empty sent sets, and an empty round list are included; if $X$ or $Y$ is empty, the condition on selected operations is vacuous. No alternating-speaker condition is part of this definition.

QAlgorithms.Papers.Independent.Intakethird100.P81.classicalWeight

For any type $A$, finite type $B$, complex matrix $\rho$ indexed by $A\times B$, and element $a\in A$, this defines

$$\operatorname{Re}\left(\sum_{b\in B}\rho_{(a,b),(a,b)}\right).$$

No positivity or normalization is required, so this real number is not assumed to be a probability. If $B$ is empty, it is zero; if $A$ is empty, there is no element $a$ to supply.

QAlgorithms.Papers.Independent.Intakethird100.P81.coherentExecutionStateAt

For arbitrary types $X,Y,O$, with finite enumerations and decidable equality for $X,Y$, any quantum protocol record $P$ with $N=P.N$ work qubits, and any sequence of measurement patterns $m_t$, this definition recursively produces complex matrices $R_t$ indexed by $(X\times Y)\times\{0,1\}^{N}$. Set $\Psi((x,y),z)=\psi(z)/\sqrt{|X||Y|}$, where $\psi=P.\mathrm{initial}$, and set $R_0=D_{m_0}(\Psi\Psi^\dagger)$, so $(\Psi\Psi^\dagger)_{p,q}=\Psi(p)\overline{\Psi(q)}$. Here $D_m$ retains an entry exactly when its Alice input coordinates agree if the pattern’s Alice Boolean is true, its Bob input coordinates agree if the Bob Boolean is true, and its work strings agree on every selected wire; it sets all other entries to zero. If the protocol has a round $r_t$ at zero-based position $t$, then

$$R_{t+1}=D_{m_{t+1}}(C_{r_t}R_tC_{r_t}^{\dagger}),$$

where $C_{r_t}$ is zero between unequal input pairs and, on the block for $(x,y)$, equals Alice’s input-$x$ unitary or Bob’s input-$y$ unitary according to that round’s speaker. If position $t$ is absent, then $R_{t+1}=R_t$, without applying the next pattern. Thus the sequence is constant after all listed rounds have been processed. No protocol validity or initial normalization is assumed; empty input types and $N=0$ are allowed, with inverse zero interpreted as zero.

QAlgorithms.Papers.Independent.Intakethird100.P81.coherentInitial

For arbitrary types $X,Y,O$, with specified finite enumerations of $X$ and $Y$, and any quantum protocol record $P$ with input types $X,Y$, output type $O$, $N=P.N$ work qubits, and initial amplitude vector $\psi=P.\mathrm{initial}$, this definition gives the complex Euclidean vector indexed by $(X\times Y)\times\{0,1\}^{N}$ whose amplitudes are

$$\Psi((x,y),z)=\frac{\psi(z)}{\sqrt{|X|\,|Y|}}.$$

The protocol’s other fields do not affect this definition, and no validity or normalization hypothesis is imposed on $P$ or $\psi$. The types $X$ and $Y$ may be empty; in that case the resulting vector has an empty coordinate index set, and the scalar inverse of zero is defined to be zero. The case $N=0$, with its single empty bit string, is also included.

QAlgorithms.Papers.Independent.Intakethird100.P81.controlledRound

For arbitrary types $X,Y$ with decidable equality, any natural number $N$, and any quantum round record $r$, let $U_{x,y}$ be Alice’s specified unitary matrix at input $x$ when $r$’s speaker is Alice, and Bob’s specified unitary matrix at input $y$ when its speaker is Bob. This definition gives a complex matrix indexed by $(X\times Y)\times\{0,1\}^{N}$, with entries

$$C_r((x,y),z;\,(x',y'),z') = \begin{cases} U_{x,y}(z,z'),&(x,y)=(x',y'),\\ 0,&\text{otherwise}. \end{cases}$$

The round’s set of sent wires does not enter this formula, and no ownership or locality condition is assumed. Empty input types and $N=0$ are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P81.dephaseSelectedRegisters

For arbitrary types $X,Y$ with decidable equality, any natural number $N$, a pattern $m$ consisting of two Booleans $m_A,m_B$ and a finite wire subset $W\subseteq\{0,\ldots,N-1\}$, and any complex matrix $\rho$ indexed by $(X\times Y)\times\{0,1\}^{N}$, this definition returns the matrix

$$D_m(\rho)((x,y),z;\,(x',y'),z') = \begin{cases} \rho((x,y),z;\,(x',y'),z'),& (m_A=\mathrm{false}\ \lor\ x=x') \land(m_B=\mathrm{false}\ \lor\ y=y') \land(\forall w\in W,\ z(w)=z'(w)),\\ 0,&\text{otherwise}. \end{cases}$$

No positivity, trace, or normalization condition is imposed on $\rho$. An empty wire subset imposes no work-register agreement condition; when both Booleans are false and the wire subset is empty, every entry is retained. Empty input types and $N=0$ are included.

QAlgorithms.Papers.Independent.Intakethird100.P81.endpoint

For every natural number $n$, natural number $k$, starting index $v_1\in\{0,\ldots,n-1\}$, and arbitrary functions $a,b:\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}$, the endpoint is obtained by applying the successor function exactly $k+1$ times to $L(v_1)$, where a successor step sends $L(v)$ to $R(a(v))$ and $R(v)$ to $L(b(v))$. In particular, when $k=0$ the endpoint is $R(a(v_1))$. The required starting index cannot be supplied when $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P81.firstRegisterConditionalBlock

For any type $A$, finite type $B$, complex matrix $\rho$ indexed by $A\times B$, and element $a\in A$, let $w_a=\operatorname{Re}\sum_{c\in B}\rho_{(a,c),(a,c)}$. This defines a matrix on $B$ by

$$(C_a)_{b,b'}=(w_a:\mathbb C)^{-1}\rho_{(a,b),(a,b')}.$$

No density or nonzero-weight hypothesis is imposed. In particular, when $w_a=0$, the inverse is defined to be zero and $C_a$ is the zero matrix. The type $B$ may be empty.

QAlgorithms.Papers.Independent.Intakethird100.P81.informationalDistance

For any finite types $A,B$ with decidable equality and any complex matrix $\rho$ indexed by $A\times B$, let $(\rho_A)_{a,a'}=\sum_b\rho_{(a,b),(a',b)}$, let $(\rho_B)_{b,b'}=\sum_a\rho_{(a,b),(a,b')}$, and put $X=\rho-\rho_A\otimes\rho_B$. This defines the real number

$$\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X},$$

where the square root is defined by continuous functional calculus. There is no factor of $1/2$. The definition applies without assuming that $\rho$ is Hermitian, positive, or normalized, and it includes empty index types.

QAlgorithms.Papers.Independent.Intakethird100.P81.iteratedLog

For every real number $x$ and natural number $j$, define $L_0(x)=\max\{1,x\}$ and recursively define $L_{j+1}(x)=\max\{1,\log_2(L_j(x))\}$. The declared function returns $L_j(x)$. Its real argument is unrestricted, including zero and negative values; all intermediate values are at least $1$, and if $x\le1$, every value is $1$.

QAlgorithms.Papers.Independent.Intakethird100.P81.jointMarginalProduct

For any finite types $A,B$ and any complex matrix $\rho$ indexed by $A\times B$, this defines the matrix whose entries are

$$\bigl(\operatorname{jointMarginalProduct}(\rho)\bigr)_{(a,b),(a',b')} = \left(\sum_{c\in B}\rho_{(a,c),(a',c)}\right) \left(\sum_{d\in A}\rho_{(d,b),(d,b')}\right).$$

Thus it is the Kronecker product of the matrices obtained by summing over the second and first registers, respectively. No positivity or normalization assumption is imposed, and either index type may be empty.

QAlgorithms.Papers.Independent.Intakethird100.P81.jointMutualInfoBits

For any finite types $A,B$ with decidable equality and any complex matrix $\rho$ indexed by $A\times B$, define matrices $\rho_A,\rho_B$ by $(\rho_A)_{a,a'}=\sum_{b\in B}\rho_{(a,b),(a',b)}$ and $(\rho_B)_{b,b'}=\sum_{a\in A}\rho_{(a,b),(a,b')}$. Writing $f[X]$ for the continuous functional calculus of the real function $f$ at $X$, set $H(X)=-\operatorname{Re}\operatorname{tr}((x\mapsto x\log_2x)[X])$. The defined real number is

$$H(\rho_A)+H(\rho_B)-H(\rho).$$

No positivity, Hermiticity, or trace normalization is required of $\rho$. Empty index types are allowed, with empty sums and traces equal to zero.

QAlgorithms.Papers.Independent.Intakethird100.P81.logStar

For every natural number $n$, regarded as a real number when used as an argument, define $L_0(n)=\max\{1,n\}$ and $L_{j+1}(n)=\max\{1,\log_2(L_j(n))\}$. The declared natural number is the infimum in $\mathbb N$ of $\{j\in\mathbb N:L_j(n)\le1\}$: the least such index when this set is nonempty, with the natural-number infimum convention giving $0$ if it is empty. In particular, the result is $0$ for $n=0$ and $n=1$.

QAlgorithms.Papers.Independent.Intakethird100.P81.mergeWork

For any natural number $N$, ownership assignment $\mathrm{own}:\{0,\ldots,N-1\}\to\{\mathrm{Alice},\mathrm{Bob}\}$, Boolean assignment $a$ on Alice’s wires, and Boolean assignment $b$ on the wires not owned by Alice, this definition gives the full $N$-bit string

$$\operatorname{merge}_{\mathrm{own}}(a,b)(q)= \begin{cases} a(q),&\mathrm{own}(q)=\mathrm{Alice},\\ b(q),&\mathrm{own}(q)\ne\mathrm{Alice}. \end{cases}$$

The arguments $a(q)$ and $b(q)$ are evaluated on their respective wire subsets. No wire is omitted, and $N=0$ gives the unique empty bit string.

QAlgorithms.Papers.Independent.Intakethird100.P81.nonDisjoint

For every natural number $n$ and Boolean functions $x,y:\{0,\ldots,n-1\}\to\{\mathrm{false},\mathrm{true}\}$, the defined Boolean is true exactly when there exists an index $i$ for which both $x(i)$ and $y(i)$ are true, and false otherwise. When $n=0$, the existential condition is false, so the result is false.

QAlgorithms.Papers.Independent.Intakethird100.P81.owned

For any natural number $N$, ownership assignment $o:\{0,\ldots,N-1\}\to\{\mathrm{Alice},\mathrm{Bob}\}$, and party $p$, the defined finite set is exactly

$$\{q\in\{0,\ldots,N-1\}:o(q)=p\}.$$

It may be empty and is necessarily empty when $N=0$.

QAlgorithms.Papers.Independent.Intakethird100.P81.pointerParity

For every natural number $n$, natural number $k$, starting index $v_1\in\{0,\ldots,n-1\}$, and arbitrary functions $a,b:\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}$, start at $L(v_1)$ and take exactly $k+1$ steps, sending $L(v)$ to $R(a(v))$ and $R(v)$ to $L(b(v))$. Label the resulting vertex by $v$ if it is $L(v)$ and by $n+v$ if it is $R(v)$. The defined Boolean is true exactly when the sum of the binary digits of this natural-number label has remainder $1$ upon division by $2$, and false otherwise. A zero label has binary digit sum zero and therefore gives false; when $n=0$, no starting index exists.

QAlgorithms.Papers.Independent.Intakethird100.P81.preparationRound

For any natural number $N$, including $N=0$, any ownership assignment $o:\{0,\ldots,N-1\}\to\{\text{Alice},\text{Bob}\}$, and any unitary matrix $U$ on the complex vector space indexed by $N$-bit strings, this defines a quantum round with singleton input sets for both parties. Alice is the speaker; the transmitted wires are exactly $\{q:o(q)=\text{Bob}\}$; Alice’s unitary is $U$ for her unique input, and Bob’s unitary is the identity for his unique input.

QAlgorithms.Papers.Independent.Intakethird100.P81.roundsLegal

For arbitrary types $X,Y$ and any natural number $N$, legality of a list of quantum rounds is defined recursively from an ownership assignment $o$. The empty list is legal. A list beginning with round $r$ is legal precisely when every selected wire currently belongs to $r$’s speaker, every input pair $x\in X,y\in Y$ gives a selected matrix acting within that speaker’s currently owned wires, and the remaining list is legal after assigning the selected wires to the opposite party and leaving other owners unchanged. The selected matrix is Alice’s matrix at $x$ for an Alice speaker and Bob’s matrix at $y$ for a Bob speaker. Explicitly, acting within the owned wires means that there exist a natural number $h$, an injection $w:\{0,\ldots,h-1\}\hookrightarrow\{0,\ldots,N-1\}$ whose image consists of wires owned by the speaker, and a complex matrix $M$ indexed by $h$-bit strings, such that the selected matrix has entries

$$U_{u,v}= \begin{cases} M_{u\circ w,v\circ w},&u(q)=v(q)\text{ for every }q\notin\operatorname{range}(w),\\ 0,&\text{otherwise}. \end{cases}$$

Here $h=0$ is permitted. The universal matrix condition is vacuous if either input type is empty; legality does not itself require speakers to alternate or selected wire sets to be nonempty.

QAlgorithms.Papers.Independent.Intakethird100.P81.speakerAt

For a starting party $p\in\{\mathrm{Alice},\mathrm{Bob}\}$ and a natural number $t$, the designated speaker is $p$ when $t$ is even and the opposite party when $t$ is odd, with Alice and Bob opposite to each other. In particular, the speaker at $t=0$ is $p$.

QAlgorithms.Papers.Independent.Intakethird100.P81.successor

For every natural number $n$ and arbitrary functions $a,b:\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}$, the successor function on the disjoint union of two copies of this index set is defined by $\operatorname{succ}_{a,b}(L(v))=R(a(v))$ and $\operatorname{succ}_{a,b}(R(v))=L(b(v))$. When $n=0$, it is the unique function on the empty vertex set.

QAlgorithms.Papers.Independent.Intakethird100.P81.swapState

For arbitrary types $A,B$ and any complex matrix $\rho$ indexed by $A\times B$, this defines a matrix on $B\times A$ by

$$\bigl(\operatorname{swapState}(\rho)\bigr)_{(b,a),(b',a')} =\rho_{(a,b),(a',b')}.$$

Neither finiteness nor any state condition is assumed; empty types are included.

QAlgorithms.Papers.Independent.Intakethird100.P81.vertexLabel

For every natural number $n$, label the vertices in the disjoint union of two copies of $\{0,\ldots,n-1\}$ by $\operatorname{label}(L(v))=v$ and $\operatorname{label}(R(v))=n+v$, as natural numbers. Thus the left labels run from $0$ through $n-1$ and the right labels from $n$ through $2n-1$; when $n=0$, the labeling function has empty domain.