# Projective characterization of higher-order quantum transformations

Timothée Hoffreumon<EMAIL_ADDRESS>Ognyan Oreshkov  Centre for
Quantum Information and Communication (QuIC), École polytechnique de
Bruxelles, CP 165/59,
Université libre de Bruxelles, Avenue F. D. Roosevelt 50, 1050 Brussels,
Belgium.

###### Abstract

Transformations of transformations, also called higher-order transformations,
is a natural concept in information processing, which has recently attracted
significant interest in the study of quantum causal relations. In this work, a
framework for characterizing higher-order quantum transformations which relies
on the use of superoperator projectors is presented. More precisely, working
with projectors in the Choi-Jamiołkowski picture is shown to provide a handy
way of defining the characterization constraints on any class of higher-order
transformations. The algebraic properties of these projectors are furthermore
identified as a model of multiplicative additive linear logic (MALL). The main
novelty of this work is the introduction in the algebra of the ‘prec’
connector. It is used for the characterization of maps that are no signaling
from input to output or the other way around. This allows to assess the
possible signaling structure of any maps characterized within the projective
framework. The properties of the prec are moreover shown to yield a canonical
form for projective expressions. This provides an unambiguous way to compare
different higher-order theories.

##  I Introduction

The same way that a quantum channel describes the most general transformation
mapping an input quantum state to an output quantum state [1], a quantum
supermap describes the most general transformation mapping an input quantum
channel to an output quantum channel [2]. Interpreting the quantum channel as
a transformation between states, the supermap is then a transformation of
transformations. For that reason, it is called higher-order transformation.
Since nothing forbids a priori to nest transformations of transformations, one
can consider successive nestings to recursively build a whole hierarchy of
higher-order transformations [3, 4, 5].

Fragments of a quantum circuit are a concrete instance of the use of a higher-
order hierarchy. A fragment of quantum circuit that ‘goes around’ a channel is
a supermap: it takes a channel as input and outputs a channel. This supermap
can itself be seen as the input for some super-supermap that will output a
channel, and so on. This ensuing hierarchy has been defined under the name
quantum comb formalism [3], which has proven to be a valuable tool in the
field of quantum information theory.

With a different goal than modeling circuit fragments, supermaps with multiple
inputs were subsequently studied. First, the quantum switch was proposed as a
supermap that takes two channels and outputs them in an order that depends on
a control qubit [6]. Soon after, Process Matrices (PM) were proposed as a
general framework of supermaps that take a fixed number of quantum instruments
[7] and map them to a joint probability for their outcomes [8]. (In the case
when the inputs are channels, that probability is 1.) Both concepts led to the
identification of Indefinite Causal Order (ICO) as a feature of supermaps.

One can then wonder what differentiates the switch from a comb, or the PM from
a comb. Especially, why certain maps and hierarchies of maps may feature ICO
while others will not. Motivated by these considerations, the goal of this
work is to present a framework that formalizes and characterizes higher-order
quantum transformations. The two main questions answered are ‘given an
operator on a set of input and output Hilbert spaces, does it represent (the
Choi-Jamiołkowski operator of) a higher order object’ and ‘what is the
underlying causal structure(s) of such an object?’. This work extends two
previous characterizations, one done using type theory [4, 5], and the other
using category theory [9]. This extension relies on the use of superoperator
projectors [10].

These projectors have a twofold advantage: first, they make the
characterization more straightforward, as one can answer the first question
simply by applying the projector corresponding to a given higher-order object
on the operator. Second, they offer an intuitive explanation of the type-
theoretic semantics of higher order: the algebraic rules for composing these
projectors correspond to the semantic rules for forming new types.

Below, we concisely reformulate ideas from Ref. [5] to give the reader an
overview of the theory upon which this work is based.

##### Types.

The formalism of quantum channels and operations [1] describes transformations
of quantum states into quantum states, but is unable to effectively describe
the transformations whose inputs and outputs are transformation themselves
[6]. To overcome this issue, Perinotti [4] and Bisio [5] extended the concept
of a supermap [2, 3] into a suitable framework to treat these general
transformations of transformations, or higher-order quantum maps.

At the core of their work is the utilization of the Choi-Jamiołkowski (CJ)
isomorphism [11, 12]. Define $\mathcal{H}^{A}$ to be a Hilbert space of
dimension $d_{A}$ associated to system $A$,
$\mathcal{L}\left(\mathcal{H}^{A}\right)$ to be the space of linear operators
on $\mathcal{H}^{A}$, and
$\mathcal{L}\left(\mathcal{L}\left(\mathcal{H}^{A}\right),\mathcal{L}\left(\mathcal{H}^{B}\right)\right)$
to be the space of linear maps from $\mathcal{L}\left(\mathcal{H}^{A}\right)$
to $\mathcal{L}\left(\mathcal{H}^{B}\right)$. Let
$\ket{\phi^{+}}=\sum_{i=0}^{d_{A}-1}\ket{i}^{A}\otimes\ket{i}^{A^{\prime}}$ be
a(n unnormalized) maximally entangled state on space
$\mathcal{H}^{A}\otimes\mathcal{H}^{A^{\prime}}$, with $A^{\prime}$ a copy of
$A$, and $\phi^{+}\equiv\outerproduct{\phi^{+}}{\phi^{+}}$ its density
operator representation. Then,

$\begin{gathered}\mathcal{L}\left(\mathcal{L}\left(\mathcal{H}^{A}\right),\mathcal{L}\left(\mathcal{H}^{B}\right)\right)\ni\mathcal{M}\mapsto
M\in\mathcal{L}\left(\mathcal{H}^{A}\otimes\mathcal{H}^{B}\right)\>:\\\
M\equiv\left[\left(\mathcal{I}\otimes\mathcal{M}\right)\left\\{\phi^{+}\right\\}\right]^{T}\>,\end{gathered}$
(1)

is an isomorphic bijective mapping. The correspondence sends linear maps
between operator spaces to operators in tensor product spaces. It has the
properties that a Hermitian-preserving (HP) map is mapped to a Hermitian
operator and a completely positive (CP) map is mapped to a positive
semidefinite operator. To recover the action of the map, the ‘reverse
direction’ of the CJ correspondence is used:

$\mathcal{M}\left(A\right)=\left(\text{Tr}_{A}\left[M\cdot\left(A\otimes\mathds{1}_{B}\right)\right]\right)^{T}\>.$
(2)

Using this correspondence, maps, maps of maps, and so on, can all be
represented as CJ operators on some composite space, and this is how we will
describe them.

Then it is possible to define types of maps. One first defines base types, out
of which one defines a hierarchy of higher-order types as maps between types
of lower order. The state spaces (in density matrix form) of standard quantum
systems of a given finite dimension are standardly taken as base types (but
different constructions are also possible). Although two different systems $A$
and $B$ could have state spaces of the same type (e.g., if they are both
qubits), in order to avoid complicated notation, when we describe types
instantiated on different systems we will use different letters – by
convention the same letters as for the systems – and will indicate by words,
if needed, when the types are the same.

More general types are then defined as sets of admissible maps 111A map is
admissible in this framework under certain axioms, which can be proven to
reduce to the requirement of CP preservation and trace-rescaling for some
normalization. that have the same types of input and output spaces. For
example, the above map $M$ is in type $A\rightarrow B$, where $A$ and $B$ are
base types. However, in the same way one could describe maps whose input and
output types $A$ and $B$ are maps themselves, by representing the input and
output maps via their CJ operators (in this case, the input or output ’state’
space would generally consist, up to a normalization, of a subset of the set
of all standard states on the respective Hilbert space).

The formalism is an instance of a type system. This “$\rightarrow$” connector,
here nicknamed transformation, is the key element of the type theory of higher
order transformations: each set can be seen as an abstract type, and new types
can be defined out of existing ones using the transformation connector as a
semantic rule.

Two special cases are of particular interest: the set of deterministic
effects, where the output type is the trivial one-dimensional system 1, i.e.
$A\rightarrow 1\equiv\bar{A}$; and the parallel composition of two types,
obtained as the transformation $\left(A\rightarrow\left(B\rightarrow
1\right)\right)\rightarrow 1=\overline{A\rightarrow\overline{B}}\equiv
A\otimes B$ [4]. The type $A\otimes B$ generalizes the idea of a no signaling
channel [14, 15] from the joint inputs of $A$ and $B$ to their joint outputs.

Thus, starting from some postulates, a trivial type 1, an elementary type $A$
(which is usually taken as the set of quantum states in density matrix form),
and this connector rule, all the higher-order generalizations of the quantum
formalism can be defined using types. These in turn yield the constraints on
the operators representing transformations of a given type [4, 5].

For example, let $A_{0}$ and $A_{1}$ be, respectively, the set of input and
output quantum states of Alice, who applies some quantum operation in between.
Then, one can infer that the set of allowed transformations to which she has
access is of type $A_{0}\rightarrow A_{1}$. This simple semantic statement is
then translated into constraints to apply on the Hilbert space
$\mathcal{L}\left(\mathcal{H}^{A_{0}}\otimes\mathcal{H}^{A_{1}}\right)$ and
yields (the Choi-Jamiołkowski representation of) the set valid quantum
channels for Alice. A more complex example is obtained by recovering the set
of bipartite process matrices [8], which corresponds to the type normalized on
the local quantum instruments of two parties, say Alice and Bob. Knowing that
their local instruments sum up to quantum channels, i.e. they belong to types
$\left(A_{0}\rightarrow A_{1}\right)$ and $\left(B_{0}\rightarrow
B_{1}\right)$, the set of process matrices is the type that takes a
composition of these two types as input and outputs a trivial system. In the
semantics, this statement corresponds to type $\left(\left(A_{0}\rightarrow
A_{1}\right)\otimes\left(B_{0}\rightarrow B_{1}\right)\right)\rightarrow 1$,
from which the constraints for the characterization directly ensue.

Importantly, the transformation connector “$\rightarrow$” is not associative:
$A\rightarrow(B\rightarrow C)\neq(A\rightarrow B)\rightarrow C$. This semantic
fact is what allows to define the notion of an order with respect to (w.r.t.)
a base type. Let $A$ be an instance of the type used as base defined in space
$\mathcal{L}\left(\mathcal{H}^{A}\right)$, and define $B,C,D$ in the same way.
Then, $A,B,C,D$ are first-order types (trivial transformation) w.r.t. the
base, types $A\rightarrow B$ and $C\rightarrow D$ are two instances of second
order (both the same kind of transformations, but defined on different Hilbert
spaces), and type $(A\rightarrow B)\rightarrow(C\rightarrow D)$ is third order
(a transformation of transformation). Notice that while this last expression
is third order, an expression like $((A\rightarrow B)\rightarrow C)\rightarrow
D)$ is only second order, as it is but a cascading of second order
transformations. With these considerations, it becomes possible to talk about
a hierarchy of higher order quantum transformations as in reference [5].

##### Outline and results.

In section II, types are put in correspondence with subsets of operators
called state structures that are characterized by a superoperator projector.
Looking at these projectors instead of the state structures, and by extension
the types they define, is the idea behind projective characterization. It is
then proven that this way of characterizing recovers the type theory.

A convenient aspect of projectors is that they form an algebra, so that
manipulations of formulae are simplified by using algebraic properties. This
point is developed in Section III. It is then observed that this algebra
furthermore constitutes a model of linear logic.

In Section IV, a new projector encoding no signaling between two systems is
introduced. In addition to its obvious role of making the signaling structure
of types apparent, it has useful algebraic properties. As presented in V.1,
these allow one to write a canonical form of a projector, which is useful to
compare any two state structure.

Finally, in Section V.2 an example of the use of projective characterization
is given. We recover the result [5, Prop. 6] that quantum combs are quantum
networks, which have a single signaling direction.

##  II Projective characterization of the type theory of higher-order quantum
transformations

Central in that work will be the notion of a trace-normalized positive
operator system in $\mathcal{L}\left(\mathcal{H}^{A}\right)$. This kind of set
is the backbone of the characterization as to each type – or “level in the
hierarchy of transformations” – corresponds such a set (Appendix C.1 provides
a motivating example if needed).

######  Definition 1 (Operator system [16]).

For a given space of operators, an operator system is a self-adjoint subspace
that contains the identity.

We will refer to both an operator system and its positive trace-normalized
subset by using the calligraphic font of the letter associated with the
subsystem it is defined upon; it should be clear from the context which one is
under consideration. For example, $\mathscr{A}$ and $\mathscr{A}^{\prime}$ are
two different operator systems over $\mathcal{L}\left(\mathcal{H}^{A}\right)$.

By definition, an operator system is closed under complex conjugation and
Hermitian conjugation, which means that they are also closed under
transposition. Note that $*$-subalgebras are a special case of operator
systems that are closed under multiplication.

Since operator systems are linear subspaces, they can be characterized by
linear superoperator projectors noted
$\mathcal{P}_{A}:\mathcal{L}\left(\mathcal{H}^{A}\right)\rightarrow\mathscr{A}$,
see Ref. [10, 17]. For the purposes of the characterization, it is assumed
that all such projectors are self-adjoint and that the composition of any two
projector must yield a valid projector. Their characteristics are presented in
details in the Appendix A.1.

A positive and trace normalized operator system can be characterized by the
following set of conditions that any of its elements $A$ have to respect:

$\displaystyle A\geq 0\>,$ (3a)
$\displaystyle\text{Tr}\left[A\right]=c_{A}\>,$ (3b)
$\displaystyle\mathcal{P}_{A}\left\\{A\right\\}=A\>.$ (3c)

This abstract structure will play a central role in the characterization of
higher-order quantum transformations, we name it state structure.

######  Definition 2 (State structure).

A state structure $\mathscr{A}\in\mathcal{L}\left(\mathcal{H}^{A}\right)$ is a
positive operator system that is trace-normalized.

An example of state structure is the set of quantum states in density matrix
form, characterized by

$\displaystyle\rho\geq 0\>,$ (4a)
$\displaystyle\text{Tr}\left[\rho\right]=1\>,$ (4b)
$\displaystyle\mathcal{I}\\{\rho\\}=\rho\>.$ (4c)

Here, $\mathcal{I}$ is the identity mapping, defined as

$\forall
A\in\mathcal{L}\left(\mathcal{H}^{A}\right)\>:\>\mathcal{I}_{A}(A)=A\>.$ (5)

Here is another example. The elements of a POVM are actually operators summing
up (or resolving) the single-element state structure defined by

$\displaystyle\mathds{1}\geq 0\>,$ (6a)
$\displaystyle\text{Tr}\left[\mathds{1}\right]=d\>,$ (6b)
$\displaystyle\mathcal{D}\\{\mathds{1}\\}=\mathds{1}\>.$ (6c)

$\mathcal{D}$ is the depolarising superoperator, obeying

$\forall
A\in\mathcal{L}\left(\mathcal{H}^{A}\right)\>:\mathcal{D}_{A}(A)=\frac{\mathds{1}^{A}}{d_{A}}\otimes\Tr_{A}\left[A\right]\>,$
(7)

which projects onto the span of the identity.

###  II.1 Functionals

First, we characterize the type $\overline{A}$, generalizing the notion of a
set of deterministic effects. It is the set of operators representing all of
the functionals mapping each element of a state structure to the number 1 via
the Hilbert-Schmidt inner product $\text{Tr}\left[\overline{A}\cdot
A\right]=1$. Note that in the following we will always mean deterministic
effect when we use the word ‘effect’ alone.

(a) States and effects defining relation (8)

(b) Diagrammatic representation of how the projectors define a splitting of
the operator space

Figure 1: Picturing the characterizing equations of states and effects
deterministic type structures.

In a previous work [17], it was noticed that since both the set of states and
effects must contain an element proportional to the identity, the two
subspaces on which the states and effects are respectively defined must be
quasi-orthogonal 222The terminology “quasi-orthogonal” originated in the study
of maximally Abelian subalgebras (MASA), see Ref. [19]. This means that
operators $A$ and $\overline{A}$ must be orthogonal everywhere but at the span
of the identity. If $\overline{\mathcal{P}}_{A}$ is the projector for
$\overline{\mathscr{A}}$ it is related to $\mathcal{P}_{A}$ by
$\overline{\mathcal{P}}_{A}\equiv\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}$.
This leads to the rephrasing in terms of projectors of the characterization of
$\overline{\mathscr{A}}$ from type theory [5, Lemma 4].

######  Proposition 1 (Functional).

Let $\mathscr{A}$ be a state structure. Then the set $\bar{\mathscr{A}}$ of
operators taking each element of $\mathscr{A}$ to the number 1 through the
inner product,

$\overline{A}\in\overline{\mathscr{A}}\iff\forall
A\in\mathscr{A}\>:\>\text{Tr}\left[\overline{A}\cdot A\right]=1\>,$ (8)

is a state structure characterized by the following conditions:

$\displaystyle\bar{A}\geq 0\>,$ (9a)
$\displaystyle\text{Tr}\left[\bar{A}\right]=\frac{d_{A}}{c_{A}}\equiv
c_{\bar{A}}\>,$ (9b)
$\displaystyle\left\\{\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}\right\\}(\bar{A})\equiv\overline{\mathcal{P}}_{A}\left\\{\bar{A}\right\\}=\bar{A}\>.$
(9c)

