---
abstract: 'Bell non-local correlations cannot be naturally explained in a fixed causal structure.  This serves as a motivation for considering models where no global assumption is made beyond logical consistency.  The assumption of a fixed causal order between a set of parties, together with free randomness, implies device-independent inequalities — just as the assumption of locality does.  It is known that local validity of quantum theory is consistent with violating such inequalities.  Moreover, for three parties or more, even the (stronger) assumption of local [*classical*]{} probability theory plus logical consistency allows for violating causal inequalities.  Here, we show that a classical environment (with which the parties interact), possibly containing loops, is logically consistent if and only if whatever the involved parties do, there is exactly one fixed-point, the latter being representable as a mixture of deterministic fixed-points.  We further show that the non-causal view allows for a model of computation strictly more powerful than computation in a world of fixed causal orders.' 
address:
- '$^1$ Faculty of Informatics, Universitá della Svizzera italiana, Via G. Buffi 13, 6900 Lugano, Switzerland'
- '$^2$ Facoltà indipendente di Gandria, Lunga scala, 6978 Gandria, Switzerland'
author:
- 'Ämin Baumeler$^{1,2}$ and Stefan Wolf$^{1,2}$'
bibliography:
- 'refs.bib'
---

Introduction
============

Device-independent tests of assumptions depend [*only*]{} on some input-output behaviour, whereas the “internals” of the concrete physical systems, as well as the used devices are ignored.  Examples of such assumptions are free randomness, the impossibility of superluminal signaling, or predefined causal structures [@Bell; @Scarani:2002br; @Colbeck:2012ie; @Wood:2015jf].  A combination of basic assumptions leads to inequalities composed of probabilities to observe certain outcomes.  Whenever a theory or an experiment [*violates*]{} a device-independent inequality, we can apply the contrapositive, and thus are forced to [*drop*]{} at least one of the assumptions made.  One of the most prominent findings of this line of reasoning is Bell-nonlocality [@Bell:1964ws], which is not only of fundamental interest but also leads to a series of device-independent protocols in cryptography [@Mayers:1998; @Barrett:2005ej; @Colbeck:2006vo; @Pironio:2010bu; @Colbeck:gb; @Scarani:2012vq; @Vazirani:2014hu]. 

Historical background on space, time, and causality
---------------------------------------------------

The debate about as how fundamental space and time are to be seen has a long history in within natural philosophy.  In pre-Socratic time, the opposite standpoints on the question have arisen in the views of [*Parmenides*]{} as opposed to [*Heraclitus*]{}: For the latter, the stage set by a fundamental space-time structure is where the play of permanent change | for him synonymous to existence | happens.  Parmenides’ world view, on the other hand, is static and such that space and, in particular, time emerge only subsequently and only subjectively.  The described opposition can be seen as a predecessor of the famous debate between [*Newton*]{} and [*Leibniz*]{} [@Leibniz:2000tq], centuries later.  Whereas Newton starts from an initially given and static space-time, Leibniz was criticizing that view: Space, for instance, is for him merely [*relational and not absolute*]{}.  The course of occidental science decided to go for Newton’s (overly successful) picture, until Leibniz’ relational view was finally adopted by [*Mach*]{}.  Indeed, Mach’s principle states that [*inertial forces are purely relational*]{}, and it was the crystallization point of [*Einstein*]{}’s general relativity although the latter did, in the end, not satisfy the principle; however, it does propose a [*dynamic*]{} space-time structure (still absolute, though) in which, additionally, space and time become closely intertwined where they have been seen independently in Newton’s picture. 

The absolute space-time resulting in general relativity has been challenged by the following observations.  First, [*Gödel*]{} [@Godel:1949eb] showed the possibility of solutions to the general-relativistic field equations corresponding to closed space-time curves.  Second, [*Bell*]{}’s non-local correlations [@Bell:1964ws] do not seem to be well explainable according to [*Reichenbach’s principle*]{} [@Reichenbach:1956vl], stating that any correlation between two space-time events in a causal structure must be due to a common cause or a direct influence from one event to the other.  These facts can serve as a motivation to drop the causal structure as being fundamental in the first place.  That idea, as sketched here, is not as novel as it may seem to be.  In 1913, Russell [@Russell:2006vn] wrote that “the law of causality \[…\] is a relic of a bygone age, surviving, like the monarchy, only because it is erroneously supposed to do no harm.”  In the view adopted here, the causal space-time structure arises only [*together with instead of prior to*]{} the pieces of classical information coming to existence, [*e.g.*]{}, in the context of a quantum-measurement process[^1].  A consequence of taking that standpoint is that the definition by Colbeck and Renner [@Colbeck:2011hw] of freeness of randomness in terms of causal structure can be turned around: May the [*free random bit*]{} be the fundamental concept from which the usual space-time causal structure emerges? 

Results
-------

This article studies [*causal inequalities*]{} that are derived from the two basic assumptions of [*free randomness*]{} and [*predefined causal structures*]{}, and their violations.  The inequalities are obeyed by input-output behaviours between multiple parties that are [*consistent*]{} with a predefined causal structure.  Any violation of such inequalities forces us to drop at least one of the two assumptions.  Indeed, in Section \[sec:causality\] we define causal order [*based*]{} on free randomness; in that perspective at least, a fundamental causal structure [*seems unnecessary*]{}.  In theory, if one drops the assumption of a global time and adheres to [*logical consistency only*]{}, such inequalities can be violated — quantumly (see Section \[sec:quantum\]) as well as classically (see Section \[sec:classical\]).  Thus, we are lead to the statement: [*The assumption of a predefined causal structure is not a logical necessity*]{}. 

In Section \[sec:fixedpoint\] we show a relation between logical consistency and the [*uniqueness of fixed-points*]{} in functions.  By pushing this line of research further, we obtain a new class of circuits that are logically consistent, yet where the gates can be connected arbitrarily (see Section \[sec:circuit\]).  Such circuits describe a new model of computational that is strictly more powerful than the standard circuit model.  We conclude the work with a list of open questions. 

Related work
------------

Hardy [@Hardy:2005wj; @Hardy:2007bk] challenged the notion of a global time in quantum theory.  His main motivation is to reconcile quantum theory with general relativity.  While indeterminism, a feature of the former theory, is absent in the latter, the latter theory is more general compared to the former as its space-time is dynamic.  Thus, a theory that is probabilistic and has a dynamic space-time is a reasonable candidate for quantum gravity.  Chiribella, D’Ariano, and Perinotti [@Chiribella:2009bh] and Chiribella, D’Ariano, Perinotti, and Valiron [@Chiribella:2013bk] introduced the notion of “quantum combs,” which are higher-order transformations, [*e.g.*]{} transformations from operations to operations.  An interesting feature of these “quantum combs” is that they allow for superpositions of causal orders [@Chiribella:2012jg].  Such superpositions have lead to a computational advantage in certain tasks [@Chiribella:2012jg; @Colnaghi:2012dv; @Araujo:2014kf; @Feix:2015ww].  In general, “quantum combs” can also describe resources beyond superpositions of causal orders.  Another framework to study such resources was introduced by Oreshkov, Costa, and Brukner [@Oreshkov:2012uh] (see also [@Brukner:2014if]). 

