# Exploring the limits of no backwards in time signalling

Yelena Guryanova  Institute for Quantum Optics and Quantum Information
(IQOQI), Boltzmanngasse 3 1090, Vienna, Austria  Ralph Silva  Group of Applied
Physics, University of Geneva, CH-1211 Geneva 4, Switzerland  Anthony J. Short
H. H. Wills Physics Laboratory, University of Bristol, Tyndall Avenue,
Bristol, BS8 1TL, United Kingdom  Paul Skrzypczyk  H. H. Wills Physics
Laboratory, University of Bristol, Tyndall Avenue, Bristol, BS8 1TL, United
Kingdom  Nicolas Brunner  Group of Applied Physics, University of Geneva,
CH-1211 Geneva 4, Switzerland  Sandu Popescu  H. H. Wills Physics Laboratory,
University of Bristol, Tyndall Avenue, Bristol, BS8 1TL, United Kingdom

###### Abstract

We present an operational and model-independent framework to investigate the
concept of no-backwards-in-time signalling. We define no-backwards-in-time
signalling conditions, closely related to the spatial no-signalling
conditions. These allow for theoretical possibilities in which the future
affects the past, nevertheless without signalling backwards in time. This is
analogous to non-local but no-signalling spatial correlations. Furthermore,
our results shed new light on situations with indefinite causal structure and
their connection to quantum theory.

##  I Introduction

One of the most routine observations that we make about our world is that we
cannot signal backwards in time. So ubiquitous is this understanding that it
is often taken as one of the basic laws of Nature111In principle, general
relativity seems to allow for closed time-like curves, but there is currently
no evidence of this in Nature.. At first glance, this remark seems
straightforward. However, as we show here, in probabilistic theories such as
quantum mechanics, the consequences of such an assertion are far more
involved. In fact, we will see that there is a surprising amount of liberty:
some theories even allow the future to affect the past, nevertheless without
signalling backwards in time.

Here, we consider the general properties of all theories which do not allow
backwards-in-time signalling; in some sense these properties are the temporal
equivalent of the no-signalling conditions that have played a central role in
the study of non-locality Bell (1964); Popescu and Rohrlich (1994a); Brunner
_et al._ (2014). The fact that the future can affect the past without
signalling backward in time is then akin to the phenomenon of non-locality, in
which correlations can be non-local yet don’t lead to superluminal signalling.

Various other aspects of causality have also been studied recently, exploring
the most general causal structures which might be possible in Nature Aharonov
_et al._ (1990); Chiribella  _et al._ (2013); Hardy (2007); Oreshkov  _et al._
(2012); Leifer and Spekkens (2013); Baumeler and Wolf (2014); Allen  _et al._
(2016); DAriano  _et al._ (2016); Perinotti (2016). Here we use our results on
no-backwards-in-time-signalling to shed further light on some of these — in
particular on the process matrix formalism for indefinite causal structures
Oreshkov  _et al._ (2012); Branciard  _et al._ (2016); Araújo  _et al._
(2015); Oreshkov and Giarmatzi (2016); Abbott  _et al._ (2016); Baumeler and
Wolf (2016), and on pre- and post-selected quantum states Aharonov  _et al._
(1964); Aharonov and Vaidman (1991); Aharonov and Gruss (2005); Aharonov  _et
al._ (2009); Silva  _et al._ (2014), two approaches which were recently shown
to be related Silva  _et al._ (2017).

##  II No backwards in time signalling

Consider first a situation involving a single party, Alice, who performs the
following procedure. At some point, a system enters her laboratory. She
performs a measurement on it and obtains an outcome $a$. Alice then performs
some transformation on the system, choosing among a set of transformations
labelled by $x$. For example, Alice might apply some unitary transformation,
or discard the system and prepare a completely new one. Finally, Alice sends
the system out of her laboratory. We can describe the probability that Alice
obtains the outcome $a$ given that she later performed the transformation $x$
via the conditional probability distribution $p(a|x)$.

If the choice of transformation $x$ depends on the result $a$ then it is
possible that $p(a|x)\neq p(a|x^{\prime})$ (for example, consider a simple
situation where the number of possible transformations is the same as the
number of outcomes, and let $x=a$). Although the probability to obtain a
result $a$ depends on a transformation made at a later time, nothing
backwards-in-time is happening here. It is simply that the transformation at
the later time depends on the result obtained earlier and this is what
generates the correlations.

To define what would constitute true backwards-in-time signalling in this
framework we modify the above situation. After measuring her system, Alice now
receives the choice of which transformation to make from outside the
laboratory. That is, $x$ is now a random number, chosen by an external party
who has no access to either the result $a$ or the input system (or anything
else correlated to them).222Note that this is an assumption, as Alice cannot
verify that this is really the case. It is similar to the measurement-
independence assumption in Bell’s theorem, whereby the measurement settings
must be independent of the hidden variables of the source.  Now, if $p(a|x)$
depends on $x$ that would mean backwards in time signalling. Thus, in this
situation the _no-backwards-in-time-signalling (NBTS) condition_ 333See also
the note added at the end of the paper. is

$p(a|x)=p(a).$ (1)

which states that the probability of obtaining outcome $a$ cannot depend on
which transformation $x$ is applied afterwards (this is similar to the
causality condition defined in Chiribella  _et al._ (2010)). Since any
probability distribution satisfying (1) can be achieved in either quantum
theory or classical probability theory we see that there is nothing
particularly interesting in this situation involving only a single party.
However, as we shall see next, things becomes more subtle in situations
involving two or more parties.

Consider now two parties, Alice and Bob, each of whom is in their own
laboratory. As before, at some point a system enters Alice’s laboratory and
she makes a measurement on it, with outcome $a$. She then performs some
transformation $x$, before sending it out of her laboratory. Similarly, at
some point a system enters Bob’s laboratory. Again, he performs a measurement
on it with outcome $b$, followed by a transformation $y$, before sending the
system out of the lab. As above, we assume that the choice of which
transformations to make, $x$ and $y$, are made freely by an external party who
has no access to $a$ and $b$ or the input system(s). Depending on the relative
timing of Alice and Bob’s actions, it could be that the system that enters
Alice’s laboratory is the same as the one that left Bob’s laboratory; in this
case Bob could have influenced its state and therefore the outcome a.
Importantly however, we assume that Bob doesn’t communicate to Alice in any
other way during the experiment (or vice versa).

The situation is then described by the joint conditional probabilities
$p(a,b|x,y)$. See Fig. 1.

Of course, as far as Alice is concerned, all she sees is the outcome $a$ (and
the input $x$), and the probability for her to obtain an outcome is just
determined by the marginal probability

$p_{A}(a|x,y):=\sum_{b}p(a,b|x,y).$ (2)

Similarly, all Bob sees is $b$ and $y$, and Bob’s outcomes will be distributed
according to the marginal probability

$p_{B}(b|x,y):=\sum_{a}p(a,b|x,y).$ (3)

Figure 1: An operational framework for investigating the presence of
signalling backwards in time. Alice and Bob have separate closed laboratories.
Each of them performs a measurement, followed by a transformation (the choice
of which is made outside the laboratory). Inside each laboratory time flows in
the usual fashion. However, the assumptions about the relative time order of
Alice experiments versus Bob’s varies from case to case as explained in the
text.

The question is how to write the NBTS conditions now. We distinguish various
scenarios which differ in the assumptions about the relative timing between
the experiments done by Alice and Bob. All of them, however, have a main
element in common: We can definitely assume time ordering inside each lab.
That is, Alice performs her measurement and obtains the outcome $a$ before $x$
is delivered to her and she performs the corresponding transformation, and
similarly for Bob. Therefore, to avoid backwards-in-time-signalling we demand
that Alice’s outcome marginal probability is independent of $x$

$p_{A}(a|x,y)=p_{A}(a|y).$ (4)

Similarly, for Bob we have

$p_{B}(b|x,y)=p_{B}(b|x).$ (5)

Coming now to the differences, there are two ‘extremal’ cases, which reflect
our knowledge about the relative timing between Alice and Bob’s laboratories:

  * •

In one case, which is in some sense ‘minimal’, we have no knowledge whatsoever
about the relative timings of Alice and Bob. It could be the case that the
timing is well defined, but is unknown by Alice and Bob, or it varies from one
run of the experiment to the next, or that the timing is undefined even in
principle. The later possibility may be very important, being relevant for
situations such as quantum gravity, where a global time might not even exist.

In this case it is possible the system that enters Alice’s laboratory
previously passed through Bob’s laboratory. In this case Alice’s measurement
result $a$ could depend on $y$, since the system could have been transformed
according to $y$ in the past. In other words, since Bob could have influenced
Alice’s system, $p_{A}(a|y)$ could actually depend on $y$. Similarly, it is
also possible that the system that enters Bob’s lab could have previously
passed through Alice’s lab, his probability may depend on Alice’s input, i.e.
$p_{B}(b|x)$ could depend on $x$. Hence in this situation the NBTS conditions
are just the basic equations (4) and (5) which describe that locally, in each
lab, the probabilities cannot depend on the actions performed in that lab at a
later time; no supplementary constraints apart from these basic ones apply.

  * •

In the other, ‘maximal’, case, we have full knowledge about the relative
timings between the laboratories. A particularly interesting situation is when
Alice’s and Bob’s actions happen in parallel – i.e. such that it is impossible
that the same system passes through Alice’s and Bob’s labs, since there is not
enough time for a system to travel from Alice’s lab to Bob’s lab, or vice
versa. 444Note that this possibility arises both in a relativistic setting,
where the system cannot travel faster than the speed of light, or in a
nonrelativistic setting (with infinite speed propagation of the system) as
long as the two experiments overlap in time. Hence the probability of Alice’s
outcome cannot depend on either $x$ or $y$ and so

$p_{A}(a|x,y)=p_{A}(a).$ (6)

Similarly, for Bob we have

$p_{B}(b|x,y)=p_{B}(b).$ (7)

The NBTS conditions are therefore stronger than those in the minimal case.

Another interesting situation in this case is when one experiment, say
Alice’s, comes before Bob’s, i.e. such that there is time for the system to
pass from Alice to Bob, but not from Bob to Alice. Here the NBTS conditions
are

$p_{A}(a|x,y)=p_{A}(a)$ (8) $p_{B}(b|x,y)=p_{B}(b|x)$ (9)

as Bob’s state may now depend on Alice’s input $x$ but Alice’s cannot depend
on $y$.

Beyond these two extremal cases one could consider intermediate cases, for
example, where Alice and Bob know the probabilities of the different time
orderings.

In the subsequent sections, we explore some of the consequences of the NBTS
constraints in the different scenarios, and their implications for particular
theories.

##  III Indefinite relative timing

We start by exploring the minimal case, where we do not assume a fixed
relative time between the laboratories.

###  III.1 No-backwards-in-time-signalling polytope

Our first goal is to characterise the set of correlations which can arise in
this situation. We start by noting that when we have indefinite relative
timing the NBTS conditions (4) and (5) resemble the well-known no-signalling
constraints from the study of non-local correlations

$\displaystyle p_{A}(a|x,y)$ $\displaystyle=$ $\displaystyle p_{A}(a|x)$
$\displaystyle p_{B}(b|x,y)$ $\displaystyle=$ $\displaystyle p_{B}(b|y).$ (10)

The well known concepts and techniques used for analysing these correlations,
in particular the geometrical tool of the ‘no-signalling polytope’, can
therefore be used in our case too.

For simplicity first consider the case when $a,b,x,y$ can each only take two
values, $0$ and $1$. The entire physical situation is then described by the 16
numbers $p(a,b|x,y)$. We can cast the situation in a geometrical form by
considering a 16-dimensional space and associating to each physical situation
a point $\mathbf{p}$ whose coordinates are $\\{p(0,0|0,0),...,p(1,1|1,1)\\}$.
Since each coordinate is actually a probability, its values can only range
between 0 and 1, meaning that the points $\mathbf{p}$ describing physical
situations live inside the 16-dimensional hypercube defined by $0\leq
p(a,b|x,y)\leq 1$. The 4 probability normalisation relations
$\sum_{a,b}p(a,b|x,y)=1$ for each pair $x,y$, impose further constraints,
specifying hyperplanes on which the points $\mathbf{p}$ must be situated. This
means that the points $\mathbf{p}$ can be only be situated in the
12-dimensional polytope obtained by intersecting the original 16-dimensional
hypercube with the four normalisation hyperplanes. That is the space of all
conceivable physical situations.