The proof is provided in Appendix B.1, see Figure 1 for an illustration.
Concrete examples of states structures characterized by Prop. 1 are given in
Appendix C.2. This proposition was first obtained as a theorem in our earlier
work on Multi-round Process Matrices (MPM) [17].

Quasi-orthogonality implies the following property [19, Theorem 2.37 iii)]:

$\forall
A\in\mathscr{A},\forall\overline{A}\in\overline{\mathscr{A}}\>,\>\text{Tr}\left[\overline{A}\cdot
A\right]=\frac{1}{d_{A}}\text{Tr}\left[\overline{A}\right]\text{Tr}\left[A\right]\>.$
(10)

As both sets have an element proportional to the identity, combining equations
(8) and (10) yields the following.

$\text{Tr}\left[\overline{A}\cdot
A\right]=\text{Tr}\left[\overline{A}\cdot\frac{\mathds{1}}{c_{\bar{A}}}\right]\text{Tr}\left[\frac{\mathds{1}}{c_{A}}\cdot
A\right]\>.$ (11)

Figure 2: Quasi-orthogonality condition (10)

Figure 2 provides a graphical interpretation of this relation. This is the
physical content of Proposition 1: the generalized Born rule is independent of
a particular choice of deterministic state and deterministic effect; Both the
state and the effect can be replaced by the identity – or any other element of
their respective state structures – without altering the outcome probability
of 1. Put differently, even when replacing either the state or the effect by
pure noise, something has to be measured in the end.

Here, the bar in
“$\overline{\mathcal{P}}_{A}\equiv\mathcal{I}-\mathcal{P}_{A}+\mathcal{D}$”
can be seen as an operation at the level of projectors that was applied on
$\mathcal{P}_{A}$. As such, the projector $\overline{\mathcal{P}}_{A}$ will be
called the negation of $\mathcal{P}_{A}$ because the operation has properties
similar to a logic not. This is developed in more details below and in
Appendix A.2.

###  II.2 Tensor product

The tensor product of two types as a parallel composition generalizes the
notion of no signaling channel [15]. In terms of projectors, the
characterization relies on raising the tensor product operation at the level
of superoperators in a natural fashion. Let $\mathcal{P}_{A}$ and
$\mathcal{P}_{B}$ be respectively projectors on operator spaces $A$ and $B$,
then $\mathcal{P}_{A}\otimes\mathcal{P}_{B}$ acts on
$\mathcal{L}\left(\mathcal{H}^{A}\otimes\mathcal{H}^{B}\right)$ so that

$\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\left\\{\sum_{i}\;q_{i}\;\left(A_{i}\otimes
B_{i}\right)\right\\}\equiv\\\
\sum_{i}\;q_{i}\;\left(\mathcal{P}_{A}\left\\{A_{i}\right\\}\otimes\mathcal{P}_{B}\left\\{B_{i}\right\\}\right)\>,$
(12)

$\forall q_{i}\in\mathbb{C}$.

######  Proposition 2 (No signaling (bipartite) composition).

Let $\mathscr{A}$ and $\mathscr{B}$ be two state structures as in Eqs. 3,
their no signaling composition
$\mathscr{A}\otimes\mathscr{B}\subset\mathcal{L}\left(\mathcal{H}^{A}\otimes\mathcal{H}^{B}\right)$
is the set of all operators $X$ characterised by the following constrains:

$\displaystyle X\in\mathscr{A}\otimes\mathscr{B}:$ $\displaystyle X\geq 0\>,$
(13a) $\displaystyle\text{Tr}\left[X\right]=c_{A}c_{B}\>,$ (13b)
$\displaystyle\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\\{X\\}=X\>.$
(13c)

Consequently, $\mathscr{A}\otimes\mathscr{B}$ is the affine span of
$\mathscr{A}$ and $\mathscr{B}$.

See Appendix B.2 for the proof. We have just stated that the affine hull of a
tensor product of state structures is a state structure itself [5, Lemma 5],
this proposition will help us in the characterization of the CJ representation
of mappings between state structures below. A diagrammatic depiction is given
in Figure 3, and examples of the use of the above can be found in Appendix
C.3.

Figure 3: Illustration of Proposition 2 and diagrammatic representation in the
case of the tensor product of 2 subsystems: the full wheel represents
$\mathcal{L}\left(\mathcal{H}^{A}\otimes\mathcal{H}^{B}\right)$ while its
parts represent its tensor factors (‘Im’ means ‘Image’, so that e.g. $D$ is a
shortcut for
$\mathrm{Im}\\{\mathcal{D}\\}=\text{Span}\left\\{\mathds{1}\right\\}$). By
convention, the projectors acting on $\mathcal{L}\left(\mathcal{H}^{A}\right)$
are always on the left-hand side of tensor products and vice-versa for $B$, so
that subscripts can be omitted. Note that the intersections are well defined;
for example the line ‘$A\otimes D$’ is indeed the intersection $A\otimes B\cap
A\otimes\bar{B}$.

###  II.3 Transformations

In the type theory of higher-order transformations, every type is an instance
of a transformation, so the previous characterization of generalized effects
(type $\bar{A}$) and bipartite states (type $A\otimes B$) are but special
cases of a more general rule. This rule says that if $A$ and $B$ are types,
then $A\rightarrow B$ is itself a type that takes $A$ to $B$. A state of type
$A$ is actually a transformation of the trivial type – the number 1 – into
$A$, noted $1\rightarrow A$. Accordingly, the effect of type $\overline{A}$ is
the transformation of type $A$ into a trivial system, $A\rightarrow 1$. No
signaling composition is the type $A\otimes
B\equiv\overline{A\rightarrow\overline{B}}$.

As we have seen, the set of elements of a given type corresponds to a state
structure, ultimately determined by its projector. Thus, to type $A\rightarrow
B$ corresponds a state structure, noted $\mathscr{A}\rightarrow\mathscr{B}$,
which is obtained by combining state structures $\mathscr{A}$ and
$\mathscr{B}$ in a certain way. This structure should then be characterized by
a composite projector built by combining $\mathcal{P}_{A}$ and
$\mathcal{P}_{B}$ using the two previously introduced rules.

Following previous approaches [1, 4, 5, 20], we want the transformation – or
dynamics – to conserve the total probability as well as probabilistic
mixtures, and it should also be defined when acting on a tensor factor of any
no signaling composite system [5, Definition 7]. In other words, the dynamical
law should remain valid even when one is coarse-graining or fine-graining the
system. The preservation of probabilistic mixtures, convex linearity, implies
that the maps representing such dynamics are linear (see Ref. [1, 8, 4, 5] for
the proof).

######  Definition 3 (Structure-preserving map).

Let $\mathcal{M}$ be a linear map from
$\mathcal{L}\left(\mathcal{H}^{A}\right)$ to
$\mathcal{L}\left(\mathcal{H}^{B}\right)$. This map is structure-preserving
between $\mathscr{A}$ and $\mathscr{B}$ if it maps any element of state
structure $\mathscr{A}$ to one in $\mathscr{B}$, and moreover if it keeps this
property when these state structures are embedded in larger systems. That is,
for any state structure $\mathscr{C}$, the map
$\mathcal{M}\otimes\mathcal{I}_{C}\in\mathcal{L}\left(\mathcal{L}\left(\mathcal{H}^{A}\otimes\mathcal{H}^{C}\right),\mathcal{L}\left(\mathcal{H}^{B}\otimes\mathcal{H}^{C}\right)\right)$
should map any element of $\mathscr{A}\otimes\mathscr{C}$ to one of
$\mathscr{B}\otimes\mathscr{C}$.

Moving on to the characterisation of valid dynamics, let
$\mathcal{M}\in\mathcal{L}\left(\mathcal{L}\left(\mathcal{H}^{A}\right),\mathcal{L}\left(\mathcal{H}^{B}\right)\right)$
be a linear map. We translate the first condition of Definition 3 into the
following conditions for all $A\in\mathscr{A}$ [20] :

$\displaystyle\mathcal{M}\left(A\right)\geq 0\>,$ (14a)
$\displaystyle\text{Tr}\left[\mathcal{M}\left(A\right)\right]=c_{B}\>,$ (14b)
$\displaystyle\mathcal{P}_{B}\circ\mathcal{M}\circ\mathcal{P}_{A}=\mathcal{M}\circ\mathcal{P}_{A}\>.$
(14c)

The second condition further constrains the positivity preserving condition
(14a) to $\mathcal{M}$ being completely positive (CP) as $\mathscr{C}$ can in
general be defined over the whole of
$\mathcal{L}\left(\mathcal{H}^{C}\right)$. If we denote by $M$ the CJ
representation of $\mathcal{M}$, the set of all these maps $M$ is a state
structure [5, Proposition 1].

######  Proposition 3 (Mapping between state structures).

Let
$\mathcal{M}\in\mathcal{L}\left(\mathcal{L}\left(\mathcal{H}^{A}\right),\mathcal{L}\left(\mathcal{H}^{B}\right)\right)$
be a structure-preserving map between state structures $\mathscr{A}$ and
$\mathscr{B}$. Call
$M\in\mathcal{L}\left(\mathcal{H}^{A}\otimes\mathcal{H}^{B}\right)$ the Choi-
Jamiołkowski representation of this map, as in Eq. (1). Then, the set
$\\{M\\}$ of all such maps belongs to the type structure
$\overline{\mathscr{A}\otimes\overline{\mathscr{B}^{T}}}$, which means that it
satisfies the following conditions:

$\displaystyle M\geq 0\>,$ (15a)
$\displaystyle\text{Tr}\left[M\right]=c_{\bar{A}}c_{B}=\frac{c_{B}}{c_{A}}d_{A}\>,$
(15b)
$\displaystyle\left(\mathcal{P}_{A}\rightarrow\mathcal{P}_{B^{T}}\right)\\{M\\}\equiv\left(\overline{\mathcal{P}_{A}\otimes\overline{\mathcal{P}}_{B^{T}}}\right)\\{M\\}=M\>.$
(15c)

(a) Graphical interpretation of $\mathscr{A}\rightarrow\mathscr{B}$

(b) Diagram for the subspaces defined by Eq. (15c) (blue) and
$\mathcal{P}_{A}\otimes\overline{\mathcal{P}}_{B}$ (yellow)

Figure 4: Illustration of Proposition 3

##### Remark.

The above derivation is very close in spirit to Ref. [20] where the projective
characterization of transformations was first made in the context of
transformation between process matrices, but the obtained projector was
missing two terms 333What the authors had obtained in the context of process
matrix to process matrix transformation was
$\mathcal{I}_{A}\otimes\mathcal{I}_{B}-\mathcal{P}_{A}\otimes\mathcal{I}_{B}+\mathcal{P}_{A}\otimes\mathcal{P}_{B}$,
where $\mathcal{P}_{A}$ is the projector characterizing the input process
matrix state structure and $\mathcal{P}_{B}$ the output. Compared to equation
(15c), here written fully without negation,
$\overline{\mathcal{P}_{A}\otimes\overline{\mathcal{P}}_{B}}=\mathcal{I}_{A}\otimes\mathcal{I}_{B}-\mathcal{P}_{A}\otimes\mathcal{I}_{B}+\mathcal{P}_{A}\otimes\mathcal{P}_{B}-\mathcal{P}_{A}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}$,
one sees that two terms are missing. In particular, they are the ones that
forbids to postselect on a process matrix before preparing a new one that is
purely noisy.. After verification, it appears that this omission has not
hindered the other conclusions of this article [22].

Concrete examples of the use of this Proposition can be found in the Appendix
C.4. This Appendix also provides motivation for the ideas introduced in
Section IV.

###  II.4 The algebra of projectors recovers the type theory

We started from the type theory of higher-order transforms in which
$\bar{A},A\rightarrow B,A\otimes B$ are the new types that one can obtain from
a base type $A$ under the semantic rules $\\{1,(,),\rightarrow\\}$.

We observed that types define state structures, which are trace-normalized
subsets of positive operator systems for which
$\overline{\mathscr{A}},\mathscr{A}\rightarrow\mathscr{B},\mathscr{A}\otimes\mathscr{B}$
are the new state structures one can obtain from a base $\mathscr{A}$. These
state structures are the sets of CJ operators representing higher-order maps.

As these state structures are defined on linear subspaces, most of their
properties are encoded by the superoperator projector that defines them.
$\overline{\mathcal{P}}_{A},\mathcal{P}_{A}\rightarrow\mathcal{P}_{B},\mathcal{P}_{A}\otimes\mathcal{P}_{B}$
are the new projectors that one can obtain from a projector $\mathcal{P}_{A}$
according to the algebraic rules $\\{1,(,),\rightarrow\\}$ (which can be taken
as $\\{\overline{\>\cdot\>},\otimes,\rightarrow\\}$ instead).

Therefore, working with projectors is a handy way to define the
characterization constraints implied by type theory.

##  III Abstracting the algebra of projectors

We now make a short pause in the characterization to point out that the
algebraic rules obeyed by the projectors are not arbitrary. They actually form
an algebra, as well as a model of logic.

###  III.1 Beyond type theory: algebra of projectors

Type theory is dependent on a base type. In Ref. [5], the first non-trivial
type in the hierarchy, called the elementary type, is taken as the set of
quantum states as in Eqs. (4). Within the framework of state structures, one
can use other elementary types as a base. The question then is how to classify
these nonequivalent theories, and how to compare them.

In terms of subspaces, comparing is straightforward as one can consider the
overlap between the two subspaces. For this purpose, one needs two new rules.
These are the intersection, nicknamed ‘cap’,

$\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\equiv\mathcal{P}_{A}\circ\mathcal{P}^{{}^{\prime}}_{A}\>,$
(16)

and the union, ‘cup’,

$\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}\equiv\mathcal{P}_{A}+\mathcal{P}^{{}^{\prime}}_{A}-\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\>.$
(17)

This definition assumes that all projectors in the algebra must commute with
respect to the cap,
$\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}=\mathcal{P}^{{}^{\prime}}_{A}\cap\mathcal{P}_{A}$,
$\forall\mathcal{P}_{A},\mathcal{P}^{{}^{\prime}}_{A}$. This is indeed a
sufficient condition for $\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}$ to
be a projector on operator system as well. More details are given in App. A.2.

With these, one can prove that an operator system is contained within another
by showing either of the following:

$\displaystyle\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}=\mathcal{P}^{{}^{\prime}}_{A}\>;$
(18a)
$\displaystyle\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}=\mathcal{P}_{A}\>.$
(18b)

In terms of projectors, these conditions will be concisely noted

$\mathcal{P}^{{}^{\prime}}_{A}\subset\mathcal{P}_{A}\>.$ (19)

Since the projectors are themselves CPTP maps, inclusion of projectors is
indeed sufficient to show inclusion of the corresponding state structures (up
to normalization).

As it turns out, the projectors form an algebra under the rules
$\\{\cap,\cup\\}$ (see Appendix A.2 for proof). And because every operator
system must contain the identity element, every projector in the algebra is
contained between the depolarizing and identity projectors,

$\mathcal{D}\subset\mathcal{P}\subset\mathcal{I}.$ (20)

However, the cap and the cup are new rules that cannot be expressed using the
$\rightarrow$ connector. So the downside of the algebra is that it is outside
of the type-theoretic framework of references [4, 5].

Adding $\overline{\>\cdot\>}$ as an operation in the algebra promotes it into
a Boolean algebra, i.e. an algebra of idempotent elements which possess a
negation. $\overline{\>\cdot\>}$ acts as the negation since it makes
$\overline{\mathcal{P}}_{A}$ complementary to $\mathcal{P}_{A}$,
$\mathcal{P}_{A}\cup\overline{\mathcal{P}}_{A}=\mathcal{I}_{A}$ and it is an
involution $\overline{\overline{\mathcal{P}}}_{A}=\mathcal{P}_{A}$ (see
Appendix A.3 for more details).

###  III.2 The algebra of projectors is (almost) Linear Logic

With the further additions of the tensor and of the transformations
operations, the Boolean algebra of projectors is lifted to an abstract
structure that happens to follow the rules of linear logic (LL) [23]. This
extends an observation made in Ref. [9] that the logic of higher-order quantum
transformations, in our language the projector rules
$\\{\overline{\>\cdot\>},\otimes,\rightarrow\\}$, form an instance of
multiplicative linear logic.

Observe that the transformation between states is equivalent to the reverse
transformation between effects,

$\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}=\overline{\mathcal{P}}_{A}\leftarrow\overline{\mathcal{P}}_{B}=\overline{\mathcal{P}_{A}\otimes\overline{\mathcal{P}}_{B}}\>.$
(21)

This is indeed a sign of the algebra being an instance of linear logic: it
follows the logic rule that if A implies B, then not B must imply not A. As
such, the $\rightarrow$ corresponds to the linear implication of LL, nicknamed
lollipop and noted “$\multimap$”. Negating the input of a transformation
allows one to treat it as a composition:

$\overline{\mathcal{P}}_{A}\rightarrow\mathcal{P}_{B}=\overline{\overline{\mathcal{P}}_{A}\otimes\overline{\mathcal{P}}_{B}}\>.$
(22)

This is a “larger” composition than the tensor as
$\overline{\overline{\mathcal{P}}_{A}\otimes\overline{\mathcal{P}}_{B}}\neq\mathcal{P}_{A}\otimes\mathcal{P}_{B}$
and