Definitions of causal relations and orders {#sec:causality}
==========================================

We describe causal relations between random variables, and in a next step, between parties.  Since we are interested in theories where causal structures are not fundamental, we distinguish between [*input*]{} and [*output*]{} random variables such that a structure emerges from these notions. 

An [*input*]{} random variable carries a hat, [*e.g.*]{}, $\hat A$.  The distribution over input random variables does not need to be specified.  An [*output*]{} random variable is denoted by a single letter, [*e.g.*]{}, $X$. Output random variables come with a distribution that is conditioned on the inputs, [*e.g.*]{}, $P_{X|\hat A}$.

This difference allows us to define [*causal future*]{} and [*causal past*]{} for random variables. 

\[def:causality\] Let $\hat A$ be an input and $X$ be an output random variable.  If and only if $\hat A$ is correlated with $X$, [*i.e.*]{}, $\exists P_{\hat A}:\,P_{\hat A}P_X\not=P_{\hat A}P_{X|\hat A}$, then $\hat A$ is said to be [*in the causal past of $X$*]{} and, equivalently $X$ is said to be [*in the causal future of $\hat A$*]{}.  Furthermore, $\hat A$ is called the [*cause*]{} and $X$ is called the [*effect*]{}.  This relation is denoted by $\hat A\preceq X$.

Such a definition follows the [*interventionists’*]{} approach to causality, [*e.g.,*]{} as defined by Woodward.  The intuition behind this definition is that we are allowed to manipulate only certain physical systems.  If such a manipulation influences another physical system, then the former manipulation [*causes*]{} the latter (see Figure \[fig:causality\]). 

\(S) ; (St) [$X$]{}; (M) ; (M.east) arc (70:110:1.18); (M.south)++(0cm,0.05cm) – ++(0.3cm,0.2cm); (T) ; (Tt) [$\hat A$]{}; (K) ; (K2) at (K) ; in [ -13+0\*30, -13+1\*30, -13+2\*30, -13+3\*30, -13+4\*30, -13+5\*30, -13+6\*30, -13+7\*30, -13+8\*30, -13+9\*30, -13+10\*30, -13+11\*30, -13+12\*30 ]{} [ (K.center)++(:0.05cm) – +(:0.15cm); ]{} (T.west) – (S.east);

This allows us to derive the causal structure from observed correlations — the causal structure [*emerges*]{} from the correlations.  Note that this definition does not allow an input to be an effect, and does not allow an output to be a cause.  For further studies, we define [*parties*]{} and causal relations on parties. 

A [*party*]{} $S=(\hat A,X,\mathcal{E})$ with $\mathcal{E}:\hat A\times I_S\rightarrow X\times O_S$, consists of an input random variable $\hat A$, an output random variable $X$, and a map $\mathcal{E}$ that maps $\hat A$ together with a physical system that $S$ receives from the environment to $X$ and a physical system that is returned to the environment (see Figure \[fig:party\]). 

\(S) [$\mathcal{E}$]{}; (S.150) – ++(-0.2,0) node \[left\] [$X$]{}; (S.210) – ++(-0.2,0) node \[left\] [$\hat A$]{}; (S.90) – ++(0,0.5) node \[above\] [$O_S$]{}; (S.270) – ++(0,-0.5) node \[below\] [$I_S$]{};

A party interacts at most once with the environment, where we consider one reception and one transmission of a system as a single interaction. 

Now, we can define causal relations between parties. 

Let $R=(\hat A,X,\mathcal{E})$ and let  be two parties.  We say $R$ is in the [*causal past*]{} of $S$ or $S$ is in the [*causal future*]{} of $R$ if and only if $\hat A$ is correlated with $Y$ and $\hat B$ is uncorrelated with $X$. This relation is denoted by $R\preceq S$.

Predefined vs. indefinite causal order
--------------------------------------

In this work we distinguish between [*predefined*]{} and [*indefinite*]{} causal orders.  In particular, we will show that if one defines causality [*based on the inputs and outputs*]{} (see Definition \[def:causality\]), then correlations that are not compatible with a predefined causal order could arise. 

\[def:2partypredefined\] Let $R=(\hat A,X,\mathcal{E})$ and $S=(\hat B,Y,\mathcal{F})$ be two parties.  A conditional probability distribution $P_{X,Y|\hat A,\hat B}$ is called [*consistent with two-party predefined causal order*]{} if and only if the conditional probability distribution can be written as a convex combination of the orderings  and , [*i.e.*]{}, $$\begin{aligned}
        P_{X,Y|\hat A,\hat B}=pP_{X|\hat A}P_{Y|\hat A,\hat B,X} + (1-p)P_{X|\hat A,\hat B,Y}P_{Y|\hat B}
        \nonumber
        \,,
    \end{aligned}$$ for some $0\leq p\leq 1$. The first term in the sum represents $R\preceq S$ and the second term represents $S\preceq R$.

This definition determines a polytope of probability distributions $P_{X,Y|\hat A,\hat B}$ that are compatible with two-party predefined causal order.  All facets for binary random variables were recently enumerated [@araujo14b]. 

For three parties or more, a distribution that is compatible with a predefined causal order can be more general than a distribution that can be written as a convex combination of all orderings.  The reason for this is that a party in the causal past of some other parties could in principle influence everything which lies in its causal future — therefore, it could also influence the [*causal order*]{} of the parties in its causal future. 

\[def:predefined\] Consider the three parties $R=(\hat A,X,\mathcal{E})$, $S=(\hat B,Y,\mathcal{F})$, and $T=(\hat C,Z,\mathcal{G})$. A conditional probability distribution $P_{X,Y,Z|\hat A,\hat B,\hat C}$ is called [*consistent with predefined causal order*]{} if and only if the probability distribution can be written as a convex combination of all orderings where one party $Q$ is in the causal past of the other two, and where the causal order of these two parties is determined by $Q$.

A generalized version of Definition \[def:predefined\] to any number of parties can be found in [@Oreshkov:2015vs]. 

[**[@Baumeler:2015wx]**]{} [(Necessary condition for predefined causal order)]{} \[lemma:necessarycondition\] A [*necessary*]{} condition for predefined causal order is that [*at least one party is not in the causal future of any party*]{}. 

If a conditional distribution is [*incompatible*]{} with predefined causal order, then we call it [*indefinite*]{}. 

Let $R=(\hat A,X,\mathcal{E})$ and $S=(\hat B,Y,\mathcal{F})$ be two parties.  The probability distribution over binary random variables $$P_{X,Y|\hat A,\hat B}(x,y,a,b)=\cases{
            1/2&for $x=b\wedge y=0$\\
            1/2&for $x=b\wedge y=1$\\
            0&otherwise
        }$$ is [*compatible*]{} with predefined causal order, because it can be written as $$\begin{aligned}
        P_{X,Y|\hat A,\hat B}&=P_{X|\hat A,\hat B,Y}P_{Y|\hat B}
        \,,
    \end{aligned}$$ with $$P_{X|\hat A,\hat B,Y}(x,a,b,y)=\cases{
            1&for~$x=b$\\
            0&otherwise,}$$ and $$P_{Y|\hat B}(y,b)=1/2
        \,.$$

Let $R=(\hat A,X,\mathcal{E})$ and $S=(\hat B,Y,\mathcal{F})$ be two parties.  The probability distribution over binary random variables $$P_{X,Y|\hat A,\hat B}(x,y,a,b)=\cases{
            1&for $x=b\wedge y=a$\\
            0&otherwise
        }$$ is [*incompatible*]{} with predefined causal order (has an [*indefinite*]{} causal order), because it [*cannot*]{} be written as described in Definition \[def:2partypredefined\]. 

Assuming quantum theory locally {#sec:quantum}
===============================

In 2012, Oreshkov, Costa, and Brukner [@Oreshkov:2012uh] introduced the process-matrix framework for quantum correlations without predefined causal order.  In that framework, a party $R=(\hat A,X,\mathcal{E}:\hat A\times I_R\rightarrow X\times O_R)$ receives a quantum state on the Hilbert space $I_R$ from the environment and returns a quantum state on the Hilbert space $O_R$ to the environment.  The map $\mathcal{E}$ is completely positive, because we assume the validity of quantum theory within the laboratories of every party.  Let[^2] $\bm{\mathcal{E}}_{x,a}$ be the corresponding Choi-Jamio[ł]{}kowski [@Jamioikowski:1972ke; @Choi:1975el] map which is an element in $I_R\otimes O_R$, where $a$ is the input value and $x$ is the output value.  Let $S=(\hat B,Y,\mathcal{F}:\hat B\times I_S\rightarrow Y\times O_S)$ be another party with Choi-Jamio[ł]{}kowski map $\bm{\mathcal{F}}_{y,b}$. The most general probability distribution $P_{X,Y|\hat A,\hat B}$ that is linear in the local operations is $$\begin{aligned}
    P_{X,Y|\hat A,\hat B}(x,y,a,b)=\mathrm{Tr}\left((\bm{\mathcal{E}}_{x,a}\otimes \bm{\mathcal{F}}_{y,b})W\right)
    \,,\end{aligned}$$ where $W$ is a matrix living in the Hilbert space $I_R\otimes O_R\otimes I_S\otimes O_S$. The matrix $W$ is called [*process matrix*]{}. 

Since $P_{X,Y|\hat A,\hat B}$ is designed to be a probability distribution, and since both parties can arbitrarily choose their local operations $\mathcal{E}$ and $\mathcal{F}$, the following two conditions must be satisfied: $$\begin{aligned}
    \forall \mathcal{E},\mathcal{F},x,y,a,b:&\,P_{X,Y|\hat A,\hat B}(x,y,a,b)\geq 0\,,\label{eq:nonneg}\\
    \forall \mathcal{E},\mathcal{F},a,b:&\,\sum_{x,y}P_{X,Y|\hat A,\hat B}(x,y,a,b)=1\,.\label{eq:totprob}\end{aligned}$$

We call a process matrix $W$ [*logically consistent*]{} if and only if $W$ satisfies the conditions (\[eq:nonneg\]) and (\[eq:totprob\]). 

Condition (\[eq:nonneg\]) implies that $W$ must be a completely positive trace-preserving map from $O_R\otimes O_S$ to $I_R\otimes I_S$. Therefore, we can interpret $W$ as a quantum channel (see Figure \[fig:W\]). 

\(R) [$\mathcal{E}$]{}; (R.150) – ++(-0.2,0) node \[left\] [$X$]{}; (R.210) – ++(-0.2,0) node \[left\] [$\hat A$]{}; (W) [$W$]{}; (S) [$\mathcal{F}$]{}; (S.30) – ++(0.2,0) node \[right\] [$Y$]{}; (S.330) – ++(0.2,0) node \[right\] [$\hat B$]{}; (R) to\[out=80,in=100\] (W); (R) to\[out=280,in=260\] (W); (S) to\[out=100,in=80\] (W); (S) to\[out=260,in=280\] (W); (SO) at (\[shift=[(-0.3cm,0.8cm)]{}\]R) [$O_R$]{}; (SI) at (\[shift=[(-0.3cm,-0.8cm)]{}\]R) [$I_R$]{}; (TO) at (\[shift=[(0.3cm,0.8cm)]{}\]S) [$O_S$]{}; (TI) at (\[shift=[(0.3cm,-0.8cm)]{}\]S) [$I_S$]{};

If we assumed a global causal structure (what we do not), then $W$ would be a [*back-in-time*]{} channel.  Rather, it can be interpreted as the [*environment which lies outside space-time*]{} — the causal structure is designed by $W$ and emerges from the correlations, as will become clear later.  First, we can understand $W$ as a generalized notion of a state and a channel: Whereas it describes a [*quantum state*]{} in Example \[ex:state\], it models a [*quantum channel*]{} in Example \[ex:channel\]. 

\[ex:state\] This logically consistent process matrix $$\begin{aligned}
        W_\mathrm{state}=\rho_{I_S,I_R}\otimes\mathds{1}_{O_S,O_R}
    \end{aligned}$$ describes the [*quantum state*]{} $\rho$ that is sent to both parties. 

\[ex:channel\] This logically consistent process matrix $$\begin{aligned}
        W_\mathrm{channel}=\mathds{1}_{I_R}\otimes|\Psi\rangle\langle\Psi|_{O_R,I_S}\otimes\mathds{1}_{O_S}
        \,,
    \end{aligned}$$ with $|\Psi\rangle=(|0,0\rangle+|1,1\rangle)/\sqrt{2}$, describes a [*qubit channel*]{} from party $R$ to party $S$.

Besides quantum states and quantum channels, a logically consistent process matrix can also describe [*superpositions of quantum channels*]{}.  For instance, we could have a channel from $R$ to $S$ to $T$ superposed with a channel from $S$ to $R$ to $T$, where $T=(\hat C,Z,\mathcal{G}:\hat C\times I_T\times I_{T'}\rightarrow Z)$ is a party which [*does not*]{} return a system to the environment, and receives two systems from the environment (the target on $I_T$ and the control on $I_{T'}$) (see Example \[ex:superposition\]). 

\[ex:superposition\] This logically consistent process matrix $$\begin{aligned}
        W_\mathrm{superposedchannel}=|w\rangle\langle w|\,,
    \end{aligned}$$ with $$\begin{aligned}
        |w\rangle = \frac{
        |0,\Psi,\Psi,0\rangle_{I_R,O_R,I_S,O_S,I_T,I_{T'}}
        +
        |0,\Psi,\Psi,1\rangle_{I_S,O_S,I_R,O_R,I_T,I_{T'}}
    }{\sqrt 2}
    \end{aligned}$$ describes a superposition of a channel from $R$ to $S$ to $T$ and a channel from $S$ to $R$ to $T$.

The process matrix from Example \[ex:superposition\] can be used to solve certain tasks more efficiently.  Suppose you are given two black boxes $\mathrm{B}$ and $\mathrm{C}$ that act on qubits, and you are guaranteed that $\mathrm{B}$ and $\mathrm{C}$ either [*commute*]{} or [*anti-commute*]{}.  In the standard circuit model, you would need to query each box twice in order to determine the (anti)commutativity.  Whereas by using the process matrix $W_\mathrm{superposedchannel}$, a single query suffices [@Chiribella:2012jg; @Colnaghi:2012dv; @Araujo:2014kf; @Araujo:2015ky; @Procopio:2015iw]. 

Non-causal process matrices
---------------------------

Whilst the above examples of process matrices are [*compatible with predefined causal order*]{}, some logically consistent process matrices lead to correlations that cannot be obtained in a world with a predefined causal ordering of the parties — such process matrices are called [*non-causal*]{}. 

A process matrix $W$ is called [*causal*]{} if and only if for any choice of operations of the parties the resulting probability distribution [*is compatible with predefined causal order*]{} (according to Definition \[def:predefined\]).  Otherwise, it is called [*non-causal*]{}. 

To show that a process matrix is non-causal, we define a game, give an upper bound on the winning probability for this game under the assumption of a predefined causal order, and show that this bound can be violated in the process-matrix framework. 

[**[@Oreshkov:2012uh]**]{} [(Two-party non-causal game)]{} \[game:2party\] Let $R=(\hat A,X,\mathcal{E})$ and $S=((\hat B,\hat B'),Y,\mathcal{F})$ be two parties that aim at maximizing $$\begin{aligned}
        p_\mathrm{succ}=\frac{1}{2}\left(\Pr\left(X=\hat B\,|\,b'=0\right)+\Pr\left(Y=\hat A\,|\,b'=1\right)\right)
        \,,
    \end{aligned}$$ where all random variables are binary and where all inputs are uniformly distributed.  Informally, if $b'=0$, then party $S$ is asked to send her input to $R$, otherwise, party $R$ is asked to send her input to $S$.

We give an upper bound on the success probability of Game \[game:2party\] under the assumption of a predefined causal order. 

[**[@Oreshkov:2012uh]**]{} [(Upper bound on success probability of Game \[game:2party\])]{} \[thm:2party\] Under the assumption of a predefined causal order, Game \[game:2party\] can at best be won with probability $3/4$.

By Lemma \[lemma:necessarycondition\], at least one party is not in the causal future of any party.  Without loss of generality, let $R$ be this party.  Then, $R$ can only make a random guess, which means $\Pr(X=\hat B\,|\,b'=0)=1/2$. Therefore, we obtain the upper bound $$\begin{aligned}
        p_\mathrm{succ}=\frac{1}{2}\left(\frac{1}{2}+\Pr\left(Y=\hat A\,|\,b'=1\right)\right)\leq\frac{3}{4}
        \,. 
    \end{aligned}$$

Then again, this upper bound given by Theorem \[thm:2party\] can be violated in the process-matrix framework. 

[**[@Oreshkov:2012uh]**]{} \[thm:2partyviolation\] Game \[game:2party\] can be won with probability $(2+\sqrt 2)/4$ if we drop the assumption of a global causal order. 

The logically consistent process matrix $$\begin{aligned}
    W=\frac{1}{4}\left( \mathds{1}+\frac{\mathds{1}_{I_R}(\sigma_z)_{O_R}(\sigma_z)_{I_S}\mathds{1}_{O_S}
    +(\sigma_z)_{I_R}\mathds{1}_{O_R}(\sigma_x)_{I_S}(\sigma_z)_{O_S} }{\sqrt 2} \right)
    \,,\end{aligned}$$ where we omit the $\otimes$ symbols for better presentation, and the local operations $$\begin{aligned}
    \bm{\mathcal{E}}_{x,a}& = &\frac{1}{4}\left( \mathds{1}+(-1)^x\sigma_z \right)_{I_R}\otimes\left( \mathds{1}+(-1)^a\sigma_z \right)_{O_R}\,,\\
    \bm{\mathcal{F}}_{y,b,b'=0}& = &\frac{1}{4}\left( \mathds{1}+(-1)^y\sigma_x \right)_{I_S}\otimes\left( \mathds{1}+(-1)^{b+y}\sigma_z \right)_{O_S}\,,\\
    \bm{\mathcal{F}}_{y,b,b'=1}& = &\frac{1}{2}\left( \mathds{1}+(-1)^z\sigma_x \right)_{I_S}\otimes\rho_{O_S}\,,\end{aligned}$$ for an arbitrary $\rho$, can be used to violate the bound given by Theorem \[thm:2party\] up to $(2+\sqrt 2)/4$ [@Oreshkov:2012uh].  Brukner [@Brukner:2014vo] proved under certain assumptions that within the process-matrix framework, this violation cannot be exceeded. 

This raised the question whether [*non-causal*]{} logically consistent process matrices in the classical realm also exist — which was answered negatively in the two-party case [@Oreshkov:2012uh; @Costa:2013vc].  However, for three parties or more, this is not true anymore; this is shown in Section \[sec:classical\]. 

Logically consistent process matrices can be understood as a new resource for quantum operations.  Oddly enough, these resources cannot be composed: If we take two logically consistent process matrices $W_1$ and $W_2$, where the former is a quantum channel from $R$ to $S$ and the latter is a quantum channel from $S$ to $R$, then $W_1\otimes W_2$ is [*not*]{} logically consistent; $R$ could in principle alter the state on $I_R$ she receives from the environment, leading to a causal paradox.  The impossibility of composing process matrices within the model reflects the fact that a process matrix is supposed to describe the environment as a [*whole*]{}. 

Assuming classical probability theory locally {#sec:classical}
=============================================

The [*classical*]{} analogue of the process-matrix framework was recently developed [@Baumeler:2015wx], and has been found to give rise to non-causal correlations for three parties or more.  It is the classical analogue in the sense that, instead of assuming the validity of quantum theory locally, classical probability theory is assumed to hold locally.  Let  be a party.  Here, the spaces $I_R$ and $O_R$ are not Hilbert spaces (as in the process-matrix framework), but describe random variables.  Therefore, the local operation $\mathcal{E}$ of a party is a conditional probability distribution $P_{X,O_R|\hat A,I_R}$; locally we assume the validity of probability theory as opposed to quantum theory.  Let $S=(\hat B,Y,\mathcal{F})$ with $\mathcal{F}:\hat B\times I_S\rightarrow Y\times O_S$ and $T=(\hat C,Z,\mathcal{G})$ with $\mathcal{G}:\hat C\times I_T\rightarrow Z\times O_T$ be two further parties.  The most general probability distribution $P_{X,Y,Z,I_R,I_S,I_T,O_R,O_S,O_T|\hat A,\hat B,\hat C}$ that is linear in the local operations is $$\begin{aligned}
    \mathcal{E}(x,o_R,a,i_R)
    \mathcal{F}(y,o_S,b,i_S)
    \mathcal{G}(z,o_T,c,i_T)
    E(i_R,i_S,i_T,o_R,o_S,o_T)
    \label{eq:classical}
    \,,\end{aligned}$$ where $E$ is called [*classical process*]{}.  Since all three parties can arbitrarily choose their local operations $\mathcal{E}$, $\mathcal{F}$, and $\mathcal{G}$, the following conditions must be satisfied (we use $\bm i$ as shorthand expression for $(i_R,i_S,i_T)$, likewise for $\bm o$, $\bm I$, and $\bm O$): $$\begin{aligned}
    \forall\mathcal{E},\mathcal{F},\mathcal{G},x,y,z,\bm i,\bm o,a,b,c:\,P_{X,Y,Z,\bm I,\bm O|\hat A,\hat B\hat C}(x,y,z,\bm i,\bm o,a,b,c)\geq 0\,,\label{eq:clnonneg}\\
    \forall\mathcal{E},\mathcal{F},\mathcal{G},a,b,c:\,\sum_{x,y,z,\bm i,\bm o}P_{X,Y,Z,\bm I,\bm O|\hat A,\hat B\hat C}(x,y,z,\bm i,\bm o,a,b,c)=1\,.\label{eq:cltotprob}\end{aligned}$$

We call a classical process $E$ [*logically consistent*]{} if and only if $E$ satisfies the conditions (\[eq:clnonneg\]) and (\[eq:cltotprob\]). 

Condition (\[eq:clnonneg\]) implies that the classical process $E$ is a conditional probability distribution $P_{I_R,I_S,I_T|O_R,O_S,O_T}$. Therefore, $E$ can be interpreted in the same way as process matrices: it maps the systems $O_R$, $O_S$, and $O_T$ to $I_R$, $I_S$, and $I_T$ (see Figure \[fig:E\]). 

\(R) [$\mathcal{E}$]{}; (R.150) – ++(-0.2,0) node \[left\] [$X$]{}; (R.210) – ++(-0.2,0) node \[left\] [$\hat A$]{}; (S) [$\mathcal{F}$]{}; (S.150) – ++(-0.2,0) node \[left\] [$Y$]{}; (S.210) – ++(-0.2,0) node \[left\] [$\hat B$]{}; (T) [$\mathcal{G}$]{}; (T.150) – ++(-0.2,0) node \[left\] [$Z$]{}; (T.210) – ++(-0.2,0) node \[left\] [$\hat C$]{}; (E) [$E$]{}; (R) to\[out=80,in=90\] (E); (R) to\[out=280,in=270\] (E); (S) to\[out=80,in=100\] (E); (S) to\[out=280,in=260\] (E); (T) to\[out=80,in=110\] (E); (T) to\[out=280,in=250\] (E); (RO) at (\[shift=[(-0.3cm,0.8cm)]{}\]R) [$O_R$]{}; (RI) at (\[shift=[(-0.3cm,-0.8cm)]{}\]R) [$I_R$]{}; (SO) at (\[shift=[(-0.3cm,0.8cm)]{}\]S) [$O_S$]{}; (SI) at (\[shift=[(-0.3cm,-0.8cm)]{}\]S) [$I_S$]{}; (TO) at (\[shift=[(-0.3cm,0.8cm)]{}\]T) [$O_T$]{}; (TI) at (\[shift=[(-0.3cm,-0.8cm)]{}\]T) [$I_T$]{};

We rewrite the conditions (\[eq:clnonneg\]) and (\[eq:cltotprob\]) by using stochastic matrices.  This helps to check whether a classical process is logically consistent or not.  We write $\bm{E}$ to denote the stochastic matrix that models the classical process $E$. Then, the non-negativity condition (\[eq:clnonneg\]) becomes $$\begin{aligned}
    \forall m,n:\,\bm{E}_{m,n}\geq 0
    \label{eq:mnonneg}
    \,,\end{aligned}$$ where $\bm{E}_{m,n}$ are the matrix elements.  For simplicity, we fix all inputs $(\hat A,\hat B,\hat C)$ to $(a,b,c)$ and consider the operations  only, and likewise for the other parties.  Let $\bm{\mathcal{E'}}$ be the corresponding stochastic matrix.  The probability that the operation $\mathcal{E'}$ produces $o_R$ conditioned on $i_R$ is $$\begin{aligned}
    P_{O_R|I_R}(o_R,i_R)=\bm{o_R}^T \bm{\mathcal{E'}}\bm{i_R}
    \,,\end{aligned}$$ where $\bm{o_R}$ is the stochastic vector\[p:sv\] that models $o_R$, [*e.g.*]{}, for a binary random variable $O_R$ the value $o_R=0$ is modeled by $$\begin{aligned}
    \bm{o_R}=
    \left(
    \begin{array}{c}
        1\\0
    \end{array}
    \right)
    \,.\end{aligned}$$ Having this, we rewrite condition (\[eq:cltotprob\]) as $$\begin{aligned}
    \forall \mathcal{E},\mathcal{F},\mathcal{G}:\,&\sum_{\bm i,\bm o}&
    \left(\bm{i_R}\otimes \bm{i_S}\otimes \bm{i_T}\right)^T
    \bm{E}
    \left(\bm{o_R}\otimes \bm{o_S}\otimes \bm{o_T}\right)\\
    &\times&\left(\bm{o_R}^T \bm{\mathcal{E'}} \bm{i_R}\right)
    \left(\bm{o_S}^T \bm{\mathcal{F'}} \bm{i_S}\right)
    \left(\bm{o_T}^T \bm{\mathcal{G'}} \bm{i_T}\right)
    \\
    &=&\mathrm{Tr}\left( \bm{E}\left(\bm{\mathcal{E'}}\otimes \bm{\mathcal{F'}}\otimes \bm{\mathcal{G'}}\right) \right)\\
    &=&1
    \,.\end{aligned}$$ Indeed, since any local operation $\mathcal{E'}$ can be written as a convex combination of deterministic operations, the total-probability condition $$\begin{aligned}
    \forall \mathcal{E'},\mathcal{F'},\mathcal{G'}\in\mathcal{D}:\,\mathrm{Tr}\left( \bm{E}\left(\bm{\mathcal{E'}}\otimes \bm{\mathcal{F'}}\otimes \bm{\mathcal{G'}}\right) \right)=1
    \label{eq:trcond}
    \,,\end{aligned}$$ where $\mathcal{D}$ is the set of all [*deterministic*]{} local operations, is sufficient. 

Non-causal classical processes
------------------------------

In analogy to the process-matrix framework, we can define [*non-causal*]{} classical processes. 

A classical process $E$ is called [*non-causal*]{} if and only if there exists a choice of operations of the parties such that the resulting probability distribution does [*not*]{} satisfy the necessary condition for predefined causal order (see Lemma \[lemma:necessarycondition\]). 

It is known that for two parties, non-causal logically consistent classical processes do not exist .  For three parties or more, however, such processes [*do*]{} exist [@Baumeler:2014cw; @Baumeler:2015wx].  We describe two non-causal logically consistent classical processes. 

[**[@Baumeler:2014cw]**]{} [(Three-party non-causal)]{} \[game:3party\] Let $R=((\hat A,\hat M),X,\mathcal{E})$, $S=((\hat B,\hat M),Y,\mathcal{F})$, and $T=((\hat C,\hat M),Z,\mathcal{G})$ be three parties that aim at maximizing $$\begin{aligned}
        p_\mathrm{succ2}&=&
        \frac{1}{3}\left(
            \Pr\left(X=\hat B\oplus \hat C\,|\,m=0\right)\right.\\
            &+&\left.\Pr\left(Y=\hat A\oplus \hat C\,|\,m=1\right)+
            \Pr\left(Z=\hat A\oplus \hat B\,|\,m=2\right)\right)
            \,,
    \end{aligned}$$ where all random variables but $\hat M$ are binary, and where $\hat M$ is a [*shared*]{} ternary random variable.  All input random variables are uniformly distributed.  Informally, if the shared random variable $\hat M$ takes value $0$, then party $R$ has to guess the parity of the inputs of $S$ and $T$, and likewise for the alternative values the random variable $\hat M$ can take. 

We give an upper bound on the success probability of Game \[game:3party\] under the assumption of a predefined causal order. 

[**[@Baumeler:2014cw]**]{} \[thm:3party\] In a predefined causal order, Game \[game:3party\] can at best be won with probability $5/6$.

A necessary condition for predefined causal order is that at least one party is not in the causal future of any party (see Lemma \[lemma:necessarycondition\]).  Without loss of generality, let $R$ be this party.  Whenever the shared trit $\hat M$ takes the value $0$, party $R$ can give a random guess only.  Therefore, $\Pr(X=\hat B\oplus \hat C\,|\,m=0)=1/2$. This gives the upper bound $$\begin{aligned}
        p_\mathrm{succ2}&=\frac{1}{3}\left( \frac{1}{2}+\Pr\left(Y=\hat A\oplus \hat C\,|\,m=1\right)+\Pr\left(Z=\hat A\oplus \hat B\,|\,m=2\right) \right)\\
        &\leq \frac{5}{6}
        \,. 
    \end{aligned}$$

[**[@Baumeler:2014cw]**]{} \[thm:3partyperfect\] Game \[game:3party\] can be won perfectly if we drop the assumption of a global causal order. 

Consider the logically consistent classical process $E$ $$\begin{aligned}
    P_{\bm I|\bm O}(\bm i,\bm o)=\cases{
        1/2&for $i_R=o_T\wedge i_S=o_R\wedge i_T=o_S$\\
        1/2&for $i_R=o_T\oplus 1\wedge i_S=o_R\oplus 1\wedge i_T=o_S\oplus 1$\\
        0&otherwise. 
    }\end{aligned}$$ This process is the uniform mixture of the identity channel from $R$ to $S$ to $T$ to $R$ and the bit-flip channel from $R$ to $S$ to $T$ to $R$ (see Figure \[fig:stopro\]). 

(-,0)++(90-:) arc (90-:-30+:); (-,0)++(-30-:) arc (-30-:-150+:); (-,0)++(-150-:) arc (-150-:-270+:); (-,0)++(90:) node (A) [$R$]{}; (-,0)++(-30:) node (B) [$S$]{}; (-,0)++(-150:) node (C) [$T$]{};

(,0)++(90-:) arc (90-:-30+:); (,0)++(-30-:) arc (-30-:-150+:); (,0)++(-150-:) arc (-150-:-270+:); (,0)++(90:) node (A2) [$R$]{}; (,0)++(-30:) node (B2) [$S$]{}; (,0)++(-150:) node (C2) [$T$]{}; (,0)++(90-60:+.3) node (n1) [$\oplus 1$]{}; (,0)++(-30-60:+.3) node (n2) [$\oplus 1$]{}; (,0)++(-150-60:+.3) node (n3) [$\oplus 1$]{};

(-/2,0) node (PLUS) [$+$]{}; (---,0) node (half1) [$\frac{1}{2}$]{}; (--,0) node (half2) [$\frac{1}{2}$]{};

By combining it with the local operations $$\begin{aligned}
    \mathcal{E}(x,o_R,a,m,i_R)=\cases{
        1&for $m=0\wedge x=i_R\wedge o_R=0$\\
        1&for $m=1\wedge x=0\wedge o_R=i_R\oplus a$\\
        1&for $m=2\wedge x=0\wedge o_R=a$\\
        0&otherwise,
    }\\
    \mathcal{F}(y,o_S,b,m,i_S)=\cases{
        1&for $m=0\wedge y=0\wedge o_S=b$\\
        1&for $m=1\wedge y=i_S\wedge o_S=0$\\
        1&for $m=2\wedge y=0\wedge o_S=i_S\oplus b$\\
        0&otherwise,
    }\\
    \mathcal{G}(z,o_T,c,m,i_T)=\cases{
        1&for $m=0\wedge z=0\wedge o_T=i_T\oplus c$\\
        1&for $m=1\wedge z=0\wedge o_T=c$\\
        1&for $m=2\wedge z=i_T\wedge o_T=0$\\
        0&otherwise,
    }\end{aligned}$$ Game \[game:3party\] is won perfectly.  The operations can be understood as follows.  The party who has to make the guess simply uses the system that she receives from the environment as guess.  If the party who has to produce a guess is the next in the chain ($R$ to $S$ to $T$ to $R$) from the point of view of the actual party, then the actual party returns the parity of the system she obtained from the environment and her input.  In the third case, if the party who has to guess is two steps ahead in the chain, then the actual party returns her input to the environment. 

[**[@Baumeler:2015wx]**]{} [(Three-party non-causal game)]{} \[game:3partydet\] Let $R=(\hat A,X,\mathcal{E})$, $S=(\hat B,Y,\mathcal{F})$, and $T=(\hat C,Z,\mathcal{G})$ be three parties that aim at maximizing $$\begin{aligned}
        p_\mathrm{succ3}&=&
        \frac{1}{2}\left(
            \Pr\left(X=\hat C,Y=\hat A,Z=\hat B\,|\,\mathrm{maj}(\hat A,\hat B,\hat C)=0\right)\right.\\
            &+&\left.\Pr\left(X=\hat B\oplus 1,Y=\hat C\oplus 1,Z=\hat A\oplus 1\,|\,\mathrm{maj}(\hat A,\hat B,\hat C)=1\right)\right)
            \,,
    \end{aligned}$$ where all random variables are binary, and where $\mathrm{maj}(a,b,c)$ is the majority of $(a,b,c)$. All inputs are uniformly distributed.  In words, if the majority of the inputs is $0$, then the parties have to guess their neighbour’s input in one direction.  Otherwise, if the majority of the inputs is $1$, then the parties have to guess their neighbour’s inverted input in the opposite direction. 

We give an upper bound on the success probability of Game \[game:3partydet\] under the assumption of a predefined causal order. 

[**[@Baumeler:2015wx]**]{} \[thm:3partydet\] Under the assumption of a predefined causal order, Game \[game:3partydet\] can at best be won with probability $3/4$.

The truth table of Game \[game:3partydet\] is given in Table \[tab:3partydet\]. 

   $\hat A$   $\hat B$   $\hat C$   $\mathrm{maj}(\hat A,\hat B,\hat C)$   $X$   $Y$   $Z$
  ---------- ---------- ---------- -------------------------------------- ----- ----- -----
      0          0          0                        0                      0     0     0
      0          0          1                        0                      1     0     0
      0          1          0                        0                      0     0     1
      0          1          1                        1                      0     0     1
      1          0          0                        0                      0     1     0
      1          0          1                        1                      1     0     0
      1          1          0                        1                      0     1     0
      1          1          1                        1                      0     0     0

  : Conditions for winning Game \[game:3partydet\].[]{data-label="tab:3partydet"}

A necessary condition for predefined causal order is that at least one party is not in the causal future of any other party (see Lemma \[lemma:necessarycondition\]).  Without loss of generality, let $R$ be this party.  Therefore, party $R$ has to output $X$ without learning any other random variable than $\hat A$.  By inspecting Table \[tab:3partydet\], we see that $X=0$ is $R$’s best guess.  Thus, in at least 2 out of the 8 cases, the game is lost, resulting in $p_\mathrm{succ3}\leq 3/4$.

[**[@Baumeler:2015wx]**]{} \[thm:3partydetperfect\] By using the logically consistent classical process framework, Game \[game:3partydet\] can be won perfectly. 

The logically consistent classical process $E$ to perfectly win Game \[game:3partydet\] is $$\begin{aligned}
    P_{\bm I|\bm O}(\bm i,\bm o)=\cases{
        1&for $\mathrm{maj}(\bm o)=0\wedge i_R=o_T\wedge i_S=o_R\wedge i_T=o_S$\\
        1&for $\mathrm{maj}(\bm o)=1\wedge i_R=o_S\oplus 1\wedge i_S=o_T\oplus 1$\\
        &$\quad\wedge i_T=o_R\oplus 1$\\
        0&otherwise. 
    }\end{aligned}$$ The local operations are $$\begin{aligned}
    \mathcal{E}(x,o_R,a,i_R)=\cases{
        1&for $x=i_R\wedge o_R=a$\\
        0&otherwise,
    }\\
    \mathcal{F}(y,o_S,b,i_S)=\cases{
        1&for $y=i_S\wedge o_S=b$\\
        0&otherwise,
    }\\
    \mathcal{G}(z,o_T,c,i_T)=\cases{
        1&for $z=i_T\wedge o_T=c$\\
        0&otherwise. 
    }\end{aligned}$$ A graphical representation of the classical process is given in Figure \[fig:detpro\]. 

(-,0)++(90-:) arc (90-:-30+:); (-,0)++(-30-:) arc (-30-:-150+:); (-,0)++(-150-:) arc (-150-:-270+:); (-,0)++(90:) node (A) [$R$]{}; (-,0)++(-30:) node (B) [$S$]{}; (-,0)++(-150:) node (C) [$T$]{};

(,0)++(90-:) arc (90-:-30+:); (,0)++(-30-:) arc (-30-:-150+:); (,0)++(-150-:) arc (-150-:-270+:); (,0)++(90:) node (A2) [$R$]{}; (,0)++(-30:) node (B2) [$S$]{}; (,0)++(-150:) node (C2) [$T$]{}; (,0)++(90-60:+.3) node (n1) [$\oplus 1$]{}; (,0)++(-30-60:+.3) node (n2) [$\oplus 1$]{}; (,0)++(-150-60:+.3) node (n3) [$\oplus 1$]{};

(---,+0.5) node (half1) [$\mathrm{maj}(O_R,O_S,O_T)=0$]{}; (--,+0.5) node (half2) [$\mathrm{maj}(O_R,O_S,O_T)=1$]{};

Geometric representation
------------------------

The set of logically consistent classical processes forms a polytope [@Baumeler:2015wx], which is defined by the linear conditions (\[eq:mnonneg\]) and (\[eq:trcond\]).  Both classical processes used to perfectly win Games \[game:3party\] and \[game:3partydet\] are [*extremal points*]{} of the mentioned polytope.  In contrast to the process of Game \[game:3partydet\], the classical process of Game \[game:3party\] is a [*mixture*]{} of [*logically inconsistent*]{} processes.  Such a classical process must be [*fine-tuned*]{}: Tiny variations of the probabilities make the classical process [*logically inconsistent*]{}.  This motivates the definition of a smaller polytope, where [*all*]{} extremal points represent [*deterministic*]{} classical processes.  This smaller polytope is called [*deterministic-extrema polytope*]{}.  Qualitative representations of both polytopes are given in Figure \[fig:polytopes\]. 

(30:) – (150:) – (270:) – (30:); (30:) – (90:) – (150:) – (210:) – (270:) – (330:) – (30:); (30:) node\[draw,solid,circle,label=[-4:causal deterministic\
extremal point]{}\] (DC) – (60:) node\[draw,solid,circle,label=[0:proper-mixture extremal point\
(fine-tuned)]{}\] (PC) – (90:) node\[draw,solid,circle,label=[3:non-causal deterministic extremal point]{}\] (DNC) – (120:) – (150:) – (180:) – (210:) – (240:) – (270:) – (300:) – (330:) – (0:) – (30:);

Characterizing logical consistency with fixed-points {#sec:fixedpoint}
====================================================

The above considerations on classical processes allow us to characterize logically consistent classical process via functions with [*unique*]{} fixed-points.  For that purpose, we redefine party $R=(\mathcal{A},\mathcal{X},\bm{f})$ with $\bm{f}:\mathcal{A}\times\mathcal{I}_R\rightarrow\mathcal{X}\times\mathcal{O}_R$ where $\mathcal{A}$, $\mathcal{X}$, $\mathcal{I}_R$, and $\mathcal{O}_R$ are sets.  Similarly, we redefine $S=(\mathcal{B},\mathcal{X},\bm{g})$ with $\bm{g}:\mathcal{B}\times\mathcal{I}_S\rightarrow\mathcal{Y}\times\mathcal{O}_S$ and $T=(\mathcal{C},\mathcal{Z},\bm{h})$ with $\bm{h}:\mathcal{C}\times\mathcal{I}_T\rightarrow\mathcal{Z}\times\mathcal{O}_T$. Further, let $f:\mathcal{I}_R\rightarrow\mathcal{O}_R$, $g:\mathcal{I}_S\rightarrow\mathcal{O}_S$, and $h:\mathcal{I}_T\rightarrow\mathcal{O}_T$ be functions. 

\[thm:fp\] A function $\bm{e}:\mathcal{O}_R\times\mathcal{O}_S\times\mathcal{O}_T\rightarrow\mathcal{I}_R\times\mathcal{I}_S\times\mathcal{I}_T$ represents an extremal point of the deterministic-extrema polytope if and only if $$\begin{aligned}
        \forall f,g,h,\exists ! ( k,\ell,m):\,(k,\ell,m)=\bm{e}(f(k),g(\ell),h(m))
        \,,
    \end{aligned}$$ where $\exists ! $ is the uniqueness quantifier. 

Recall the total-probability condition (\[eq:trcond\]) that we express using stochastic matrices $$\begin{aligned}
        \forall \mathcal{E'},\mathcal{F'},\mathcal{G'}\in\mathcal{D}:\,\mathrm{Tr}
        \left( \bm{E}\left(\bm{\mathcal{E'}}\otimes \bm{\mathcal{F'}}\otimes \bm{\mathcal{G'}}\right) \right)=1
        \,,
    \end{aligned}$$ where $\mathcal{D}$ is the set of all [*deterministic*]{} local operations.  By definition, a classical process $E$ that is an extremal point of the deterministic-extrema polytope is deterministic.  This implies that the matrix $$\begin{aligned}
        \bm{M}=\bm{E}\left(\bm{\mathcal{E'}}\otimes \bm{\mathcal{F'}}\otimes \bm{\mathcal{G'}}\right)
        \,,
    \end{aligned}$$ for some $\mathcal{E'},\mathcal{F'},\mathcal{G'}\in\mathcal{D}$, is a stochastic matrix with trivial probabilities.  The diagonal $\bm q$ of $\bm M$ consists of $0$’s and exactly one $1$. In particular, by applying the stochastic matrix $\bm M$ to $\bm q$ results in $\bm q$, [*i.e.*]{}, $\bm{M}\bm{q}=\bm{q}$, which means that $\bm q$ is a unique fixed-point of $\bm M$.

Theorem \[thm:fp\] implies that deterministic causal and non-causal classical processes can be expressed as functions with one and only one fixed-point if the former is composed with arbitrary deterministic local operations.  Such a function for a causal classical process is given in Example \[ex:fpcausal\] and for a non-causal classical process in Example \[ex:fpnoncausal\]. 

\[ex:fpcausal\] Let the sets $\mathcal{A}$, $\mathcal{X}$, $\mathcal{I}_R$, and $\mathcal{O}_R$, and likewise for the other two parties, be $\{0,1\}$. Consider the causal classical process $E$ with an identity channel from party $R$ to $S$ and an identity channel from party $S$ to $T$, and where $R$ receives the element $0$ from the environment.  We express $E$ as a function $\bm e:\mathcal O_R\times\mathcal O_S\times\mathcal O_T\rightarrow\mathcal I_R\times\mathcal I_S\times\mathcal I_T$: $$\begin{aligned}
        \bm e:(o,p,q)\mapsto(0,o,p)
        \,. 
    \end{aligned}$$ Since the sets $\mathcal O_R$ and $\mathcal I_R$, and likewise for the other parties, are binary, the local operation of a party is one out of four functions: $$\begin{aligned}
        d_\mathrm{id}&:&i\mapsto i\,,\\
        d_\mathrm{not}&:&i\mapsto i\oplus 1\,,\\
        d_0&:&i\mapsto 0\,,\\
        d_1&:&i\mapsto 1\,. 
    \end{aligned}$$ For any choice $f,g,h$ of the local operations, the function $$\begin{aligned}
        \bm e\circ(f,g,h):\mathcal I_R\times\mathcal I_S\times\mathcal I_T\rightarrow\mathcal I_R\times\mathcal I_S\times\mathcal I_R
    \end{aligned}$$ has a unique fixed-point.  We discuss a few cases.  First, let $f=g=h=d_\mathrm{id}$. Then, the fixed-point is $(0,0,0)$, as can be verified by Table \[tab:ex1\], which describes the composed function $\bm e\circ(d_\mathrm{id},d_\mathrm{id},d_\mathrm{id})$.

   $\mathcal I_R$   $\mathcal I_S$   $\mathcal I_T$   $\mathcal I_R$   $\mathcal I_S$   $\mathcal I_T$
  ---------------- ---------------- ---------------- ---------------- ---------------- ----------------
         0                0                0                0                0                0
         0                0                1                0                0                0
         0                1                0                0                0                1
         0                1                1                0                0                1
         1                0                0                0                1                0
         1                0                1                0                1                0
         1                1                0                0                1                1
         1                1                1                0                1                1

  : Classical process from Example \[ex:fpcausal\] as a function composed with the identity as local operations of all three parties.[]{data-label="tab:ex1"}

In the case $f=g=d_\mathrm{id}$ and $h=d_\mathrm{not}$, the fixed-point is $(0,0,0)$ as well.  In the case $f=g=h=d_\mathrm{not}$, the fixed-point is $(0,1,0)$. A final case we express explicitly is $f=g=h=d_1$; the fixed-point is $(0,1,1)$.

\[ex:fpnoncausal\] We use the same parties as they are described in Example \[ex:fpcausal\].  Take the logically consistent classical process that can be used to win Game \[game:3partydet\].  A graphical representation of this classical process is given in Figure \[fig:detpro\].  We rewrite the process as a function $\bm e:\mathcal O_R\times\mathcal O_S\times\mathcal O_T\rightarrow\mathcal I_R\times\mathcal I_S\times\mathcal I_T$: $$\begin{aligned}
        \bm e:(o,p,q)\mapsto((p\oplus 1)q,o(q\oplus 1),(o\oplus 1)p)
        \,. 
    \end{aligned}$$ If the parties use the identity as local operations, then $\bm e\circ(d_\mathrm{id},d_\mathrm{id},d_\mathrm{id})$ has a unique fixed-point $(0,0,0)$, as can be verified by inspecting Table \[tab:ex2\]. 

   $\mathcal I_R$   $\mathcal I_S$   $\mathcal I_T$   $\mathcal I_R$   $\mathcal I_S$   $\mathcal I_T$
  ---------------- ---------------- ---------------- ---------------- ---------------- ----------------
         0                0                0                0                0                0
         0                0                1                1                0                0
         0                1                0                0                0                1
         0                1                1                0                0                1
         1                0                0                0                1                0
         1                0                1                1                0                0
         1                1                0                0                1                0
         1                1                1                0                0                0

  : Classical process from Example \[ex:fpnoncausal\] as a function composed with the identity as local operations of all three parties.[]{data-label="tab:ex2"}

For the local operations , the unique fixed-point is $(0,0,0)$ as well.  In another case, if the local operations are $f=g=d_\mathrm{id}$ and $h=d_\mathrm{not}$, then the unique fixed-point is $(1,0,0)$.

We present a statement similar to Theorem \[thm:fp\], yet for any logically consistent classical process (probabilistic or deterministic). 

\[thm:fpp\] A conditional probability distribution $E=P_{I_R,I_S,I_T|O_R,O_S,O_T}$ is a logically consistent classical process if and only if one of the decomposition $E=\sum_i p_i D_i$, where $\forall i:D_i$ is a deterministic distribution, has the property $$\begin{aligned}
        \forall f,g,h:\,\sum_i p_i\left|\{(k,\ell,m)\,|\,(k,\ell,m)=\bm d_i(f(k),g(\ell),h(m))\}\right|=1
        \,,
    \end{aligned}$$ where $\bm d_i:\mathcal O_R\times\mathcal O_S\times\mathcal O_T\rightarrow\mathcal I_R\times\mathcal I_S\times\mathcal I_T$ is a function modelling $D_i$.

The classical process $\bm E$ can be decomposed as $$\begin{aligned}
        \bm E=\sum_i p_i\bm D_i
        \,,
    \end{aligned}$$ where $\forall i:\,D_i$ is a [*deterministic*]{} distribution.  The total-probability condition (\[eq:trcond\]), that we express using stochastic matrices, is $$\begin{aligned}
        \forall \mathcal{E'},\mathcal{F'},\mathcal{G'}\in\mathcal{D}:&\,&
        \mathrm{Tr}\left( \bm{E}\left(\bm{\mathcal{E'}}\otimes \bm{\mathcal{F'}}\otimes \bm{\mathcal{G'}}\right) \right)\\
        &=&\mathrm{Tr}\left( \sum_ip_i\bm D_i\left( \bm{\mathcal{E'}}\otimes\bm{\mathcal{F'}}\otimes\bm{\mathcal{G'}} \right) \right)\\
        &=&\sum_ip_i\mathrm{Tr}\left( \bm D_i\left( \bm{\mathcal{E'}}\otimes\bm{\mathcal{F'}}\otimes\bm{\mathcal{G'}} \right) \right)\\
        &=&\sum_ip_i\sum_{\bm j}\bm j^T\bm D_i\left( \bm{\mathcal{E'}}\otimes\bm{\mathcal{F'}}\otimes\bm{\mathcal{G'}} \right)\bm j\\
        &=&1
        \,,
    \end{aligned}$$ where $\mathcal{D}$ is the set of all [*deterministic*]{} local operations, and where $\bm j$ is a stochastic vector with all $0$’s and exactly one $1$. The expression $$\begin{aligned}
        n_i:=\sum_{\bm j}\bm j^T\bm D_i\left( \bm{\mathcal{E'}}\otimes\bm{\mathcal{F'}}\otimes\bm{\mathcal{G'}} \right)\bm j
    \end{aligned}$$ is thus the number of fixed-points of the stochastic matrix $\bm D_i\left( \bm{\mathcal{E'}}\otimes\bm{\mathcal{F'}}\otimes\bm{\mathcal{G'}} \right)$. From this we get $\sum_i p_in_i=1$.

The informal statement of Theorem \[thm:fpp\] is: The average number of fixed-points of a logically consistent classical process is one.  Clearly, the classical processes of Examples \[ex:fpcausal\] and \[ex:fpnoncausal\] can be rewritten as a convex combination of deterministic processes fulfilling this property.  However, there are classical processes which lie [*outside*]{} the deterministic-extrema polytope — Theorem \[thm:fp\] does not apply to those — to which we can apply Theorem \[thm:fpp\].  Theorems \[thm:fp\] and \[thm:fpp\] can naturally be extend to more than three parties. 

\[ex:finetuned\] The classical process used to win Game \[game:3party\] is $$\begin{aligned}
        P_{\bm I|\bm O}(\bm i,\bm o)=\cases{
            1/2&for $i_R=o_T\wedge i_S=o_R\wedge i_T=o_S$\\
            1/2&for $i_R=o_T\oplus 1\wedge i_S=o_R\oplus 1\wedge i_T=o_S\oplus 1$\\
            0&otherwise. 
        }
    \end{aligned}$$ A graphical representation of this classical process is given in Figure \[fig:stopro\].  The classical process can be written as a convex combination $E=(E_0+E_1)/2$ with $$\begin{aligned}
        E_0(i_R,i_S,i_T,o_R,o_S,o_T)&=&(i_R=o_T\wedge i_S=o_R\wedge i_T=o_S)\,,\\
        E_1(i_R,i_S,i_T,o_R,o_S,o_T)&=&(i_R=o_T\oplus 1\wedge i_S=o_R\oplus 1\wedge i_T=o_S\oplus 1)\,. 
    \end{aligned}$$ Now, we switch to the parties as defined in Example \[ex:fpcausal\] and rewrite $E_0$ and $E_1$ as functions $\bm e_0:\mathcal O_R\times\mathcal O_S\times\mathcal O_T\rightarrow\mathcal I_R\times\mathcal I_S\times\mathcal I_T$ and $\bm e_1:\mathcal O_R\times\mathcal O_S\times\mathcal O_T\rightarrow\mathcal I_R\times\mathcal I_S\times\mathcal I_T$: $$\begin{aligned}
        \bm e_0:(o,p,q)\rightarrow (q,o,p)\,,\\
        \bm e_1:(o,p,q)\rightarrow (q\oplus 1,o\oplus 1,p\oplus 1)\,. 
    \end{aligned}$$ For the choice $f=g=h=d_\mathrm{id}$ of local operations, the function $\bm e_0\circ(d_\mathrm{id},d_\mathrm{id},d_\mathrm{id})$ has two fixed-points, and the function $\bm e_1\circ(d_\mathrm{id},d_\mathrm{id},d_\mathrm{id})$ has no fixed-points (see Table \[tab:ex3\]). 

   $\mathcal I_R$   $\mathcal I_S$   $\mathcal I_T$   $\mathcal I_R$   $\mathcal I_S$   $\mathcal I_T$
  ---------------- ---------------- ---------------- ---------------- ---------------- ----------------
         0                0                0                0                0                0
         0                0                1                1                0                0
         0                1                0                0                0                1
         0                1                1                1                0                1
         1                0                0                0                1                0
         1                0                1                1                1                0
         1                1                0                0                1                1
         1                1                1                1                1                1

  : The pair of functions that yield the classical process from Example \[ex:finetuned\] when mixed, as functions composed with the identity as local operations.  The left table describes the function $\bm e_0\circ(d_\mathrm{id},d_\mathrm{id},d_\mathrm{id})$, and the right table describes the function $\bm e_1\circ(d_\mathrm{id},d_\mathrm{id},d_\mathrm{id})$.[]{data-label="tab:ex3"}

   $\mathcal I_R$   $\mathcal I_S$   $\mathcal I_T$   $\mathcal I_R$   $\mathcal I_S$   $\mathcal I_T$
  ---------------- ---------------- ---------------- ---------------- ---------------- ----------------
         0                0                0                1                1                1
         0                0                1                0                1                1
         0                1                0                1                1                0
         0                1                1                0                1                0
         1                0                0                1                0                1
         1                0                1                0                0                1
         1                1                0                1                0                0
         1                1                1                0                0                0

  : The pair of functions that yield the classical process from Example \[ex:finetuned\] when mixed, as functions composed with the identity as local operations.  The left table describes the function $\bm e_0\circ(d_\mathrm{id},d_\mathrm{id},d_\mathrm{id})$, and the right table describes the function $\bm e_1\circ(d_\mathrm{id},d_\mathrm{id},d_\mathrm{id})$.[]{data-label="tab:ex3"}

Thus, the average number of fixed-points is $(2+0)/2=1$. An alternative choice of local operations is $f=g=d_\mathrm{id}$ and $h=d_\mathrm{not}$. Then $\bm e_0\circ(d_\mathrm{id},d_\mathrm{id},d_\mathrm{not})$ has $0$, and $\bm e_1\circ(d_\mathrm{id},d_\mathrm{id},d_\mathrm{not})$ has $2$ fixed-points: $(0,1,0)$ and $(1,0,1)$. As a last choice, consider $f=g=h=d_0$, in which both composed functions have $1$ fixed-point: $(0,0,0)$ for the former function, and $(1,1,1)$ for the latter function. 

A non-causal model for computation {#sec:circuit}
==================================

Above we took the [*operational approach*]{}, where we think in terms of parties that can choose to perform arbitrary experiments within their laboratories.  A model for computation can be designed if we depart from this point of view and rather think in terms of [*circuits*]{}.  We briefly sketch such a model [@inprep2].  In the logical-consistency conditions of the process-matrix framework and its classical analogue, we consider [*any local operation*]{} of the parties.  In a circuit, however, there are no parties.  Thus, the logical-consistency condition has to be adopted.  Let $\mathcal{C}$ be a classical circuit that consists of wires and gates. 

A classical circuit $\mathcal{C}$ is called [*logically consistent*]{} if and only if there exists a probability distribution over all values on the wires where the probabilities are linear in the choice of the inputs. 

This definition allows gates to be connected in a circular way — which is not allowed in the standard circuit model.  The wires which are connected to a gate on [*one*]{} side only are either the inputs or the outputs of the circuit.  Intuitively, if a closed circuit (when ignoring the open wires) admits a unique fixed-point, then it is logically consistent.  The wires, in that case, carry the value of the fixed-point.  This non-causal model for computation is more powerful than the standard circuit model.  As a demonstration, consider the following task. 

\[task:fp\] Suppose you are given a black-box $\mathrm{B}$ with the [*promise*]{} that $\mathrm{B}$ has [*exactly one*]{} fixed-point.  The task is to find the fixed-point with as few queries to $\mathrm{B}$ as possible. 

In the worst case, the minimal number of queries to $\mathrm{B}$ in the standard circuit model is $n-1$, where $n$ is the input size. 

By using this new model of computation, a single query to black box $\mathrm{B}$ suffices to solve Task \[task:fp\]. 

To solve the task, we use the logically consistent non-causal circuit given by Figure \[fig:circuit\] with $a=0$.

\(B) [$\mathrm{B}$]{}; (B.east) – ++(0.6,0) node\[midway,above\] [$b$]{} – ++(1.4,0) to\[out=0,in=0\] ++(0,-2) – ++(-3.5,0) node\[midway,above\] [$y$]{} to\[out=180,in=180\] ++(0,2) – (B.west); (B.center)++(0,1) – ++(-1,0) node\[left\] [$a$]{}; (B.center)++(0,1) – ++(1,0) node (O) [$\oplus$]{} – ++(1,0) node\[right\] [$x$]{}; (O.center) – (O|-B); (O|-B) circle \[radius=2pt\];

The stochastic matrix of the $\mathrm{CNOT}$ gate $C$ is $$\begin{aligned}
        \bm{C}=\sum_{i,j=1}^n ((\bm i\oplus \bm j)\otimes\bm j)^T(\bm i\otimes\bm j)
        \,,
    \end{aligned}$$ and the stochastic matrix of the black-box $\mathrm{B}$ is $$\begin{aligned}
        \bm{B}=\sum_{i=1}^n \bm e_i^T\bm i\,,
    \end{aligned}$$ with $$\begin{aligned}
        \left|\{i\,|\,i=e_i\}\right|=1
        \,. 
    \end{aligned}$$ Since $\mathrm{B}$ is a black-box, the values $e_i$ are unknown to us.  We write the probability of getting $(b,x,y)$ conditioned on the input $a$ with stochastic matrices and stochastic vectors: $$\begin{aligned}
        P_{B,X,Y|A}(b,x,y,a)=
        \left(
        (\bm x\otimes \bm y)^T
        \bm{C}
        (\bm a\otimes \bm b)
        \right)
        \left(\bm b^T\bm{B}\bm y\right)
        \,,
    \end{aligned}$$ where $\bm x$ is the stochastic vector of the value $x$, as described on page , and where $\bm b^T\bm{B}\bm y$ is the probability of obtaining $b$ when $y$ is given as input to $\mathrm{B}$. Now, if we use $a=0$, we find the fixed-point $x$: $$\begin{aligned}
        P_{B,X,Y|A}(b,x,y,0)=
        \cases{
            1&for $x=b=y$\\
            0&otherwise. 
        }
    \end{aligned}$$

So far we ignore how to deal with black boxes that have an [*unknown number of fixed-points*]{}, and whether, in that case, a computational advantage is achievable at all. 

Open questions
==============

The main open question in this field of research is whether nature violates causal inequalities.  Contrary to some superpositions of causal orders [@Procopio:2015iw], no experiment has been proposed or carried out to violate such inequalities.  Even though some results [@Baumeler:2013wy; @Brukner:2014vo] indicate a strong connection between non-causal correlations and non-local correlations — the maximally achievable violation of a two-party causal inequality in the quantum setting is $(2+\sqrt 2)/4$, which is the same value as Cirel’son’s bound [@Cirelson:1980fp], and for three parties, the algebraic maximum is achievable [@Greenberger:1989vx; @Greenberger:1990it] —, the connection remains unknown.  A violation of a two-party causal inequality up to the algebraic maximum by the use of higher-dimensional systems is also unknown so far; such a result would strengthen the connection between both types of correlations and could give insight on how these correlations are connected.  To our knowledge, it is also unknown which process matrices can be purified.  Since purification is of great importance in quantum information [@Chiribella:2012kz], purification of process matrices is also desired.  It has been suspected that the process matrices that [*can*]{} be purified [*cannot*]{} violate causal inequalities.  However, a counterexample has been provided recently [@Baum; @inprep].  The same was conjectured for classical processes.  This has been refuted as well: For the classical case, it is known that classical processes from the deterministic-extrema polytope can be made reversible [@Baum; @inprep] — this fact is the classical analogue of purification.  Of great interest are also information-theoretic considerations of non-causal correlations, similar to [@Pawiowski:2009dt; @Ibnouhsein:2015cf].  For instance, it might be possible to quantify the amount of “superposition” versus the amount of “loops” a process matrix carries.  Finally, little is known on the computational power of process matrices, classical processes, and of our model of computation.  While the D-CTC model [@Deutsch:1991jo] can efficiently solve problems that are in PSPACE [@Aaronson:2009dy], it is unknown what the complexity class is of the efficiently solvable problems in our model of computation. 

Acknowledgements {#acknowledgements .unnumbered}
================

We thank Mateus Ara[ú]{}jo, Veronika Baumann, [Č]{}aslav Brukner, Fabio Costa, Adrien Feix, Christina Giarmatzi, and Thomas Strahm for helpful discussions.  Furthermore, we thank the anonymous referees for their detailed comments.  The present work was supported by the Swiss National Science Foundation (SNF) and the National Centre of Competence in Research “Quantum Science and Technology” (QSIT). 

References {#references .unnumbered}
==========

[^1]: The key to understanding [*how exactly*]{} this happens is perhaps hidden in thermodynamics and a suitable interpretation of quantum theory. 

[^2]: Throughout this work we use bold letters for vectors and matrices.