The no-backwards-in-time-signalling constraints (4) and (5) further limit the
space, specifying further hyperplanes on which $\mathbf{p}$ must lie. The
resulting ‘no-backwards-in-time-signalling polytope’ is 8-dimensional and is
the basic object we are interested in. It is similar to the ‘no-signalling
polytope’ Barrett  _et al._ (2005); Brunner  _et al._ (2014) well known from
the study of non-locality, see Fig. 3.

In particular, one finds that this polytope has 24 vertices. 16 of these
correspond to deterministic probability distributions

$p(a,b|x,y)=\begin{cases}1&\text{if }a=\mu y\oplus\alpha,\quad b=\nu
x\oplus\beta\\\ 0&\text{otherwise}\end{cases}$ (11)

where $\alpha$, $\beta$, $\mu,\nu\in\\{0,1\\}$, and $\oplus$ denotes addition
modulo 2. The remaining 8 vertices are ‘PR-like’ Popescu and Rohrlich (1994a)
probability distributions, given by

$p(a,b|x,y)=\begin{cases}\tfrac{1}{2}&\text{if }a\oplus
b=(x\oplus\gamma)(y\oplus\delta)\oplus\epsilon\\\
0&\text{otherwise}\end{cases}$ (12)

where $\gamma,\delta,\epsilon\in\\{0,1\\}$. Note that the vertices are in one-
to-one correspondence with the vertices of the no-signalling polytope, except
that $x$ and $y$ are swapped.

###  III.2 Classical polytope

Figure 2: The classical situation $A\to B$, in which Alice’s operations occur
before Bob’s. It is therefore possible for a system to pass from Alice’s lab
into Bob’s, and thus for the outcome $b$ to depend upon Alice’s input $x$.
However, note that in this case, all outcome probabilities are independent of
the transformation labelled $y$, as it occurs after all measurements have been
made.  Figure 3: A comparison of the no-backwards-in-time signaling polytope
(left) with the no-signalling polytope (right) for the case of indefinite
relative timing between the labs. (a) In the NBTS case, the classical polytope
coincides with the quantum polytope, and is of lower dimension, depicted by
the solid diagonal line. Vertices labelled GYNI correspond to vertices which
always win ‘guess-your-neighbours-input’ type games Almeida  _et al._ (2010).
PR vertices correspond to Popescu-Rohrlich type correlations Popescu and
Rohrlich (1994a). C correspond to deterministic vertices, where at most one
party’s output depends on the other’s input. (b) In the NS case, the local
polytope $\mathcal{L}$ (with vertices denoted L) is full-dimensional in the
space of non-signalling correlations. The quantum set, $\mathcal{Q}$, lies
between the local and non-signalling polytopes.

Classical physics obeys the principle of NBTS, but also imposes supplementary
constraints. In any run of the experiment the time ordering between Alice and
Bob is well defined. There are three possibilities — either Alice’s actions
occur entirely before Bob’s, which we denote $A\rightarrow B$, Bob’s actions
occur entirely before Alice’s, $A\leftarrow B$, or their actions overlap in
time, $A|B$. However, we might imagine that the time ordering is chosen at
random in each run, and is unknown to Alice and Bob.

In the first case, in which Alice’s actions occur entirely before Bob’s, a
classical system could pass through Alice’s lab then enter Bob’s lab (see Fig.
2). This could carry information about $a$ and $x$, hence Bob’s outcome $b$
can depend on these variables. The achievable probability distributions via
this time ordering are therefore

$p^{A\rightarrow B}(a,b|x,y)=p_{A}(a)p_{B}(b|a,x).$ (13)

where $p_{A}(a)$ and $p_{B}(b|a,x)$ are arbitrary probability distributions.
Similarly, when Bob’s actions occur before Alice, we obtain

$p^{A\leftarrow B}(a,b|x,y)=p^{\prime}_{A}(a|b,y)p^{\prime}_{B}(b).$ (14)

Finally, when their actions overlap in time, both outcomes $a$ and $b$ must be
given before $x$ and $y$ are known, hence

$p^{A|B}(a,b|x,y)=p_{AB}(a,b).$ (15)

However, note that the situation $A|B$ is strictly weaker than the other two
cases, as the outputs are independent of the inputs. Any correlations of this
form could be generated by either of the other two cases and can be absorbed
into them without loss of generality. All classically achievable probability
distributions can therefore be written as

$p(a,b|x,y)=qp_{A}(a)p_{B}(b|a,x)+(1-q)p^{\prime}_{A}(a|b,y)p^{\prime}_{B}(b)$
(16)

where $q\in[0,1]$ denotes the probability of the time-ordering $A\rightarrow
B$, and $p_{A}(a),p_{B}(b|a,x),p^{\prime}_{A}(a|b,x)$ and $p^{\prime}_{B}(b)$
are valid probability distributions. Such probability distributions define the
‘classical polytope’ for a given number of inputs and outputs.

For the case considered previously, with each party having binary inputs and
outputs, the ‘classical polytope’ is straightforward to construct. It has 12
vertices given by

$p(a,b|x,y)=\begin{cases}1&\text{if }a=\mu y\oplus\alpha,\quad b=\nu
x\oplus\beta\\\ 0&\text{otherwise}\end{cases}$ (17)

with $\alpha$, $\beta$, $\mu,\nu\in\\{0,1\\}$ and $\mu$ and $\nu$ not both
equal to 1. i.e. it is the subset of deterministic vertices of the no-
backwards-in-time polytope which do not depend on both $x$ and $y$.

It is interesting to note that the classical polytope is not only smaller than
the no-backwards-in-time-signalling polytope, but lives in a lower dimensional
space — it has only 7 dimensions (see Fig. 3). Indeed, classical correlations
obey the additional equalities

$p(a,b|x,y)+p(a,b|x^{\prime},y^{\prime})=p(a,b|x,y^{\prime})+p(a,b|x^{\prime},y)$
(18)

for all $a,b,x,y,x^{\prime}$ and $y^{\prime}$. This can be easily understood
by noting that each classical situation can be expressed as a mixture of
${A\rightarrow B}$ and ${A\leftarrow B}$ cases. In the former case,
$p^{A\rightarrow B}(a,b|x,y)$ is independent of $y$ and thus

$p(a,b|x,y)=p(a,b|x,y^{\prime}),\;\text{and}\;p(a,b|x^{\prime},y)=p(a,b|x^{\prime},y^{\prime})$
(19)

which ensures that (18) is satisfied. In the latter case, $p^{A\leftarrow
B}(a,b|x,y)$ is independent of $x$ and thus

$p(a,b|x,y)=p(a,b|x^{\prime},y),\;\text{and}\;p(a,b|x,y^{\prime})=p(a,b|x^{\prime},y^{\prime})$
(20)

which also satisfies (18). As both cases independently satisfy (18), any
mixture of them also will.

The new equalities given by (18) are not all independent of the NBTS
conditions. In particular, for the case considered earlier in which each party
has binary inputs and outputs, the single equality

$p(0,0|0,0)+p(0,0|1,1)=p(0,0|0,1)+p(0,0|1,0)$ (21)

can be combined with the NBTS conditions to generate all of the other cases.
For more details see Appendix A.

In this case, the classical polytope is obtained precisely by taking the NBTS
polytope and imposing the additional equality (21), which is why its dimension
is one smaller.

Furthermore, we show in Appendix B that when considering two parties with any
number of inputs and outputs, the classical polytope can be obtained by
intersecting the NBTS polytope with the equalities given in (18). That is, the
conditions (18) completely characterise classicality in the two-party scenario
— they constitute the necessary and sufficient conditions that need to be
satisfied (in addition to the NBTS, normalisation and positivity conditions),
in order for a distribution to be classical.

###  III.3 Pre- and post-selected quantum states

In the standard quantum formalism, the timing of all measurements are fixed.
Considering such cases, or mixtures of them, we obtain precisely the same
polytope of correlations as in the classical case.

However, as discovered by Aharonov, Bergmann and Lebowitz Aharonov  _et al._
(1964), and developed further in subsequent works Aharonov and Vaidman (1991);
Aharonov and Gruss (2005); Aharonov  _et al._ (2009); Silva  _et al._ (2014),
in quantum mechanics one can impose on a system a final state in addition to
and independently from the initial state. The influence of the final state
then propagates backwards in time from the final time to any previous times.
This raises the obvious question about signalling backwards in time in such
situations.

Systems with two time boundary conditions, initial and final, can be prepared
in two ways:

a) By experimental post-selection. For example, by performing a measurement at
the final time, and considering only those cases which yield a subset of the
possible results.

b) By fundamental post-selection. For example, Nature could just provide the
final boundary condition with certainty. Such situations have never been
observed, but they are theoretically possible. In fact there are a few
proposals for the possible existence of such situations: as a final state of
the Universe or a final state at the singularity of a black-hole Aharonov
(1990); *AhaRoh05; *Aharonov; Hawking  _et al._ (2000); Gell-Mann and Hartle
(1990); Horowitz and Maldacena (2004).

Pre- and post-selected states allow in general for backwards in time
signalling. However, as we show in Appendix C (and sketch below) there exists
a subclass of pre and post-selected states that does not allow for backwards
in time signalling, as discussed in the present paper. These particular pre-
and post-selected states have a special property: the probability of
succeeding to prepare such a state (by an experimental post-selection
procedure) is independent of the measurements we perform on the system at
intermediate times between pre- and post-selection, as long as the
measurements are of local observables for Alice and Bob. As a consequence, the
probability of obtaining a given outcome for an intermediate time measurement
depends linearly on the measured operators, a property that is not valid in
general for pre and post selected states.

There is an important observation to be made here: The correlations that arise
from this special set of pre and post-selected states obey the equalities
given in (18). Hence they are the same as the classical set of correlations.

A detailed proof of this result is given in Appendix C, using a formalism
developed specifically for analysing pre- and post-selected situations.
However, we sketch the key ideas below.

We first consider the most general pre- and post selected quantum states for a
single party that satisfy NBTS. Consider that you prepare an arbitrary quantum
state of a system and ancilla, and pass the system into Alice’s lab. Alice
then performs a quantum measurement, obtaining output $a$, followed by a
transformation labelled by $x$. Finally, she outputs the resulting system, and
you perform a post-selected measurement on the system and ancilla. We can
characterise the entire procedure outside Alice’s lab by a two-time state on
her input and output spaces. We will say that this state satisfies NBTS if
$p(a|x)=p(a)$ for all choices of measurement and transformation by Alice.

By considering a sufficiently large set of measurements and
transformations555in particular, destructive measurements in a selection of
bases, followed by preparation of the $|0\rangle$ state, and a range of
unitary transformations, we show in Appendix C that a single party two-time
state satisfies NBTS if and only if it corresponds to a case without post-
selection, or with trivial post-selection (i.e. post-selection on an ancilla
for which the probability of success is independent of Alice’s operations).

In the case of two parties, the NBTS conditions state that when we sum over
Bob’s output $b$, Alice’s marginal probability distribution (which may in
general depend on $y$) must satisfy the single-party NBTS conditions. Given
the above result, it follows that from Alice’s perspective there must either
be no post-selection, or a trivial post-selection (where the probability of
success is independent of $x$). Following the same argument with the parties
reversed, we can show that the probability of a successful post-selection must
also be independent of $y$. Hence, the probability of a successful post-
selection must be independent of both $x$ and $y$. This is sufficient to imply
that the situation can be represented by a linear two-time state. To prove the
converse, that any linear two-time state satisfies NBTS, we can use the
theorem from Silva  _et al._ (2017).

Note that when preparing a linear two-time state of two parties via
experimental post-selection, the probability of success is a constant for any
local operations of Alice and Bob. However, if Alice and Bob were to combine
their laboratories and perform some joint measurement on their systems, then
this could in principle affect the post-selection probability. Hence, such
states may involve non-trivial post-selection at a global level, even though
the local effects appear trivial.

###  III.4 Process Matrices

Recently, a framework for correlations has been investigated which does not
assume a global causal order, but only the local validity of quantum theory —
leading to the discovery of correlations with indefinite causal order Oreshkov
_et al._ (2012). The key object in this formalism is the process matrix, which
captures the connection between Alice’s and Bob’s laboratories. The setup
considered is similar to the one presented in this paper, except for the
crucial difference that the time ordering of the inputs and outputs in each
lab is reversed. In the process matrix formalism Alice first receives an input
$x$, then performs a measurement depending on this to generate her output $a$,
whereas in the setup considered in this paper she first performs a fixed
measurement to produce $a$, and then receives an input $x$ and performs a
transformation depending on this. The process matrix formalism includes all
quantum processes with definite time ordering ($A\rightarrow B,A\leftarrow
B,A|B$) but also includes cases which cannot be explained by any mixture of
such processes.