$\mathcal{P}_{A}\otimes\mathcal{P}_{B}\subset\overline{\overline{\mathcal{P}}_{A}\otimes\overline{\mathcal{P}}_{B}}.$
(23)

As such, operation “ $\overline{\>\cdot\>}\rightarrow\>\cdot\>$” corresponds
to the par, “$\mathrel{\rotatebox[origin={c}]{180.0}{$\&$}}$”, of LL, which,
together with $\otimes$, respectively constitute the multiplicative
disjunction and conjunction. The additive disjunction and conjunction
correspond to the cup and the cap, respectively, and the linear negation is
the negation. They happen to be because on the one hand they respect the De
Morgan laws

$\displaystyle\overline{\overline{\mathcal{P}}}_{A}=\mathcal{P}_{A}\>;$ (24a)
$\displaystyle\overline{\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}}=\overline{\mathcal{P}}_{A}\cup\overline{\mathcal{P}}^{{}^{\prime}}_{A}\>;$
(24b)
$\displaystyle\overline{\overline{\mathcal{P}}_{A}\otimes\mathcal{P}_{B}}=\overline{\mathcal{P}}_{A}\rightarrow\overline{\mathcal{P}}_{B}\>.$
(24c)

On the other hand, there exist a truth and a falsity for both additive and
multiplicative rules, and they are the negation of each other. See Appendix
A.4.3 for the details. The correspondence with LL is made in Table 1, where
the rules we have introduced are put in correspondence with their usual
notation of LL.

Name | Symbol | Unit
---|---|---
| proj. | LL | proj. | LL
Negation | $\overline{\>\cdot\>}$ | $\cdot^{\perp}$ | / | /
Additive conjunction | $\cap$ | $\&$ | $\mathcal{I}$ | T
Additive disjunction | $\cup$ | $\oplus$ | $\mathcal{D}$ | 0
Multiplicative conjunction | $\otimes$ | $\otimes$ | 1 | 1
Multiplicative disjunction | $\overline{\>\cdot\>}\rightarrow\cdot$ | $\mathrel{\rotatebox[origin={c}]{180.0}{$\&$}}$ | 1 | $\perp$
Linear Implication | $\rightarrow$ | $\multimap$ | 1 | /
Table 1: Correspondence of the algebraic rules of projective characterization
(proj.) with linear logic (LL)

Nonetheless, the algebra of projectors is still not a full model of linear
logic as the exponential connectors used to relate additive and multiplicative
formulae have not been defined. To be precise, it is a model of multiplicative
additive linear logic (MALL). In addition to that, remark that the
multiplicative truth and falsity are the same thing: the trivial projector
onto the trivial system, i.e. the number 1. There is also the issue that the
additive falsity is not absorbant for multiplicative formulae, i.e.,
$\mathcal{P}_{A}\otimes\mathcal{D}_{B}\neq\mathcal{D}_{AB}$.

The fact that the algebra of the projectors characterizing quantum higher-
order transformations is an instance of MALL can additionally be understood as
the consequence of the correspondence between the types of Ref. [5] and
$*-$autonomous categories as in Ref. [9].

##  IV No signaling

In a previous work, the projective characterization was used to prove that the
multi-round process matrix is a linear sum of quantum combs [17, Theorem 2].
That is, it allowed to split an MPM, which typically involves several
directions of signaling, into a sum of quantum combs, featuring single, fixed
directions.

In this section, the notion of no signaling is extended to state structures,
in order for this decomposition to be generalized. Quasi-orthogonality will be
shown to be the relevant notion for no signaling at the level of projectors,
allowing in turn to define the prec, an algebraic rule for composing
projectors that encodes a one-way signaling constraint.

###  IV.1 Definition

No signaling from the input to the output can be imposed on a transformation
as an extra condition. This translates the physical idea that, if the output
is assumed to be in the causal future of the input, no (deterministic)
operation done in the future can influence, or signal to, the past [24].

The subset obeying this constraint will be noted using a “$\prec$” symbol,
nicknamed the prec. By convention this connector will be seen as a
composition, meaning that to represent a transformation, the input has to be
negated. Thus, we want to define the set
$\overline{\mathscr{A}}\prec\mathscr{B}\subset\mathscr{A}\rightarrow\mathscr{B}$.
This condition is expressed as the requirement that the input of the
transformation should be independent of the particular choice of effect
applied at its output:

$M\in\overline{\mathscr{A}}\prec\mathscr{B}\subset\mathscr{A}\rightarrow\mathscr{B}:\quad\forall\overline{B},\overline{B}^{\prime}\in\overline{\mathscr{B}},\\\
\text{Tr}_{B}\left[M\cdot\left(\mathds{1}\otimes\overline{B}\right)\right]=\text{Tr}_{B}\left[M\cdot\left(\mathds{1}\otimes\overline{B}^{\prime}\right)\right]\>.$
(25)

As the identity matrix $\mathds{1}$ is always both a valid state and effect
(with suitable normalization), this requirement is rephrased as the following
constraint,

$\forall\overline{B}\in\overline{\mathscr{B}},\;\text{Tr}_{B}\left[M\cdot\left(\mathds{1}\otimes\overline{B}\right)\right]=\text{Tr}_{B}\left[M\cdot\left(\mathds{1}\otimes\frac{\mathds{1}}{c_{B}}\right)\right]\>.$
(26)

This is depicted in Fig. 5c. When the above is satisfied, we will use it as a
definition to say that $M$ is no signaling from $B$ to $A$ [14, 15]. The same
way, one can define the no input-to-output signaling subset,
$\overline{\mathscr{A}}\succ\mathscr{B}$, by requiring the condition drawn in
Fig. 5f.

(a) $\overline{\mathscr{A}}\leftarrow\overline{\mathscr{B}}$, which is an
equivalent condition to Fig. 4a because of Eq. (21)

(b) Notion of causality for channels;
$\overline{\mathscr{A}}\leftarrow\overline{\mathscr{B}}$, in the case
$\overline{\mathcal{P}}_{B}=\mathcal{D}_{B}$

(c) No signaling from output to input, Eq. (26); Eq. (37a)

(d) Eq. (26) is trivial for the case
$\overline{\mathcal{P}}_{B}=\mathcal{D}_{B}$

(e) Diagram for the subspace defined by Eq. (26)

(f) No signaling from input to output, Eq. (37b)

Figure 5: Graphical interpretation of the various conditions that can be
imposed on a map, and illustration of Prop. 4

##### Relation with the usual definition.

This no signaling definition recovers the one used in the respective case of
quantum channel formalism. Indeed, the validity condition of transformations
between quantum states implies that $\mathscr{A}=\left\\{\rho|\rho\geq
0\cap\text{Tr}\left[\rho\right]=1\right\\}$, so that
$\overline{\mathscr{A}}=\\{\mathds{1}_{A}\\}$ and
$\overline{\mathscr{B}}=\left\\{\mathds{1}_{B}\right\\}$. Observe that because
of Eq. (21), a map $M\in\mathscr{A}\rightarrow\mathscr{B}$ can be equivalently
interpreted as $\overline{\mathscr{B}}\rightarrow\overline{\mathscr{A}}$.
Since $M$ must obey
$\text{Tr}_{B}\left[M\left(\mathds{1}_{A}\otimes\overline{B}\right)\right]\in\overline{\mathscr{A}}$
by definition (see Fig. 5a), and since
$\overline{\mathscr{A}}=\\{\mathds{1}_{A}\\}$, we attain the usual
$M\in\mathscr{A}\rightarrow\mathscr{B}\iff$

$\text{Tr}_{B}\left[M\left(\mathds{1}_{A}\otimes\mathds{1}_{B}\right)\right]=\text{Tr}_{B}\left[M\right]=\mathds{1}_{A}\>,$
(27)

which is used as both a validity and a causality condition in previous works
[3, 9] (Fig. 5b). The reason is that condition (26) becomes tautological in
that case (Fig. 5d). However, this equivalence between a general
transformation and a no signaling one is only valid for the case of density
matrices and hides the subtle difference between the two definitions in the
general case for which being a valid transformation does not guarantee that
the output cannot be used to signal to the input.

###  IV.2 Projective characterization

Equation (26) can be rewritten as

$\forall\overline{B}\in\overline{\mathscr{B}},\;\text{Tr}_{B}\left[M\cdot\left(\mathds{1}\otimes\overline{B}\right)\right]=\frac{1}{d_{B}}\text{Tr}_{B}\left[M\right]\text{Tr}\left[\overline{B}\right]\>.$
(28)

This ‘factorization’ of the partial trace is reminiscent of the property (10)
of quasi-orthogonal subspaces. In Appendix B.4, it is proven that the no
signaling requirement defined in the previous section is enforced by a system-
wise notion of quasi-orthogonality.

######  Theorem 1.

Let $M$ be a positive operator in
$\mathcal{L}\left(\mathcal{H}^{A}\otimes\mathcal{H}^{B}\right)$, let $A$ be
one in $\mathscr{A}$ and let $B$ be one in $\mathscr{B}$. Then a necessary and
sufficient condition for condition

$\text{Tr}_{A}\left[M\cdot\left(A\otimes
B\right)\right]=\frac{\text{Tr}_{A}\left[M\right]\text{Tr}_{A}\left[A\right]}{d_{A}}\cdot
B\>,$ (29)

to hold for all $A$, implying that

$\text{Tr}_{A}\left[M\cdot\left(A\otimes\mathds{1}\right)\right]=c_{A}\text{Tr}_{A}\left[M\right]\>,$
(30)

is that

$\left(\overline{\mathcal{P}}_{A}\otimes\mathcal{I}_{B}\right)\left\\{M\right\\}=M\>.$
(31)

That is to say, that $M$ belongs to
$\overline{\mathscr{A}}\otimes\mathcal{L}\left(\mathcal{H}^{B}\right)$.

As the above theorem states that no signaling is equivalent to restricting the
operator to a subspace, a necessary and sufficient condition for the state
structure $\mathscr{A}\rightarrow\mathscr{B}$ to be no signaling from the
output to the input is that its projector gets restricted accordingly. The
projector for $\overline{\mathscr{A}}\prec\mathscr{B}$ is thus obtained by
taking the intersection of the projectors

$\left(\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}\right)\cap\left(\mathcal{I}_{A}\otimes\mathcal{P}_{B}\right)\\\
=\left(\mathcal{I}_{A}\otimes\mathcal{I}_{B}-\mathcal{P}_{A}\otimes\overline{\mathcal{P}}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\right)\cap\left(\mathcal{I}_{A}\otimes\mathcal{P}_{B}\right)\\\
=\mathcal{I}_{A}\otimes\mathcal{P}_{B}-\mathcal{P}_{A}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\\\
\equiv\overline{\mathcal{P}}_{A}\prec\mathcal{P}_{B}\>.$ (32)

As a consequence, $\overline{\mathscr{A}}\prec\mathscr{B}$ is a state
structure.

######  Proposition 4 (One-way signaling composition).

Let $\mathscr{A}$ and $\mathscr{B}$ be two state structures as in Eqs. (3),
their one-way signaling composition
$\mathscr{A}\prec\mathscr{B}\subset\mathcal{L}\left(\mathcal{H}^{A}\otimes\mathcal{H}^{B}\right)$
is the set of all operators $W$ characterized by the following conditions:

$\displaystyle W\geq 0\>,$ (33a)
$\displaystyle\text{Tr}\left[W\right]=c_{A}c_{B}\>,$ (33b)
$\displaystyle\left(\mathcal{P}_{A}\prec\mathcal{P}_{B}\right)\\{W\\}=W\>.$
(33c)

where

$\mathcal{P}_{A}\prec\mathcal{P}_{B}\equiv\mathcal{I}_{A}\otimes\mathcal{P}_{B}-\overline{\mathcal{P}}_{A}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\;.$
(34)

###### Proof.

Directly from the above discussion, the conditions are obtained by applying
the linear constraint $\mathcal{I}_{A}\otimes\mathcal{P}_{B}$ to the set
$\overline{\mathscr{A}}\rightarrow\mathscr{B}=\overline{\overline{\mathscr{A}}\otimes\overline{\mathscr{B}}}=\mathscr{A}\leftarrow\overline{\mathscr{B}}$
characterized by Proposition 3. ∎

See Fig. 5e for a diagrammatic depiction of the subspace associated with
projector (33c). The main rules for characterizing higher-order theories
through their projector rules are summarized in Table 2.

Name | Characterization | Proj. rule | Rule nickname
---|---|---|---
State | Def. 2; Eqs. (3) | $\mathcal{P}_{A}$ | /
Effect | Prop. 1; Eqs. (9) | $\overline{\mathcal{P}}_{A}$ | Negation
No Sign. | Prop. 2; Eqs. (13) | $\overline{\mathcal{P}}_{A}\otimes\mathcal{P}_{B}$ | Tensor
2-ways Sign. | Prop. 3; Eqs. (15) | $\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}$ | Transformation
1-way Sign. | Prop. 4; Eqs. (33) | $\overline{\mathcal{P}}_{A}\prec\mathcal{P}_{B}$ | Prec
Table 2: Summary of the characterization rules for state structure of states,
effects, and the three compositions

###  IV.3 Relating the compositions

Using the algebra, the three bipartite rules $\otimes,\prec,\rightarrow$ can
be related together by the following relations:

$\displaystyle\overline{\mathcal{P}}_{A}\otimes\mathcal{P}_{B}$
$\displaystyle=(\overline{\mathcal{P}}_{A}\prec\mathcal{P}_{B})\cap(\overline{\mathcal{P}}_{A}\succ\mathcal{P}_{B})\>,$
(35a) $\displaystyle\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}$
$\displaystyle=(\overline{\mathcal{P}}_{A}\prec\mathcal{P}_{B})\cup(\overline{\mathcal{P}}_{A}\succ\mathcal{P}_{B}).$
(35b)

See Appendix A.5 for the proof. These have a concrete physical interpretation.
In a first time, consider the set $\overline{\mathscr{A}}\otimes\mathscr{B}$.
Its elements are transformations from $\mathscr{A}$ to $\mathscr{B}$ as each
$M\in\overline{\mathscr{A}}\otimes\mathscr{B}$ satisfies

$\text{Tr}_{A}\left[M\cdot(A\otimes\mathds{1})\right]\in\mathscr{B}\>,$ (36)

because
$\overline{\mathcal{P}}_{A}\otimes\mathcal{P}_{B}\subset\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}$.

In addition to that, the right-hand side of Eq. (35a) puts two extra
conditions on $\overline{\mathscr{A}}\otimes\mathscr{B}$ that are similar to
Eq. (26); it requires that
$\left(\overline{\mathcal{P}}_{A}\otimes\mathcal{P}_{B}\right)\\{M\\}=M\iff\forall
A\in\mathscr{A},\forall\overline{B}\in\overline{\mathscr{B}}$,

$\displaystyle\text{Tr}_{A}\left[M\cdot\left(A\otimes\mathds{1}\right)\right]=\text{Tr}_{A}\left[M\cdot\left(\frac{\mathds{1}}{c_{\bar{A}}}\otimes\mathds{1}\right)\right]\>;$
(37a)
$\displaystyle\text{Tr}_{B}\left[M\cdot\left(\mathds{1}\otimes\overline{B}\right)\right]=\text{Tr}_{B}\left[M\cdot\left(\mathds{1}\otimes\frac{\mathds{1}}{c_{B}}\right)\right]\>.$
(37b)

Therefore, the above pair of conditions reveals the set
$\overline{\mathscr{A}}\otimes\mathscr{B}$ as the set of transformations that
are compatible with no signaling from system A to system B and from B to A at
the same time; it is no signaling in both directions, hence the name.

The same way, the $\mathscr{A}\rightarrow\mathscr{B}$ set is the set of
transformations that respect no signaling from A to B or B to A. Thus, it may
allow linear combinations of signaling in both directions and consequently to
indefinite causal order.

The sets $\overline{\mathscr{A}}\prec\mathscr{B}$ and
$\overline{\mathscr{A}}\succ\mathscr{B}$ lie in between, as they permit
signaling in only one direction. Their elements indeed obey condition (35a)
but only one of the conditions (37).

This discussion underlies the following chain of inclusions:

$\displaystyle\overline{\mathcal{P}}_{A}\otimes\mathcal{P}_{B}\subset\overline{\mathcal{P}}_{A}\prec\mathcal{P}_{B}\subset\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}\>,$
(38a)
$\displaystyle\overline{\mathcal{P}}_{A}\otimes\mathcal{P}_{B}\subset\overline{\mathcal{P}}_{A}\succ\mathcal{P}_{B}\subset\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}\>,$
(38b)

See Figure 6 for a diagrammatic interpretation.

Figure 6: Inclusions between the various ways of composing projectors

##### Defining the tensor product as no signaling.

Naturally, Eqs. (37) are also valid for bipartite states:
$\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\\{W\\}=W\iff\forall\overline{A}\in\overline{\mathscr{A}}{},\forall\overline{B}\in\overline{\mathscr{B}}$,