A physical mechanism for generating such indefinite causal correlations was
originally left open. However, it was recently shown Silva  _et al._ (2017)
(see also Oreshkov and Cerf (2016)) that any process matrix can be simulated
by quantum theory with post-selection. Furthermore, the set of pre- and post-
selected quantum states corresponding to valid process matrices are precisely
the linear two time states described in the previous section. In the context
of pre- and post- selected states, linearity seems a somewhat arbitrary and
technical restriction. The results presented in the previous section provide a
physical motivation for this set, by showing that it contains precisely those
pre-and post-selected quantum states which satisfy NBTS. It also follows that
any situation described by a process matrix cannot yield backwards-in-time
signalling in the sense considered here, and moreover that they can only
generate classical correlations. This generalises an earlier result
(considered in a different context) Baumann and Brukner (2016), which implies
that Alice and Bob can only generate classical correlations when each performs
a fixed basis measurement followed by a variable transformation on a process
matrix. Our results show that any fixed measurement (including POVMs or
projective measurements involving projectors of any rank) followed by a
variable transformation will also lead to classical correlations between Alice
and Bob.

##  IV Definite relative timing

We now move onto the second situation of interest, where there are well
defined relative times between the laboratories. We will look at two
situations: one where the experiments are in parallel (i.e. where there is a
frame where $a$ and $b$ are produced simultaneously), and one where one party
comes before the other (where will we take Alice to be first without loss of
generality).

###  IV.1 No-backwards-in-time-signalling polytopes

Consider first the situation when Alice and Bob’s experiments are in parallel.
In this situation we have

$\displaystyle p_{A}(a|x,y)$ $\displaystyle=p_{A}(a)$ (22) $\displaystyle
p_{B}(a|x,y)$ $\displaystyle=p_{B}(b)$ (23)

In the simple case of $a,b,x,y\in\\{0,1\\}$ we find that the NBTS polytope is
found to be 6 dimensional and to have 18 vertices: It has 4 deterministic
vertices given by

$p(a,b|x,y)=\begin{cases}1&\text{if }a=\alpha,\quad b=\beta\\\
0&\text{otherwise}\end{cases}$ (24)

where $\alpha,\beta\in\\{0,1\\}$, 8 ‘PR-like’ Popescu and Rohrlich (1994b)
vertices

$p(a,b|x,y)=\begin{cases}\tfrac{1}{2}&\text{if }a\oplus
b=(x\oplus\gamma)(y\oplus\delta)\oplus\epsilon\\\
0&\text{otherwise}\end{cases}$ (25)

where $\gamma,\delta,\epsilon\in\\{0,1\\}$ and 6 ‘linear correlation’ type
vertices given by

$p(a,b|x,y)=\begin{cases}\tfrac{1}{2}&\text{if }a\oplus b=\alpha x\oplus\beta
y\oplus\delta\\\ 0&\text{otherwise}\end{cases}$ (26)

where $\alpha,\beta,\delta\in\\{0,1\\}$ and $\alpha$ and $\beta$ cannot be
both simultaneously 0.

In the case where Alice’s experiment takes place before Bob’s then we find,
again in the simple case of $a,b,x,y\in\\{0,1\\}$, that the NBTS polytope is 7
dimensional with 20 vertices: It now has 8 deterministic vertices given by

$p(a,b|x,y)=\begin{cases}1&\text{if }a=\alpha,\quad b=\beta x\oplus\gamma\\\
0&\text{otherwise}\end{cases}$ (27)

where $\alpha,\beta,\gamma\in\\{0,1\\}$, the same 8 ‘PR-like’ Popescu and
Rohrlich (1994b) vertices

$p(a,b|x,y)=\begin{cases}\tfrac{1}{2}&\text{if }a\oplus
b=(x\oplus\gamma)(y\oplus\delta)\oplus\epsilon\\\
0&\text{otherwise}\end{cases}$ (28)

where $\gamma,\delta,\epsilon\in\\{0,1\\}$ but only 4 linear correlation type
vertices given by

$p(a,b|x,y)=\begin{cases}\tfrac{1}{2}&\text{if }a\oplus b=y\oplus\alpha
x\oplus\beta\\\ 0&\text{otherwise}\end{cases}$ (29)

where $\alpha,\beta,\in\\{0,1\\}$, i.e only those which having a dependence on
$y$ remain.

###  IV.2 Classical polytopes

The classical polytopes in these two cases are easily characterised. In the
case of parallel experiments, the classical polytope is only 3 dimensional,
with vertices given by the deterministic vertices of the NBTS polytope

$p(a,b|x,y)=\begin{cases}1&\text{if }a=\alpha,\quad b=\beta\\\
0&\text{otherwise}\end{cases}$ (30)

Apart from the normalisation and NBTS conditions, the additional equalities
that are obeyed are given by

$p(a,b|0,0)=p(a,b|x,y)$ (31)

for all $x$,$y$. That is, these equalities encode directly that $a$ and $b$
are constant.

In the case where Alice’s experiment takes place before Bob’s experiment, we
now find that the classical polytope is $5$ dimensional, with vertices given
again by the deterministic vertices of the corresponding NBTS polytope

$p(a,b|x,y)=\begin{cases}1&\text{if }a=\alpha,\quad b=\beta x\oplus\gamma\\\
0&\text{otherwise}\end{cases}$ (32)

Apart from the normalisation and NBTS conditions, the additional equalities
that are obeyed are given by

$p(a,b|x,0)=p(a,b|x,y)$ (33)

for all $x$, $y$, which again just directly encode that $a$ must be constant
(but now $b$ is allowed to be a function of $x$).

###  IV.3 Backwards in time influence without backwards in time signalling

A very interesting phenomenon is the possibility of having the future
influencing the past, without backwards in time signalling. This possibility
appears clearly in situations with well defined relative timing between Alice
and Bob.

Suppose, for example, that Alice and Bob’s experiments are in parallel. We can
then envisage that in some frame events that occur on Monday may depend on
what happens on Tuesday but that Alice and Bob can only find this out on
Wednesday. Indeed, the results of Alice and Bob’s measurements which occur on
Monday may depend on the actions $x$ and $y$ that occur on Tuesday but since
only the correlations between $a$ and $b$ are affected (not the marginals),
this dependency can only be observed on Wednesday when Alice and Bob emerge
from their labs and compare their results to check their correlations.
Mathematically, this is the case when $p_{A}(a|x,y)=p_{A}(a)$,
$p_{B}(b|x,y)=p_{B}(b)$, ensuring no backwards in time signalling can be
observed by Alice and Bob while in their labs, but $p(a,b|x,y)\neq p(a,b)$.,
i.e. the correlations depend on $x$ and $y$ that both occur after obtaining
$a$ and $b$. Similarly, when Alice’s experiment takes place before Bob’s, such
a situation arises when $p_{A}(a|x,y)=p_{A}(a)$, $p_{B}(b|x,y)=p_{B}(b|x)$ but
$p(a,b|x,y)\neq p(a,b)$.

In cases with indefinite relative time ordering the situation is far more
subtle and needs further analysis.

###  IV.4 Pre- and post-selected quantum states

We can again ask the question of what are the class of two-time quantum states
that do not lead to backwards in time signalling in scenarios with definite
causal order. In the appendix we show that in the case of parallel
experiments, the only two-time states that do not lead to signalling are those
states without post-selection, or with trivial post-selection. For the case of
Alice’s experiments coming before Bob’s we find that the only two-time states
allowed are those where there is a no post-selection, or a trivial post-
selection, taking place at Bob.

Crucially, once again we find that in both cases such two-time states can only
produce classical correlations in the given scenario, just as in the previous
case of indefinite relative timings.

##  V discussion

We have presented a theory-independent definition of no-backwards-in-time-
signalling, that is a temporal analogue of the no-signalling conditions that
lie at the heart of research into non-locality. What we discovered is that in
probabilistic theories it is theoretically possible to have situations (such
as in (12)) in which the future demonstrably affects the past, but in such a
way that the effect can only be discovered later, thereby avoiding paradoxes
such as killing one’s own grandfather. Such situations have not yet been
observed, so their existence is purely speculative at the moment. However it
is nevertheless instructive to understand the full scope of possible natural
laws which avoid these paradoxes.

In a scenario with two parties, we split our study into three cases, which
distinguish the prior knowledge we have about the relative time order between
the two labs. In the first case, where we have no knowledge (indefinite
relative timing), the NBTS polytope is isomorphic to the no-signalling
polytope of the same scenario. However, the set of correlations which can be
achieved classically (which obey standard ‘forwards-in-time’ causality) differ
from the analogous local polytope, obeying additional equalities. This means
that they lie in a lower dimensional subset of the full NBTS polytope (i.e. of
relative measure zero).

In the second case we know that the actions of Alice and Bob happen in
parallel (definite parallel timing), which gives additional constraints which
restrict the scenario above. The corresponding NBTS and classical polytopes
are lower dimensional than for the case with no knowledge about the relative
timings.

Finally, in the third case we have knowledge about the relative timing between
the labs, for example, that Alice’s experiment took place before Bob’s
(definite sequential timing). Here, the NBTS and classical polytopes are of
intermediate dimension between the first and second cases since the linear
constraints represent a relaxation of most restrictive case of parallel
timing. These results are summarised in Table 1.

Order | Constraints | Polytope |  |
---|---|---|---|---
|  |  | (2-input, |  |
|  |  | 2-output) |  |
Indefinite relative timing | NBTS | $\begin{aligned} \sum_{a}p(ab|xy)&=p_{B}(b|x)\\\ \sum_{b}p(ab|xy)&=p_{A}(a|y)\end{aligned}$ |  |  $8$-$d$
---
$24$ vertices
|
|  | Classical
---
and quant.
$\begin{aligned} p(ab|xy)=qp^{A\rightarrow B}\\\ +(1-q)p^{B\rightarrow A}\end{aligned}$ |  |  $7$-$d$
---
$12$ vertices
|
Definite parallel timing | NBTS | $\begin{aligned} \sum_{a}p(ab|xy)&=p_{B}(b)\\\ \sum_{b}p(ab|xy)&=p_{A}(a)\end{aligned}$ |  |  $6$-$d$
---
$18$ vertices
|
|  | Classical
---
and quant.
$\begin{aligned} p(ab|xy)=p_{A}(a)p_{B}(b)\end{aligned}$ |  |  $3$-$d$
---
$4$ vertices
|
Definite sequential timing $A\rightarrow B$ | NBTS | $\begin{aligned} \sum_{a}p(ab|xy)&=p_{B}(b|x)\\\ \sum_{b}p(ab|xy)&=p_{A}(a)\end{aligned}$ |  |  $7$-$d$
---
$20$ vertices
|
|  | Classical
---
and quant.
$\begin{aligned} p(ab|xy)=qp^{A\rightarrow B}\\\ +(1-q)p^{B\rightarrow A}\end{aligned}$ |  |  $5$-$d$
---
$8$ vertices
|
Table 1: Summary of results. According to the knowledge about the relative
timing between laboratories, different linear constraints apply and yield
different polytopes for the spaces of joint correlations $\\{p(ab|xy)\\}$
between Alice and Bob. The constraints hold for an arbitrary number of inputs
and outputs, while the polytopes described are for the specific case where
$a,b,x,y\in\\{0,1\\}$.

Despite the mathematical similarity between the NBTS polytope and the no-
signalling polytope in the case of indefinite timing, it is important to note
that the physics of the two cases is very different. In the case of non-local
boxes, Alice and Bob are outside the boxes. They then use the boxes as
resources, since whatever they do doesn’t change the way in which the boxes
act. On the other hand, in the NBTS scenario, we consider closed laboratories
with Alice and Bob inside (and part of) their respective laboratory.
Crucially, their actions can, and do, modify the correlations obtained within
their laboratories. Hence we cannot think of NBTS correlations as a resource
in the same way as NL boxes. In particular, if instead of using the
independently generated external inputs $x$ and $y$ to determine which
transformations to perform on their systems (as we have considered throughout
this work), Alice and Bob attempt to ‘close a time loop’ by using their
earlier measurement results to determine their transformations, they may
create different time-flow structures inside their labs, so the correlations
that arise are no longer the same as if they had used the external inputs.