$\displaystyle\text{Tr}_{A}\left[\left(\overline{A}\otimes\mathds{1}\right)\cdot
W\right]=\text{Tr}_{A}\left[\left(\frac{\mathds{1}}{c_{A}}\otimes\mathds{1}\right)\cdot
W\right]\>;$ (39a)
$\displaystyle\text{Tr}_{B}\left[\left(\mathds{1}\otimes\overline{B}\right)\cdot
B\right]=\text{Tr}_{B}\left[\left(\mathds{1}\otimes\frac{\mathds{1}}{c_{B}}\right)\cdot
W\right]\>.$ (39b)

It should be noted that the definition of the no signaling composition
$\otimes$ can be done solely by requiring these two equations to be valid
simultaneously; there is no need to additionally require that $W$ is a
transformation (i.e. that it belongs to
$\overline{\mathscr{A}}\rightarrow\mathscr{B}=\mathscr{A}\rightarrow\overline{\mathscr{B}}$).
This observation have a two corollaries: on the one hand, it provides a
‘transformation-free’ definition of the tensor product based only on the
validity of Theorem 1. On the other hand, it justifies its nickname of ‘no
signaling composition’.

##### Remark.

While the interpretation of the transformation (“$\rightarrow$”) in linear
logic is the linear implication (“$\multimap$”), the “$\prec$” connector has
no studied counterpart in linear logic. Still, the fact that it is a
multiplicative connector that commutes with negation makes its appearance in
the algebra look natural. Exploring the properties of the prec in LL is left
for future work.

##### Categorical perspectives.

In terms of categories, higher-order theories of transformations built using
two-way signaling composition can be seen as a category with objects in
$\mathscr{A}$ and morphisms in $\mathscr{A}\rightarrow\mathscr{B}$, thereafter
noted $\mathcal{C}(\mathscr{A},\mathscr{A}\rightarrow\mathscr{B})$. These are
$*-$autonomous categories, meaning that they possess two monoidal structures
($\otimes$ and $\overline{\cdot}\rightarrow\cdot$) and that negation commutes
with neither of them [9].

The one-way signaling composition provides a decomposition of these
$*-$autonomous categories into the union of two closed compact categories,
$\mathcal{C}(\mathscr{A},\overline{\mathscr{A}}\prec\mathscr{B})$ and
$\mathcal{C}(\mathscr{A},\overline{\mathscr{A}}\succ\mathscr{B})$. These
induce the following chains of wide subcategories:

$\displaystyle\mathcal{C}(\mathscr{A},\overline{\mathscr{A}}\otimes\mathscr{B})\subset\mathcal{C}(\mathscr{A},\overline{\mathscr{A}}\prec\mathscr{B})\subset\mathcal{C}(\mathscr{A},\mathscr{A}\rightarrow\mathscr{B})\>,$
(40)
$\displaystyle\mathcal{C}(\mathscr{A},\overline{\mathscr{A}}\otimes\mathscr{B})\subset\mathcal{C}(\mathscr{A},\overline{\mathscr{A}}\succ\mathscr{B})\subset\mathcal{C}(\mathscr{A},\mathscr{A}\rightarrow\mathscr{B})\>.$
(41)

Surely, this decomposition calls for a more systematic functorial treatment:
the category of higher-order transformations actually features not two but
three monoidal structures, with one of them ($\prec$) being compact and
closed.

###  IV.4 The algebra of projectors recovers no signaling

We started from the projective characterization of higher-order
transformations in which
$\overline{\mathcal{P}}_{A},\mathcal{P}_{A}\rightarrow\mathcal{P}_{B},\mathcal{P}_{A}\otimes\mathcal{P}_{B}$
are the new projectors one can obtain from a projector $\mathcal{P}_{A}$ under
the algebraic rules $\\{\overline{\>\cdot\>},\otimes,\rightarrow\\}$.

We observed that the notion of no signaling could be generalized for the case
of state structures. In particular, it was noticed that the notion could be
encoded by a new rule $\prec$ in the algebra of projectors, introduced under
the name prec.

Bipartite state structures obtained by combining $\overline{\mathscr{A}}$ and
$\mathscr{B}$ fall into four classes, essentially determined by conditions
(36), (37a), and (37b). All of these classes must satisfy the first condition,
which amounts to being a valid transformation and to which corresponds the
projector $\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}$. If in addition
condition (37a) (respectively, (37b)) is satisfied, the set is restricted to
transformation that is no signaling from the output to the input (resp., from
the input to the output), to which corresponds the projector
$\overline{\mathcal{P}}_{A}\prec\mathcal{P}_{B}$ (resp.,
$\overline{\mathcal{P}}_{A}\succ\mathcal{P}_{B}$). If both conditions are
satisfied, the set is no signaling, to which corresponds the projector
$\overline{\mathcal{P}}_{A}\otimes\mathcal{P}_{B}$.

Therefore, working with projectors provides a handy way of assessing the
signaling structure within a state structure.

##  V Implications of the formalism

With the formalization of the projective characterization and the introduction
of the one-way signaling subsets using the prec, we now have the tools to
address signaling in theories of higher-order quantum transformations. In this
section, we are interested only in the qualitative aspects of state
structures, meaning that we will not be referring to operators, but only sets
and their projectors. As a consequence, the calligraphic notation will be
dropped for clarity, and capital letters will refer to state structure or
projectors depending on the context.

###  V.1 Algebraic manipulations using the prec: two birds with one stone

On purely algebraic grounds, the transformation $\rightarrow$ has two defining
properties that make it inconvenient to work with. The first is not commuting
with negation:

$\overline{A\rightarrow B}\neq\overline{A}\rightarrow\overline{B}\>.$ (42)

While in the categorical treatment this is a manifestation of the
$*-$autonomous character of the category of higher-order transformations [9],
it leads to difficulties for relating seemingly similar sets together using
the algebra alone. Two expressions involving the same states and effects may
be incomparable because one features a negation on several subsystems at once
while the other does not. For example, $\overline{A\rightarrow
B}=A\otimes\overline{B}$ cannot be compared with
$\overline{A}\rightarrow\overline{B}=\overline{\overline{A}\otimes B}$ without
explicitly doing computations to show set inclusions.

The second inconvenient property is that $\rightarrow$ is not associative:

$A\rightarrow(B\rightarrow C)\neq(A\rightarrow B)\rightarrow C\>.$ (43)

As we have seen, this is what allows one to define the notion of an order with
respect to a base type in the first place. Let
$A_{0},A_{1},A_{2},A_{3},\ldots$ be some base type $A$ defined on different
spaces
$\mathcal{L}\left(\mathcal{H}^{A_{0}}\right),\mathcal{L}\left(\mathcal{H}^{A_{1}}\right),\ldots$,
then $A_{0}$ is a type of first order, $A_{0}\rightarrow A_{1}$ is second
order, $(A_{0}\rightarrow A_{1})\rightarrow(A_{2}\rightarrow A_{3})$ is third
order and so on… However, a naive application of the notion of order may hide
the equivalence between some theories. For example, consider
$((A_{0}\rightarrow A_{1})\rightarrow A_{2})\rightarrow A_{3}$ and
$(A_{1}\rightarrow A_{2})\rightarrow(A_{0}\rightarrow A_{3})$. Some
computations will reveal that they both feature $\overline{A}_{0}\otimes
A_{1}\otimes\overline{A}_{2}\otimes A_{3}$ as their no signaling subset (this
notion is more precisely defined below), and accordingly they should be
comparable. But they are not of the same order: the former is a succession of
three transformations of a state $A$, whereas the latter is a transformation
of higher-order state $A_{1}\rightarrow A_{2}$ into $A_{0}\rightarrow A_{3}$.
Looking at the formula alone, one would conclude that there is no use in
comparing them because they do not feature the same base state structures.
Yet, in some cases they happen to be the same. In this example, if the base
types $A$’s are the quantum states, then the two expressions are two ways of
describing the same thing, the set of quantum 2-combs [3].

Surprisingly, the prec does not lead to these issues, as it commutes with the
negation:

$\overline{A\prec B}=\overline{A}\prec\overline{B}\>.$ (44)

And, like the tensor, it is associative:

$(A\prec B)\prec C=A\prec(B\prec C)=A\prec B\prec C\>.$ (45)

As the algebra obeys the De Morgan relations (Eqs. (24)) and that the tensor
and transformation split into precs (Eqs. (35)), it becomes possible to
express any expression $\Gamma$ involving $n$ projectors
$A_{1},A_{2},\ldots,A_{n}$ composed with $\otimes$ and $\rightarrow$ as the
union and intersection of types built using the prec.

To make this point precise, we first define the following.

######  Definition 4 (No signaling subset).

For a projector expression $\Gamma$ that involves $n$ projectors
$A_{1},A_{2},\ldots,A_{n}$ composed together using $\otimes$ and
$\rightarrow$, the no signaling subset is the subset built using only
negations over single projector and tensor products. It has the form

$\tilde{A}_{1}\otimes\tilde{A}_{2}\otimes\ldots\otimes\tilde{A}_{n}\subset\Gamma\>,$
(46)

where the $\tilde{A}_{i}$ notation means that projector $A_{i}$ is potentially
negated, depending on $\Gamma$.

Using the definition (15c), any $\rightarrow$ can be turned into a mix of
tensor and negation,
$\>\cdot\>\rightarrow\>\cdot\>=\overline{\>\cdot\>\otimes\overline{\>\cdot\>}}$.
Then, because of Eq. (23), one can always find the no signaling subset of an
expression by distributing the negations.

A rule of thumb for finding the no signaling subset is to ‘count the number of
bars’ above each projectors in an expression. Since negation is an involution,
an odd (respectively, even) amount will indicate that the projector is (not)
negated in the no signaling subset. For example, to find the no signaling
subset of $\left(A_{0}\otimes\left(A_{1}\rightarrow
A_{2}\right)\right)\rightarrow A_{3}$, one first expresses it using negations
and tensors products, $\left(A_{0}\otimes\left(A_{1}\rightarrow
A_{2}\right)\right)\rightarrow
A_{3}=\overline{A_{0}\otimes\overline{A_{1}\otimes\overline{A_{2}}}\otimes\overline{A_{3}}}$,
then by inspection $A_{0}$ and $A_{2}$ have an odd number of negations above
them (one and three, respectively) so they will be negated, whereas $A_{1}$
and $A_{3}$ have an even number (two and two) so they will not be. On that
account, the no signaling subset of $\left(A_{0}\otimes\left(A_{1}\rightarrow
A_{2}\right)\right)\rightarrow A_{3}$ is $\overline{A_{0}}\otimes
A_{1}\otimes\overline{A_{2}}\otimes A_{3}$.

Now, in the algebra, the cap is distributive over the cup,

$(A\cup A^{\prime})\cap A^{\prime\prime}=(A\cap
A^{\prime\prime})\cup(A^{\prime}\cap A^{\prime\prime})\>,$ (47)

but the converse is not true. Furthermore, the cap and the cup are both
distributive over the prec (and in this case the converse holds, see App.
A.5.1 for proofs),

$\displaystyle(A\cup A^{\prime})\prec B=(A\prec B)\cup(A^{\prime}\prec B)\>,$
(48a) $\displaystyle A\prec(B\cap B^{\prime})=(A\prec B)\cap(A\prec
B^{\prime})\>.$ (48b)

Where the above are also satisfied when caps and cups are switched,
$(\cap\leftrightarrow\cup)$. Consequently, there is an order in
distributivity; expressions involving these three connectors can always be
rewritten so that they are put into a union of intersections of one-way
signaling compositions. As these three operations are associative, the
intermediate parenthesis can be dropped everywhere.

Finally, by combining Eqs. (35) with the De Morgan rule (24b) and using the
fact that prec commutes with negation, it should be clear that in the
decomposition, the projectors on each single subsystem are the same as the
ones appearing in the no signaling subset.

For these reasons, any expression $\Gamma$ involving $n$ projectors
$A_{1},A_{2},\ldots,A_{n}$ composed using $\otimes$ and $\rightarrow$ can be
brought to a canonical form.

######  Definition 5 (Canonical form).

Let $\Gamma$ be a projector expression that involves $n$ projectors
$A_{1},A_{2},\ldots,A_{n}$ composed together using $\otimes$ and
$\rightarrow$, and whose no signaling subset is given by
$\tilde{A}_{1}\otimes\tilde{A}_{2}\otimes\ldots\otimes\tilde{A}_{n}\subset\Gamma$.
Then, its canonical form is the decomposition

$\Gamma=\bigcup_{i=1}^{x}\left(\bigcap_{j=1}^{y_{i}}\tilde{A}_{\sigma_{ij}(1)}\prec\tilde{A}_{\sigma_{ij}(2)}\prec\ldots\prec\tilde{A}_{\sigma_{ij}(n)}\right),$
(49)

in which there are $x$ unions of expressions labeled by index $i$, and each
expression involves $y_{i}$ intersections of sub-expressions labelled by index
$j$. $\sigma_{ij}$ is an element of the permutation group so that each sub-
expression is a permutation of
$\tilde{A}_{1}\prec\tilde{A}_{2}\prec\ldots\prec\tilde{A}_{n}$ (indices $i$
and $j$ do not necessarily run over the full permutation group).

This implies that any expression can be brought down to the union of several
first-order expressions (which further decompose into intersections if
needed)). This way of rewriting is essentially unique for any state structure,
lifting any ambiguity induced by the negation or non-associativity.

In the first example discussed above, the expressions reduce to
$\overline{A\rightarrow B}=(A\prec\overline{B})\cap(A\succ\overline{B})$ and
$\overline{A}\rightarrow\overline{B}=(A\prec\overline{B})\cup(A\succ\overline{B})$.
Now one can meaningfully compare them: they are both built from a combination
of the same two one-way signaling transformations, but one set is the
intersection and the other is the union, we thus conclude that
$\overline{A\rightarrow B}\subset\overline{A}\rightarrow\overline{B}$.

Moreover, the prec connector and the decomposition it induces also allows for
an identification of the possible signaling directions these two sets may
feature. Indeed, since the prec is exactly the no signaling condition, the
above canonical form is a breakdown of a general expression into several
ordered expressions built using only the prec, then combined first by
requiring no signaling between some subsystems, i.e. using cap, and then by
allowing signaling in several directions, i.e. using cup.

Summarizing, the algebraic fact that the prec is associative and commutes with
the negation allows one to write an unambiguous ‘canonical’ form useful to
compare theories. This gives a tool to determine whether two higher-order
theories are equivalent by sole inspection of their projectors. In addition,
the physical fact that the prec is a one-way signaling composition, combined
with the algebraic rules, allows one to split projectors in several terms with
a fixed signaling direction between its base state structures. This implies
that one can know the possible signaling structure that a higher-order theory
may feature by sole inspection of its projector.

###  V.2 When quantum combs are isomorphic to quantum networks

The next part of the results is concerned with the relationship between two
different ways of building higher-order objects using the developed formalism
of projectors. This can be seen as an example of how to use it in order to
swiftly recover results of reference [5].

Figure 7: Isomorphisms when the projectors are $\mathcal{I}$, i.e. in the case
of transformations between quantum states

Following reference [3], a network is defined as the causally ordered (i.e.
one-way signaling) succession of ‘nodes’ of the same state structure. A
‘1-network of base $A$’ will be the set $A$ itself, thereafter noted $A_{0}$
for clarity, then the ‘2-network’ will be the set $A_{0}\prec A_{1}$, the
‘3-network’ will be $A_{0}\prec A_{1}\prec A_{2}$, etc. A common occurrence of
this structure is the quantum network, where the base object is a quantum
channel such as $A\equiv I_{A_{0}}\rightarrow I_{A_{1}}$. This quantum
network, here associated with some party that will be called Alice, represents
the successive operations of that party. If Alice has a single node quantum
network, it means that Alice acts once on the system $A_{0}$ with a quantum
channel and outputs a quantum state in $A_{1}$. If she has a network with two
nodes, she will act a first time on $A_{0}$ and output a first state at
$A_{1}$, then a second time on $A_{2}$, now potentially using any size of
ancillary qudit as a memory register she preserved from her first operation,
and output in $A_{3}$. And so on, as defined recursively.

Another way of building a higher-order state structure is by doing a comb,
which consists of recursively transforming into a base type: the ‘1-comb of
base $A$’ is again $A_{0}$, then the $2-$comb is $A_{0}\rightarrow A_{1}$, the
$3-$comb is $(A_{0}\rightarrow A_{1})\rightarrow A_{2}$, etc up to the
$n-$comb defined as $(...(A_{0}\rightarrow A_{1})\rightarrow...)\rightarrow
A_{n}$. Note that we reserve the name “quantum comb” to the specific case of
combs based on quantum channels.

When the two constructions were introduced in reference [3], it was proven
that a quantum network is a quantum comb. When treated using the formalism
developed here, there is a stark contradiction: All quantum combs are built
using the transformation, $\rightarrow$, which permits two-ways signaling. How
could it be that they are all equivalent to networks – that is, objects
featuring a single direction of signaling? Especially, why is the 1-comb
(built using the two-ways signaling transformation) equivalent to the quantum
channel (which is causal)? Why does the quantum 2-comb reduce to a two-node
quantum network, i.e., a map acting on two quantum states, when by definition
it should be a supermap? And why does it reduce to a succession of two
operations that have a well-defined direction of signaling between parties,
and not, as its projector suggests, a nesting of two two-way signaling
compositions, resulting in four possible signaling directions?

##### Transformations between quantum states.