In the context of two-party pre- and post-selected quantum states with
indefinite relative timing, the NBTS condition exactly characterises the
special set of cases corresponding to process matrices Oreshkov  _et al._
(2012). Furthermore, the correlations achievable by such states are identical
to those achievable classically666Note that the correlations are classical for
the situation considered here, where Alice and Bob’s measurements occur before
their transformations. However, process matrices do lead to non-classical
correlations in the situation where Alice and Bob perform measurements based
upon their inputs..

For the case of indefinite relative timing, the NBTS conditions can be
generalised straightforwardly to multiple parties. Given $N$ parties, with
inputs $\textbf{x}=\\{x_{1},x_{2},\ldots x_{N}\\}$ and outputs
$\textbf{a}=\\{a_{1},a_{2},\ldots a_{N}\\}$, we demand that each party’s
marginal probability distribution is independent of their input. i.e.

$\displaystyle\sum_{a_{2},a_{3},\dots
a_{N}}P(\textbf{a}|\textbf{x})=P_{A}(a_{1}|x_{2},\ldots,x_{N})$

and similarly for the other parties. This ensures that each party individually
does not perceive backwards in time signalling. Note that this is different
from the usual multi-party no-signalling conditions, where we only sum over
one party’s input (e.g. $\sum_{a_{1}}P(\textbf{a}|\textbf{x})$ is independent
of $x_{1}$). Hence, in general, the multi-party polytopes in the two cases
will not be isomorphic. Finally, the multipartite cases of definite relative
timings would present further constraints to the one above. The extremal case
of when everyone’s actions happen in parallel generalises trivially as

$\displaystyle\sum_{a_{2},a_{3},\dots
a_{N}}P(\textbf{a}|\textbf{x})=P_{A}(a_{1})\,,$ (34)

and analogously for the other parties. The other cases of definite relative
timing are more subtle, since they could contain some subset of the parties
acting in parallel and then signalling to the others. For example in the case
where Alice’s actions come before Bob and Charlie’s (who act in parallel),
whose actions come before Dave, denoted $A\rightarrow B|C\rightarrow D$. It
would be interesting to explore these cases further and find the general
classes of behaviours.

###### Acknowledgements.

YG acknowledges funding from the Austrian Science Fund (FWF) through the
project P 31339-N27, the START project Y879-N27, and the joint Czech-Austrian
project Multi-QUEST (I 3053-N27 and GF17-33780L). SP and PS acknowledge
support from the ERC through the AdG NLST. PS acknowledges support from the
Royal Society through a University Research Fellowship (UHQT). RS and NB
acknowledge financial support from the Swiss National Science Foundation
(Starting grants DIAQ and QSIT). AJS acknowledges support from an FQXi
“Physics of what happens” grant, via SVCF. _Note added:_ After the completion
of this work we have learned of an unpublished related earlier work by Caslav
Brukner Brukner (2014) where the NBTS conditions (1), (4) and (5) were also
formulated, and implications for the process matrix formalism were considered.

## References

  * Bell (1964) J. S. Bell, Physics Physique Fizika 1, 195 (1964).
  * Popescu and Rohrlich (1994a) S. Popescu and D. Rohrlich, Found. Phys. 24, 379 (1994a).
  * Brunner  _et al._ (2014) N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Rev. Mod. Phys. 86, 419 (2014).
  * Aharonov  _et al._ (1990) Y. Aharonov, J. Anandan, S. Popescu, and L. Vaidman, Phys. Rev. Lett. 64, 2965 (1990).
  * Chiribella  _et al._ (2013) G. Chiribella, G. M. D’Ariano, P. Perinotti, and B. Valiron, Phys. Rev. A 88, 022318 (2013).
  * Hardy (2007) L. Hardy, J. Phys A: Math. Theor. 40, 3081 (2007).
  * Oreshkov  _et al._ (2012) O. Oreshkov, F. Costa, and C. Brukner, Nat Commun 3, 1092 (2012).
  * Leifer and Spekkens (2013) M. S. Leifer and R. W. Spekkens, Phys. Rev. A 88, 052130 (2013).
  * Baumeler and Wolf (2014) A. Baumeler and S. Wolf, in  _2014 IEEE Int. Symp. Info. Theory_ (2014) pp. 526–530.
  * Allen  _et al._ (2016) J.-M. A. Allen, J. Barrett, D. C. Horsman, C. M. Lee, and R. W. Spekkens, arXiv:1609.09487 (2016).
  * DAriano  _et al._ (2016) G. M. DAriano, G. Chiribella, and P. Perinotti,  _Quantum Theory from First Principles_ (Cambridge University Press, 2016).
  * Perinotti (2016) P. Perinotti, arXiv:1612.05099 [quant-ph] (2016), arXiv: 1612.05099.
  * Branciard  _et al._ (2016) C. Branciard, M. Araújo, A. Feix, F. Costa, and Časlav Brukner, New J. Phys. 18, 013008 (2016).
  * Araújo  _et al._ (2015) M. Araújo, C. Branciard, F. Costa, A. Feix, C. Giarmatzi, and Časlav Brukner, New J. Phys. 17, 102001 (2015).
  * Oreshkov and Giarmatzi (2016) O. Oreshkov and C. Giarmatzi, New J. Phys. 18, 093020 (2016).
  * Abbott  _et al._ (2016) A. A. Abbott, C. Giarmatzi, F. Costa, and C. Branciard, Phys. Rev. A 94, 032131 (2016).
  * Baumeler and Wolf (2016) A. Baumeler and S. Wolf, New J. Phys. 18, 035014 (2016).
  * Aharonov  _et al._ (1964) Y. Aharonov, P. G. Bergmann, and J. L. Lebowitz, Phys. Rev. 134, B1410 (1964).
  * Aharonov and Vaidman (1991) Y. Aharonov and L. Vaidman, J. Phys. A: Math. Gen. 24, 2315 (1991).
  * Aharonov and Gruss (2005) Y. Aharonov and E. Y. Gruss,  (2005), arXiv:0507269 [quant-ph] .
  * Aharonov  _et al._ (2009) Y. Aharonov, S. Popescu, J. Tollaksen, and L. Vaidman, Phys. Rev. A 79, 052110 (2009).
  * Silva  _et al._ (2014) R. Silva, Y. Guryanova, N. Brunner, N. Linden, A. J. Short, and S. Popescu, Phys. Rev. A 89, 012121 (2014).
  * Silva  _et al._ (2017) R. Silva, Y. Guryanova, A. J. Short, P. Skrzypczyk, N. Brunner, and S. Popescu, New J. Phys. 19, 103022 (2017).
  * Chiribella  _et al._ (2010) G. Chiribella, G. M. D’Ariano, and P. Perinotti, Phys. Rev. A 81, 062348 (2010).
  * Barrett  _et al._ (2005) J. Barrett, N. Linden, S. Massar, S. Pironio, S. Popescu, and D. Roberts, Phys. Rev. A 71, 022101 (2005).
  * Almeida  _et al._ (2010) M. L. Almeida, J.-D. Bancal, N. Brunner, A. Acín, N. Gisin, and S. Pironio, Phys. Rev. Lett. 104, 230404 (2010).
  * Aharonov (1990) Y. Aharonov, (1990), personal communication.
  * Aharonov and Rohrlich (2005) Y. Aharonov and D. Rohrlich,  _Quantum Paradoxes: Quantum Theory for the Perplexed_ (Wiley VCH, 2005).
  * Hawking  _et al._ (2000) S. W. Hawking, T. Hertog, and H. S. Reall, Phys. Rev. D 62, 043501 (2000).
  * Gell-Mann and Hartle (1990) M. Gell-Mann and J. Hartle,  _Complexity, Entropy and the physics of information, SFI Studies in the Sciences of Complexity_ , edited by A. W. Zurek, Vol. VIII (Wesley, 1990).
  * Horowitz and Maldacena (2004) G. T. Horowitz and J. Maldacena, J. High Energy Phys. 2004, 008 (2004).
  * Oreshkov and Cerf (2016) O. Oreshkov and N. J. Cerf, New J. Phys. 18, 073037 (2016).
  * Baumann and Brukner (2016) V. Baumann and i. c. v. Brukner, Phys. Rev. A 93, 062324 (2016).
  * Popescu and Rohrlich (1994b) S. Popescu and D. Rohrlich, Found. Phys. 24, 379 (1994b).
  * Brukner (2014) C. Brukner, (2014), talk given at 554. WE-Heraeus-Seminar conference _Quantum Contextuality, Non-Locality, and the Foundations of Quantum Mechanics_ .

##  Appendix A Relation between classical equalities for indefinite relative
timing

In this appendix we focus on the case of indefinite relative timing (minimal)
and show that combining the NBTS conditions with the relations

$p(a,b|x,y)+p(a,b|x^{\prime},y^{\prime})=p(a,b|x,y^{\prime})+p(a,b|x^{\prime},y)$
(35)

when $a,b,x,y,x^{\prime},y^{\prime}$ are binary yields just one new equality.
First note that the only non-trivial cases occur when $x\neq x^{\prime}$ and
$y\neq y^{\prime}$. Consider the equality

$p(0,0|0,0)+p(0,0|1,1)=p(0,0|0,1)+p(0,0|1,0)$ (36)

by combining this with the NBTS conditions (Eqns. (4) and (5)) we can show

$p(0,1|0,0)+p(0,1|1,1)=p(0,1|0,1)+p(0,1|1,0)$ (37)

as follows

$\displaystyle p(0,1|0,0)+p(0,1|1,1)$
$\displaystyle=p_{A}(0|y=0)+p_{A}(0|y=1)-p(0,0|0,0)-p(0,0|1,1)$
$\displaystyle=p_{A}(0|y=0)+p_{A}(0|y=1)-p(0,0|0,1)-p(0,0|1,0)$
$\displaystyle=p(0,1|1,0)+p(0,1|0,1).$ (38)

where we have used the fact that

$\displaystyle p_{A}(0|y=0)$ $\displaystyle=p(0,0|0,0)+p(0,1|0,0)$
$\displaystyle=p(0,0|1,0)+p(0,1|1,0).$ (39)

Using a similar approach, we can prove the case with $a=1,b=0$, and by
combining the NBTS conditions with one of these new equalities we can prove
the $a=1,b=1$ case.

In general if $a,b,x$ and $y$ can take $A,B,X$ and $Y$ different values
respectively, then a similar argument shows that the number of new equalities
given by (35) is $(A-1)(B-1)(X-1)(Y-1)$.

##  Appendix B Characterisation of the classical polytope for indefinite
relative timings

In this appendix, in the case of indefinite relative timing (minimal), we show
that when considering two parties and any number of inputs and outputs, the
classical polytope is given by the intersection of the NBTS polytope with the
the additional classicality conditions

$\displaystyle p(a,b|x,y)$
$\displaystyle+p(a,b|x^{\prime},y^{\prime})=p(a,b|x,y^{\prime})+p(a,b|x^{\prime},y),$
(40)

for all $a$, $b$, $x$, $y$, $x^{\prime}$, $y^{\prime}$.

Let us consider that each party obtains one of $d$ outcomes, $a$, $b$
$\in\\{0,\ldots,d-1\\}$ and has $m$ inputs, $x$, $y$ $\in\\{0,\ldots,m-1\\}$.
The classical polytope, in terms of vertices, is the convex hull of
deterministic distributions, which fall into three families: the ‘actions
overlap in time’ family, comprised of vertices of the form

$p(a,b|x,y)=\begin{cases}1&\text{if }a=\alpha,\quad b=\beta\\\
0&\text{otherwise}\end{cases}$ (41)

parametrised by $\alpha\in\\{0,\ldots,d-1\\}$ and
$\beta\in\\{0,\ldots,d-1\\}$. Here $a=\alpha$ and $b=\beta$ are the
deterministic outcomes, independent of $x$ and $y$; The ‘Alice’s actions occur
entirely before Bob’s actions’ family, comprised of vertices of the form

$p(a,b|x,y)=\begin{cases}1&\text{if }a=\alpha,\quad b=\beta_{x}\\\
0&\text{otherwise}\end{cases}$ (42)

parametrised by $\alpha\in\\{0,\ldots,d-1\\}$ and
$\beta_{x}\in\\{0,\ldots,d-1\\}$ for all $x$. Here $a=\alpha$, independent of
$y$, and $b=\beta_{x}$; The ‘Bob’s actions occur entirely before Alice’s
actions’ family, comprised of vertices of the form

$p(a,b|x,y)=\begin{cases}1&\text{if }a=\alpha_{y},\quad b=\beta\\\
0&\text{otherwise}\end{cases}$ (43)