From the definition (see App. A.5.2), it can be proven that the expression for
the prec simplifies when either side corresponds to the identity projector or
the depolarizing one:

$\displaystyle\overline{A}\prec B=A\rightarrow B\>$
$\displaystyle\iff\>A=I\>\text{or}\>B=I\>;$ (50a)
$\displaystyle\overline{A}\prec B=\overline{A}\otimes B\>$
$\displaystyle\iff\quad A=D\>\text{or}\>B=D\>.$ (50b)

These relations are depicted in Figure 7 for the case where both $A$ and $B$
are density operators. This should be compared with the general case of Figure
6.

Eq. (50a) is abstractly the reason why the quantum 1-comb, or quantum channel,
happens to have no signaling from its output to its input. As previously
discussed in Section IV.1, this is the case where the definition of no
signaling overlaps with the one of transformation like in equation (27), and
the usual definition of no signaling is recovered. Because of that, a network
of quantum channels is then an alternating network of effects and states as
associativity can be used.

Eq. (50b) is for example the reason why the single partite process matrix
reduces to an effect and a state in tensor product [8].

##### Equivalence of quantum combs and networks.

Now, all the ideas needed to understand why quantum combs are causal networks
are in place. Formally, it was proven [4, 5] that:
1) The comb based on quantum states (for clarity, let $A_{i}=I_{A_{i}}$):

$(\ldots((A_{0}\rightarrow A_{1})\rightarrow
A_{2})\rightarrow\ldots)\rightarrow A_{2n-1}\>,$ (51)

is equivalent to the quantum comb (notice the reordering of the terms),

$(\ldots((A_{n-1}\rightarrow A_{n})\rightarrow(A_{n-2}\rightarrow
A_{n+1}))\rightarrow\ldots)\\\ \rightarrow(A_{0}\rightarrow A_{2n-1})\>.$ (52)

2) Operators $M$ in these structures obey the causality condition

$\text{Tr}_{A_{2i+1}}\left[M\right]=\frac{1}{d_{A_{2i}}}\text{Tr}_{A_{2i+1}A_{2i}}\left[M\right]\otimes\mathds{1}_{A_{2i}}\quad\forall
i.$ (53)

According to the discussion in Section IV.1, the causality conditions can be
recast into a single projector,

$\left(A_{0}\rightarrow A_{1}\right)\prec\ldots\prec\left(A_{2n-2}\rightarrow
A_{2n-1}\right)\>.$ (54)

Because of the isomorphism (50a) and associativity of the prec, this is
equivalent to

$\overline{A_{0}}\prec A_{1}\prec\ldots\prec\overline{A_{2n-2}}\rightarrow
A_{2n-1}\>.$ (55)

For $n=1$, these three equations (51), (52) and (54) are trivially equivalent.
For $n=2$, we recover the second example of the last section: Statement 1)
implies that the quantum 2-comb $(A_{1}\rightarrow
A_{2})\rightarrow(A_{0}\rightarrow A_{3})$ is equivalent to the quantum-state-
based 4-comb $(((A_{0}\rightarrow A_{1})\rightarrow A_{2})\rightarrow A_{3}$,
although, in general, the latter is a subset of the former. Statement 2)
implies that, in the quantum case, the two have a fixed signaling direction,
although they are built using the 2-way signaling transformation.

With the prec rules and the isomorphisms of equations (50), the proofs of both
statements are obtained from algebraic manipulations. First, for the state-
based comb, the transformation is isomorphic to a prec, $A_{0}\rightarrow
A_{1}=\overline{A_{0}}\prec A_{1}$, then $((A_{0}\rightarrow A_{1})\rightarrow
A_{2})\rightarrow A_{3}=\overline{(\overline{(\overline{A_{0}}\prec
A_{1})}\prec A_{2})}\prec A_{3}=\overline{A_{0}}\prec
A_{1}\prec\overline{A_{2}}\prec A_{3}$, because the negation is distributed
over the prec, and this connector is associative.

Next, the equivalence between the combs, statement 1), is obtained using the
same properties: $(A_{1}\rightarrow A_{2})\rightarrow(A_{0}\rightarrow
A_{3})=(\overline{A_{1}}\prec A_{2})\rightarrow(\overline{A_{0}}\prec
A_{3})=\overline{(\overline{A_{1}}\prec
A_{2})\otimes(A_{0}\prec\overline{A_{3}})}=\overline{(\overline{A_{1}}\prec
A_{2})\otimes(A_{0}\otimes\overline{A_{3}})}$, some reordering and the use of
the tensor associativity yield $\overline{A_{0}\otimes((\overline{A_{1}}\prec
A_{2})\otimes\overline{A_{3}})}=\overline{A_{0}\otimes(\overline{A_{1}}\prec
A_{2}\prec\overline{A_{3}})}=\overline{A_{0}\prec\overline{A_{1}}\prec
A_{2}\prec\overline{A_{3}}}=\overline{A_{0}}\prec
A_{1}\prec\overline{A_{2}}\prec A_{3}$.

Finally, the proofs can be generalized mutatis mutandis for any number of
nodes, see Appendix B.6 for the details. We therefore have

$(\ldots((A_{0}\rightarrow A_{1})\rightarrow
A_{2})\rightarrow\ldots)\rightarrow A_{2n-1}=\\\ \overline{A_{0}}\prec
A_{1}\prec\overline{A_{2}}\prec\ldots\prec A_{2n-1}\>,$ (56)

so the statement 2) that this comb has a single signaling direction is now
directly apparent as the structure has a single ‘prec chain’ in canonical
form.

We also have that

$(\ldots(A_{n-1}\rightarrow
A_{n})\rightarrow\ldots)\rightarrow(A_{0}\rightarrow A_{2n-1})=\\\
\overline{A_{0}}\prec A_{1}\prec\overline{A_{2}}\prec\ldots\prec A_{2n-1}\>.$
(57)

Hence isomorphisms between $\prec$ and $\rightarrow$ in the case of theories
whose base structure are the quantum states explain this apparent counter-
logical equivalence of a second-order (with respect to quantum states) theory
with a third-order one.

A different example of the consequences of this result in the case of MPM can
be found in Appendix C.5. It also features another example of the use of the
canonical form.

##  VI Discussion

In this work, a correspondence was developed between several characterizations
of the theory of higher-order quantum transformations. Starting at the most
abstract layer, its formulation in terms of types, we added a new layer, its
formulation in terms of superoperator projectors, to bridge to a less abstract
layer, its formulation in terms of sets of CJ operators – here called state
structures. Correspondences between the characterizations can be summed up as
follow: Given types $A$ and $B$, types $\bar{A},A\otimes B$, and $A\rightarrow
B$ can be constructed using the semantic rules $\\{1,(,),\rightarrow\\}$. To
these types correspond projectors: given projectors $\mathcal{P}_{A}$ and
$\mathcal{P}_{B}$, projectors
$\overline{\mathcal{P}}_{A},\mathcal{P}_{A}\otimes\mathcal{P}_{B}$ and
$\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}$ can be constructed using the
algebraic rules $\\{\overline{\>\cdot\>},\otimes\\}$ as in equations (9c),
(13c), and (15c). To these types and projectors correspond state structures:
given state structures $\mathscr{A}$ and $\mathscr{B}$ as in equation (2), the
state structures
$\overline{\mathscr{A}},\overline{\mathscr{A}}\otimes\mathscr{B}$, and
$\mathscr{A}\rightarrow\mathscr{B}$ can be constructed by requiring that,
respectively, conditions (8), (39), and (36) hold.

The main novelty is the prec connector, Prop. 4, giving the state structure
$\overline{\mathscr{A}}\prec\mathscr{B}$ of maps which are no signaling from
the output to the input. This allows to speak about the possible signaling
structure of the maps characterized by the projective framework. In addition
to that, the properties of the prec give an unambiguous way to compare
different theories as they allow to expand them as unions and intersection of
expressions involving only this prec connector.

In the mean time, we identified the features of the algebra of projectors. We
showed in particular that it was a Boolean algebra under the rules
$\\{\overline{\>\cdot\>},\cap,\cup\\}$, which is subsequently extended into a
model of linear logic under the rules
$\\{\overline{\>\cdot\>},\cap,\cup,\otimes,\overline{\>\cdot\>}\rightarrow\>\cdot\>\\}$.
The introduced prec fits naturally as a multiplicative rule in-between
$\otimes$ and $\overline{\>\cdot\>}\rightarrow\>\cdot\>$, which moreover has
the property of commuting with the negation. It remains to investigate how the
role of the prec is understood in terms of linear logic, as well as in terms
of categories. To the authors’ knowledge, the prec connector appears as a
genuinely new abstract mathematical concept discovered in a physically
motivated problem.

Finally, we rederived the proof of equivalence between combs based on quantum
states, quantum combs, and networks based on quantum channels [5] as an
example of the use of the projective characterization. This equivalence
explains in particular why these structures feature a definite signaling
direction, which comes with a clear physical implementation. The question of
whether these are the only isomorphic constructions is left open for future
work. Another related but more general question that can be asked in terms of
projectors is to determine for which base state structures a given
construction based on the transformation reduces to a construction based on
the one-way signaling composition. In other words, given an abstract way of
constructing higher-order theories, for which base state structures does it
reduce to a network?

Several aspects of the theory of higher-order transformations have not been
explored here and remain open for future work. The composition of types in the
sense of reference [5] has only been partially addressed. Knowing the
projector characterizing a transformation is sufficient to know what will be
the projector characterizing its set of outputs. However, if the input state
structure is now restricted to a subset with a different projector, is there a
rule to apply on the projector of the transformation in order to get the
projector of the possibly now restricted output set? For example, an $n$-comb
takes $(n-1)$-combs as inputs and outputs a 1-comb. One can ask what happens
when the inputs are restricted to the no signaling subset: when $(n-1)$
1-combs are plugged into an $n-$comb instead, is the output set still the full
set of 1-combs?

The notion of causal separability [8, 25, 26, 17] still is to be defined for
general higher-order transformations. The link between the prec and single
signaling direction, as well as the canonical form, should give a basis for
the definition. Nonetheless, there remains to tackle the question of dynamical
causal orders, which is a probabilistic notion, and therefore not naturally
captured by the formalism of projectors.

The issue of realizability has not been explored. That is, given a state
structure, is it possible to realize each of its elements in a lab experiment?
Is there a systematic way to relate these abstract mathematical objects to a
circuit realization, as is the case for quantum combs [3] and for time-
delocalized subsystems [27, 28]? One may expect that the canonical
decomposition of general state structures into the union of several one-way
signaling structures could prove useful for answering this question.

Note added: After completion of this work and during the preparation of the
manuscript, we became aware of an independent work by Simmons and Kissinger
[29], which also investigates the signaling structure of higher-order quantum
transformations. Some of the results presented here were also found in this
other work using a different formalism.

###### Acknowledgements.

T.H. is grateful to the organizers and participants of the 2021 Sejny Summer
Institute for listening to his rambling interventions about nesting supermaps
– in particular to Pablo Arnault, Titouan Carette, Natália Móller, Eleftherios
Tselentis, and Augustin Vanrietvelde for technical discussions. T. H. is
especially indebted to Titouan Carette for pointing out the connection with
linear logic. In addition, T.H. would like to thank Esteban Castro-Ruiz and
Joseph Cunningham for help and comments, as well as Alexandra Elbakyan for
providing access to the scientific literature. T. H. benefits from the support
of the French Community of Belgium within the framework of the financing of a
FRIA grant. O. O. is a Research Associate of the Fonds de la Recherche
Scientifique (F.R.S.–FNRS). This publication was made possible through the
support of the ID# 61466 grant from the John Templeton Foundation, as part of
the “The Quantum Information Structure of Spacetime (QISS)” Project (qiss.fr).
The opinions expressed in this publication are those of the authors and do not
necessarily reflect the views of the John Templeton Foundation. This work was
supported by the Program of Concerted Research Actions (ARC) of the Université
libre de Bruxelles. Illustrations were drawn using draw.io
(https://www.diagrams.net/).

## References

  * Kraus [1983] K. Kraus,  _States, Effects, and Operations: Fundamental Notions of Quantum Theory_, 1st ed., edited by A. Böhm, J. Dollard, and W. Wootters, Lecture notes in physics, Vol. 190 (Springer-Verlag Berlin Heidelberg, 1983).
  * Chiribella  _et al._ [2008] G. Chiribella, G. M. D’Ariano, and P. Perinotti, Transforming quantum operations: Quantum supermaps, EPL (Europhysics Letters) 83, 30004 (2008), arXiv:0804.0180 [quant-ph] .
  * Chiribella  _et al._ [2009] G. Chiribella, G. M. D’Ariano, and P. Perinotti, Theoretical framework for quantum networks, Physical Review A - Atomic, Molecular, and Optical Physics 80, 10.1103/PhysRevA.80.022339 (2009), arXiv:0904.4483 [quant-ph] .
  * Perinotti [2017] P. Perinotti, Causal structures and the classification of higher order quantum computations, Tutorials, Schools, and Workshops in the Mathematical Sciences , 103–127 (2017), arXiv:1612.05099 [quant-ph] .
  * Bisio and Perinotti [2019] A. Bisio and P. Perinotti, Theoretical framework for higher-order quantum theory, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475, 20180706 (2019), arXiv:1806.09554 [quant-ph] .
  * Chiribella  _et al._ [2013] G. Chiribella, G. M. D’Ariano, P. Perinotti, and B. Valiron, Quantum computations without definite causal structure, Phys. Rev. A 88, 022318 (2013), arXiv:0912.0195 [quant-ph] .
  * Davies and Lewis [1970] E. B. Davies and J. T. Lewis, An operational approach to quantum probability, Communications in Mathematical Physics 17, 239 (1970).
  * Oreshkov  _et al._ [2012] O. Oreshkov, F. Costa, and Č. Brukner, Quantum correlations with no causal order, Nature Communications 3, 1 (2012), arXiv:1105.4464 .
  * Kissinger and Uijlen [2019] A. Kissinger and S. Uijlen, A categorical semantics for causal structure, Logical Methods in Computer Science Volume 15, Issue 3, 10.23638/LMCS-15(3:15)2019 (2019), arXiv:1701.04732 [quant-ph] .
  * Araújo  _et al._ [2015] M. Araújo, C. Branciard, F. Costa, A. Feix, C. Giarmatzi, and Č. Brukner, Witnessing causal nonseparability, New Journal of Physics 17, 102001 (2015), arXiv:1506.03776 [quant-ph] .
  * Jamiołkowski [1972] A. Jamiołkowski, Linear transformations which preserve trace and positive semidefiniteness of operators, Reports on Mathematical Physics 3, 275 (1972).
  * Choi [1975] M.-D. Choi, Positive linear maps on complex matrices, Linear Algebra and its Applications 10, 285 (1975).
  * Note [1] A map is admissible in this framework under certain axioms, which can be proven to reduce to the requirement of CP preservation and trace-rescaling for some normalization.
  * Beckman  _et al._ [2001] D. Beckman, D. Gottesman, M. A. Nielsen, and J. Preskill, Causal and localizable quantum operations, Physical Review A 64, 10.1103/physreva.64.052309 (2001), arXiv:quant-ph/0102043 [quant-ph] .
  * Piani  _et al._ [2006] M. Piani, M. Horodecki, P. Horodecki, and R. Horodecki, Properties of quantum nonsignaling boxes, Physical Review A 74, 10.1103/physreva.74.012305 (2006), arXiv:quant-ph/0505110 [quant-ph] .
  * Choi and Effros [1977] M.-D. Choi and E. G. Effros, Injectivity and operator spaces, Journal of Functional Analysis 24, 156 (1977).
  * Hoffreumon and Oreshkov [2021] T. Hoffreumon and O. Oreshkov, The multi-round process matrix, Quantum 5, 384 (2021), arXiv:2005.04204 [quant-ph] .
  * Note [2] The terminology “quasi-orthogonal” originated in the study of maximally Abelian subalgebras (MASA), see Ref. [19].
  * Hiai and Petz [2014] F. Hiai and D. Petz,  _Introduction to Matrix Analysis and Applications_, Universitext (Springer, Cham, 2014).
  * Castro-Ruiz  _et al._ [2018] E. Castro-Ruiz, F. Giacomini, and Č. Brukner, Dynamics of Quantum Causal Structures, Physical Review X 8, 1 (2018), arXiv:1710.03139 [quant-ph] .
  * Note [3] What the authors had obtained in the context of process matrix to process matrix transformation was $\mathcal{I}_{A}\otimes\mathcal{I}_{B}-\mathcal{P}_{A}\otimes\mathcal{I}_{B}+\mathcal{P}_{A}\otimes\mathcal{P}_{B}$, where $\mathcal{P}_{A}$ is the projector characterizing the input process matrix state structure and $\mathcal{P}_{B}$ the output. Compared to equation (15c), here written fully without negation, $\overline{\mathcal{P}_{A}\otimes\overline{\mathcal{P}}_{B}}=\mathcal{I}_{A}\otimes\mathcal{I}_{B}-\mathcal{P}_{A}\otimes\mathcal{I}_{B}+\mathcal{P}_{A}\otimes\mathcal{P}_{B}-\mathcal{P}_{A}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}$, one sees that two terms are missing. In particular, they are the ones that forbids to postselect on a process matrix before preparing a new one that is purely noisy.
  * Castro-Ruiz [2019] E. Castro-Ruiz, (2019), private communication.
  * Girard [1987] J.-Y. Girard, Linear logic, Theoretical Computer Science 50, 1 (1987).
  * Chiribella  _et al._ [2011] G. Chiribella, G. M. D’Ariano, and P. Perinotti, Informational derivation of quantum theory, Physical Review A 84, 10.1103/physreva.84.012311 (2011), arXiv:1011.6451 [quant-ph] .
  * Oreshkov and Giarmatzi [2016] O. Oreshkov and C. Giarmatzi, Causal and causally separable processes, New Journal of Physics 18, 093020 (2016), arXiv:1506.05449 [quant-ph] .
  * Wechs  _et al._ [2019] J. Wechs, A. A. Abbott, and C. Branciard, On the definition and characterisation of multipartite causal (non)separability, New Journal of Physics 21, 013027 (2019), arXiv:1807.10557 [quant-ph] .
  * Oreshkov [2019] O. Oreshkov, Time-delocalized quantum subsystems and operations: on the existence of processes with indefinite causal structure in quantum mechanics, Quantum 3, 206 (2019), arXiv:1801.07594 [quant-ph] .
  * Wechs  _et al._ [2022] J. Wechs, C. Branciard, and O. Oreshkov, Existence of processes violating causal inequalities on time-delocalised subsystems (2022), arXiv:2201.11832 [quant-ph] .
  * Simmons and Kissinger [2022] W. Simmons and A. Kissinger, Higher-order causal theories are models of bv-logic (2022), arXiv:2205.11219 [quant-ph] .
  * Roman [2008] S. Roman,  _Advanced Linear Algebra_, 3rd ed. (Springer, 2008).
  * Piziak  _et al._ [1999] R. Piziak, P. Odell, and R. Hahn, Constructing projections on sums and intersections, Computers & Mathematics with Applications 37, 67 (1999).
  * Note [4] We could also have used the terminology ‘inverse’ or we could have stuck with ‘complement’, but these two words are used for different concepts in quantum information and functional analysis. This choice is by consequent made to avoid ambiguities.
  * Note [5] Albeit the unit must be doubled by convention, $\mathcal{D}_{A}\mapstochar\rightarrow\mathcal{D}_{AB}=\mathcal{D}_{A}\otimes\mathcal{D}_{B}$.
  * Note [6] Be careful about the relabelling of subsystems in each iteration of the comb base on channel. It has to be done so that the subsystems are matching their counterparts in the two other constructions.
  * Nielsen and Chuang [2009] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information_, 2nd ed. (Cambridge University Press, 2009).
  * Peres [2002] A. Peres,  _Quantum Theory: Concepts and Methods_, 1st ed. (Springer Dordrecht, 2002).
  * Keyl [2002] M. Keyl, Fundamentals of quantum information theory, Physics Report 369, 431 (2002), arXiv:0202122 [quant-ph] .
  * Morimae [2014] T. Morimae, The process matrix framework for a single-party system (2014), arXiv:1408.1464 [quant-ph] .
  * Shrapnel  _et al._ [2018] S. Shrapnel, F. Costa, and G. Milburn, Updating the Born rule, New Journal of Physics 20, 10.1088/1367-2630/aabe12 (2018), arXiv:1702.01845 .
  * Note [7] Note that the ‘state’ is on the left side of the inner product because of how we defined CJ isomorphism, this has no influence on the probability rule other than messing with our convention since we are dealing with positive operators.