parametrised by $\alpha_{y}\in\\{0,\ldots,d-1\\}$ for all $y$, and
$\beta\in\\{0,\ldots,d-1\\}$. Here $a=\alpha_{y}$, and $b=\beta$, independent
of $x$.777We note that the ‘actions overlap in time’ (41) family is contained
in both other families (42) and (43), (in the case that $\alpha_{y}=\alpha$ or
$\beta_{x}=\beta$). We present it as a separate sub-family for presentational
purposes for what follows.

In what follows, we will show that this polytope has an alternative
characterisation, as the intersection of the NBTS polytope with the
classicality conditions (40).

Note first that the classical polytope is contained in this intersection. This
follows, since all of the above vertices satisfy the NBTS conditions (since
they are a subset of the vertices of the NBTS polytope), and moreover can be
seen to satisfy the classicality conditions (40), due to the fact that in all
three families at least one of the parties has a constant output. Finally any
convex combination of the vertices also satisfy the same equalities.

What needs to be shown then is that any point
$\mathbf{p}=\\{p(a,b|x,y)\\}_{a,b,x,y}$ that satisfies the NBTS and
classicality conditions is contained inside the classical polytope. To do so,
it suffices to show that any such $\mathbf{p}$ can be written as a convex
combination of the vertices of the classical polytope, i.e. of vertices of the
form (41) – (43). In what follows, we will give an iterative procedure which
at every stage decomposes a point $\mathbf{p}$ into a vertex of the classical
polytope and a second point $\mathbf{p}^{\prime}$ that still satisfies the
NBTS and classicality conditions. This procedure is shown to terminate, in
which case an explicit decomposition is obtained.

Consider a point $\mathbf{p}=\\{p(a,b|x,y)\\}$ which satisfies the NBTS and
classicality conditions. We start by identifying the smallest individual non-
zero probability, i.e, the specific choice of outputs and inputs $a^{*}$,
$b^{*}$, $x^{*}$, $y^{*}$ such that $p(a^{*},b^{*}|x^{*},y^{*})\leq
p(a,b|x,y)$ for all $a,b,x,y$ such that $p(a,b|x,y)\neq 0$. Let us denote
$\epsilon=p(a^{*},b^{*}|x^{*},y^{*})$.

We next check whether, for any value $x\neq x^{*}$

$p(a^{*},b^{*}|x,y^{*})=0,$ (44)

or whether for any value $y\neq y^{*}$

$p(a^{*},b^{*}|x^{*},y)=0.$ (45)

There are four possibilities: (i) there is no $x$ such that (44) is satisfied
and no $y$ such that (45) is satisfied; (ii) there is no $x$ such that (44) is
satisfied but a non-empty subset of $y$ such that (45) is satisfied; (iii)
there is no $y$ such that (45) is satisfied but a non-empty subset of $x$ such
that (44) is satisfied; (iv) there is simultaneously a non-empty subset of $x$
such that (44) is satisfied and a non-empty subset of $y$ such that (45) is
satisfied.

Note that the last possibility is in fact impossible. It would imply in
particular that there is an $x^{\prime}$ and $y^{\prime}$ such that
$p(a^{*},b^{*}|x^{\prime},y^{*})=0$ and $p(a^{*},b^{*}|x^{*},y^{\prime})=0$.
From the classicality conditions (40) applied to $x^{\prime}$ and $y^{\prime}$
in conjunction with $x^{*}$ and $y^{*}$, it would then follow that
$p(a^{*},b^{*}|x^{*},y^{*})=0$, since

$\displaystyle p(a^{*},b^{*}|x^{*},y^{*})$
$\displaystyle+p(a^{*},b^{*}|x^{\prime},y^{\prime})$ (46)
$\displaystyle\qquad=p(a^{*},b^{*}|x^{\prime},y^{*})+p(a^{*},b^{*}|x^{*},y^{\prime}),$
$\displaystyle\qquad=0,$ (47)

but by assumption $p(a^{*},b^{*}|x^{*},y^{*})=\epsilon>0$, which is a
contradiction.

Let us assume first then that case (i) holds, i.e. that
$p(a^{*},b^{*}|x,y^{*})\geq\epsilon$ for all $x$ and
$p(a^{*},b^{*}|x^{*},y)\geq\epsilon$ for all $y$.888Note that, since
$p(a^{*},b^{*}|x^{*},y^{*})=\epsilon$ was assumed to be the smallest non-zero
probability, if $p(a^{*},b^{*}|x,y^{*})\neq 0$ then necessarily
$p(a^{*},b^{*}|x,y^{*})\geq\epsilon$, and similarly for
$p(a^{*},b^{*}|x^{*},y)$. It then follows that

$p(a^{*},b^{*}|x,y)\geq\epsilon$ (48)

for all $x$, $y$. Indeed, let us assume that this were not the case, i.e. that
for some choice $x^{\prime}$ and $y^{\prime}$,
$p(a^{*},b^{*}|x^{\prime},y^{\prime})~{}=~{}0$. From the classicality
conditions (40) it would then follow that

$\displaystyle p(a^{*},b^{*}|x^{*},y^{\prime})$
$\displaystyle+p(a^{*},b^{*}|x^{\prime},y^{*})$ (49)
$\displaystyle\qquad=p(a^{*},b^{*}|x^{*},y^{*})+p(a^{*},b^{*}|x^{\prime},y^{\prime})$
$\displaystyle\qquad=\epsilon.$ (50)

However this is impossible, since both $p(a^{*},b^{*}|x^{*},y^{\prime})$ and
$p(a^{*},b^{*}|x^{\prime},y^{*})$ are by assumption non-vanishing and at least
as large as $\epsilon$. Thus in case (i), we see that
$p(a^{*},b^{*}|x,y)\geq\epsilon$ for all $x$, $y$.

Consider now the point $\mathbf{p}_{c}=\\{p_{c}(a,b|x,y)\\}$ that is a vertex
of the classical polytope from the family (41) with $\alpha=a^{*}$,
$\beta=b^{*}$, i.e. the deterministic distribution where $a=a^{*}$, $b=b^{*}$
and $p_{c}(a,b|x,y)=\delta_{a,a^{*}}\delta_{b,b^{*}}$.

The above shows that the distribution $\mathbf{p}$ can be written as

$\mathbf{p}=\epsilon\mathbf{p}_{c}+(1-\epsilon)\mathbf{p}^{\prime}$ (51)

if $\epsilon<1$, or $\mathbf{p}=\mathbf{p}_{c}$ if $\epsilon=1$, where
$\mathbf{p}^{\prime}=\\{p^{\prime}(a,b|x,y)\\}$ is some other point. Indeed,
the above analysis guarantees that $p^{\prime}(a,b|x,y)\geq 0$ for all $a$,
$b$, $x$, $y$, since
$p^{\prime}(a^{*},b^{*}|x,y)=(p(a^{*},b^{*}|x,y)-\epsilon)/(1-\epsilon)\geq 0$
and $p^{\prime}(a,b|x,y)=p(a,b|x,y)/(1-\epsilon)\geq 0$ if $a\neq a^{*}$ or
$b\neq b^{*}$. Moreover it also satisfies the NBTS conditions, normalisation
of probabilities, and the classicality conditions (40), due to linearity.
Finally, it has the important property that
$p^{\prime}(a^{*},b^{*}|x^{*},y^{*})=0$, i.e. $\mathbf{p}^{\prime}$ has at
least one more vanishing probability than $P$.

Thus, when case (i) occurs, either $\mathbf{p}$ was an ‘actions overlap in
time’ vertex of the classical polytope (when $\epsilon=1)$, or it is possible
to write it as a convex combination of such a vertex and a second
distribution. In the former case, we have achieved the goal of showing that
$\mathbf{p}$ is contained in the classical polytope, while in the second case
we can now re-start the above procedure, focusing on $\mathbf{p}^{\prime}$
instead of $\mathbf{p}$.

Let us now assume that case (i) does not hold, but rather case (ii), i.e.
$p(a^{*},b^{*}|x,y^{*})\geq\epsilon$ for all $x$ and
$p(a^{*},b^{*}|x^{*},y)=0$ for some non-empty subset of $y$.

We will show that for each value of $y$, there is an outcome $a=a_{y}$ such
that $p(a_{y},b^{*}|x,y)\geq\epsilon$ for all $x$.

The only way that it would be impossible to find, for some $y^{\prime}$, an
$a_{y^{\prime}}$ such that $p(a_{y^{\prime}},b^{*}|x,y^{\prime})\geq\epsilon$
for all $x$, would be if for each value of $a$, there was an input $x_{a}$
such that $p(a,b^{*}|x_{a},y^{\prime})=0$. Indeed, in this case, there is no
suitable choice for $a_{y^{\prime}}$, since every choice is ruled out by the
input $x_{a}$. We will now show that this cannot occur.

Assuming that the above can happen, that an $x_{a}$ exists for each $a$ such
that $p(a,b^{*}|x_{a},y^{\prime})=0$, then from the classicality conditions
(40) it would follow that for all $a$,

$\displaystyle p(a,b^{*}|x^{*},y^{*})=p(a,b^{*}|x_{a},y^{*})$
$\displaystyle+p(a,b^{*}|x^{*},y^{\prime}).$ (52)

From the NBTS condition of Alice, it holds that

$\sum_{a}p(a,b^{*}|x^{*},y^{*})=\sum_{a}p(a,b^{*}|x^{*},y^{\prime}).$ (53)

Substituting (52) into this NBTS condition, this would therefore imply that

$\sum_{a}p(a,b^{*}|x_{a},y^{*})=0$ (54)

which in turn would imply that $p(a,b^{*}|x_{a},y^{*})=0$ for all $a$. This
however cannot occur, since for the choice $a=a^{*}$ it would imply that
$p(a^{*},b^{*}|x_{a^{*}},y^{*})=0$, however by assumption of case (ii),
$p(a^{*},b^{*}|x,y^{*})\geq\epsilon$ for all $x$. This contradiction shows
that no such $x_{a}$ can exist.

In summary, for each value of $y$ there is an outcome $a=a_{y}$ such that
$p(a_{y},b^{*}|x,y)\geq\epsilon$ for all $x$.

Thus, similarly to case (i), if we consider now the point $\mathbf{p}_{c}$
which is a classical vertex from the family (43) with $\alpha_{y}=a_{y}$ and
$\beta=b^{*}$, i.e. such that
$p_{c}(a,b|x,y)=\delta_{a,a_{y}}\delta_{b,b^{*}}$, then the above implies that
it is possible to decompose $\mathbf{p}$ as

$\mathbf{p}=\epsilon\mathbf{p}_{c}+(1-\epsilon)\mathbf{p}^{\prime}$ (55)

if $\epsilon<1$, or $\mathbf{p}=\mathbf{p}_{c}$ if $\epsilon=1$, where again
$\mathbf{p}^{\prime}$ is some other (positive) distribution which, as well as
still satisfying the NBTS, normalisation and classicality conditions, has the
analogous property to before that $p^{\prime}(a^{*},b^{*}|x^{*},y^{*})=0$,
i.e. has at least one more vanishing probability than $p(a,b|x,y)$.

Thus, when case (ii) occurs, $\mathbf{p}$ is shown either to be equal to an
‘Alice’s actions occur entirely before Bob’s actions’ vertex of the classical
polytope, or it is possible to write it as a convex combination of a such a
vertex and a second distribution. Once again, in the former case we have the
desired decomposition, and in the latter we can re-start the above procedure,
focusing on $\mathbf{p}^{\prime}$ instead of $\mathbf{p}$.

Finally, case (iii) is identical to case (ii), except the role of Alice and
Bob is reversed. That is, if we are in case (iii), for each value of $x$ it is
always possible to find an outcome $b=b_{x}$ such that
$p(a^{*},b_{x}|x,y)\geq\epsilon$ for all $y$. Subsequently $\mathbf{p}$ can be
decomposed as
$\mathbf{p}=\epsilon\mathbf{p}_{c}+(1-\epsilon)\mathbf{p}^{\prime}$ if
$\epsilon<1$ or $\mathbf{p}=\mathbf{p}_{c}$ if $\epsilon=1$, where now
$\mathbf{p}_{c}$ is a vertex from the family (42) with $\alpha=a^{*}$ and
$\beta_{x}=b_{x}$, and $\mathbf{p}^{\prime}$ has at least one more vanishing
probability compared to $\mathbf{p}$.

In conclusion, given any distribution $\mathbf{p}=\\{p(a,b|x,y)\\}_{a,b,x,y}$
that satisfies the NBTS, normalisation and classicality conditions, by
iterating the above procedure, a sequence of decompositions are generated,

$\displaystyle\mathbf{p}$
$\displaystyle=\epsilon^{(1)}\mathbf{p}_{c}^{(1)}+(1-\epsilon^{(1)})\mathbf{p}^{(1)}$
$\displaystyle=\epsilon^{(1)}\mathbf{p}_{c}^{(1)}+(1-\epsilon^{(1)})[\epsilon^{(2)}\mathbf{p}_{c}^{(2)}+(1-\epsilon^{(2)})\mathbf{p}^{(2)}]$
$\displaystyle\hskip 142.26378pt\vdots$
$\displaystyle=\epsilon^{(1)}\mathbf{p}_{c}^{(1)}+(1-\epsilon^{(1)})\epsilon^{(2)}\mathbf{p}_{c}^{(2)}+\ldots+\prod_{i=1}^{k}(1-\epsilon^{(i)})\mathbf{p}^{(k)}$
$\displaystyle\hskip 142.26378pt\vdots$ (56)

such that the ‘remainder’ $\mathbf{p}^{(k)}$ is a valid distribution
(positive, normalised and satisfying the NBTS conditions) and has at least one
more vanishing probability than the previous remainder $\mathbf{p}^{(k-1)}$.
Since there are only at most $d^{2}m^{2}$ non-vanishing probabilities, the
sequence cannot carry on indefinitely and it must be the case that after a
finite number $N$ of iterations the procedure terminates. This happens exactly
when the smallest probability of the remainder is in fact unity,
$\epsilon^{(N)}=1$, in which case, from the above analysis, we are guaranteed
that it will be a vertex of the classical polytope,
$\mathbf{p}^{(N)}=\mathbf{p}^{(N)}_{c}$. When the procedure terminates at this
stage we have thus obtained an explicit convex decomposition of the original
distribution $\mathbf{p}$ into vertices of the classical polytope,

$\mathbf{p}=\epsilon^{(1)}\mathbf{p}_{c}^{(1)}+(1-\epsilon^{(1)})\epsilon^{(2)}\mathbf{p}_{c}^{(2)}+\ldots+\prod_{i=1}^{N-1}(1-\epsilon^{(i)})\mathbf{p}_{c}^{(N)}\\\
$

As such, any $\mathbf{p}$ satisfying the NBTS, normalisation, and classicality
conditions is contained inside the classical polytope. The classical polytope
for two parties is thus characterised as the intersection of the NBTS polytope
with the classicality conditions (40). An alternative way of saying this, is
that the NBTS, normalisation and classicality conditions are necessary and
sufficient conditions for a point $\mathbf{p}$ to be classical.

##  Appendix C Two-time quantum states

In this appendix we consider which two-time (pre- and post-selected) quantum
states obey NBTS, in the sense that they give rise to probabilities obeying
the NBTS constraints. In particular, we first consider a single party (Alice)
who has a lab into which a quantum state enters, they perform a quantum
measurement on that state (obtaining result $a$), then apply a quantum channel
to the state (labelled by $x$), before sending it out of their laboratory. At
the entrance and exit of their laboratory, a general pre- and post-selected
quantum state $\eta$ is prepared. If $p(a|x)=p(a)$ for all choices of
measurement and channel by Alice, then we say that the two-time state $\eta$
obeys NBTS.

We then consider two parties, Alice and Bob, each of whom has a laboratory
into which a quantum state enters, they perform a measurement on it (with
outputs $a$ and $b$ respectively), then apply a channel to the state (labelled
by $x$ and $y$) and then output the resultant system from their laboratory.
Outside their laboratories, Alice and Bob’s inputs and outputs are prepared in
an arbitrary pre- and post-selected state. If $p(a,b|x,y)$ satisfies the NBTS
conditions for a given scenario, then we say that the two-party state obeys
NBTS.

We prove the following results: (i) for a single party, the only states which
obey NBTS correspond to standard (pre-selected) quantum states with no post-
selection, or with trivial post-selection (i.e. post-selection on an ancilla
for which the probability of success is independent of Alice’s operations).
For two parties: (ii) the states which obey the NBTS conditions for indefinite
relative timing correspond to the _linear two time states_ defined in Silva
_et al._ (2017), which are equivalent to process matrices Oreshkov  _et al._
(2012). If these states are prepared via experimental post-selection, then the
probability of success in the post-selection is independent of each party’s
operations. (iii) Linear two-time states satisfy the equality (18) satisfied
by classical correlations. (iv) the states which obey the NBTS conditions with
definite and parallel relative timing correspond to standard pre-selected
quantum states with no post-selection, or with trivial post-selection. (v) the
states which obey the NBTS conditions with definite relative timing and Alice
before Bob correspond to states which do not involve a post-selection for Bob
(or a trivial post-selection). (vi) In all of the above cases, the states can
only produce classical correlations.

###  C.1 Review of pre- and post-selected formalism

Here we briefly review the formalism for pre- and post- selected quantum
states presented in Silva  _et al._ (2014, 2017).

For an arbitrary process (which may be a state, measurement or channel), we
associate a Hilbert space
$\mathcal{H}^{\mathcal{O}}\otimes\mathcal{H}_{\mathcal{O}^{\dagger}}$ to every
output $O$, where $\mathcal{H}^{\mathcal{O}}$ (with raised index) is a
standard vector space (represented by a ket) and
$\mathcal{H}_{\mathcal{O}^{\dagger}}$ (with lowered index) is a dual vector
space (represented by a bra). Similarly, we associate a Hilbert space
$\mathcal{H}_{\mathcal{I}}\otimes\mathcal{H}^{\mathcal{I}^{\dagger}}$ to every
input $I$.

The mathematical object associated with that process is then a vector in the
tensor product space of all of the output and input spaces. Composition of two
processes is given by the $\bullet$ operation, which connects vectors and dual
vectors with the same label to give a scalar (i.e.
${}_{\mathcal{A}}\langle\psi|\bullet|\phi\rangle^{\mathcal{A}}=\langle\psi|\phi\rangle$)
and performs the tensor product on vectors or dual vectors with different
labels. All allowed physical processes correspond to ‘positive’ vectors in the
appropriate Hilbert space. In particular given a process $C_{A_{1}}^{A_{2}}$
with input $A_{1}$ and output $A_{2}$, then $(v\otimes v^{\dagger})\bullet
C_{A_{1}}^{A_{2}}\geq 0$ for all
$v\in\mathcal{H}^{\mathcal{A}_{1}}\otimes\mathcal{H}_{\mathcal{A}_{2}}$ (with
Hermitian conjugate
$v^{\dagger}\in\mathcal{H}_{\mathcal{A}_{1}^{\dagger}}\otimes\mathcal{H}^{\mathcal{A}_{2}^{\dagger}}$).

Positivity is the only condition for a pre- and post-selected state to be
physically achievable. Channels (implemented without post selection) must also
satisfy an additional condition, which corresponds to them being trace-
preserving. For a channel $C_{A_{1}}^{A_{2}}$ from $A_{1}$ to $A_{2}$ we
require that $\mathbb{I}_{A_{2}}\bullet C_{A_{1}}^{A_{2}}=\mathbb{I}_{A_{1}}$,
where
$\mathbb{I}_{A_{1}}=\sum_{i}|i\rangle^{\mathcal{A}_{1}^{\dagger}}\otimes\langle
i|_{\mathcal{A}_{1}}$ (i.e. they must be future-identity preserving). A
measurement is described by a set of processes $M_{a}$ corresponding to the
output $a$, such that $M=\sum_{a}M_{a}$ is a valid channel. For the sake of
familiarity, it is sometimes helpful to move between vectors in the pre- and
post-selected formalism (such as
$\rho^{A}=\sum_{ij}\rho_{ij}|i\rangle^{\mathcal{A}}\otimes\langle
j|_{\mathcal{A}^{\dagger}}$) and the corresponding operator in the standard
quantum formalism, which we will denote with a ‘hat’ (e.g.
$\hat{\rho}^{A}=\sum_{ij}\rho_{ij}|i\rangle\langle j|$).

In any pre- and post-selected scenario, the joint probability of obtaining any
particular set of measurement outcomes can be obtained by composing all of the
processes (with the measurements having those particular outcomes), and
dividing by the same quantity summed over all outcomes (which corresponds with
replacing the individual measurement outcomes with the corresponding
measurement channels). For example, given a pre- and post-selected state state
$\eta^{A_{1}}_{A_{2}}$ and a measurement $(M_{a})_{A_{1}}^{A_{2}}$, the
probability of obtaining outcome $a$ is given by

$p(a)=\frac{\eta\bullet M_{a}}{\eta\bullet M}$ (57)

where $M=\sum_{a}M_{a}$. Note that the overall normalisation of $\eta$ is not
physically relevant. If $\eta$ is prepared via experimental post-selection,
then the denominator of this expression ($\eta\bullet M$) is proportional to
the probability of the post-selection succeeding (with respect to changes in
$M$).

###  C.2 No-backwards-in-time signalling states

Within the framework described in the previous section, we now define the
class of two-time states obeying NBTS.

###### Definition 1

No-backwards-in-time-signalling for two-time states. We say that a two-time
state $\eta$ for a single party obeys NBTS if the outcome probabilities
$p(a|x)$ are independent of $x$ when we perform any (non-destructive, trace-
preserving) measurement $J_{a}$ followed by a trace-preserving channel chosen
from a set $L_{x}$. In particular we demand

$p(a|x)\equiv\frac{L_{x}\bullet J_{a}\bullet\eta}{L_{x}\bullet
J\bullet\eta}=p(a)\;\;\textrm{i.e. it is independent of $x$ }$ (58)

where $\eta=\eta^{A_{1}}_{A_{3}}$, $J_{a}=(J_{a})^{A_{2}}_{A_{1}}$, with
$J=\sum_{a}J_{a}$, and $L_{x}=(L_{x})^{A_{3}}_{A_{2}}$.

When considering a pre- and post- selected state $\eta$ of two parties, in the
case of indefinite relative timing, we say that it obeys NBTS if

$\displaystyle p(a|x,y)$ $\displaystyle\equiv\frac{L_{x}\bullet J_{a}\bullet
L^{\prime}_{y}\bullet J^{\prime}\bullet\eta}{L_{x}\bullet J\bullet
L^{\prime}_{y}\bullet J^{\prime}\bullet\eta}=p(a|y)$ (59) $\displaystyle
p(b|x,y)$ $\displaystyle\equiv\frac{L_{x}\bullet J\bullet
L^{\prime}_{y}\bullet J^{\prime}_{b}\bullet\eta}{L_{x}\bullet J\bullet
L^{\prime}_{y}\bullet J^{\prime}\bullet\eta}=p(b|x)$ (60)

where $J_{a}$ and $L_{x}$ are defined as above,
$\eta=\eta^{A_{1}B_{1}}_{A_{3}B_{3}}$,
$J^{\prime}_{b}=(J^{\prime}_{b})^{B_{2}}_{B_{1}}$ with
$J^{\prime}=\sum_{b}J_{b}$, and $L^{\prime}_{y}=(L_{y})^{B_{3}}_{B_{2}}$.

For the case of definite parallel timing, the same state $\eta$ obeys NBTS if

$\displaystyle p(a|x,y)$ $\displaystyle\equiv\frac{L_{x}\bullet J_{a}\bullet
L^{\prime}_{y}\bullet J^{\prime}\bullet\eta}{L_{x}\bullet J\bullet
L^{\prime}_{y}\bullet J^{\prime}\bullet\eta}=p(a)$ (61) $\displaystyle
p(b|x,y)$ $\displaystyle\equiv\frac{L_{x}\bullet J\bullet
L^{\prime}_{y}\bullet J^{\prime}_{b}\bullet\eta}{L_{x}\bullet J\bullet
L^{\prime}_{y}\bullet J^{\prime}\bullet\eta}=p(b)\,.$ (62)

Finally, for the case of definite relative timing ($A\rightarrow B$), the two-
time state $\eta$ obeys NBTS if

$\displaystyle p(a|x,y)$ $\displaystyle\equiv\frac{L_{x}\bullet J_{a}\bullet
L^{\prime}_{y}\bullet J^{\prime}\bullet\eta}{L_{x}\bullet J\bullet
L^{\prime}_{y}\bullet J^{\prime}\bullet\eta}=p(a)$ (63) $\displaystyle
p(b|x,y)$ $\displaystyle\equiv\frac{L_{x}\bullet J\bullet
L^{\prime}_{y}\bullet J^{\prime}_{b}\bullet\eta}{L_{x}\bullet J\bullet
L^{\prime}_{y}\bullet J^{\prime}\bullet\eta}=p(b|x)\,.$ (64)