##  Appendix A Superoperator projectors

This appendix explores the properties of orthogonal superoperator projectors
that are used as the main tool for the characterization in the main text.

###  A.1 Definition and required properties of superoperator projectors

A superoperator $\mathcal{P}_{A}$ is a projector on a subspace of
$\mathcal{L}\left(\mathcal{H}^{A}\right)$ if it satisfies the condition

$\mathcal{P}_{A}\circ\mathcal{P}_{A}=\mathcal{P}_{A}\>.$ (58)

An element $A$ belongs to the subspace defined by $\mathcal{P}_{A}$ if and
only if

$\mathcal{P}_{A}\left\\{A\right\\}=A\>.$ (59)

$\mathcal{P}_{A}$ projects to a self-adjoint subspace if it obeys

$\mathcal{P}_{A}\circ{\dagger}\circ\mathcal{P}_{A}={\dagger}\circ\mathcal{P}_{A}\>,$
(60)

where ${\dagger}$ means ‘taking the adjoint in
$\mathcal{L}\left(\mathcal{H}^{A}\right)$’.

A projector is orthogonal if it does not increase the norm of operators:

$\big{|}\big{|}\mathcal{P}_{A}\left\\{A\right\\}\big{|}\big{|}\leq\big{|}\big{|}A\big{|}\big{|}\>,$
(61)

where
$\big{|}\big{|}A\big{|}\big{|}\equiv\sqrt{\text{Tr}\left[A^{\dagger}\cdot
A\right]}$ is the Hilbert-Schmidt norm. Note that this condition is equivalent
to requiring the projector to be self-adjoint with respect to the inner
product (see e.g. Ref. [30, Theorem 10.5]),

$\text{Tr}\left[\mathcal{P}_{A}\left\\{A^{\prime}\right\\}^{\dagger}\cdot
A\right]=\text{Tr}\left[A^{\prime{\dagger}}\cdot\mathcal{P}_{A}\left\\{A\right\\}\right]\>,\quad\forall
A,A^{\prime}\>.$ (62)

All projectors in this work are assumed orthogonal and projecting to self-
adjoint subspaces. As the projectors should project onto operator systems,
which are subspaces that contain the identity, it should be true that their
images contain the span of the identity as a subspace. A necessary and
sufficient condition for that to be true is

$\mathcal{P}_{A}\circ\mathcal{D}_{A}=\mathcal{D}_{A}\circ\mathcal{P}_{A}=\mathcal{D}_{A}\>,$
(63)

with $\mathcal{D}_{A}$ defined as in Eq. (7).

In addition, it is required for the composition of two projectors to be a
projector,
$\left(\mathcal{P}_{A}\circ\mathcal{P}^{{}^{\prime}}_{A}\right)^{2}=\mathcal{P}_{A}\circ\mathcal{P}^{{}^{\prime}}_{A}$.
A necessary and sufficient condition for
$\mathcal{P}_{A}\circ\mathcal{P}^{{}^{\prime}}_{A}$ to be a projector is that
its constituents commute [30, Theorem 2.26 3)]. Therefore, the condition

$\mathcal{P}_{A}\circ\mathcal{P}^{{}^{\prime}}_{A}=\mathcal{P}^{{}^{\prime}}_{A}\circ\mathcal{P}_{A}\quad\forall\mathcal{P}_{A},\mathcal{P}^{{}^{\prime}}_{A}\>,$
(64)

will be required on every pair of abstract superoperator projectors
$\mathcal{P}_{A},\mathcal{P}^{{}^{\prime}}_{A}$ defined on the same space. The
reason for requiring such a condition comes from the fact that all the
introduced rules in this work will preserve commutativity. Hence, any two
projectors $\mathcal{P}$ and $\mathcal{P}^{{}^{\prime}}$ obtained by relating
the same base projectors on the same subsystems using the various algebraic
rules defined in the following will be commutative by construction.

Thus, a projector onto an operator system $\mathscr{A}$ as in Eq. (4c) is
defined as a linear superoperator
$\mathcal{P}_{A}\in\mathcal{L}\left(\mathcal{L}\left(\mathcal{H}^{A}\right),\mathcal{L}\left(\mathcal{H}^{A}\right)\right)$
that obeys conditions (58), (60), (63), and (62). In addition to that, any two
such projectors are assumed to commute, Eq. (64).

###  A.2 Adding cap and cup operations makes an algebra

Here, we prove that superoperator projectors on operator systems constitute an
algebra under certain rules. Assume $\mathcal{P}_{A}$ and
$\mathcal{P}^{{}^{\prime}}_{A}$ to be two arbitrary projectors on operator
systems, not necessarily the same. By definition, a projector is
$\mathbb{C}$-linear:

$\mathcal{P}_{A}\left\\{\sum_{i}q_{i}A_{i}\right\\}=\sum_{i}\;q_{i}\;\mathcal{P}_{A}\left\\{A_{i}\right\\}\>,$
(65)

$q_{i}\in\mathbb{C}$. This linearity allows us to carry on the addition ‘+’ of
$\mathcal{L}\left(\mathcal{H}^{A}\right)$ at the level of the projectors:

$\left(\mathcal{P}_{A}+\mathcal{P}^{{}^{\prime}}_{A}\right)\\{A\\}\equiv\mathcal{P}_{A}\left\\{A\right\\}+\mathcal{P}^{{}^{\prime}}_{A}\left\\{A\right\\}\>.$
(66)

Using linearity again, one can define the negation ‘-’ and scalar
multiplication of projectors, thereby defining a vector space over
$\mathbb{C}$. Associativity and commutativity are not hard to prove from
there.

Projectors also have a natural ‘conjunction’ operation that can be interpreted
as a multiplication or as a logic ‘and’, nicknamed the cap:

$\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\equiv\mathcal{P}_{A}\circ\mathcal{P}^{{}^{\prime}}_{A}\>.$
(67)

It is again straightforward to prove that it fits the definition: it is a
binary operation that is distributive under the addition defined above and it
is compatible with scalar multiplication. Moreover, it is both associative and
commutative, and it inherits the idempotent property from the projector
definition:

$\mathcal{P}_{A}\cap\mathcal{P}_{A}\equiv\mathcal{P}_{A}\circ\mathcal{P}_{A}\equiv\mathcal{P}^{2}_{A}=\mathcal{P}_{A}\>.$
(68)

In the above equation, we have also defined a shorthand notation for
‘squaring’ under the multiplication $\cap$:
$\mathcal{P}_{A}\cap\mathcal{P}_{A}\equiv\mathcal{P}^{2}_{A}$.

An issue revealed by squaring is that the operation ‘+’ does not necessarily
map projectors to a valid projector:

$\left(\mathcal{P}_{A}+\mathcal{P}^{{}^{\prime}}_{A}\right)^{2}=\mathcal{P}^{2}_{A}+\mathcal{P}^{{}^{\prime}2}_{A}+2\left(\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\right)\>.$
(69)

As the last term of the right-hand side is not always zero,
$\left(\mathcal{P}_{A}+\mathcal{P}^{{}^{\prime}}_{A}\right)^{2}\neq\mathcal{P}_{A}+\mathcal{P}^{{}^{\prime}}_{A}$
in general, so addition does not preserve idempotency. We wish nonetheless to
have operations that keep us in the vector space of projectors, so we redefine
the addition to be the union of two projectors (see e.g. Ref. [31]). This is
inspired by set theory: as $\mathcal{P}_{A}$ maps to a subspace
$\mathscr{A}\subset\mathcal{L}\left(\mathcal{H}^{A}\right)$ and
$\mathcal{P}^{{}^{\prime}}_{A}$ to
$\mathscr{A}^{\prime}\subset\mathcal{L}\left(\mathcal{H}^{A}\right)$ we want
an addition ‘$\cup$’ so that
$\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}$ maps to
$\mathscr{A}\cup\mathscr{A}^{\prime}$. This requirement is realized by the
‘disjunction’ operation, thereafter nicknamed cup (see also Ref. [17]):

$\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}\equiv\mathcal{P}_{A}+\mathcal{P}^{{}^{\prime}}_{A}-\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\>,$
(70)

which will acts like addition, or logic ‘or’, in the space of projectors.

$\cap$ and $\cup$ can indeed be seen as some multiplication and addition of
projectors as the former distributes over the latter:

$\left(\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}\right)\cap\mathcal{P}^{{}^{\prime\prime}}_{A}=\left(\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime\prime}}_{A}\right)\cup\left(\mathcal{P}^{{}^{\prime}}_{A}\cap\mathcal{P}^{{}^{\prime\prime}}_{A}\right)\>.$
(71)

Indeed,
$\left(\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}\right)\cap\mathcal{P}^{{}^{\prime\prime}}_{A}=\left(\mathcal{P}_{A}+\mathcal{P}^{{}^{\prime}}_{A}-(\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A})\right)\cap\mathcal{P}^{{}^{\prime\prime}}_{A}=\big{(}\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\big{)}+\big{(}\mathcal{P}^{{}^{\prime}}_{A}\cap\mathcal{P}^{{}^{\prime\prime}}_{A}\big{)}-\big{(}\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\big{)}\cap\mathcal{P}^{{}^{\prime\prime}}_{A}$.

These caps and cup operands give a quick way to prove subspace inclusions. A
state structure $\mathscr{A}^{\prime}$ has its subspace embedded in the
subspace of another state structure $\mathscr{A}$ if and only if

$\displaystyle\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}=\mathcal{P}^{{}^{\prime}}_{A}\>;$
(72a)
$\displaystyle\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}=\mathcal{P}_{A}\>.$
(72b)

As defined in the main text, this is concisely noted as
$\mathcal{P}^{{}^{\prime}}_{A}\subset\mathcal{P}_{A}$. Condition (63) is then
recast into

$\mathcal{P}_{A}\cap\mathcal{D}_{A}=\mathcal{D}_{A}\>.$ (73)

Any projector built using cap and cup conserve both idempotency, Eq. (68) and
the identity, Eq. (73). While in the case of cap this directly follows from
definition, in the case of the cup we have proven idempotency above, and
condition (73) follows by distributivity:
$\mathcal{D}_{A}\cap\left(\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}\right)=\left(\mathcal{D}_{A}\cap\mathcal{P}_{A}\right)\cup\left(\mathcal{D}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\right)=\mathcal{D}_{A}\cup\mathcal{D}_{A}$,
thus

$\mathcal{D}_{A}\cap\left(\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}\right)=\mathcal{D}_{A}\>.$
(74)

With this, projectors acting on $\mathcal{L}\left(\mathcal{H}\right)$ form an
algebra over $\mathbb{C}$ since they are closed under $(\cap,\cup)$ operations
as well as scalar multiplication. The special projectors $\mathcal{I}$ and
$\mathcal{D}$ we define above play a special role in it: one can identify
$\mathcal{I}$ as the multiplicative identity or ‘unit’ of the algebra of
projectors since for all projectors $\mathcal{P}$

$\mathcal{I}\cap\mathcal{P}=\mathcal{P}\>;$ (75)

it is also the additive absorbant i.e.

$\mathcal{I}\cup\mathcal{P}=\mathcal{I}\>.$ (76)

The other way around, $\mathcal{D}$ is the multiplicative absorbant or ‘zero’
of the algebra,

$\mathcal{D}\cap\mathcal{P}=\mathcal{D}\>,$ (77)

and the additive identity,

$\mathcal{D}\cup\mathcal{P}=\mathcal{P}\>.$ (78)

Because of that property, it should be clear that for any element of the
algebra, the following is true:

$\mathcal{D}\subset\mathcal{P}\subset\mathcal{I}\>.$ (79)

We are dealing with an algebra of idempotent elements equipped with a partial
ordering.

Although referring to the cap and cup as ‘multiplication’ and ‘addition’
provides an intuitive meaning to the operands, in the following we will call
them respectively ‘additive disjunction and conjunction’. This choice is made
in order to avoid an ambiguity with the multiplicative conjunction and
disjunction that will be introduced in a next section.

###  A.3 Adding negation makes a Boolean algebra

In the algebra of superoperator projectors, the new object that naturally
appears in Proposition 1, $\overline{\mathcal{P}}_{A}$, can be seen as an
operation on the original projector $\mathcal{P}_{A}$, whence the ‘bar over
$\mathcal{P}_{A}$’ notation. This new operation is defined for any projector,
and it promotes the algebra to a Boolean algebra.

It is a Boolean algebra if, in addition to the conjunction (‘multiplication’)
operation $\cap$ and the disjunction (‘addition’) operation $\cup$, any
element is idempotent and has a well-defined complement (or logic ‘not’,
thereby referred to as ‘negation’ 444We could also have used the terminology
‘inverse’ or we could have stuck with ‘complement’, but these two words are
used for different concepts in quantum information and functional analysis.
This choice is by consequent made to avoid ambiguities.) characterized by the
condition that the addition of any projector with its negation yields the
additive identity, i.e.

$\mathcal{P}_{A}\cup\overline{\mathcal{P}}_{A}=\mathcal{I}_{A}\>,$ (80)

where $\overline{\mathcal{P}}_{A}$ is the negation of $\mathcal{P}_{A}$. This
is exactly what the quasi-orthogonal complement of Proposition 1 is doing.
First, compute the cap as
$\mathcal{P}_{A}\cap\overline{\mathcal{P}}_{A}=\mathcal{P}_{A}\circ\left(\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}\right)=\mathcal{P}_{A}-\mathcal{P}^{2}_{A}+\mathcal{D}_{A}=\mathcal{P}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}$,
so

$\mathcal{P}_{A}\cap\overline{\mathcal{P}}_{A}=\mathcal{D}_{A}\>.$ (81)

Then, it is true for the cup because
$\mathcal{P}_{A}\cup\overline{\mathcal{P}}_{A}=\mathcal{P}_{A}+\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}-(\mathcal{P}_{A}\cap\overline{\mathcal{P}}_{A})=\mathcal{I}_{A}$.
Thus, we define the negation of any projector $\mathcal{P}_{A}$ as