###### Remark 1

Note that if $\eta$ is a state for two parties which obeys NBTS, then the
marginal state

$\eta\,^{\\!(A)}=L_{y}^{\prime}\bullet J^{\prime}\bullet\eta$ (65)

for a single party obeys NBTS for every $y$.

We now prove the first result, concerning single-party states which obey NBTS.

###### Theorem 1

States for a single party satisfying no-backwards-in-time-signalling
correspond to states without post-selection, or with trivial post-selection.
If the two-time state $\eta={\eta}^{A_{1}}_{A_{3}}$ for a single party obeys
no-backwards-in-time-signalling, then

$\eta^{A_{1}}_{A_{3}}=\rho^{A_{1}}\otimes\mathbb{I}_{A_{3}},$ (66)

where $\rho$ is a positive vector.

Proof - Any $\eta$ can be decomposed as

$\eta=\sum_{i,j}|i\rangle^{a_{1}}\otimes\langle
j|_{a_{1}^{\dagger}}\otimes(B_{ij})_{A_{3}}.$ (67)

Consider a measurement $J_{a}$ followed by a set of channels $L_{x}$, and two
outcomes $l$ and $k$. We now consider three particular choices of measurements

  1. (i)

$J_{a}$ corresponds to a measurement in the computational basis, followed by
the preparation of the $|0\rangle$ state:

$J_{a}=|0\rangle^{a_{2}}\otimes\langle
a|_{a_{1}}\otimes|a\rangle^{a_{1}^{\dagger}}\otimes\langle
0|_{a_{2}^{\dagger}}.$ (68)

$L_{x}$ corresponds to a unitary channel $U_{x}$ with $x$ labelling all
possible unitaries999or alternatively a sufficient set of $x$ such that
$U_{x}|0\rangle\\!\langle 0|U_{x}^{\dagger}$ form an operator basis,

$L_{x}=(U_{x})^{a_{3}}_{a_{2}}\otimes(U_{x}^{\dagger})^{a_{2}^{\dagger}}_{a_{3}^{\dagger}}.$
(69)

In this case

$\displaystyle L_{x}\bullet J_{a}\bullet\eta$ $\displaystyle=\sum_{i,j}\langle
a|i\rangle\,\langle j|a\rangle\,\langle
0|\hat{U}_{x}^{\dagger}\hat{B}_{ij}\hat{U}_{x}|0\rangle$
$\displaystyle=\langle
0|\hat{U}_{x}^{\dagger}\hat{B}_{aa}\hat{U}_{x}|0\rangle$ (70)

from (58) we therefore obtain

$\frac{\langle
0|\hat{U}_{x}^{\dagger}\hat{B}_{aa}\hat{U}_{x}|0\rangle}{\sum_{k}\langle
0|\hat{U}_{x}^{\dagger}\hat{B}_{kk}\hat{U}_{x}|0\rangle}=p(a)$ (71)

and hence, defining $B=\sum_{k}B_{kk}$,

$\langle
0|\hat{U}_{x}^{\dagger}(\hat{B}_{aa}-p(a)\hat{B})\hat{U}_{x}|0\rangle=0$ (72)

As this holds for all $\hat{U}_{x}$ we find

$B_{aa}=p(a)B.$ (73)

  2. (ii)

The second measurement we consider is similar to the first, but two of the
measurement outcomes correspond to the states
$|\pm\rangle=\frac{1}{\sqrt{2}}\left(|r\rangle\pm|s\rangle\right)$ for
arbitrary $r$ and $s$. The other measurement elements can be taken to be in
the computational basis.

$\displaystyle J_{\pm}$
$\displaystyle=|0\rangle^{a_{2}}\otimes\langle\pm|_{a_{1}}\otimes|\pm\rangle^{a_{1}^{\dagger}}\otimes\langle
0|_{a_{2}^{\dagger}},$ $\displaystyle J_{a\neq r,s}$
$\displaystyle=|0\rangle^{a_{2}}\otimes\langle
a|_{a_{1}}\otimes|a\rangle^{a_{1}^{\dagger}}\otimes\langle
0|_{a_{2}^{\dagger}}.$ (74)

$L_{x}$ is the same as in case 1. Proceeding as before we obtain

$\frac{1}{2}\left(B_{rr}+B_{rs}+B_{sr}+B_{ss}\right)=p(+)B.$ (75)

  3. (iii)

The third measurement we consider is the same as case (ii), but two of the
measurement outcomes correspond to $|\pm
i\rangle=\frac{1}{\sqrt{2}}\left(|r\rangle\pm i|s\rangle\right)$, with

$\displaystyle J_{\pm i}$ $\displaystyle=|0\rangle^{a_{2}}\otimes\langle\pm
i|_{a_{1}}\otimes|\pm i\rangle^{a_{1}^{\dagger}}\otimes\langle
0|_{a_{2}^{\dagger}},$ $\displaystyle J_{a\neq r,s}$
$\displaystyle=|0\rangle^{a_{2}}\otimes\langle
a|_{a_{1}}\otimes|a\rangle^{a_{1}^{\dagger}}\otimes\langle
0|_{a_{2}^{\dagger}}.$ (76)

$L_{x}$ is the same as in case 1. Proceeding as before we obtain

$\frac{1}{2}\left(B_{rr}+iB_{rs}-iB_{sr}+B_{ss}\right)=p(+i)B.$ (77)

Combining equations (73), (75) and (77) for all $a,r,s$ it is straightforward
to see that all $B_{ij}$ are proportional to $B$. Writing $B_{ij}=c_{ij}B$ it
follows from (67) that $\eta$ has the product form

$\eta=C^{A_{1}}\otimes B_{A_{3}}$ (78)

where

$C^{A_{1}}=\sum_{i,j}c_{ij}|i\rangle^{a_{1}}\otimes\langle
j|_{a_{1}^{\dagger}}.$ (79)

We now show that $B\propto I$. Consider performing the measurement given by

$J_{a}=\frac{1}{d_{a_{2}}}|a\rangle^{a_{2}}\otimes\langle
a|_{a_{2}^{\dagger}}\otimes\mathbb{I}_{A_{1}}.$ (80)

This measurement corresponds to throwing away the input state, outputting a
random number $a$ from 1 to $d_{A_{2}}$ and then outputting the pure state
$|a\rangle_{a_{2}}$. We then perform the channel $L_{x}$ as above. This gives

$L_{x}\bullet J_{a}\bullet\eta=\frac{1}{d_{A2}}\textrm{tr}(\hat{C})\langle
a|\hat{U}_{x}^{\dagger}\hat{B}\hat{U}_{x}|a\rangle$ (81)

and hence,

$p(a)=\frac{\textrm{tr}(\hat{C})\langle
a|\hat{U}_{x}^{\dagger}\hat{B}\hat{U}_{x}|a\rangle}{\textrm{tr}(\hat{C})\textrm{tr}(\hat{B})}.$
(82)

As this holds for all $U_{x}$ it follows that $B=\lambda\mathbb{I}$ for some
constant $\lambda$. Hence

$\eta^{A_{1}}_{A_{3}}=\rho^{A_{1}}\otimes\mathbb{I}_{A_{3}}$ (83)

as desired, where $\rho=\lambda C$. $\Box$

We now use this result to prove that for two parties, the two-time states
which obey NBTS are equivalent to the linear two time states (which were
previously shown to be equivalent to process matrices in Silva  _et al._
(2017)).

###### Theorem 2

For the case of indefinite relative timing, a two-party, two-time state obeys
NBTS if and only if it is proportional to (and thus physically equivalent to)
a linear two-time state. Given any two trace-preserving measurements
$(J_{a})^{A_{3}}_{A_{1}}$ and $(K_{b})^{B_{3}}_{B_{1}}$, with
$J=\sum_{a}J_{a}$, and $K=\sum_{b}K_{b}$, a two-time state
$\eta={\eta}^{{A_{1}B_{1}}}_{{A_{3}B_{3}}}$ is linear if

$p(a,b)=J_{a}\bullet K_{b}\bullet{\eta}$ (84)

Proof - We first show that any causal two-time state is proportional to a
linear two-time state. Consider a channel for each party corresponding to
doing nothing to the state. These are given by

$L_{0}={\mathbb{I}}_{a_{2}}^{a_{3}}\otimes\mathbb{I}_{a_{3}^{\dagger}}^{a_{2}^{\dagger}}\qquad
M_{0}={\mathbb{I}}_{b_{2}}^{b_{3}}\otimes{\mathbb{I}}_{b_{3}^{\dagger}}^{b_{2}^{\dagger}}.$
(85)

Relabelling the spaces on which the measurements act to get
$J_{a}^{\prime}=(J_{a})_{A_{1}}^{A_{2}}$ and
$K^{\prime}_{b}=(K_{b})^{B_{2}}_{B_{1}}$, we note that

$J\bullet K\bullet\eta=L_{0}\bullet J^{\prime}\bullet M_{0}\bullet
K^{\prime}\bullet\eta^{\prime}.$ (86)

If $\eta^{\prime}$ is a two-party causal state, it follows from Remark 1 and
Theorem 1 that the marginal state satisfies

$\eta\,^{\\!(A)}=M_{0}\bullet
K^{\prime}\bullet\eta=\rho^{A_{1}}\otimes\mathbb{I}_{A_{3}}$ (87)

and thus

$\displaystyle J\bullet K\bullet\eta$ $\displaystyle=L_{0}\bullet
J^{\prime}\bullet\left(\rho\otimes\mathbb{I}_{A_{3}}\right)$ (88)
$\displaystyle=J^{\prime}\bullet\mathbb{I}_{A_{2}}\bullet\rho$ (89)
$\displaystyle=\mathbb{I}_{A_{1}}\bullet\rho$ (90)

where we have used the fact that $J^{\prime}$ and $L_{0}$ are trace-preserving
channels. Hence $J\bullet K\bullet\eta$ is independent of $J$. Following the
same argument with the parties swapped shows that $J\bullet K\bullet\eta$ is
also independent of $K$ and is thus a constant $c$. Now the state
${\eta}_{{W}}=\eta/c$ satisfies $J\bullet K\bullet{\eta}_{{W}}$=1 and thus

$p(a,b)=J_{a}\bullet K_{b}\bullet{\eta}_{{W}}$ (91)

and hence ${\eta}_{{W}}$ is a linear two-time state. To prove the converse we
use the Theorem given in Silva  _et al._ (2017), which implies101010To obtain
the first expression, consider the first equation in (30) from Silva  _et al._
(2017). Then set $C=L_{x}$ and $\tilde{C}=L_{x^{\prime}}$, replace $K$ by
$M_{y}\bullet K$, and take $\bullet J_{a}$ on both sides. The second equation
can be obtained by a similar argument with the parties swapped. that for a
linear two-time state ${\eta}_{{W}}$

$\displaystyle L_{x}\bullet J_{a}\otimes M_{y}\bullet K\bullet{\eta}_{{W}}$
$\displaystyle=L_{x^{\prime}}\bullet J_{a}\otimes M_{y}\bullet
K\bullet{\eta}_{{W}}$ (92) $\displaystyle L_{x}\bullet J\otimes M_{y}\bullet
K_{b}\bullet{\eta}_{{W}}$ $\displaystyle=L_{x}\bullet J\otimes
M_{y^{\prime}}\bullet K_{b}\bullet{\eta}_{{W}}$ (93)

where $J_{a}$ corresponds to Alice’s measurement and $K_{b}$ to Bob’s
measurement, and $L_{x},M_{y},J=\sum_{a}J_{a}$ and $K=\sum_{b}K_{b}$
correspond to completely positive trace preserving maps. These are just a
representation of the NBTS conditions equivalent to

$\displaystyle\sum_{b}p(a,b|x,y)=\sum_{b}p(a,b|x^{\prime},y)$ (94)
$\displaystyle\sum_{a}p(a,b|x,y)=\sum_{a}p(a,b|x,y^{\prime}).$ (95)

$\Box$

Finally, the third equation of (30) in Silva  _et al._ (2017) implies that for
a linear two-time state

$(L_{x}-L_{x^{\prime}})\bullet J_{a}\bullet(M_{y}-M_{y}^{\prime})\bullet
K_{b}\bullet{\eta}_{{W}}=0$ (96)

which correspond to the equalities obeyed by the classical polytope (35)

$p(a,b|x,y)+p(a,b|x^{\prime},y^{\prime})=p(a,b|x,y^{\prime})+p(a,b|x^{\prime},y).$
(97)

Now, moving on to the case of definite relative timings, we prove the
following:

###### Theorem 3

A two-party, two-time state obeys the NBTS conditions with a fixed relative
time ordering where both experiments occur in parallel if and only if it is
proportional to (and thus physically equivalent to) a pre-selected only state.
If the two-time state $\eta={\eta}^{A_{1}B_{1}}_{A_{3}B_{3}}$ obeys no-
backwards-in-time-signalling in this setting, then

$\eta^{A_{1}B_{1}}_{A_{3}B_{3}}=\rho^{A_{1}B_{1}}\otimes\mathbb{I}_{A_{3}}\otimes\mathbb{I}_{B_{3}},$
(98)

where $\rho$ is a positive vector.

Proof - The NBTS conditions in this scenario, at the level of two-time states
are

$\displaystyle(L\bullet J_{a}\otimes M)\bullet\eta$
$\displaystyle=(L^{\prime}\bullet J_{a}\otimes M)\bullet\eta$ (99a)
$\displaystyle(L\bullet J_{a}\otimes M)\bullet\eta$ $\displaystyle=(L\bullet
J_{a}\otimes M^{\prime})\bullet\eta$ (99b) $\displaystyle(L\otimes M\bullet
K_{b})\bullet\eta$ $\displaystyle=(L\otimes M^{\prime}\bullet
K_{b})\bullet\eta$ (99c) $\displaystyle(L\otimes M\bullet K_{b})\bullet\eta$
$\displaystyle=(L^{\prime}\otimes M\bullet K_{b})\bullet\eta$ (99d)

where $J_{a}$ and $K_{b}$ are arbitrary trace-preserving measurements, and
$L$, $L^{\prime}$, $M$ and $M^{\prime}$ are arbitrary trace-preserving
channels.

Note first that $L\bullet J_{a}$ is an arbitrary positive vector.111111The
only requirement on $L\bullet J_{a}$ is that $L\bullet J_{a}\bullet\eta\geq 0$
for all $\eta$, which can be seen as a ‘positivity’ requirement. The only way
that (99b) can be true for an arbitrary positive vector $L\bullet J_{a}$ is if
it is true at the level of the two-time state itself121212In particular, it is
always possible to construct a basis of positive vectors, and the only way
this equation can hold true for a basis is if it holds true in general, i.e.
if

$M\bullet\eta=M^{\prime}\bullet\eta$ (100)

where we recall that $M=M^{B_{3}}_{B_{1}}$ and
$M^{\prime}=(M^{\prime})^{B_{3}}_{B_{1}}$.

Now, let us consider the specific choice

$\displaystyle M^{B_{3}}_{B_{1}}$ $\displaystyle=T^{B_{3}}_{B_{1}}$
$\displaystyle(M^{\prime})^{B_{3}}_{B_{1}}$
$\displaystyle=T^{B_{3}}_{B_{1}}+\epsilon(T^{B_{3}}_{B_{2}}-I^{B_{3}}_{B_{2}})\bullet
X^{B_{2}}_{B_{1}}$ (101)

where $T$ is the throw-away-and-replace channel defined as

$\displaystyle
T^{B_{3}}_{B_{1}}=\frac{1}{d_{b_{3}}}\mathbb{I}^{B_{3}}\bullet\mathbb{I}_{B_{1}}\,,$
(102)

$I$ is the identity channel; $X$ is an arbitrary vector131313this vector must
be ‘Hermitian’ in the sense that it produces real numbers when acting on valid
two-time states $\eta^{{B_{1}}}_{{B_{2}}}\bullet
X_{B_{1}}^{B_{2}}\;\in\mathbb{R}\,,\,\forall\eta^{{B_{1}}}_{{B_{2}}}\,.$ , and
$\epsilon>0$ is sufficiently small such that $M^{\prime}$ is a valid channel
(i.e. such that it is positive). For this pair of channels, (100) becomes

$T^{B_{3}}_{B_{2}}\bullet
X^{B_{2}}_{B_{1}}\bullet\eta=I^{B_{3}}_{B_{2}}\bullet
X^{B_{2}}_{B_{1}}\bullet\eta$ (103)

However, $X$ is an arbitrary vector, and just as before, the one way that this
can hold in all cases is if it holds at the level of the state, i.e.

$T^{B_{3}}_{B_{2}}\bullet\eta=I^{B_{3}}_{B_{2}}\bullet\eta$ (104)

That is, the only states that satisfy (99b) are those such that the throw-
away-and-replace channel applied on the post-selected state of Bob leaves the
state invariant.

A completely equivalent line of reasoning, starting from (99d) (i.e.
interchanging the role of Alice and Bob), leads directly to the symmetric
requirement

$T^{A_{3}}_{A_{2}}\bullet\eta=I^{A_{3}}_{A_{2}}\bullet\eta.$ (105)

Combining these two conditions, we finally arrive at

$(T^{A_{3}}_{A_{2}}\otimes
T^{B_{3}}_{B_{2}})\bullet\eta=(I^{A_{3}}_{A_{2}}\otimes
I^{B_{3}}_{B_{2}})\bullet\eta$ (106)

The state on the left-hand-side has the form
$\rho^{A_{1}B_{1}}\otimes\mathbb{I}_{A_{2}}\otimes\mathbb{I}_{B_{2}}$, while
on the right-hand-side we recognise that $(I^{A_{3}}_{A_{2}}\otimes
I^{B_{3}}_{B_{2}})\bullet\eta_{A_{3}B_{3}}^{A_{1}B_{1}}=\eta_{A_{2}B_{2}}^{A_{1}B_{1}}$,
and therefore we prove the claim that the only allowed states are those of the
form

$\eta^{A_{1}B_{1}}_{A_{3}B_{3}}=\rho^{A_{1}B_{1}}\otimes\mathbb{I}_{A_{3}}\otimes\mathbb{I}_{B_{3}}.$
(107)

$\Box$

This form implies that

$\displaystyle(L\bullet J_{a}$ $\displaystyle\otimes M\bullet
K_{b})\bullet\eta^{A_{1}B_{1}}_{A_{3}B_{3}}$ $\displaystyle=(L\bullet
J_{a}\otimes M\bullet
K_{b})\bullet\rho^{A_{1}B_{1}}\otimes\mathbb{I}_{A_{3}}\otimes\mathbb{I}_{B_{3}}$
$\displaystyle=(J_{a}\otimes
K_{b})\bullet\rho^{A_{1}B_{1}}\otimes\mathbb{I}_{A_{2}}\otimes\mathbb{I}_{B_{2}}$
(108)

where we used the fact that
$L^{A_{3}}_{A_{2}}\bullet\mathbb{I}_{A_{3}}=\mathbb{I}_{A_{2}}$ and
$M^{B_{3}}_{B_{2}}\bullet\mathbb{I}_{B_{3}}=\mathbb{I}_{B_{2}}$ for all $L$
and $M$. Thus, the probabilities are independent of the channels $L$ and $M$,
and hence

$p(a,b|x,y)=p(a,b|x^{\prime},y^{\prime})$ (109)

for all $a$, $b$, $x$, $y$, $x^{\prime}$, $y^{\prime}$, which are the
sufficient additional conditions satisfied by classical correlations.

Finally, for the case of definite timings but where Alice’s experiment is
performed before Bob’s, we can show the following:

###### Theorem 4

A two-party, two-time state obeys the NBTS conditions with a fixed relative
time ordering where both of Alice’s experiments occur before Bob’s if and only
if it is proportional to (and thus physically equivalent to) a state where
Bob’s post-selection is trivial. If the two-time state
$\eta={\eta}^{A_{1}B_{1}}_{A_{3}B_{3}}$ obeys no-backwards-in-time-signalling
in this setting, then

$\eta^{A_{1}B_{1}}_{A_{3}B_{3}}=\eta^{A_{1}B_{1}}_{A_{3}}\otimes\mathbb{I}_{B_{3}}\,.$
(110)

Proof - The NBTS conditions in this case are

$\displaystyle(L\bullet J_{a}\otimes M)\bullet\eta$
$\displaystyle=(L^{\prime}\bullet J_{a}\otimes M)\bullet\eta$ (111a)
$\displaystyle(L\bullet J_{a}\otimes M)\bullet\eta$ $\displaystyle=(L\bullet
J_{a}\otimes M^{\prime})\bullet\eta$ (111b) $\displaystyle(L\otimes M\bullet
K_{b})\bullet\eta$ $\displaystyle=(L\otimes M^{\prime}\bullet
K_{b})\bullet\eta$ (111c)

where $J_{a}$ is Alice’s measurement; $K_{b}$ Bob’s measurement, and
$L,L^{\prime},M,M^{\prime}$ are completely positive trace preserving maps. The
proof follows immediately from the previous proof. In particular, by the same
logic as previously it is still the case that

$T^{B_{3}}_{B_{2}}\bullet\eta=I^{B_{3}}_{B_{2}}\bullet\eta$ (112)

from which the claim follows. Furthermore, it must be the case that
$\eta^{A_{1}B_{1}}_{A_{3}}$ is constrained such that the full state
$\eta^{A_{1}B_{1}}_{A_{3}B_{3}}$ is a linear two-time state. As shown in Silva
_et al._ (2017), the four necessary and sufficient conditions for a two-time
state to be a process matrix are also necessary and sufficient conditions for
a two-time state to be linear. These are:

$\displaystyle\left({\mathbb{I}}_{{A_{1}}}\\!\otimes{\mathbb{I}}^{{A_{3}}}\\!\otimes{\mathbb{I}}_{{B_{1}}}\\!\otimes{\mathbb{I}}^{{B_{3}}}\\!\right)\bullet\eta$
$\displaystyle=d_{A_{3}}d_{B_{3}},$ (113a)
$\displaystyle({I}^{{A_{3}}}_{{A_{2}}}\otimes{T}^{{B_{3}}}_{{B_{1}}})\bullet\eta$
$\displaystyle=({T}^{{A_{3}}}_{{A_{2}}}\otimes{T}^{{B_{3}}}_{{B_{1}}})\bullet\eta,$
(113b)
$\displaystyle({T}^{{A_{3}}}_{{A_{1}}}\otimes{I}^{{B_{3}}}_{{B_{2}}})\bullet\eta$
$\displaystyle=({T}^{{A_{3}}}_{{A_{1}}}\otimes{T}^{{B_{3}}}_{{B_{2}}})\bullet\eta,$
(113c)
$\displaystyle({I}^{{A_{3}}}_{{A_{2}}}\otimes{I}^{{B_{3}}}_{{B_{2}}})\bullet\eta$
$\displaystyle=({I}^{{A_{3}}}_{{A_{2}}}\otimes{T}^{{B_{3}}}_{{B_{2}}})\bullet\eta$
$\displaystyle+({T}^{{A_{3}}}_{{A_{2}}}$
$\displaystyle\otimes{I}^{{B_{3}}}_{{B_{2}}})\bullet\eta-({T}^{{A_{3}}}_{{A_{2}}}\otimes{T}^{{B_{3}}}_{{B_{2}}})\bullet\eta\,,$
(113d)

of which Eqns. (113a), (113c) and (113d) are trivially satisfied by a state of
the form $\eta^{A_{1}B_{1}}_{A_{3}}\otimes\mathbb{I}_{B_{3}}$ (using
$T^{B_{3}}_{B_{X}}\bullet\mathbb{I}_{B_{3}}=\mathbb{I}_{B_{X}}$). Eq. (113b)
is satisfied with the additional constraint that Alice cannot locally signal
backwards in time, i.e. Eq. (112). Together this implies that
$\eta^{A_{1}B_{1}}_{A_{3}B_{3}}$ is linear. $\Box$

Once again, from this form it directly follows that

$\displaystyle(L\bullet J_{a}$ $\displaystyle\otimes M\bullet
K_{b})\bullet\eta^{A_{1}B_{1}}_{A_{3}B_{3}}$ $\displaystyle=(L\bullet
J_{a}\otimes M\bullet
K_{b})\bullet\eta^{A_{1}B_{1}}_{A_{3}}\otimes\mathbb{I}_{B_{3}}$
$\displaystyle=(L\bullet J_{a}\otimes
K_{b})\bullet\eta^{A_{1}B_{1}}_{A_{3}}\otimes\mathbb{I}_{B_{2}}$ (114)

which is independent of $M$. Therefore, we have

$p(a,b|x,y)=p(a,b|x,y^{\prime})$ (115)

for all $a$, $b$, $x$, $y$, $y^{\prime}$. Again, these are sufficient
conditions (on top of NBTS) that guarantee that a correlation is classical.
Hence the set of two-time states cannot generate non-classical correlations.