$\overline{\mathcal{P}}_{A}\equiv\mathcal{P}_{\bar{A}}\equiv\left(\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}\right)\>.$
(82)

In addition to property (80), one can verify from Eq. (81) that the projector
and its negation intersect at the zero of the algebra, which in this case is
indeed $\mathcal{D}_{A}$ (refer to the diagram in Fig. 1).

As it should be, negation is an involution:

$\overline{\overline{\mathcal{P}}}_{A}=\mathcal{P}_{A}\>,$ (83)

and it is closed so that the negation of any projector is a valid projector.
It is the case because the idempotency property is conserved,
$\overline{\mathcal{P}}^{2}_{A}=\left(\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}\right)\cap\left(\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}\right)=\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}-\mathcal{P}_{A}+\mathcal{P}^{2}_{A}-\mathcal{D}_{A}+\mathcal{D}_{A}-\mathcal{D}_{A}+\mathcal{D}_{A}=\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}$,
hence

$\overline{\mathcal{P}}^{2}_{A}=\overline{\mathcal{P}}_{A}\>.$ (84)

The identity is still contained in any projector built using negation:

$\mathcal{D}_{A}\cap\overline{\mathcal{P}}_{A}=\mathcal{D}_{A}\>.$ (85)

This follows from
$\mathcal{D}_{A}\cap\overline{\mathcal{P}}_{A}=\mathcal{D}_{A}\cap\left(\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}\right)=\mathcal{D}_{A}-\mathcal{D}_{A}+\mathcal{D}_{A}$.
If we did not have the heuristic of Prop. 1, this could be interpreted as a
reason for choosing Eq. (82) as the definition of negation instead of the
orthogonal complement $\mathcal{I}_{A}-\mathcal{P}_{A}$. In this latter case,
identity does not belong to the negated state structure. It should also be
clear from
$\mathcal{P}_{A}\cap\overline{\mathcal{P}}_{A}=\mathcal{P}_{A}\cap\left(\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}\right)=\mathcal{P}_{A}-\mathcal{P}^{2}_{A}+\mathcal{D}_{A}=\left(\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}\right)\cap\mathcal{P}_{A}$
that negated projectors commute with original ones, and by the same reasoning
that the negations of two commuting projectors still commute:

$\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}=\mathcal{P}^{{}^{\prime}}_{A}\cap\mathcal{P}_{A}\Longrightarrow\overline{\mathcal{P}}_{A}\cap\overline{\mathcal{P}}^{{}^{\prime}}_{A}=\overline{\mathcal{P}}^{{}^{\prime}}_{A}\cap\overline{\mathcal{P}}_{A}\>.$
(86)

Moreover, the De Morgan laws are valid for the Boolean algebra of projectors:

$\displaystyle\overline{\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}}=\overline{\mathcal{P}_{A}}\cap\overline{\mathcal{P}^{{}^{\prime}}_{A}}\>,$
(87a)
$\displaystyle\overline{\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}}=\overline{\mathcal{P}_{A}}\cup\overline{\mathcal{P}^{{}^{\prime}}_{A}}\>.$
(87b)

The proof is more involved:
$\overline{\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}}=\mathcal{I}_{A}-\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}+\mathcal{D}_{A}=\mathcal{I}_{A}-(\mathcal{P}_{A}+\mathcal{P}^{{}^{\prime}}_{A}-(\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}))+\mathcal{D}_{A}=\mathcal{I}_{A}-\mathcal{P}_{A}+\mathcal{D}_{A}+\mathcal{D}_{A}-\mathcal{P}^{{}^{\prime}}_{A}-\mathcal{D}_{A}+(\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A})-\mathcal{D}_{A}+\mathcal{D}_{A}=(\mathcal{I}_{A}-\mathcal{P}_{A}+D)\cap(I-\mathcal{P}^{{}^{\prime}}_{A}+D)=\overline{\mathcal{P}}_{A}\cap\overline{\mathcal{P}}^{{}^{\prime}}_{A}$.
The second identity directly ensues.

###  A.4 Adding tensor and par makes Linear Logic

####  A.4.1 The tensor operation

For Proposition 2, we also defined a tensor product at the level of the
projectors. Here we now present its algebraic properties so that we can
meaningfully consider
$\mathscr{A}\otimes\mathscr{B}\subset\mathcal{L}\left(\mathcal{H}^{A}\otimes\mathcal{H}^{B}\right)$
when we know that $\mathscr{A}$ (respectively, $\mathscr{B}$) is characterized
by a projector $\mathcal{P}_{A}$ acting on
$\mathcal{L}\left(\mathcal{H}^{A}\right)$ ($\mathcal{P}_{B}$ acting on
$\mathcal{L}\left(\mathcal{H}^{B}\right)$). Because of the isomorphism
$\mathcal{L}\left(\mathcal{H}^{A}\otimes\mathcal{H}^{B}\right)\cong\mathcal{L}\left(\mathcal{H}^{A}\right)\otimes\mathcal{L}\left(\mathcal{H}^{B}\right)$,
the definition of no signaling composition, nicknamed tensor, is
straightforward:

$\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\left\\{\sum_{i}\;q_{i}\;\left(A_{i}\otimes
B_{i}\right)\right\\}\equiv\\\
\sum_{i}\;q_{i}\;\left(\mathcal{P}_{A}\left\\{A_{i}\right\\}\otimes\mathcal{P}_{B}\left\\{B_{i}\right\\}\right)\>,$
(88)

and it should hold for all $i$ such that $q_{i}\in\mathbb{C}$,
$A_{i}\in\mathcal{L}\left(\mathcal{H}^{A}\right)$,
$B_{i}\in\mathcal{L}\left(\mathcal{H}^{B}\right)$ as any operator in
$\mathcal{L}\left(\mathcal{H}^{A}\otimes\mathcal{H}^{B}\right)$ can be
expressed as such.

By the inherited properties of the tensor product at the level of operators,
the tensor at the level of superoperators is also associative, and
distributive with respect to multiplication,

$\left(\mathcal{P}_{A}\cap\mathcal{P}_{A^{\prime}}\right)\otimes\mathcal{P}_{B}=\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\cap\left(\mathcal{P}_{A^{\prime}}\otimes\mathcal{P}_{B}\right)\>,$
(89)

as well and additions,

$\left(\mathcal{P}_{A}\cup\mathcal{P}_{A^{\prime}}\right)\otimes\mathcal{P}_{B}=\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\cup\left(\mathcal{P}_{A^{\prime}}\otimes\mathcal{P}_{B}\right)\>.$
(90)

This directly follows from idempotency:

$\left(\mathcal{P}_{A}\cap\mathcal{P}_{A^{\prime}}\right)\otimes\mathcal{P}_{B}=\left(\mathcal{P}_{A}\cap\mathcal{P}_{A^{\prime}}\right)\otimes\left(\mathcal{P}_{B}\cap\mathcal{P}_{B}\right),$
(91)

and that the composition of projectors is party-wise and thus commute with the
tensor product. Another way to see it is that composition of superoperators
obeys an interchange law with the tensor product of superoperators:

$\left(\mathcal{P}_{A}\cap\mathcal{P}_{A^{\prime}}\right)\otimes\left(\mathcal{P}_{B}\cap\mathcal{P}_{B^{\prime}}\right)=\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\cap\left(\mathcal{P}_{A^{\prime}}\otimes\mathcal{P}_{B^{\prime}}\right)\>.$
(92)

Expressions built from the tensor product result in valid projectors as they
preserve idempotency,

$\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)^{2}=\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\cap\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\\\
\overset{\eqref{eq:interchange_tensor_cap}}{=}\left(\mathcal{P}_{A}\cap\mathcal{P}_{A}\right)\otimes\left(\mathcal{P}_{B}\cap\mathcal{P}_{B}\right)\>,$
(93)

because of interchange law so

$\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)^{2}=\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\>.$
(94)

Tensor composition also preserve the identity 555Albeit the unit must be
doubled by convention,
$\mathcal{D}_{A}\mapsto\mathcal{D}_{AB}=\mathcal{D}_{A}\otimes\mathcal{D}_{B}$.
, again because of the interchange law,
$\mathcal{D}_{AB}\cap\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)=\left(\mathcal{D}_{A}\otimes\mathcal{D}_{B}\right)\cap\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)=\left(\mathcal{D}_{A}\cap\mathcal{P}_{A}\right)\otimes\left(\mathcal{D}_{B}\cap\mathcal{P}_{B}\right)=\mathcal{D}_{A}\otimes\mathcal{D}_{B}$,

$\mathcal{D}_{AB}\cap\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)=\mathcal{D}_{AB}\>.$
(95)

And the tensor product preserves commutation, as if
$\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}=\mathcal{P}^{{}^{\prime}}_{A}\cap\mathcal{P}_{A}$
and
$\mathcal{P}_{B}\cap\mathcal{P}^{{}^{\prime}}_{B}=\mathcal{P}^{{}^{\prime}}_{B}\cap\mathcal{P}_{B}$
then
$\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\cap\left(\mathcal{P}^{{}^{\prime}}_{A}\otimes\mathcal{P}^{{}^{\prime}}_{B}\right)=\left(\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\right)\otimes\left(\mathcal{P}_{B}\cap\mathcal{P}^{{}^{\prime}}_{B}\right)=\left(\mathcal{P}^{{}^{\prime}}_{A}\cap\mathcal{P}_{A}\right)\otimes\left(\mathcal{P}^{{}^{\prime}}_{B}\cap\mathcal{P}_{B}\right)$,
and so

$\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\cap\left(\mathcal{P}^{{}^{\prime}}_{A}\otimes\mathcal{P}^{{}^{\prime}}_{B}\right)=\left(\mathcal{P}^{{}^{\prime}}_{A}\otimes\mathcal{P}^{{}^{\prime}}_{B}\right)\cap\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\>.$
(96)

Interestingly, however, the tensor and negation do not commute with each
other:
$\overline{\mathcal{P}_{A}\otimes\mathcal{P}_{B}}\neq\overline{\mathcal{P}_{A}}\otimes\overline{\mathcal{P}_{B}}$.
Actually, the latter expression define a subspace in the former since

$\overline{\mathcal{P}_{A}\otimes\mathcal{P}_{B}}\cap\overline{\mathcal{P}_{A}}\otimes\overline{\mathcal{P}_{B}}=\\\
\left(\mathcal{I}_{A}\otimes\mathcal{I}_{B}-\mathcal{P}_{A}\otimes\mathcal{P}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\right)\cap\overline{\mathcal{P}_{A}}\otimes\overline{\mathcal{P}_{B}}=\\\
\overline{\mathcal{P}_{A}}\otimes\overline{\mathcal{P}_{B}}-\mathcal{D}_{A}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\>,$
(97)

so that

$\overline{\mathcal{P}_{A}\otimes\mathcal{P}_{B}}\cap\overline{\mathcal{P}_{A}}\otimes\overline{\mathcal{P}_{B}}=\overline{\mathcal{P}_{A}}\otimes\overline{\mathcal{P}_{B}}\>.$
(98)

And from this result

$\overline{\mathcal{P}_{A}\otimes\mathcal{P}_{B}}\cup\overline{\mathcal{P}_{A}}\otimes\overline{\mathcal{P}_{B}}=\overline{\mathcal{P}_{A}\otimes\mathcal{P}_{B}}\>.$
(99)

Hence,

$\overline{\mathcal{P}_{A}}\otimes\overline{\mathcal{P}_{B}}\subset\overline{\mathcal{P}_{A}\otimes\mathcal{P}_{B}}\>;$
(100)

where the subset symbol, $\subset$, implicitly means that we are considering
the images of these projectors. This identity, which can be recasted as

$\mathcal{P}_{A}\otimes\mathcal{P}_{B}\subset\overline{\overline{\mathcal{P}}_{A}\otimes\overline{\mathcal{P}}_{B}}\>,$
(101)

is fundamentally the reason an indefinite causal order may arise; this will
become clearer in the following. Most of the answer rely on the interpretation
of the tensor as intrinsic no-signaling constraints that are presented below.
For an illustration of this relation, the left hand side of this identity is
depicted to the leftmost diagram in Fig. 8, whereas the right-hand side is the
rightmost.

Figure 8: Diagram of the subspaces defined by the three ways of defining a
composite projector.

Observe that the only time the identity
$\mathcal{P}_{A}\otimes\mathcal{P}_{B}=\overline{\overline{\mathcal{P}}_{A}\otimes\overline{\mathcal{P}}_{B}}$
holds is when the projector is either characterising the totality of the space
or only the span of identity. In equation,

$\mathcal{P}_{A}\otimes\mathcal{P}_{B}=\overline{\overline{\mathcal{P}}_{A}\otimes\overline{\mathcal{P}}_{B}}\>\iff\>\mathcal{P}_{A}=\mathcal{P}_{B}=\mathcal{I}\>\text{or}\>\mathcal{D}\>.$
(102)

This is proven by rewriting
$\overline{\overline{\mathcal{P}}_{A}\otimes\overline{\mathcal{P}}_{B}}$ into

$\overline{\overline{\mathcal{P}}_{A}\otimes\overline{\mathcal{P}}_{B}}=\mathcal{P}_{A}\otimes\mathcal{P}_{B}\>+\\\
\left(\overline{\mathcal{P}}_{A}\otimes\mathcal{P}_{B}-\overline{\mathcal{P}}_{A}\otimes\mathcal{D}_{B}-\mathcal{D}_{A}\otimes\mathcal{P}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\right)+\\\
\left(\mathcal{P}_{A}\otimes\overline{\mathcal{P}}_{B}-\mathcal{P}_{A}\otimes\mathcal{D}_{B}-\mathcal{D}_{A}\otimes\overline{\mathcal{P}}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\right)\>,$
(103)

using the definition of negation and algebraic properties. It can then be
understood from Fig. 8: first term of the above is the right quarter of the
wheel, second is the top quarter with its boundary removed, and third is the
bottom also without boundaries. As the three parts share no intersection, the
regular addition ‘+’ is equivalent to a conjunction ‘$\cup$’. Next, more
algebraic manipulations lead to

$\overline{\overline{\mathcal{P}}_{A}\otimes\overline{\mathcal{P}}_{B}}=\mathcal{P}_{A}\otimes\mathcal{P}_{B}\>+\\\
\left(\overline{\mathcal{P}}_{A}\otimes\mathcal{P}_{B}+\mathcal{P}_{A}\otimes\overline{\mathcal{P}}_{B}-\mathcal{I}_{A}\otimes\mathcal{D}_{B}-\mathcal{D}_{A}\otimes\mathcal{I}_{B}\right)\>,$
(104)

and from this expression it is direct to check that the term in parenthesis
vanishes if and only if either of the conditions in Eq. (102) hold.

####  A.4.2 The transformation operation

The projector appearing in Proposition 3 is built from the projectors
characterizing its input and output. The corresponding operation is defined as
the transformation, represented by $\rightarrow$ :

$\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}\equiv\overline{\mathcal{P}_{A}\otimes\overline{\mathcal{P}}_{B}}\>.$
(105)

This additional operation in the Boolean algebra of projectors is actually
secondary, since it can be entirely defined using the negation and causal
composition. Therefore it will automatically be a valid projector in the sense
that it will yield obey Eqs. (68) and (73). Furthermore, as this expression
involves both composition and negation, it will not be associative in general.
For example,
$\left(\left(\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}\right)\rightarrow\mathcal{P}_{C}\right)\neq\left(\mathcal{P}_{A}\rightarrow\left(\mathcal{P}_{B}\rightarrow\mathcal{P}_{C}\right)\right)$,
because the uncurrying rule proven in Ref. [4] can be applied to the right
hand side:

$\mathcal{P}_{A}\rightarrow\left(\mathcal{P}_{B}\rightarrow\mathcal{P}_{C}\right)=\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\rightarrow\mathcal{P}_{C}\>,$
(106)

which is obviously different than
$\left(\left(\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}\right)\rightarrow\mathcal{P}_{C}\right)$.

At the level of Boolean logic, the transformation operation can be understood
as a logical implication. Indeed, the transformation is equal to its inverse
implication, meaning that it satisfies

$\mathcal{P}_{A}\rightarrow\mathcal{P}_{B}=\overline{\mathcal{P}_{A}}\leftarrow\overline{\mathcal{P}_{B}}\>,$
(107)

which comes from the definition. Additionally, note that it is equivalent to
$\overline{\mathcal{P}_{B}}\rightarrow\overline{\mathcal{P}_{A}}$ since the
order of the systems in the tensor product does not matter as
$\mathcal{H}^{A}\otimes\mathcal{H}^{B}\cong\mathcal{H}^{B}\otimes\mathcal{H}^{A}$,
we only keep it fixed to avoid adding confusion. If we define the trivial
system as ‘1’, that is to say, the 1-dimensional state structure made of {1},
one can interpret the measurement (thus the negation of a given state
structure) as a transformation into the trivial system. This leads to the
identity

$\overline{\mathcal{P}_{A}}=\mathcal{P}_{A}\rightarrow 1\>,$ (108)

which justifies the notation $\mathscr{A}\rightarrow
1\equiv\overline{\mathscr{A}}$. The proof is straightforward from the
definition since $1$ is 1-dimensional: $\mathcal{P}_{A}\rightarrow
1=\overline{\mathcal{P}_{A}\otimes\overline{1}}=\overline{\mathcal{P}_{A}}$.
In the same way, one can prove that

$\mathcal{P}_{A}=1\rightarrow\mathcal{P}_{A}\>.$ (109)

Therefore, a state structure can be seen as a transformation from the trivial
system to itself and its negation as a transformation from itself to the
trivial system. In view of the link between composition and transformation,
one may also interpret the former in terms of the latter. A bipartite system
which is causally composed, $\mathscr{A}\otimes\mathscr{B}$ for instance, can
actually be seen as characterized by projectors

$\mathcal{P}_{A}\otimes\mathcal{P}_{B}=\overline{\mathcal{P}_{A}\rightarrow\overline{\mathcal{P}}_{B}}=\overline{\overline{\mathcal{P}}_{A}\leftarrow\mathcal{P}_{B}}\>.$
(110)

Meaning that a no signaling composite bipartite system is equivalent to a
linear transformation normalized on a transformation from one side to the
complement of the other. We see that the direction of the transformation has
no influence, which is expected since it is a causal composition.

####  A.4.3 Linear Logic

We now show under which definition that the rules
$\\{\overline{\>\cdot\>},\cap,\cup,\otimes,\overline{\>\cdot\>}\rightarrow\>\cdot\>\\}$
form a model of multiplicative additive linear logic (MALL) [23]. If one sees
the projectors as the propositions in a sequent calculus, the set of
propositions is similar to those of MALL:

  1. 1.

The set from which we start is made of valid projectors;

  2. 2.

For every projector $\mathcal{P}$, there exists a projector
$\overline{\mathcal{P}}$;

  3. 3.

For every projectors $\mathcal{P}_{A}$ and $\mathcal{P}^{{}^{\prime}}_{A}$,
there exist an additive conjunction
$\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}$ as well as an additive
disjunction $\mathcal{P}_{A}\cup\mathcal{P}^{{}^{\prime}}_{A}$;

  4. 4.

For every projectors $\mathcal{P}_{A}$ and $\mathcal{P}_{B}$, there exist a
multiplicative conjunction $\mathcal{P}_{A}\otimes\mathcal{P}_{B}$ as well as
a multiplicative disjunction
$\overline{\mathcal{P}}_{A}\rightarrow\mathcal{P}_{B}$;

  5. 5.

There are two constants $\left(\mathcal{I},\mathcal{D}\right)$ that go with
each additive binary connectors;

  6. 6.

There are two constants $\left(1,1\right)$ that go with each multiplicative
binary connectors.

And so are the properties:

  1. 1.

All binary connectors are commutative;

  2. 2.

Multiplicative connectors distribute over additive ones;

  3. 3.

All proposition has a negation obeying the De Morgan rules (24);

  4. 4.

Additive constants are the negation of each other;

  5. 5.

Multiplicative constants are the negation of each other;

Proposition 1 is always true as we take it as an axiom. Proposition 2 to 4 are
true from the fact that the definition of these various connectors implies
closure, which, in the case of projectors, is the conservation of properties
(68) and (73). These where proven for each connector in the previous sections.
Proposition 5 follows from equations (75) and (78). Proposition 6 happens
because of the isomorphism
$\mathcal{L}\left(\mathcal{H}\right)\otimes\mathbb{C}\cong 1$ so that
$\mathcal{P}\otimes 1=\mathcal{P}$ and the same way,
$\overline{\overline{\mathcal{P}}\otimes\overline{1}}=\overline{\overline{\mathcal{P}}}=\mathcal{P}$,
$\overline{1\otimes\overline{\mathcal{P}}}=\overline{\overline{\mathcal{P}}}=\mathcal{P}$.

Property 1 is true from definition. In the case of the mutiplicative
connectors, $\mathcal{P}_{A}\otimes\mathcal{P}_{B}$ and
$\overline{\overline{\mathcal{P}}_{A}\otimes\overline{\mathcal{P}}_{B}}$, the
isomorphism
$\mathcal{H}^{A}\otimes\mathcal{H}^{B}\cong\mathcal{H}^{B}\otimes\mathcal{H}^{A}$
should of course be used.

Property 2 follows from Eqs. (89) and (90) in the case of $\otimes$ and
application of the de Morgan rules (87) on these two equations can be used to
prove the property in the case of $\overline{\>\cdot\>}\rightarrow\>\cdot\>$.
Put differently, the multiplicative conjunction (respectively, disjunction)
distributes over the additive conjunction (disjunction)

$\displaystyle\mathcal{P}_{A}\otimes\left(\mathcal{P}_{B}\cap\mathcal{P}^{{}^{\prime}}_{B}\right)=\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)\cap\left(\mathcal{P}_{A}\otimes\mathcal{P}^{{}^{\prime}}_{B}\right)\>;$
(111a)
$\displaystyle\overline{\mathcal{P}}_{A}\rightarrow\left(\mathcal{P}_{B}\cup\mathcal{P}^{{}^{\prime}}_{B}\right)=\left(\overline{\mathcal{P}}_{A}\rightarrow\mathcal{P}_{B}\right)\cup\left(\overline{\mathcal{P}}_{A}\rightarrow\mathcal{P}^{{}^{\prime}}_{B}\right)\>.$
(111b)

But as $\otimes$ and $\rightarrow$ are both operations that merge subspaces,
the converse obviously does not hold. Indeed an expression like
$\mathcal{P}_{X}\cap\left(\mathcal{P}_{A}\otimes\mathcal{P}_{B}\right)=\left(\mathcal{P}_{X}\otimes\mathcal{P}_{A}\right)\cap\left(\mathcal{P}_{X}\otimes\mathcal{P}_{B}\right)$
makes no sense as the right-hand side feature a cap between two superoperators
defined on different spaces that are not isomorphic in general.

Property 3 was proven at Eq. (83) for the negation, Eq. (87) for the additive
connectors, and follows from the definition in the case of multiplicative
connectors.

Property 4 is the statement
$\overline{\mathcal{I}}=\mathcal{I}-\mathcal{I}+\mathcal{D}=\mathcal{D}$,
whose converse hold by idempotency or can be proven by the same kind of
computation.

Property 5 is the statement $\overline{1}=1-1+1$, as in the 1-dimensional case
$\mathcal{D}=\mathcal{I}=1$.

As pointed out in the main text, there is however some discrepancies with
MALL, that we now list

  1. 1.

The multiplicative disjunction is not associative;

  2. 2.

The multiplicative units are equivalent;

  3. 3.

The additive falsity (i.e. the unit for $\cup$) is not absorbant.

Despite these particularities, the connection between the algebra of
projectors and MALL is too obvious not to be pointed out.

###  A.5 Adding the prec

Define the $\mathbf{A\prec B}$ one-way signaling composition as

$\mathcal{P}_{A}\prec\mathcal{P}_{B}\equiv\mathcal{I}_{A}\otimes\mathcal{P}_{B}-\overline{\mathcal{P}}_{A}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\>.$
(112)

Compared to transformation, one-way signaling composition is better behaved in
the sense that it is associative

$\mathcal{P}_{A}\prec\left(\mathcal{P}_{B}\prec\mathcal{P}_{C}\right)=\left(\mathcal{P}_{A}\prec\mathcal{P}_{B}\right)\prec\mathcal{P}_{C}\>.$
(113)

So that
$\mathcal{P}_{A}\prec\left(\mathcal{P}_{B}\prec\mathcal{P}_{C}\right)=\mathcal{P}_{A}\prec\mathcal{P}_{B}\prec\mathcal{P}_{C}$
can be written unambiguously. Even more, it is better behaved than both the no
signaling (the tensor) and the two-ways signaling (then transformation)
compositions as it is distributive with respect to the negation

$\overline{\mathcal{P}_{A}\prec\mathcal{P}_{B}}=\overline{\mathcal{P}}_{A}\prec\overline{\mathcal{P}}_{B}\>.$
(114)

We first prove commutation with negation by direct computation,

$\overline{\mathcal{P}_{A}\prec\mathcal{P}_{B}}=\mathcal{I}_{A}\otimes\mathcal{I}_{B}-\mathcal{P}_{A}\prec\mathcal{P}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}=\\\
\mathcal{I}_{A}\otimes\mathcal{I}_{B}-\mathcal{I}_{A}\otimes\mathcal{P}_{B}+\overline{\mathcal{P}}_{A}\otimes\mathcal{D}_{B}-\mathcal{D}_{A}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}=\\\
\big{(}\mathcal{I}_{A}\otimes\mathcal{I}_{B}-\mathcal{I}_{A}\otimes\mathcal{P}_{B}+\mathcal{I}_{A}\otimes\mathcal{D}_{B}\big{)}-\mathcal{P}_{A}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}=\\\
\big{(}\mathcal{I}_{A}\otimes\overline{\mathcal{P}}_{B}\big{)}-\overline{\overline{\mathcal{P}}}_{A}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}=\\\
\overline{\mathcal{P}}_{A}\prec\overline{\mathcal{P}}_{B}\>.$ (115)

This can be used to prove associativity,

$\mathcal{P}_{A}\prec\left(\mathcal{P}_{B}\prec\mathcal{P}_{C}\right)=\\\
\mathcal{I}_{A}\otimes\left(\mathcal{P}_{B}\prec\mathcal{P}_{C}\right)-\\\
\overline{\mathcal{P}}_{A}\otimes\mathcal{D}_{B}\otimes\mathcal{D}_{C}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\otimes\mathcal{D}_{C}=\\\
\mathcal{I}_{A}\otimes\mathcal{I}_{B}\otimes\mathcal{P}_{C}-\mathcal{I}_{A}\otimes\overline{\mathcal{P}}_{B}\otimes\mathcal{D}_{C}+\mathcal{I}_{A}\otimes\mathcal{D}_{B}\otimes\mathcal{D}_{C}-\\\
\overline{\mathcal{P}}_{A}\otimes\mathcal{D}_{B}\otimes\mathcal{D}_{C}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\otimes\mathcal{D}_{C}=\\\
\big{(}\mathcal{I}_{A}\otimes\mathcal{I}_{B}\big{)}\otimes\mathcal{P}_{C}-\big{(}\mathcal{I}_{A}\otimes\overline{\mathcal{P}}_{B}-\mathcal{P}_{A}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\big{)}\otimes\mathcal{D}_{C}+\\\
\mathcal{D}_{A}\otimes\mathcal{D}_{B}\otimes\mathcal{D}_{C}=\\\
\big{(}\mathcal{I}_{A}\otimes\mathcal{I}_{B}\big{)}\otimes\mathcal{P}_{C}-\big{(}\overline{\mathcal{P}}_{A}\prec\overline{\mathcal{P}}_{B}\big{)}\otimes\mathcal{D}_{C}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\otimes\mathcal{D}_{C}=\\\
\big{(}\mathcal{I}_{A}\otimes\mathcal{I}_{B}\big{)}\otimes\mathcal{P}_{C}-\overline{\big{(}\mathcal{P}_{A}\prec\mathcal{P}_{B}\big{)}}\otimes\mathcal{D}_{C}+\left(\mathcal{D}_{A}\otimes\mathcal{D}_{B}\right)\otimes\mathcal{D}_{C}=\\\
\big{(}\mathcal{P}_{A}\prec\mathcal{P}_{B}\big{)}\prec\mathcal{P}_{C}\>,$
(116)

where we have used the definition to go to the last line, and commutation of
the prec with the negation to go to the penultimate one.

Like the tensor product, one-way signaling composition with the trivial system
amounts to doing nothing since $\mathcal{P}_{A}\prec 1=\mathcal{I}_{A}\otimes
1-\overline{\mathcal{P}}_{A}\otimes 1+\mathcal{D}_{A}\otimes
1=\overline{\overline{\mathcal{P}}_{A}}\otimes 1$ and
$1\prec\mathcal{P}_{A}=\mathcal{P}_{A}\otimes 1-\mathcal{D}_{A}\otimes
1+\mathcal{D}_{A}\otimes 1$ so that

$\displaystyle\mathcal{P}_{A}\prec 1=\mathcal{P}_{A}\>,$ (117a) $\displaystyle
1\prec\mathcal{P}_{A}=\mathcal{P}_{A}\>.$ (117b)

One can finally link the transformation (here seen as two-ways signaling
composition by negating its input), one-way signaling, and no signaling
compositions by noticing that

$\left(\mathcal{P}_{A}\prec\mathcal{P}_{B}\right)\cap\left(\mathcal{P}_{A}\succ\mathcal{P}_{B}\right)=\mathcal{P}_{A}\otimes\mathcal{P}_{B}\>,$
(118)

and

$\left(\mathcal{P}_{A}\prec\mathcal{P}_{B}\right)\cup\left(\mathcal{P}_{A}\succ\mathcal{P}_{B}\right)=\overline{\mathcal{P}}_{A}\rightarrow\mathcal{P}_{B}\>.$
(119)

First equation is proven by developing it,
$\left(\mathcal{P}_{A}\prec\mathcal{P}_{B}\right)\cap\left(\mathcal{P}_{A}\succ\mathcal{P}_{B}\right)=\big{(}\mathcal{I}_{A}\otimes\mathcal{P}_{B}-\overline{\mathcal{P}}_{A}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\big{)}\cap\big{(}\mathcal{P}_{A}\otimes\mathcal{I}_{B}-\mathcal{D}_{A}\otimes\overline{\mathcal{P}}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\big{)}$,
and noting that the intersection of any two elements but
$\big{(}\mathcal{I}_{A}\otimes\mathcal{P}_{B}\big{)}\cap\big{(}\mathcal{P}_{A}\otimes\mathcal{I}_{B}\big{)}=\mathcal{P}_{A}\otimes\mathcal{P}_{B}$
is giving $\mathcal{D}_{A}\otimes\mathcal{D}_{B}$. Thus, the expression
reduces to $\mathcal{P}_{A}\otimes\mathcal{P}_{B}$ followed by eight
occurrences of $\mathcal{D}_{A}\otimes\mathcal{D}_{B}$ alternating between a
plus and minus sign, therefore canceling each other. The second equation has a
quick proof using the De Morgan rule and the associativity of the negation:

$\left(\mathcal{P}_{A}\prec\mathcal{P}_{B}\right)\cup\left(\mathcal{P}_{A}\succ\mathcal{P}_{B}\right)\\\
\overset{\eqref{eq:invol}}{=}\overline{\overline{\left(\mathcal{P}_{A}\prec\mathcal{P}_{B}\right)\cup\left(\mathcal{P}_{A}\succ\mathcal{P}_{B}\right)}}\\\
\overset{\eqref{eq:deMorgan_cup_to_cap}}{=}\overline{\overline{\left(\mathcal{P}_{A}\prec\mathcal{P}_{B}\right)}\cap\overline{\left(\mathcal{P}_{A}\succ\mathcal{P}_{B}\right)}}\\\
\overset{\eqref{eq:semi-
causal_negation}}{=}\overline{\left(\overline{\mathcal{P}}_{A}\prec\overline{\mathcal{P}}_{B}\right)\cap\left(\overline{\mathcal{P}}_{A}\succ\overline{\mathcal{P}}_{B}\right)}\\\
\overset{\eqref{eq:causal=0ways}}{=}\overline{\overline{\mathcal{P}}_{A}\otimes\overline{\mathcal{P}}_{B}}=\overline{\mathcal{P}}_{A}\rightarrow\mathcal{P}_{B}\>.$
(120)

####  A.5.1 Distribution properties of the prec

Cap and prec satisfy an interchange law,

$\big{(}\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\big{)}\prec\big{(}\mathcal{P}_{B}\cap\mathcal{P}^{{}^{\prime}}_{B}\big{)}=\big{(}\mathcal{P}_{A}\prec\mathcal{P}_{B}\big{)}\cap\big{(}\mathcal{P}^{{}^{\prime}}_{A}\prec\mathcal{P}^{{}^{\prime}}_{B}\big{)}\>.$
(121)

This can be shown as follows:

$\left(\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\right)\prec\left((\mathcal{P}_{B}\cap\mathcal{P}^{{}^{\prime}}_{B}\right)\\\
=\mathcal{I}_{A}\otimes\left(\mathcal{P}_{B}\cap\mathcal{P}^{{}^{\prime}}_{B}\right)-\overline{\left(\mathcal{P}_{A}\cap\mathcal{P}^{{}^{\prime}}_{A}\right)}\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\\\
\overset{\eqref{eq:deMorgan_cap_to_cup}}{=}\mathcal{I}_{A}\otimes\left(\mathcal{P}_{B}\cap\mathcal{P}^{{}^{\prime}}_{B}\right)-\left(\overline{\mathcal{P}}_{A}\cup\overline{\mathcal{P}}^{{}^{\prime}}_{A}\right)\otimes\mathcal{D}_{B}+\mathcal{D}_{A}\otimes\mathcal{D}_{B}\\\
=\mathcal{I}_{A}\otimes\big{(}\mathcal{P}_{B}\cap\mathcal{P}^{{}^{\prime}}_{B}\big{)}-\overline{\mathcal{P}}_{A}\otimes\mathcal{D}_{B}-\overline{\mathcal{P}}^{{}^{\prime}}_{A}\otimes\mathcal{D}_{B}\\\