# On Equivalent Color Transform and Four Coloring Theorem

Wenhong Tiana School of Information and Software Engineering,
University of Electronic Science and Technology of China (UESTC)

###### Abstract

In this paper, we apply an equivalent color transform (ECT) for a minimal
$k$-coloring of any graph $G$. It contracts each color class of the graph to a
single vertex and produces a complete graph $K_{k}$ for $G$ by removing
redundant edges between any two vertices. Based on ECT, a simple proof for
four color theorem for planar graph is then proposed.

###### keywords:

Four color theorem, Equivalent color transform (ECT)

##  1 Introduction

Four Coloring Theorem (FCT) states that every planar map is four colorable so
that no two adjacent regions have the same color, given any separation of a
plane into contiguous regions in the map. Proving four colors theorem is a
very hard and challenging task since the first statement of the four color
theorem in 1852.
The four color theorem was proved in 1976 by Kenneth Appel and Wolfgang Haken
[3] [4] with computer assistance. It was the first major theorem to be proved
using a computer.

To dispel remaining doubt about the Appel-Haken proof, a simpler proof using
the same ideas still with computer-assistance was published in 1996 by
Robertson, Sanders, Seymour, and Thomas [7] and the part which required hand
verification was not as tedious as in Appel-Haken proof. A quadratic algorithm
to 4-color planar graph was proposed in [5] by Appel and Haken. An efficient
algorithm for four-coloring planar graph was also proposed in [6]. In this
paper, we apply an equivalent color transform (ECT) for planar graph and
propose a simpler proof for four color theorem.

##  2 Methods

Definition 1. Equivalent Color Class (ECC). For coloring a simple graph, node
$i$ and $j$ can have the same color if they are non-adjacent, node $i$ and $j$
are called in equivalent color class.

Definition 2. Equivalent Color Graph (ECG) is a composite graph, where
composite nodes are formed by moving those non-adjacent nodes in original
graph together and edges are kept the same as in the original graph.

Definition 3. Equivalent Color Transform (ECT) is contracting each equivalent
color class in ECG to a single vertex and keep just one edge between any
adjacent vertex.

There may be more than one way to form ECG for any given graph. Figure 1 shows
an example of 6-node simple graph (a) and its corresponding ECG (b) and ECT
(c).

Figure 1: An instance of ECG and ECT

Definition 4. Planar Graph is a graph that can be embedded in the plane, i.e.,
it can be drawn in such a way that no edges cross each other [1].

Lemma 1. There exists an efficient ECT for planar graph.

There are exact algorithms to determine if a graph is 4-colorable such as one
suggested in [2]; there are also efficient algorithms such as one suggested in
[6] for efficiently four-coloring a planar graph. Notice that the
RSST(abbreviated by the first letter of four authors in [6]) algorithm has
computational complexity of $O(n^{2})$, where $n$ is the number of nodes in
the graph. We therefore can conduct ECT efficiently by using RSST algorithm or
similar algorithm.

Theorem 1. For a planar graph, there exist an ECT which does not change the
planarity of the graph.

###### Proof.

Building ECG just moves the place of original nodes and does not alter any
node or edge or their connection relationship, so we can apply RSST algorithm
to find an ECT, which do not change the planarity of the original graph.
∎

Notice that there may be more than one ECG and ECT for any given planar graph;
we can apply RSST algorithm and similar algorithm to find an ECG and ECT,
which do not change the planarity of the graph. To do this, we may need
running RSST algorithm a few times until the ECG and ECT are found to keep the
planarity of the original graph.

Theorem 2. A $k$-coloring graph which needs the minimum number of $k$ colors,
can be converted to a complete simple graph $K_{k}$ by ECT.

###### Proof.

We prove by contradiction. Let us assume the original $k$-coloring graph
$G_{1}$ is converted to a simple graph $G_{2}$ with $k$ nodes by ECT and
$G_{2}$ is not complete graph. Since $G_{2}$ is not complete graph, there must
exist at least two nodes $n_{i}$ and $n_{j}$ which are not adjacent. According
to the definition of ECC and ECG, $n_{i}$ and $n_{j}$ can be contracted to a
single vertex (by equivalent color class and ECT) and a new graph with ($k$-1)
nodes is formed. Therefore there only need ($k$-1) colors for $G_{1}$ and
$G_{2}$, this contradicts the fact that $G_{1}$ is $k$-coloring and needs the
minimum $k$ colors. ∎

Lemma 1. Wagner’s Theorem. A finite graph is planar if and only if it does not
have $K_{5}$ or $K_{3,3}$ as a minor [1].

Theorem 3. Planar graph is four colorable.

###### Proof.

We prove by contradiction. Set $k$ as the minimum number of colors needed for
coloring planar graph $G$. Let assume the planar graph $G$ needs more than
four colors, i.e., $k>4$. From Theorem 2, we know that $G$ can be converted to
a complete graph $K_{k}$ ($k>$4) in this case. This means $G$ is transformed
by ECT to a complete graph $K_{k}$ ($k>$4) which is not planar because any
complete graph with more than 4 nodes will have $K_{5}$ as a minor and is not
planar (by Lemma 1). But this contradicts the fact that $G$ is planar and
there exits an ECT which does not change the planarity of the original graph
(by Theorem 1). So $k\leq 4$ and planar graph is four colorable.

∎

## Acknowledgments

This research is sponsored by the National Natural Science Foundation of China
(NSFC) (Grand Number: 61672136). The manuscript is also posted online at
https://arxiv.org/

## References

  * [1] https://en.wikipedia.org/wiki/Planar_graph
  * [2] Fomin, F.V.; Gaspers, S.; Saurabh, S. (2007), Improved Exact Algorithms for Counting 3- and 4-Colorings, Proc. 13th Annual International Conference, COCOON 2007, Lecture Notes in Computer Science, 4598, Springer, pp. 65-74.
  * [3] K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977), 429-490.
  * [4] K. Appel, W. Haken and J. Koch, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math. 21 (1977), 491-567.
  * [5] K. Appel and W. Haken, Every planar map is four colorable. Contemp. Math. 98,1989.
  * [6] N. Robertson, D. P. Sanders, Efficiently four-coloring planar graphs, STOC ’1996 Proceedings of the twenty-eighth annual ACM symposium on Theory of computing,Pages 571-575.
  * [7] N. Robertson, D. P. Sanders,P. D. Seymour and R. Thomas, A new proof of the four colour theorem, Electron. Res. Announc. AMS 2 (1996), 17-25.


[rm]bfb

# Possibilistic and maximal indefinite causal order in the quantum switch

Tein van der Lugt  Department of Computer Science, University of Oxford,
Wolfson Building, Parks Road, Oxford, OX1 3QD, United Kingdom
<EMAIL_ADDRESS>Nick Ormrod  Department of Computer Science,
University of Oxford, Wolfson Building, Parks Road, Oxford, OX1 3QD, United
Kingdom<EMAIL_ADDRESS>
###### Abstract

It was recently found that the indefinite causal order in the quantum switch
can be certified device-independently when assuming the impossibility of
superluminal influences. Here we strengthen this result in two ways. First, we
give a proof of this fact which is possibilistic, rather than probabilistic,
i.e. which does not rely on the validity of probability theory at the hidden
variable level. Then, returning to the probabilistic setting, we show that the
indefinite causal order in the quantum switch is also maximal, in the sense
that the observed correlations are incompatible even with the existence of a
causal order on only a small fraction of the runs of the experiment. While the
original result makes use of quantum theory’s violation of a Clauser-Horne-
Shimony-Holt inequality, the proofs presented here are based on Greenberger,
Horne, and Zeilinger’s and Mermin’s proofs of nonlocality, respectively.

When two measurements are performed within a quantum circuit, the topology of
the circuit puts constraints on the causal relations between them: either the
choice of measurement at $A$ can influence the outcome of the measurement at
$B$, or vice versa, but not both. Recent extensions to the quantum circuit
paradigm have however facilitated considering situations in which the topology
of the quantum circuit itself, and in particular the causal order between
measurements, is in a quantum superposition. The simplest example of this is
the _quantum switch_ [1], a mathematical device that applies two operations to
a target system in an order coherently controlled by the state of a qubit.

It was recently found that under some metaphysical assumptions, the indefinite
causal order between measurements in the quantum switch can also be
demonstrated device-independently, that is, relying just on correlations
between classical settings and outcomes of the measurements, and not on a
characterisation of the measurements themselves (or indeed the assumption that
they are governed by quantum theory) [2, 3]. The argument of [2] works via the
violation of an inequality derived from assumptions named definite causal
order, relativistic causality, and free interventions. This derivation relies
closely on Bell’s theorem [4]: the crucial observation is that a hidden
variable determining a causal order (which exists by the first assumption) in
some particular cases must also fix, or, in other words, ‘predetermine’, a
measurement outcome—and that this determinism, together with the other
assumptions, implies Bell inequalities which are violated by the quantum
correlations under consideration.

This observation suggests that it is possible to transform other proofs of
Bell nonlocality, beyond that based on the Clauser-Horne-Shimony-Holt (CHSH)
inequality employed in [2], into proofs of indefinite causal order in the
quantum switch. Here we give a proof in the style of Mermin’s version of
Greenberger-Horne-Zeilinger (GHZ) nonlocality [5, 6, 7]. Similarly to the
latter, the proof does not involve inequalities and is of a possibilistic,
rather than probabilistic, character: the quantum switch data are shown to
contradict the assumptions mentioned above even when both are formulated
merely in terms of which events have zero and nonzero probabilities. In
particular this shows that the quantum switch is incompatible with a
(relativistically well-behaved) definite causal order even if causal orders
are not required to follow the laws of probability theory.

We also give a statistical inequality, analogous to Mermin’s inequality [8]
for Bell nonlocality, which parallels our possibilistic argument. Although
this takes us back to assuming the validity of probability theory, it allows
us to improve on the results of [2, 3] in a different way, namely by showing
that the quantum switch exhibits ‘maximal’ indefinite causal order. More
precisely, the quantum switch correlations violate this inequality to the
algebraic maximum, which implies incompatibility even with the hypothesis that
there is a definite causal order on only some positive fraction of the runs of
the experiment.

##  1 Notation and terminology

Possibilities are modelled by the Boolean semiring ${\mathbb{B}=\\{0,1\\}}$,
where $0$ denotes impossibility and $1$ possibility of an event. Addition and
multiplication in $\mathbb{B}$ are defined as $0+0=0$, $0+1=1+0=1+1=1$,
$0\cdot 0=0\cdot 1=1\cdot 0=0$ and $1\cdot 1=1$. A _possibility distribution_
over a set of variables $a_{1},\dots,a_{n}$ taking values in the finite sets
$A_{1},\dots,A_{n}$ is a function $p:A_{1}\times\cdots\times
A_{n}\to\mathbb{B}$ satisfying $\sum_{a_{1},\dots,a_{n}}p(a_{1}\cdots
a_{n})=1$; i.e. at least one tuple of values is possible. (We will abuse
notation by using lower-case letters to denote random variables as well as
their values.) A _probability_ distribution $P:A\to\mathbb{R}_{\geq 0}$
defines a possibility distribution $p$ over the same variable by
$p(a)=\pi(P(a))$, where $\pi:\mathbb{R}_{\geq 0}\to\mathbb{B}$ takes $0$ to
$0$ and any $r>0$ to $1$.

(Conditional) independence is denoted by
$\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}$. In
the case of a possibility distribution $p(abc)$,
$a\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{p}b\mid
c$ is defined as $\forall a,b,c:p(abc)=p(ac)p(bc)$, while unconditional
independence
$a\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{p}b$
means that $\forall a,b:p(ab)=p(a)p(b)$. Moreover, $\ \ \Longrightarrow\ \ $
denotes implication: for propositions $P$ and $Q$, $P\ \ \Longrightarrow_{p}\
\ Q$ is short for $p(P,\neg Q)=0$.

Finally, $\oplus$ denotes addition modulo 2, and
$\ket{\pm}\coloneqq{(\ket{0}\pm\ket{1})/\sqrt{2}}$ and $\ket{\pm
i}\coloneqq(\ket{0}\pm i\ket{1})/\sqrt{2}$.

##  2 GHZ-Mermin nonlocality

We first review Mermin’s version [6] of the GHZ proof [5] of Bell nonlocality.
Three spacelike-separated parties labelled $A$, $B$, and $C$ share three
qubits prepared in the state
$\ket{\mathrm{GHZ}}\coloneqq(\ket{000}+\ket{111})/\sqrt{2}$. Each party has a
binary classical input variable ($x,y,z\in\\{0,1\\}$, resp.), and measures
their qubit in the $Y$ basis $\\{\ket{+i},\ket{-i}\\}$ if their input is 0,
and in the $X$ basis $\\{\ket{+},\ket{-}\\}$ if their input is 1. The
measurement outcomes are recorded in the output variables $a,b,c\in\\{0,1\\}$.
Given a probability distribution over the input variables, the Born rule
provides joint probabilities $P(abcxyz)$ for all combinations of input and
output variables. All that the following argument relies on are however the
induced _possibilities_ $p(abcxyz)\coloneqq\pi(P(abcxyz))$.

A particular property of these possibilities, predicted by the Born rule, is
that

$\begin{split}x=1,y=1,z=1\ \ \Longrightarrow_{p}\ \ a\oplus b\oplus c=0;\\\
x=1,y=0,z=0\ \ \Longrightarrow_{p}\ \ a\oplus b\oplus c=1;\\\ x=0,y=1,z=0\ \
\Longrightarrow_{p}\ \ a\oplus b\oplus c=1;\\\ \text{ and\quad}x=0,y=0,z=1\ \
\Longrightarrow_{p}\ \ a\oplus b\oplus c=1.\end{split}$ (1)

These perfect correlations can be used in an EPR-like argument [9] to argue
for the existence of local deterministic hidden variables, i.e. to argue that
for each wing of the experiment, there are pre-existing physical properties
that determine the outcome for any possible measurement setting on that wing.
Mathematically, these are described by variables
$\lambda_{A,B,C}^{0,1}\in\\{0,1\\}$, independent of $x,y,z$ and satisfying
$x=i\Longrightarrow_{p}a=\lambda_{A}^{i}$ and similar conditions for $B$ and
$C$.

Together with the assumption that all combinations of inputs appearing in (1)
are in fact possible, this leads us to conclude that with certainty

$\begin{split}\lambda_{A}^{1}\oplus\lambda_{B}^{1}\oplus\lambda_{C}^{1}&=0;\\\
\lambda_{A}^{1}\oplus\lambda_{B}^{0}\oplus\lambda_{C}^{0}&=1;\\\
\lambda_{A}^{0}\oplus\lambda_{B}^{1}\oplus\lambda_{C}^{0}&=1;\\\
\lambda_{A}^{0}\oplus\lambda_{B}^{0}\oplus\lambda_{C}^{1}&=1;\quad\oplus\\\
\vskip 3.0pt plus 1.0pt minus 1.0pt\cr\hline\cr\vskip 3.0pt plus 1.0pt minus
1.0pt\cr 0&=1.\end{split}$ (2)

This contradiction demonstrates that no model with local deterministic hidden
variables $\lambda_{A,B,C}^{0,1}$ can reproduce the correlations (1) predicted
by the Born rule.

##  3 Adding switches

We will now see how this argument can be turned into a possibilistic proof of
indefinite causal order in the quantum switch. Our first objective will be to
identify a scenario involving quantum switches that yields possibilistic data
satisfying properties analogous to (1) above.

The quantum switch [1] is defined as a supermap [10] taking two quantum
operations $\mathcal{E},\mathcal{F}$ on a _target system_ $T$ to an operation
$\operatorname{\textsc{switch}}(\mathcal{E},\mathcal{F})$ on the joint system
$CT$, which applies $\mathcal{E}$ and $\mathcal{F}$ to $T$ in an order that is
coherently controlled by the state of the _control qubit_ $C$ (see Figure 1).
We will consider a variant of the quantum switch which is controlled in the
$X$ basis $\\{\ket{+},\ket{-}\\}$. Hence, if the target and control systems
are described by Hilbert spaces $\mathcal{H}_{T}$ and
$\mathcal{H}_{C}\cong\mathbb{C}^{2}$ and if
$\mathcal{E}(\cdot)=E(\cdot)E^{\dagger}$ and
$\mathcal{F}(\cdot)=F(\cdot)F^{\dagger}$ are pure operations with Kraus
operators $E,F:\mathcal{H}_{T}\to\mathcal{H}_{T}$, then
$\operatorname{\textsc{switch}}(\mathcal{E},\mathcal{F})(\cdot)=W(\cdot)W^{\dagger}$
where
$W:\mathcal{H}_{C}\otimes\mathcal{H}_{T}\to\mathcal{H}_{C}\otimes\mathcal{H}_{T}$
is the operator defined by

$W\coloneqq\ket{+}\bra{+}_{C}\otimes FE+\ket{-}\bra{-}_{C}\otimes EF.$ (3)

$T$$C$$C$$T$$\mathcal{E}$switch$\mathcal{F}$$\mathcal{E}$$T$$T$,$\mathcal{F}$$T$$T$$\longmapsto$switch
Figure 1: The quantum switch takes two quantum operations on the system $T$,
here $\mathcal{E}$ and $\mathcal{F}$, to an operation on $CT$, where $C$ is a
control qubit. The dotted (red) and dashed (blue) lines illustrate the wirings
to which the quantum switch reduces upon preparation of $C$ in state
$\outerproduct{+}{+}$ and $\outerproduct{-}{-}$, respectively.

We consider a scenario in which three such quantum switches, labelled by $A$,
$B$ and $C$, are implemented at spacelike-separated locations. Their control
qubits are prepared in the GHZ state, while their target systems, also qubits,
are all prepared in the state $\ket{0}$ (see Figure 2). We will think of the
two operations on the target system $T_{A}$ inside switch $A$ as being
performed by two agents, $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$, with
classical input variables $x_{1},x_{2}\in\\{0,1\\}$ and output variables
$a,b\in\\{0,1\\}$, respectively. If $x_{i}=0$ (for $i=1,2$), then
$\mathcal{A}_{i}$ performs no intervention (i.e. lets $T_{A}$ undergo the
identity channel), and outputs $a_{i}=0$. If $x_{i}=1$, she instead measures
$T_{A}$ in the computational basis, records the result in $a_{i}\in\\{0,1\\}$,
and prepares the outgoing target system in state $\ket{1}_{T_{A}}$. A third
agent $\mathcal{A}_{3}$ has no input variable and always measures the output
control system $C_{A}$ in the $Y$ basis, recording their result in the output
variable $a_{3}\in\\{0,1\\}$. Similar measurements are performed on the
systems of switches $B$ and $C$.

The Born rule, together with the definition of the quantum switch (3) and a
distribution over input variables, provides us with a probability distribution
$Q(a_{1}a_{2}a_{3}b_{1}b_{2}b_{3}c_{1}c_{2}c_{3}x_{1}x_{2}y_{1}y_{2}z_{1}z_{2})$
(see Appendix A for a more precise definition). We will abbreviate this by
$Q(\mathbfit a\mathbfit b\mathbfit c\mathbfit x\mathbfit y\mathbfit z)$ where
$\mathbfit a\coloneqq(a_{1},a_{2},a_{3})$, $\mathbfit x\coloneqq(x_{1},x_{2})$
and $\mathbfit b$, $\mathbfit c$, $\mathbfit y$, and $\mathbfit z$ are defined
similarly. As was the case for GHZ nonlocality, it will suffice to consider
only the induced possibility distribution $q(\mathbfit a\mathbfit b\mathbfit
c\mathbfit x\mathbfit y\mathbfit z)\coloneqq\pi(Q(\mathbfit a\mathbfit
b\mathbfit c\mathbfit x\mathbfit y\mathbfit z))$.

$T$$C$$C$$T$$\mathcal{E}$switch$\mathcal{F}$$\mathcal{E}$$T$$T$,$\mathcal{F}$$T$$T$$\longmapsto$switchghz$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch$x_{1}$$a_{1}$0$a_{3}$$T_{B}$$C_{B}$$C_{B}$$T_{B}$switch0$T_{C}$$C_{C}$$C_{C}$$T_{C}$switch0$\lambda_{A}$$\lambda_{B}$$\lambda_{C}$$\mathcal{A}_{3}$$\mathcal{A}_{1}$$x_{2}$$a_{2}$$\mathcal{A}_{2}$$z_{1}$$c_{1}$$\mathcal{C}_{1}$$z_{2}$$c_{2}$$\mathcal{C}_{2}$$y_{1}$$b_{1}$$\mathcal{B}_{1}$$y_{2}$$b_{2}$$\mathcal{B}_{2}$$b_{3}$$\mathcal{B}_{3}$$c_{3}$$\mathcal{C}_{3}$
Figure 2: A GHZ-inspired quantum switch setup. The diagram is read from bottom
to top; black wires are quantum systems while grey wires are classical
variables. Three quantum switches (in blue) have control qubits entangled in
the GHZ state. Their target systems are qubits, initially prepared in the
computational basis state $\ket{0}$. Inside each switch, two parties act on
the target system; their actions, here represented by classical-quantum
channels, are described in the main text. The output target systems are
discarded. Overall, this diagram defines the classical channel (conditional
probability distribution) $Q(\mathbfit a\mathbfit b\mathbfit c\mid\mathbfit
x\mathbfit y\mathbfit z)$. The orange variables $\lambda_{A,B,C}$ denote the
postulated hidden causal orders, which are assumed to take a value in the past
lightcone of their respective switches. The orange line is an example of a
spacelike hypersurface that can be used to argue for Equation (14b).

We now want to find patterns in these possibilities analogous to those in (1).
For that purpose, the following two observations will be useful (cf. Figure
3). (These informal statements are given to provide intuition; formalised
versions and their proofs can be found as Lemmas 2 and 3 in Appendix A.)

######  Observation 1.

If $x_{1}=x_{2}=0$, then $a_{3}$ simulates the outcome of a $Y$ basis
measurement of the _input_ control system $C_{A}$; similarly for switches $B$
and $C$.

Indeed, when $x_{1}=x_{2}=0$, no interventions are performed on the target
system inside the switch, so that the switch itself reduces to the identity
channel. This leaves the control system unaffected for $\mathcal{A}_{3}$ to
measure (see Figure 3a).

######  Observation 2.

If $x_{1}=x_{2}=1$, then $a_{1}$ simulates the outcome of an $X$ basis
measurement of the input control system $C_{A}$; similarly for switches $B$
and $C$.

This is because the input target system is initially prepared in state
$\ket{0}_{T_{A}}$, while $\mathcal{A}_{2}$ (given $x_{2}=1$) reprepares it in
the orthogonal state $\ket{1}_{T_{A}}$. As a result, a measurement of
$a_{1}=1$ is only compatible with the wiring in which $\mathcal{A}_{1}$ comes
after $\mathcal{A}_{2}$—and therefore only with finding the control qubit in
state $\ket{-}_{C_{A}}$ upon an $X$ basis measurement. Similarly, $a_{1}=0$ is
only compatible with the control qubit being found in state $\ket{+}_{C_{A}}$.
Therefore the probabilities (and hence possibilities) of these events are
identical. This is depicted diagrammatically in Figure 3b and proven in
Appendix A.

a)
$T$$C$$C$$T$$\mathcal{E}$switch$\mathcal{F}$$\mathcal{E}$$T$$T$,$\mathcal{F}$$T$$T$$\longmapsto$switchghz$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch$x_{1}$$a_{1}$0$a_{3}$$T_{B}$$C_{B}$$C_{B}$$T_{B}$switch0$T_{C}$$C_{C}$$C_{C}$$T_{C}$switch0$\lambda_{A}$$\lambda_{B}$$\lambda_{C}$$\mathcal{A}_{3}$$\mathcal{A}_{1}$$x_{2}$$a_{2}$$\mathcal{A}_{2}$$z_{1}$$c_{1}$$\mathcal{C}_{1}$$z_{2}$$c_{2}$$\mathcal{C}_{2}$$y_{1}$$b_{1}$$\mathcal{B}_{1}$$y_{2}$$b_{2}$$\mathcal{B}_{2}$$b_{3}$$\mathcal{B}_{3}$$c_{3}$$\mathcal{C}_{3}$$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch0ghz$\large=$$C_{A}$ghz$a_{3}$$a_{3}$
b)
$T$$C$$C$$T$$\mathcal{E}$switch$\mathcal{F}$$\mathcal{E}$$T$$T$,$\mathcal{F}$$T$$T$$\longmapsto$switchghz$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch$x_{1}$$a_{1}$0$a_{3}$$T_{B}$$C_{B}$$C_{B}$$T_{B}$switch0$T_{C}$$C_{C}$$C_{C}$$T_{C}$switch0$\lambda_{A}$$\lambda_{B}$$\lambda_{C}$$\mathcal{A}_{3}$$\mathcal{A}_{1}$$x_{2}$$a_{2}$$\mathcal{A}_{2}$$z_{1}$$c_{1}$$\mathcal{C}_{1}$$z_{2}$$c_{2}$$\mathcal{C}_{2}$$y_{1}$$b_{1}$$\mathcal{B}_{1}$$y_{2}$$b_{2}$$\mathcal{B}_{2}$$b_{3}$$\mathcal{B}_{3}$$c_{3}$$\mathcal{C}_{3}$$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch0ghz$\large=$$C_{A}$ghz$a_{3}$$a_{3}$$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch$1$0ghz$\large=$$C_{A}$ghz$a_{1}$$X$
mmt$a_{1}$$Z$ mmt$1$

Figure 3: a) If $x_{1}=x_{2}=0$, then $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$
perform identity operations, so that the quantum switch itself also reduces to
the identity channel. b) If $x_{1}=x_{2}=1$, they both measure the target
system in the computational ($Z$) basis and afterwards prepare the state
$\ket{1}_{T_{A}}$. The $a_{1}$ outcome then has the same probability and
postselected state as an $X$ basis measurement of the input control qubit.
(Note that the switch is controlled in the $X$ basis.)

Observations 1 and 2, together with the fact that the control qubits are
entangled in the GHZ state, tell us that if we make appropriate changes to the
variables featuring in (1) then the resulting implications will hold in our
new possibility distribution $q$:

$\begin{split}\mathbfit x=\mathbf{1},\mathbfit y=\mathbf{1},\mathbfit
z=\mathbf{1}\ \ \Longrightarrow_{q}\ \ a_{1}\oplus b_{1}\oplus c_{1}=0;\\\
\mathbfit x=\mathbf{1},\mathbfit y=\mathbf{0},\mathbfit z=\mathbf{0}\ \
\Longrightarrow_{q}\ \ a_{1}\oplus b_{3}\oplus c_{3}=1;\\\ \mathbfit
x=\mathbf{0},\mathbfit y=\mathbf{1},\mathbfit z=\mathbf{0}\ \
\Longrightarrow_{q}\ \ a_{3}\oplus b_{1}\oplus c_{3}=1;\\\ \mathbfit
x=\mathbf{0},\mathbfit y=\mathbf{0},\mathbfit z=\mathbf{1}\ \
\Longrightarrow_{q}\ \ a_{3}\oplus b_{3}\oplus c_{1}=1\end{split}$ (4)

(here $\mathbf{0}\coloneqq(0,0)$ and $\mathbf{1}\coloneqq(1,1)$). (It is worth
noting that these implications are nothing more than properties of the
possibility distribution $q$ and can therefore also be derived directly from
the Born rule and definition of the quantum switch. Observations 1 and 2 are
only given to provide intuition for why (4) should hold, given that we already
know the GHZ correlations of (1).)

The implications in (4), like those in (1), do not immediately lead to a
contradiction, because each equation on the right refers to outputs for a
different set of inputs. As in the case of nonlocality, a contradiction only
arises when some of the outcome variables can be replaced by (hidden)
variables that are independent of these measurement choices. The next sections
show that the assumptions of definite causal order and relativistic causality
imply the existence of such variables.

##  4 Definite causal order

In the following we will want to probe causal relations on the basis of
(possibilistic) correlations. An important assumption enabling this is that
the input variables $x_{1},x_{2},y_{1},y_{2},z_{1},z_{2}$ of the agents’
interventions are freely chosen. In particular, this means that they are
uncorrelated with variables outside their causal future, motivating some of
the mathematical conditions defined below. It also motivates the assumption
that all inputs are jointly possible, which will be needed later:

$\forall\mathbfit x,\mathbfit y,\mathbfit z\ q(\mathbfit x\mathbfit y\mathbfit
z)=1.$ (5)

######  Definition 1.

A _hidden causal order model_ for a possibility distribution
$r(a_{1}a_{2}x_{1}x_{2})$ is a possibility distribution
$r(a_{1}a_{2}x_{1}x_{2}\lambda)$, where $\lambda\in\\{0,1\\}$, such that

$\displaystyle{\sum}_{\lambda}r(a_{1}a_{2}x_{1}x_{2}\lambda)$
$\displaystyle=r(a_{1}a_{2}x_{1}x_{2}),$ (6a) $\displaystyle\lambda$
$\displaystyle\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{r}x_{1}x_{2},$
(6b) $\displaystyle a_{1}$
$\displaystyle\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{r}x_{2}\mid\lambda=0,$
(6c) $\displaystyle\text{and\quad}a_{2}$
$\displaystyle\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{r}x_{1}\mid\lambda=1.$
(6d)

The interpretation of this hidden variable $\lambda$ is that it determines the
causal order between interventions performed by parties $\mathcal{A}_{1}$ and
$\mathcal{A}_{2}$ with inputs $x_{1},x_{2}$ and outputs $a_{1},a_{2}$,
respectively: viz. the value $\lambda=0$ indicates that $\mathcal{A}_{1}$ acts
outside the causal future of $\mathcal{A}_{2}$, so that the possibility of
outcome $a_{1}$ is independent of the freely chosen input $x_{2}$.

######  Assumption 1 (Definite causal order).

There exist three variables $\lambda_{A},\lambda_{B},\lambda_{C}\in\\{0,1\\}$
and a joint possibility distribution $q(\mathbfit a\mathbfit b\mathbfit
c\mathbfit x\mathbfit y\mathbfit z\lambda_{A}\lambda_{B}\lambda_{C})$
satisfying

$\sum_{\lambda_{A},\lambda_{B},\lambda_{C}}q(\mathbfit a\mathbfit b\mathbfit
c\mathbfit x\mathbfit y\mathbfit
z\lambda_{A}\lambda_{B}\lambda_{C})=q(\mathbfit a\mathbfit b\mathbfit
c\mathbfit x\mathbfit y\mathbfit z),$ (7)

such that $q(a_{1}a_{2}x_{1}x_{2}\lambda_{A})$ is a hidden causal order model
for $q(a_{1}a_{2}x_{1}x_{2})$, $q(b_{1}b_{2}y_{1}y_{2}\lambda_{B})$ for
$q(b_{1}b_{2}y_{1}y_{2})$, and $q(c_{1}c_{2}z_{1}z_{2}\lambda_{C})$ for
$q(c_{1}c_{2}z_{1}z_{2})$.

In the GHZ proof, the hidden variables were (when assumed to exist) directly
revealed by outcomes of measurements, allowing us to replace the output
variables $a,b,c$ in (1) by hidden variables to obtain (2). This is not
necessarily the case for hidden variables determining causal orders. However,
as we already noted after Observation 2, our choice of initial target state
and operations performed inside the switch are such that, for $x_{1}=x_{2}=1$,
each value of $a_{1}$ is compatible with only one of the orderings of the
operations on the target system. The following Lemma elevates this observation
to the device-independent level.

######  Lemma 1.

Suppose that the possibility distribution $r(a_{1}a_{2}x_{1}x_{2})$, where
$a_{1},a_{2},x_{1},x_{2}\in\\{0,1\\}$, satisfies

$\displaystyle r(a_{1}=1,x_{2}=0)$ $\displaystyle=0,$ (8a) $\displaystyle
r(a_{2}=1,x_{1}=0)$ $\displaystyle=0,$ (8b)
$\displaystyle\text{and\quad}r(a_{1}=a_{2}=0,x_{1}=x_{2}=1)$
$\displaystyle=0,$ (8c)

then any hidden causal order model $r(a_{1}a_{2}x_{1}x_{2}\lambda)$ for
$r(a_{1}a_{2}x_{1}x_{2})$ satisfies

$x_{1}=x_{2}=1\Longrightarrow_{r}a_{1}=\lambda.$ (9)

###### Proof.

Our first claim is that

$a_{1}=1\Longrightarrow_{r}\lambda=1.$ (10)

Indeed, from Equation (8a),

$\begin{split}0&=r(a_{1}=1,x_{2}=0)\\\ &\geq r(a_{1}=1,x_{2}=0,\lambda=0)\\\
&\stackrel{{\scriptstyle\eqref{eq:hco-
def-a1x2}}}{{=}}r(a_{1}=1,\lambda=0)r(x_{2}=0,\lambda=0)\\\
&\stackrel{{\scriptstyle\eqref{eq:hco-def-
fc}}}{{=}}r(a_{1}=1,\lambda=0)r(x_{2}=0)r(\lambda=0)\\\
&\stackrel{{\scriptstyle\eqref{eq:all-inputs-
possible}}}{{=}}r(a_{1}=1,\lambda=0)r(\lambda=0)\\\ &=r(a_{1}=1,\lambda=0).\\\
\end{split}$ (11)

Moreover, we have

$x_{1}=x_{2}=1,a_{1}=0\ \Longrightarrow_{r}\ a_{2}=1\ \Longrightarrow_{r}\
\lambda=0;$ (12)

here the first implication is Equation (8c), while the second follows from an
argument analogous to that for (10) but using (8b). (10) and (12) together
imply the result. ∎

The marginals $q(a_{1}a_{2}x_{1}x_{2}),q(b_{1}b_{2}y_{1}y_{2})$ and
$q(c_{1}c_{2}z_{1}z_{2})$ for our three switches satisfy the conditions of
Lemma 1. Therefore we can, under Assumption 1, replace some of the observed
variables in (4) by hidden variables:

$\begin{split}\mathbfit x=\mathbf{1},\mathbfit y=\mathbf{1},\mathbfit
z=\mathbf{1}&\ \ \Longrightarrow_{q}\ \
\lambda_{A}\oplus\lambda_{B}\oplus\lambda_{C}=0;\\\ \mathbfit
x=\mathbf{1},\mathbfit y=\mathbf{0},\mathbfit z=\mathbf{0}&\ \
\Longrightarrow_{q}\ \ \lambda_{A}\oplus b_{3}\oplus c_{3}=1;\\\ \mathbfit
x=\mathbf{0},\mathbfit y=\mathbf{1},\mathbfit z=\mathbf{0}&\ \
\Longrightarrow_{q}\ \ a_{3}\oplus\lambda_{B}\oplus c_{3}=1;\\\ \mathbfit
x=\mathbf{0},\mathbfit y=\mathbf{0},\mathbfit z=\mathbf{1}&\ \
\Longrightarrow_{q}\ \ a_{3}\oplus b_{3}\oplus\lambda_{C}=1.\end{split}$ (13)

To derive a contradiction from this set of implications, we need our final
assumption.

##  5 Relativistic causality

Recall that the three switches are implemented at spacelike separation.
Moreover, the hidden variables $\lambda_{A,B,C}$ determine the causal order
between the parties in their respective switch and must therefore take values
in the causal past of those parties. With this in mind, the following
conditions are motivated by the principle of relativistic causality, which
requires the causal order on the variables to be compatible with the provided
lightcone structure—meaning in particular that freely chosen inputs cannot
influence the possibility of events outside their future lightcone.

######  Assumption 2 (Relativistic causality).

The possibility distribution $q(\mathbfit a\mathbfit b\mathbfit c\mathbfit
x\mathbfit y\mathbfit z\lambda_{A}\lambda_{B}\lambda_{C})$ of Assumption 1
satisfies

$\displaystyle\lambda_{A}\lambda_{B}\lambda_{C}$
$\displaystyle\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{q}\mathbfit
x\mathbfit y\mathbfit z;$ (14a) $\displaystyle\lambda_{A}b_{3}c_{3}$
$\displaystyle\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{q}\mathbfit
x\mid\mathbfit y\mathbfit z;$ (14b) $\displaystyle a_{3}\lambda_{B}c_{3}$
$\displaystyle\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{q}\mathbfit
y\mid\mathbfit x\mathbfit z;$ (14c) $\displaystyle a_{3}b_{3}\lambda_{C}$
$\displaystyle\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{q}\mathbfit
z\mid\mathbfit x\mathbfit y.$ (14d)

(Equation (14b), for instance, is motivated by the existence of the spacelike
hypersurface depicted in orange in Figure 2.) These four conditions can be
directly applied to the correlations in (13) to yield the four equations

$\begin{split}\mathbfit x=\mathbf{0},\mathbfit y=\mathbf{0},\mathbfit
z=\mathbf{0}&\ \ \Longrightarrow_{q}\ \
\lambda_{A}\oplus\lambda_{B}\oplus\lambda_{C}=0\\\ \mathbfit
x=\mathbf{0},\mathbfit y=\mathbf{0},\mathbfit z=\mathbf{0}&\ \
\Longrightarrow_{q}\ \ \lambda_{A}\oplus b_{3}\oplus c_{3}=1\\\ \mathbfit
x=\mathbf{0},\mathbfit y=\mathbf{0},\mathbfit z=\mathbf{0}&\ \
\Longrightarrow_{q}\ \ a_{3}\oplus\lambda_{B}\oplus c_{3}=1\\\ \mathbfit
x=\mathbf{0},\mathbfit y=\mathbf{0},\mathbfit z=\mathbf{0}&\ \
\Longrightarrow_{q}\ \ a_{3}\oplus b_{3}\oplus\lambda_{C}=1\qquad\oplus\\\
\vskip 3.0pt plus 1.0pt minus 1.0pt\cr\hline\cr\vskip 3.0pt plus 1.0pt minus
1.0pt\cr\mathbfit x=\mathbf{0},\mathbfit y=\mathbf{0},\mathbfit z=\mathbf{0}&\
\ \Longrightarrow_{q}\ \ 0=1.\end{split}$ (15)

Together with the fact that the combination $\mathbfit x=\mathbfit y=\mathbfit
z=\mathbf{0}$ is possible (by Eq. (5)), this yields our desired contradiction.
Summarising, we have proven the following.

######  Theorem 1.

No possibility distribution $q(\mathbfit a\mathbfit b\mathbfit c\mathbfit
x\mathbfit y\mathbfit z)$ that satisfies Equations (4), (5), (8) and similar
conditions for $B$ and $C$ can also satisfy the conjunction of Assumptions 1
and 2. In particular, the distribution $q(\mathbfit a\mathbfit b\mathbfit
c\mathbfit x\mathbfit y\mathbfit z)$ arising in the quantum switch scenario
depicted in Figure 2 is incompatible with these assumptions.

##  6 Back to probabilities: a causal Mermin inequality

Although quantum theory makes predictions about the (im)possibility of events
in ideal measurement scenarios, experimental data are inevitably subject to
uncertainties and are thus bound to be probabilistic. Impossibilities like
those of Eqs. (4) and (8) can therefore not be verified with certainty,
leaving the possibilistic argument of the preceding sections unamenable to
experiment. However, when the probabilistic data approximately satisfy the
required impossibilities, a refutation of (probabilistic versions of) the
assumptions is still possible via the violation of the following inequality,
closely analogous to Mermin’s inequality [8] for Bell nonlocality. The
derivation of this inequality relies on the probabilistic conditions (28)
given in Appendix B, which are analogous to (but stronger than) the
possibilistic conditions expressed in Equation (5) and Assumptions 1 and 2,
and are likewise physically motivated by the principles of free interventions,
definite causal order, and relativistic causality.

######  Theorem 2.

Any probability distribution $P(\mathbfit a\mathbfit b\mathbfit c\mathbfit
x\mathbfit y\mathbfit z\lambda_{A}\lambda_{B}\lambda_{C})$ that fulfills the
conditions in (28) satisfies the inequality

$\displaystyle P(a_{1}\oplus b_{1}\oplus c_{1}=0\mid\mathbfit
x=\mathbf{1},\mathbfit y=\mathbf{1},\mathbfit z=\mathbf{1})+P(a_{1}\oplus
b_{3}\oplus c_{3}=1\mid\mathbfit x=\mathbf{1},\mathbfit y=\mathbf{0},\mathbfit
z=\mathbf{0})$ $\displaystyle+{}$ $\displaystyle P(a_{3}\oplus b_{1}\oplus
c_{3}=1\mid\mathbfit x=\mathbf{0},\mathbfit y=\mathbf{1},\mathbfit
z=\mathbf{0})+P(a_{3}\oplus b_{3}\oplus c_{1}=1\mid\mathbfit
x=\mathbf{0},\mathbfit y=\mathbf{0},\mathbfit z=\mathbf{1})$
$\displaystyle-{}2\big{[}\ $ $\displaystyle P(a_{1}=1\mid x_{1}x_{2}=10)$
$\displaystyle+{}P(a_{2}=1\mid x_{1}x_{2}=01)$
$\displaystyle+{}P(a_{1}a_{2}=00\mid x_{1}x_{2}=11)$ (16) $\displaystyle+{}$
$\displaystyle P(b_{1}=1\mid y_{1}y_{2}=10)$ $\displaystyle+{}P(b_{2}=1\mid
y_{1}y_{2}=01)$ $\displaystyle+{}P(b_{1}b_{2}=00\mid y_{1}y_{2}=11)$
$\displaystyle+{}$ $\displaystyle P(c_{1}=1\mid z_{1}z_{2}=10)$
$\displaystyle+{}P(c_{2}=1\mid z_{1}z_{2}=01)$
$\displaystyle+{}P(c_{1}c_{2}=00\mid z_{1}z_{2}=11)\big{]}$ $\displaystyle\leq
3.$

###### Proof.

See Appendix B. ∎

A violation of this inequality to the algebraic bound of 4 requires precisely
the possibilistic properties expressed in Eqs. (4) and (8), and is therefore
attained by precisely those probabilistic data that also admit a possibilistic
derivation of a contradiction with the conjunction of (5) and Assumptions 1
and 2 as in Sections 3–5—including the data $Q$ predicted for the quantum
switch scenario of Figure 2.

It is worth noting that, as Mermin did with his three-party GHZ scenario [8],
the three-switch scenario considered here can be suitably generalised to one
with $N>3$ spacelike-separated switches. Definite causal order and
relativistic causality then imply an inequality with bound
$2^{\lfloor(3N-4)/2\rfloor}$, which is violated by the switch scenario to the
algebraic maximum of $2^{2N-3}$. The proportional violation of the inequality
thus grows exponentially with $N$.

##  7 Discussion

When it was shown in [2, 3] that the quantum switch exhibits indefinite causal
order that can be device-independently tested, this meant that it predicts
probabilities that cannot be recovered from a joint _probability_ distribution
with a variable that constrains the causal order on _every_ run of the
experiment (in such a way that the order is always in accordance with
relativity theory). Here, we have strengthened that result in two ways.

First, the argument in Sections 3–5 relies only on the calculus of
possibilities, rather than probabilities, so it eliminates the assumption that
probability theory is applicable on the hidden variable level. This assumption
is nontrivial: even if the variables $\lambda_{A,B,C}$ are postulated to take
values on every run of the experiment, their frequencies might not converge to
probabilities satisfying the probability axioms. And while there are empirical
grounds for assuming such convergence in the case of observable quantities,
these do not necessarily apply to the causal order variables, as those might
be unobservable in principle. In addition, the possibilistic independence
assumptions involved in our argument of Sections 3–5 are much weaker than the
probabilistic ones required in [2, 3], with relativistic causality conditions
like (14) merely requiring that a choice of input cannot influence the
_possibility_ , rather than probability, of events that are spacelike-
separated or lie to its past.

The maximal violation of the causal Mermin inequality (16), meanwhile,
strengthens the results of [2, 3] by showing that the quantum switch (or any
other, say experimental, data that reach the algebraic maximum) is not even
compatible with a (probabilistic) hidden variable model that specifies a
causal order _sometimes_ : any nonzero fraction of runs in which all
operations are causally ordered and no superluminal influences occur leads to
a value strictly below the algebraic bound.111In the terminology of [3], this
means that the data have a causally separable fraction of 0% over the relevant
spaces of input histories. In this sense the device-independent indefinite
causal order in the quantum switch can be said to be maximal. It is shown in
Appendix C that this result can in fact also be achieved with a single quantum
switch, by using the idea of chained CHSH inequalities [11] and taking an
appropriate limit.

Our proofs are much like those of Bell nonlocality by GHZ and Mermin, except
that the existence of hidden variables predetermining measurement outcomes is
derived from the definite causal order assumption together with properties of
the data, rather than directly assumed or concluded from an EPR argument. This
connection between Bell nonlocality and indefinite causal order, initially
discovered in [2] in the context of a CHSH inequality, thus extends to
possibilistic arguments as well. In light of this connection, this work and
[2] can be compared to recent works on extended Wigner’s friend scenarios (see
for instance Refs. [12, 13, 14]), in which not a definite causal order, but
the observation of an agent is what predetermines a measurement outcome.222
Our notion of relativistic causality is analogous to what is called Locality
or Local Agency in [12, 13], and to what is known as parameter independence
(and measurement independence) in the context of Bell’s theorem [15]. It is
strictly weaker than the kind of locality already ruled out by Bell [4], GHZ
[7] and Mermin [6]. On its own it is consistent with quantum physics; only in
the presence of another assumption, like definite causal order (Theorems 1 and
2 and [2]), absoluteness of an agent’s observation [12, 13], determinism
(Section 2 and [4, 5]), or alternatively, outcome independence [15, 8], can
contradictions be derived.  It will be worth investigating what other device-
independent tests can be devised using this method, going beyond causal order
and Wigner’s friend scenarios.

Another important direction for future work is to understand the physical
implications of experimental violations of the inequalities presented here and
in [2]. The notion of causal order, and whether it is definite or not,
naturally depends on what is being ordered, i.e. on what are taken as the
relata of the causal relations. In the device-independent treatment, it is
customary to assume that each relatum covers both the choosing of an input and
the generation of an output. This is the approach taken here and in [2, 3].
This tradition goes back to Bell’s theorem, in which such input-output pairs
can be confined to a small spacetime region. Current implementations of the
quantum switch however necessitate that the inputs of the operations inside
the switch are chosen early, and the outcomes are only measured after
execution of the switch [16, 17]. Consequently, (classical) relativity theory
does not rule out two-way communication between the regions occupied by the
input-output pairs. Is indefinite causal order with respect to these relata
then still an interesting physical phenomenon, or is another choice of relata
more natural? Answering these questions might require a more in-depth analysis
which investigates whether such two-way communication is indeed facilitated by
the used experimental setups.

## Acknowledgements

We would like to thank Jonathan Barrett, Giulio Chiribella, Marc-Olivier Renou
and Nicola Pinzani for insightful discussions. This research was funded in
part by the Engineering and Physical Sciences Research Council (EPSRC), and
was supported by the John Templeton Foundation through the ID# 62312 grant, as
part of the ‘The Quantum Information Structure of Spacetime’ Project (QISS).
The opinions expressed in this publication are those of the authors and do not
necessarily reflect the views of the John Templeton Foundation. For the
purpose of Open Access, the authors have applied a CC BY public copyright
licence to any Author Accepted Manuscript (AAM) version arising from this
submission.

## References

  * [1] Giulio Chiribella, Giacomo Mauro D’Ariano, Paolo Perinotti, and Benoit Valiron.  “Quantum computations without definite causal structure”.  Physical Review A 88, 022318 (2013).  arxiv:0912.0195.
  * [2] Tein van der Lugt, Jonathan Barrett, and Giulio Chiribella.  “Device-independent certification of indefinite causal order in the quantum switch”.  Nature Communications 14, 5811 (2023).  arxiv:2208.00719.
  * [3] Stefano Gogioso and Nicola Pinzani.  “The Geometry of Causality” (2023).  arxiv:2303.09017.
  * [4] John Stewart Bell.  “On the Einstein Podolsky Rosen paradox”.  Physics 1, 195–200 (1964).
  * [5] Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger.  “Going Beyond Bell’s Theorem”.  In Menas Kafatos, editor, Bell’s Theorem, Quantum Theory and Conceptions of the Universe.  Pages 69–72.  Springer Netherlands, Dordrecht (1989).
  * [6] N. David Mermin.  “Quantum mysteries revisited”.  American Journal of Physics 58, 731–734 (1990).
  * [7] Daniel M. Greenberger, Michael A. Horne, Abner Shimony, and Anton Zeilinger.  “Bell’s theorem without inequalities”.  American Journal of Physics 58, 1131–1143 (1990).
  * [8] N. David Mermin.  “Extreme quantum entanglement in a superposition of macroscopically distinct states”.  Physical Review Letters 65, 1838–1840 (1990).
  * [9] A. Einstein, B. Podolsky, and N. Rosen.  “Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?”.  Physical Review 47, 777–780 (1935).
  * [10] G. Chiribella, G. M. D’Ariano, and P. Perinotti.  “Transforming quantum operations: Quantum supermaps”.  EPL (Europhysics Letters) 83, 30004 (2008).  arxiv:0804.0180.
  * [11] Samuel L Braunstein and Carlton M. Caves.  “Wringing Out Better Bell inequalities”.  Annals of Physics 202, 22–56 (1990).
  * [12] Kok Wei Bong, Aníbal Utreras-Alarcón, Farzad Ghafari, Yeong Cherng Liang, Nora Tischler, Eric G. Cavalcanti, Geoff J. Pryde, and Howard M. Wiseman.  “A strong no-go theorem on the Wigner’s friend paradox”.  Nature Physics 16, 1199–1205 (2020).  arxiv:1907.05607.
  * [13] Marwan Haddara and Eric G. Cavalcanti.  “A possibilistic no-go theorem on the Wigner’s friend paradox”.  New Journal of Physics 25, 093028 (2023).  arxiv:2205.12223.
  * [14] Nick Ormrod, V. Vilasini, and Jonathan Barrett.  “Which theories have a measurement problem?” (2023).  arxiv:2303.03353.
  * [15] Abner Shimony.  “Events and processes in the quantum world”.  In Roger Penrose and Christopher J. Isham, editors, Quantum Concepts in Space and Time.  Oxford University Press (1986).
  * [16] Giulia Rubino, Lee A. Rozema, Adrien Feix, Mateus Araújo, Jonas M. Zeuner, Lorenzo M. Procopio, Časlav Brukner, and Philip Walther.  “Experimental verification of an indefinite causal order”.  Science Advances 3, e1602589 (2017).  arxiv:1608.01683.
  * [17] Huan Cao, Jessica Bavaresco, Ning-Ning Wang, Lee A. Rozema, Chao Zhang, Yun-Feng Huang, Bi-Heng Liu, Chuan-Feng Li, Guang-Can Guo, and Philip Walther.  “Semi-device-independent certification of indefinite causal order in a photonic quantum switch”.  Optica 10, 561 (2023).  arxiv:2202.05346.
  * [18] Bob Coecke and Aleks Kissinger.  “Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning”.  Cambridge University Press. (2017).  1 edition.
  * [19] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt.  “Proposed Experiment to Test Local Hidden-Variable Theories”.  Physical Review Letters 23, 880–884 (1969).
  * [20] Jonathan Barrett, Adrian Kent, and Stefano Pironio.  “Maximally Nonlocal and Monogamous Quantum Correlations”.  Physical Review Letters 97, 170409 (2006).  arxiv:quant-ph/0605182.

left=3cm,right=3cm,top=3cm,bottom=3cm

##  Appendix A The quantum switch correlations and formalisation of
Observations 1 and 2

Here we describe in more detail the outcome probabilities (and thus
possibilities) arising in the three-switch scenario described in the main
text. We then state and prove formal versions of Observations 1 and 2.

The interventions of each of the nine agents
$\mathcal{A}_{1,2,3},\mathcal{B}_{1,2,3},\mathcal{C}_{1,2,3}$ can, for each
value of their classical input variable, be described by a quantum instrument,
i.e. a quantum operation with a classical outcome. A quantum instrument, with
input and output systems described by Hilbert spaces $\mathcal{H}$ and
$\mathcal{K}$ and with finite classical outcome set $E$, is a collection of
completely positive (CP) maps
$\\{\mathcal{E}^{e}:\mathcal{B}(\mathcal{H})\to\mathcal{B}(\mathcal{K})\\}_{e\in
E}$ that sum to a trace-preserving map $\sum_{e\in E}\mathcal{E}^{e}$. (Here
$\mathcal{B}(\mathcal{H})$ and $\mathcal{B}(\mathcal{K})$ are the spaces of
bounded linear operators on $\mathcal{H}$ and $\mathcal{K}$.) Each map
$\mathcal{E}^{e}$ represents the quantum operation that ends up being
performed in case outcome $e$ is observed.

For $i=1,2$, the instrument performed by $\mathcal{A}_{i}$ on the target
system $T_{A}$ for a fixed value of $x_{i}$, described intuitively in the main
text, is defined by the CP maps
$\mathcal{A}_{i}^{a_{i}|x_{i}}:\mathcal{B}(\mathcal{H}_{T_{A}})\to\mathcal{B}(\mathcal{H}_{T_{A}})$
given by

$\displaystyle\mathcal{A}_{i}^{a_{i}|x_{i}=0}$
$\displaystyle=\delta_{a_{i}=0}\cdot\operatorname{id}_{T_{A}}$ (17a)
$\displaystyle\text{and\quad}\mathcal{A}_{i}^{a_{i}|x_{i}=1}(\rho_{T_{A}})$
$\displaystyle=\outerproduct{1}{a_{i}}\\!\rho_{T_{A}}\\!\outerproduct{a_{i}}{1},$
(17b)

where $\operatorname{id}_{T_{A}}$ is the identity operation on
$\mathcal{B}(\mathcal{H}_{T_{A}})$ and $\delta_{a_{i}=0}$ is $1$ if $a_{i}=0$
and 0 otherwise. $\mathcal{A}_{3}$ performs a projective measurement in the
$Y$ basis, described by CP maps
$\mathcal{A}_{3}^{a_{3}}:\mathcal{B}(\mathcal{H}_{C_{A}})\to\mathcal{B}(\mathbb{C})$
with trivial output system:

$\mathcal{A}_{3}^{a_{3}=0}(\rho_{C_{A}})=\expectationvalue{\rho_{C_{A}}}{+i};\qquad\mathcal{A}_{3}^{a_{3}=1}(\rho_{C_{A}})=\expectationvalue{\rho_{C_{A}}}{-i}.$
(18)

Together, when situated in one wing of the quantum switch setup considered in
the main text, these instruments define the ‘joint’ instrument
$\\{\mathcal{A}^{\mathbfit a|\mathbfit
x}:\mathcal{B}(\mathcal{H}_{C_{A}})\to\mathcal{B}(\mathcal{H}_{C_{A}})\\}_{\mathbfit
a}$, with

$\mathcal{A}^{\mathbfit a|\mathbfit
x}(\rho_{C_{A}})\coloneqq\left((\mathcal{A}_{3}^{a_{3}}\otimes\Tr_{T_{A}})\circ\operatorname{\textsc{switch}}(\mathcal{A}_{1}^{a_{1}|x_{1}},\mathcal{A}_{2}^{a_{2}|x_{2}})\right)(\rho_{C_{A}}\otimes\outerproduct{0}{0}_{T_{A}}).$
(19)

The joint instruments $\mathcal{B}^{\mathbfit b|\mathbfit y}$ and
$\mathcal{C}^{\mathbfit c|\mathbfit z}$ are defined similarly. The joint
probabilities of the outcomes $\mathbfit a,\mathbfit b,\mathbfit c$ given
inputs $\mathbfit x,\mathbfit y,\mathbfit z$ are then given by the
distribution

$Q(\mathbfit a\mathbfit b\mathbfit c\mid\mathbfit x\mathbfit y\mathbfit
z)\coloneqq\left(\mathcal{A}^{\mathbfit a|\mathbfit
x}\otimes\mathcal{B}^{\mathbfit b|\mathbfit y}\otimes\mathcal{C}^{\mathbfit
c|\mathbfit
z}\right)\left(\outerproduct{\mathrm{GHZ}}{\mathrm{GHZ}}_{C_{A}C_{B}C_{C}}\right),$
(20)

which is defined diagrammatically [18] in Figure 2. Finally, together with a
distribution over the input variables $Q(\mathbfit x\mathbfit y\mathbfit z)$,
this gives a probability distribution $Q(\mathbfit a\mathbfit b\mathbfit
c\mathbfit x\mathbfit y\mathbfit z)$, which in turn leads to the possibility
distribution $q(\mathbfit a\mathbfit b\mathbfit c\mathbfit x\mathbfit
y\mathbfit z)$ considered in the main text.

It is straightforward to verify that the marginals of this distribution
satisfy the conditions (8) of Lemma 1. We can now also formalise and prove
Observations 1 and 2 from the main text. This is done by Lemmas 2 and 3 below,
respectively.

######  Lemma 2.

We have

$\mathcal{A}^{\mathbfit a|\mathbfit
x=\mathbf{0}}(\rho_{C_{A}})=\delta_{a_{1}=a_{2}=0}\cdot\mathcal{A}_{3}^{a_{3}}(\rho_{C_{A}}).$
(21)

###### Proof.

This follows from the fact that
$\operatorname{\textsc{switch}}\left(\operatorname{id}_{T_{A}},\operatorname{id}_{T_{A}}\right)=\operatorname{id}_{C_{A}T_{A}}$,
which is evident from the definition of the quantum switch in Eq. (3). ∎

######  Lemma 3.

We have

$\sum_{a_{2}a_{3}}\mathcal{A}^{\mathbfit a|\mathbfit
x=\mathbf{1}}(\rho_{C_{A}})=\begin{cases}\expectationvalue{\rho_{C_{A}}}{+}&\text{
if }a_{1}=0;\\\ \expectationvalue{\rho_{C_{A}}}{-}&\text{ if
}a_{1}=1.\end{cases}$ (22)

###### Proof.

We prove the fact for pure states
$\rho_{C_{A}}=\outerproduct{\psi}{\psi}_{C_{A}}$; by linearity this implies
the result for mixed states too. From the definition of the quantum switch (3)
and the quantum instruments (17b, 19), we have

$\begin{split}\mathcal{A}^{\mathbfit a|\mathbfit
x=\mathbf{1}}(\outerproduct{\psi}{\psi}_{C_{A}})=\Big{\|}\bra{(-1)^{a_{3}}i}\Big{(}&\outerproduct{+}{+}_{C_{A}}\otimes\ket{1}\innerproduct{a_{2}}{1}\bra{a_{1}}_{T_{A}}+\\\
&\outerproduct{-}{-}_{C_{A}}\otimes\ket{1}\innerproduct{a_{1}}{1}\bra{a_{2}}_{T_{A}}\Big{)}\ket{\psi}_{C_{A}}\ket{0}_{T_{A}}\Big{\|}^{2}.\end{split}$
(23)

If $a_{1}=0$ then the second term (in which $\mathcal{A}_{1}$ is after
$\mathcal{A}_{2}$) vanishes, giving

$\mathcal{A}^{\mathbfit a|\mathbfit
x=\mathbf{1}}(\outerproduct{\psi}{\psi}_{C_{A}})=\left|\innerproduct{(-1)^{a_{3}}i}{+}_{C_{A}}\innerproduct{+}{\psi}_{C_{A}}\cdot\delta_{a_{2}=1}\right|^{2}$
(24)

so that

$\sum_{a_{2}a_{3}}\mathcal{A}^{\mathbfit a|\mathbfit
x=\mathbf{1}}(\outerproduct{\psi}{\psi}_{C_{A}})=\left|\innerproduct{+}{\psi}\right|^{2}.$
(25)

The case for $a_{1}=1$ is similar. ∎

Together with the known GHZ correlations (1), these facts imply the
correlations in (4), used in our possibilistic argument, as well as the fact
that the quantum switch setup violates, with the choice of instruments
described here, the causal Mermin inequality (16) to the algebraic bound of 4.

##  Appendix B Proof of Theorem 2

In the below, probabilistic conditional independence will be denoted as

$\displaystyle
a\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}b\mid
c\quad$ $\displaystyle:\\!\iff\quad\forall a,b,c:P(ab|c)=P(a|c)P(b|c)$ (26)
$\displaystyle\text{and}\quad
a\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}b\mid
c=i\quad$ $\displaystyle:\\!\iff\quad\forall a,b:P(ab|c=i)=P(a|c=i)P(b|c=i)$
(27)

$a\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}b$
denotes unconditional independence $\forall a,b:P(ab)=P(a)P(b)$. The following
is a restatement of Theorem 2.

######  Theorem.

Let
$P(a_{1}a_{2}a_{3}b_{1}b_{2}b_{3}c_{1}c_{2}c_{3}x_{1}x_{2}y_{1}y_{2}z_{1}z_{2}\lambda_{A}\lambda_{B}\lambda_{C})\eqqcolon
P(\mathbfit a\mathbfit b\mathbfit c\mathbfit x\mathbfit y\mathbfit
z\lambda_{A}\lambda_{B}\lambda_{C})$ be a probability distribution on
variables taking values in $\\{0,1\\}$ that satisfies the following
conditions, physically motivated as in the main text by the assumptions of
free interventions, definite causal order, and relativistic causality 333Note
that unlike the other conditions in 28, condition (28f) does not have a
counterpart in the main text. In brief, that is because it is not needed when
assuming the perfect theoretical predictions of the quantum switch data,
whilst in this appendix we wish to accommodate for noise or data that
otherwise deviate from those of the quantum switch. The justification for
(28f), just like (28e), is the principle of relativistic causality..

$\displaystyle\forall\mathbfit x\mathbfit y\mathbfit z:P(\mathbfit x\mathbfit
y\mathbfit z)$ $\displaystyle>0;$ (28a) $\displaystyle
a_{1}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}x_{2}\mid\lambda_{A}=0;\qquad$
$\displaystyle
a_{2}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}x_{1}\mid\lambda_{A}=1;$
(28b) $\displaystyle
b_{1}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}y_{2}\mid\lambda_{B}=0;\qquad$
$\displaystyle
b_{2}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}y_{1}\mid\lambda_{B}=1;$
(28c) $\displaystyle
c_{1}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}z_{2}\mid\lambda_{C}=0;\qquad$
$\displaystyle
c_{2}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}z_{1}\mid\lambda_{C}=1;$
(28d)
$\displaystyle\lambda_{A}\lambda_{B}\lambda_{C}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}\mathbfit
x\mathbfit y\mathbfit
z;\qquad\lambda_{A}b_{3}c_{3}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}\mathbfit
x\mid\mathbfit y\mathbfit z;\qquad$ $\displaystyle
a_{3}\lambda_{B}c_{3}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}\mathbfit
y\mid\mathbfit x\mathbfit z;\qquad
a_{3}b_{3}\lambda_{C}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}\mathbfit
z\mid\mathbfit x\mathbfit y;$ (28e) $\displaystyle
a_{1}a_{2}\lambda_{A}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}\mathbfit
y\mathbfit z\mid\mathbfit x;\qquad
b_{1}b_{2}\lambda_{B}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}\mathbfit
x$ $\displaystyle\mathbfit z\mid\mathbfit y;\qquad
c_{1}c_{2}\lambda_{C}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}\mathbfit
x\mathbfit y\mid\mathbfit z.$ (28f)

Then $P$ satisfies the inequality

$\displaystyle P(a_{1}\oplus b_{1}\oplus c_{1}=0\mid\mathbfit
x=\mathbf{1},\mathbfit y=\mathbf{1},\mathbfit z=\mathbf{1})+P(a_{1}\oplus
b_{3}\oplus c_{3}=1\mid\mathbfit x=\mathbf{1},\mathbfit y=\mathbf{0},\mathbfit
z=\mathbf{0})$ $\displaystyle+{}$ $\displaystyle P(a_{3}\oplus b_{1}\oplus
c_{3}=1\mid\mathbfit x=\mathbf{0},\mathbfit y=\mathbf{1},\mathbfit
z=\mathbf{0})+P(a_{3}\oplus b_{3}\oplus c_{1}=1\mid\mathbfit
x=\mathbf{0},\mathbfit y=\mathbf{0},\mathbfit z=\mathbf{1})$
$\displaystyle-{}2\big{[}\ $ $\displaystyle P(a_{1}=1\mid x_{1}x_{2}=10)$
$\displaystyle+{}P(a_{2}=1\mid x_{1}x_{2}=01)$
$\displaystyle+{}P(a_{1}a_{2}=00\mid x_{1}x_{2}=11)$ (29) $\displaystyle+{}$
$\displaystyle P(b_{1}=1\mid y_{1}y_{2}=10)$ $\displaystyle+{}P(b_{2}=1\mid
y_{1}y_{2}=01)$ $\displaystyle+{}P(b_{1}b_{2}=00\mid y_{1}y_{2}=11)$
$\displaystyle+{}$ $\displaystyle P(c_{1}=1\mid z_{1}z_{2}=10)$
$\displaystyle+{}P(c_{2}=1\mid z_{1}z_{2}=01)$
$\displaystyle+{}P(c_{1}c_{2}=00\mid z_{1}z_{2}=11)\big{]}$ $\displaystyle\leq
3.$

###### Proof.

The proof consists of two parts: we will first see that definite causal order
(28b)–(28d) implies some amount of determinism, quantified by the last three
lines of the inequality, and then how that determinism, together with
relativistic causality (28e)–(28f), provides a Mermin-like bound on the first
two lines of the inequality. (The first part parallels our going from (4) to
(13) in the main text, while the second parallels the transition to (15) by
relativistic causality.)

Denote the final three lines in the inequality by $\alpha,\beta$ and $\gamma$:

$\displaystyle\alpha$ $\displaystyle\coloneqq P(a_{1}=1\mid
x_{1}x_{2}=10)+P(a_{2}=1\mid x_{1}x_{2}=01)+P(a_{1}a_{2}=00\mid
x_{1}x_{2}=11);$ (30a) $\displaystyle\beta$ $\displaystyle\coloneqq
P(b_{1}=1\mid y_{1}y_{2}=10)+P(b_{2}=1\mid y_{1}y_{2}=01)+P(b_{1}b_{2}=00\mid
y_{1}y_{2}=11);$ (30b) $\displaystyle\gamma$ $\displaystyle\coloneqq
P(c_{1}=1\mid z_{1}z_{2}=10)+P(c_{2}=1\mid z_{1}z_{2}=01)+P(c_{1}c_{2}=00\mid
z_{1}z_{2}=11).$ (30c)

(The probabilities are independent of the omitted input variables by (28f).)
The following mirrors Lemma 1 in the main text, but is probabilistic and
robust to noise in the values of $\alpha,\beta,$ and $\gamma$.

######  Claim.

We have

$\displaystyle P(a_{1}=\lambda_{A}\mid\mathbfit x=\mathbf{1})$
$\displaystyle\geq 1-\alpha;$ (31a) $\displaystyle
P(b_{1}=\lambda_{B}\mid\mathbfit y=\mathbf{1})$ $\displaystyle\geq 1-\beta;$
(31b) $\displaystyle P(c_{1}=\lambda_{C}\mid\mathbfit z=\mathbf{1})$
$\displaystyle\geq 1-\gamma.$ (31c)

###### Proof.

For $i\in\\{0,1\\}$, define the probability distributions
$P^{i}(a_{1}a_{2}\lambda_{A}\mid
x_{1}x_{2})\coloneqq\delta_{\lambda_{A}=i}P(a_{1}a_{2}\mid
x_{1}x_{2},\lambda_{A}=i)$. By (28b), we have
$a_{1}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P^{0}}x_{2}$
and
$a_{2}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P^{1}}x_{1}$,
and so

$\displaystyle P^{0}(a_{1}=1\mid 11)$ $\displaystyle=P^{0}(a_{1}=1\mid
10)\leq\alpha;$ (32) $\displaystyle\begin{split}P^{1}(a_{1}=0\mid
11)&=P^{1}(a_{1}=0,a_{2}=0\mid 11)+P^{1}(a_{1}=0,a_{2}=1\mid 11)\\\ &\leq
P^{1}(a_{1}=0,a_{2}=0\mid 11)+P^{1}(a_{2}=1\mid 11)\\\
&=P^{1}(a_{1}=0,a_{2}=0\mid 11)+P^{1}(a_{2}=1\mid 01)\leq\alpha.\end{split}$
(33)

(Here the conditioned-upon variables are always $x_{1}$ and $x_{2}$.) In other
words, $P^{i}(a_{1}\neq\lambda\mid 11)\leq\alpha$ for both $i=0,1$. But
$P=P(\lambda=0)P^{0}+P(\lambda=1)P^{1}$, so this inequality also holds for
$P$. This implies (31a); (31b) and (31c) follow similarly. ∎

Thus, if $\alpha=0$, as is the case for the theoretical quantum switch data
discussed in the main text, then we could replace terms like $P(a_{1}\oplus
b_{1}\oplus c_{1}=0\mid\mathbfit x=\mathbfit y=\mathbfit z=1)$ in inequality
(29) with terms like
$P(\lambda_{A}\oplus\lambda_{B}\oplus\lambda_{C}=0\mid\mathbfit x=\mathbfit
y=\mathbfit z=1)$ and derive Mermin’s inequality directly. To generalise this
to other values of $\alpha$ (thereby making the result robust to noise), we
use the following fact about probabilities.

######  Lemma 4.

For a probability distribution $P$ over a set $\Omega$ and events
$A_{1},A_{2},\dots,A_{n}\subseteq\Omega$, we have

$P(A_{1})+P(A_{2})+\cdots+P(A_{n})\leq P(A_{1},A_{2},\dots,A_{n})+n-1.$ (34)

###### Proof.

This follows from $P(A_{1},A_{2})=P(A_{1})+P(A_{2})-P(A_{1}\lor A_{2})\geq
P(A_{1})+P(A_{2})-1$ for $n=2$ and induction. ∎

From this we get, for instance,

$\begin{split}P(a_{1}&\oplus b_{3}\oplus
c_{3}=1\mid\mathbf{100})+P(a_{1}=\lambda_{A}\mid\mathbf{100})\\\ &\leq
P(a_{1}\oplus b_{3}\oplus c_{3}=1,a_{1}=\lambda_{A}\mid\mathbf{100})+1\\\
&\leq P(\lambda_{A}\oplus b_{3}\oplus c_{3}=1\mid\mathbf{100})+1\\\
&=P(\lambda_{A}\oplus b_{3}\oplus c_{3}=1\mid\mathbf{000})+1,\end{split}$ (35)

where in the last equation we have used the relativistic causality condition
(28e). (Here we have suppressed the labels of the conditioned-upon variables,
which are $\mathbfit x$, $\mathbfit y$, and $\mathbfit z$, respectively.) Note
that by condition (28f) and the Claim above,

$P(a_{1}=\lambda_{A}\mid\mathbf{100})=P(a_{1}=\lambda_{A}\mid\mathbfit
x=\mathbf{1})\geq 1-\alpha.$ (36)

This, together with (35), implies (37b) below. The other inequalities can be
derived in a similar way.

$\displaystyle P(a_{1}\oplus b_{1}\oplus
c_{1}=0\mid\mathbf{111})-\alpha-\beta-\gamma$ $\displaystyle\leq
P(\lambda_{A}\oplus\lambda_{B}\oplus\lambda_{C}=0\mid\mathbf{000})$ (37a)
$\displaystyle P(a_{1}\oplus b_{3}\oplus c_{3}=1\mid\mathbf{100})-\alpha$
$\displaystyle\leq P(\lambda_{A}\oplus b_{3}\oplus c_{3}=1\mid\mathbf{000})$
(37b) $\displaystyle P(a_{3}\oplus b_{1}\oplus c_{3}=1\mid\mathbf{010})-\beta$
$\displaystyle\leq P(a_{3}\oplus\lambda_{B}\oplus c_{3}=1\mid\mathbf{000})$
(37c) $\displaystyle P(a_{3}\oplus b_{3}\oplus
c_{1}=1\mid\mathbf{001})-\gamma$ $\displaystyle\leq P(a_{3}\oplus
b_{3}\oplus\lambda_{C}=1\mid\mathbf{000})$ (37d)

The desired inequality (29) now follows by adding these equations together and
noting that the sum of the right-hand sides is bounded (similarly to Mermin’s
inequality [8]) by 3. This last fact follows from Lemma 4, and parallels the
derivation of the logical contradiction (15) in the main text:

$\begin{split}&\phantom{+}P(\lambda_{A}\oplus\lambda_{B}\oplus\lambda_{C}=0\mid\mathbf{000})+P(\lambda_{A}\oplus
b_{3}\oplus c_{3}=1\mid\mathbf{000})\\\ &+P(a_{3}\oplus\lambda_{B}\oplus
c_{3}=1\mid\mathbf{000})+P(a_{3}\oplus
b_{3}\oplus\lambda_{C}=1\mid\mathbf{000})\\\ &\leq
P(0=1\mid\mathbf{000})+3=3.\end{split}$ (38)

This concludes the proof of Theorem 2. ∎

##  Appendix C Chained inequalities

That the Mermin inequality (resp. causal Mermin inequality (16)) is violated
up to the algebraic maximum (i.e. the maximum value among all valid
probability distributions) implies that no fraction of the distribution allows
a local deterministic hidden variable model (resp. definite causal order model
satisfying relativistic causality). However, this only implies that it is
never the case that all of the three switches have a causal order
simultaneously. Here we show that a similar result can be derived for a single
quantum switch, by using the idea of chained Bell inequalities introduced by
Braunstein and Caves [11], which are violated to the algebraic maximum in the
limit of a large number of measurement settings $N$.

We first recall Braunstein and Caves’s chained inequalities as they apply to
Bell nonlocality. Consider a scenario with two spacelike-separated parties
$\mathcal{A}$ and $\mathcal{B}$, having inputs $x,y\in\\{0,1,\dots,N-1\\}$ and
outputs $a,b\in\\{0,1\\}$. Any choice of a pair of values for $x$ as well as
for $y$ can be used to define a Clauser-Horne-Shimony-Holt (CHSH) expression:
more precisely, for any probability distribution $R(ab|xy)$ and
$\xi_{0},\xi_{1},\upsilon_{0},\upsilon_{1}\in\\{0,1,\dots,N-1\\}$, define

$\begin{split}\operatorname{CHSH}_{\xi_{0},\xi_{1};\upsilon_{0},\upsilon_{1}}[R]&\coloneqq
R(a=b\mid x=\xi_{0},y=\upsilon_{0})\\\ &+R(a=b\mid
x=\xi_{1},y=\upsilon_{0})\\\ &+R(a=b\mid x=\xi_{1},y=\upsilon_{1})\\\
&-R(a=b\mid x=\xi_{0},y=\upsilon_{1}).\\\ \end{split}$ (39)

Summing an appropriate set of such CHSH expressions together defines the
Braunstein-Caves expression

$\displaystyle\operatorname{BC}_{N}[R]$
$\displaystyle\coloneqq\sum_{i=0}^{N-1}\operatorname{CHSH}_{0,i;i-1,i}[R]$
(40) $\displaystyle\begin{split}&=\sum_{i=0}^{N-1}\left[R(a_{3}=b\mid
x_{3}=i,y=i)+R(a_{3}=b\mid x_{3}=i+1,y=i)\right]\\\
&\phantom{\sum_{i=0}^{N-1}[R(a_{3}=b}+R(a_{3}=b|x_{3}=N,y=N)-R(a_{3}=b|x_{3}=0,y=N).\end{split}$
(41)

The classical bound for each of the CHSH expressions is 2 [19], leading to an
overall classical bound of

$\operatorname{BC}_{N}[R]\leq 2N.$ (42)

The algebraic maximum of $\operatorname{BC}_{N}[R]$, on the other hand, can be
read off from (41) to be $2N+1$.

A high quantum value for $\operatorname{BC}_{N}$ can be achieved by letting
$\mathcal{A}$ and $\mathcal{B}$ measure the two parts of the Bell state
$\ket{\Phi^{+}}$ in the measurement directions shown in Figure 5. The
directions are spaced an angle $\theta=\pi/(N+1)$ apart on the Bloch sphere.
All terms in the expansion (41) except the last involve a neighbouring pair of
measurement directions, yielding a probability of $\cos^{2}\theta/2$. In
total, the quantum value is

$\begin{split}\operatorname{BC}_{N}[R]&=(2N+1)\cos^{2}\frac{\theta}{2}-\left(1-\cos^{2}\frac{\theta}{2}\right)\\\
&=(N+1)\left(\cos\frac{\pi}{N+1}+1\right)-1\quad\xrightarrow{N\gg 1}\quad
2N+1,\end{split}$ (43)

which approaches the algebraic maximum in the limit of large $N$.

A crucial observation is that the classical bound of 2 for a CHSH expressions
follows (under additional requirements sometimes called measurement
independence and parameter independence) not only from the assumption that all
measurements outcomes are predetermined, but also from the weaker requirement
that only $\mathcal{A}$’s outcome $a$ for one of her inputs $x$ is
predetermined. Because all CHSH expressions in (40) involve the input $x=0$,
this means that the classical bound $\operatorname{BC}_{N}[R]\leq 2N$ also
holds when only the $x=0$ measurement is predetermined. This will allow us to
make the translation from Bell nonlocality to indefinite causal order in the
quantum switch, by using a quantum switch to simulate the $x=0$ measurement
(in the spirit of Observation 1 in the main text), while noting that the
definite causal order assumption implies predetermination of that measurement
(in the spirit of Lemma 1).

The relevant quantum switch scenario is depicted in Figure 5. The quantum
switch is now controlled in the $Z$ basis (rather than $X$, as in the main
text). $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ perform the same quantum
instruments as described in the main text and Appendix A. $\mathcal{A}_{3}$
and $\mathcal{B}$ perform measurements on the output control qubit and a qubit
$B$ entangled to the input control qubit, respectively. Their inputs $x_{3},y$
take values in $\\{0,1,\dots,N\\}$ and their measurement directions are
identical to those in the usual chained inequality scenario just described
(Figure 5). All other variables are binary, as in the main text. This setup
defines a conditional probability distribution
$Q(a_{1}a_{2}a_{3}b|x_{1}x_{2}x_{3}y)$, which in turn defines an unconditional
probability distribution $Q(a_{1}a_{2}a_{3}bx_{1}x_{2}x_{3}y)$ by assuming
uniform distribution of the inputs: $Q(x_{1}x_{2}x_{3}y)=1/4N^{2}$.

In the main text, our first step was to find a subset of the quantum switch
data that exhibited GHZ-like correlations (i.e. going from (1) to (4)).
Likewise, here we will need to find a subset of the data $Q$ that behaves as
$R$ in (43) above, i.e. which violates the Braunstein-Caves inequality to the
algebraic maximum in the limit of large $N$. To do this, note that one can
consider $\mathcal{A}_{3}$ and $\mathcal{B}$ as performing a Braunstein-Caves
test on the shared entangled state $\ket{\Phi^{+}}$, with two differences.
First of all, when $x_{3}=0$, we need to ensure that $x_{1}=x_{2}=1$ and let
$\mathcal{A}_{3}$ output $a_{1}$, as that is a simulation of the computational
basis measurement (Observation 2). When $x_{3}\neq 0$, on the other hand, we
need to ensure that $x_{1}=x_{2}=0$, so that the outcome $a_{3}$ is not
disturbed by the presence of the quantum switch (Observation 1). The data in
$Q$ that are relevant to the derivation and violation of Braunstein-Caves
inequalities is therefore summarised in the distribution $R_{Q}$ defined in
(45) below.

$T$$C$$C$$T$$\mathcal{E}$switch$\mathcal{F}$$\mathcal{E}$$T$$T$,$\mathcal{F}$$T$$T$$\longmapsto$switchghz$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch$x_{1}$$a_{1}$0$a_{3}$$T_{B}$$C_{B}$$C_{B}$$T_{B}$switch0$T_{C}$$C_{C}$$C_{C}$$T_{C}$switch0$\lambda_{A}$$\lambda_{B}$$\lambda_{C}$$\mathcal{A}_{3}$$\mathcal{A}_{1}$$x_{2}$$a_{2}$$\mathcal{A}_{2}$$z_{1}$$c_{1}$$\mathcal{C}_{1}$$z_{2}$$c_{2}$$\mathcal{C}_{2}$$y_{1}$$b_{1}$$\mathcal{B}_{1}$$y_{2}$$b_{2}$$\mathcal{B}_{2}$$b_{3}$$\mathcal{B}_{3}$$c_{3}$$\mathcal{C}_{3}$$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch0ghz$\large=$$C_{A}$ghz$a_{3}$$a_{3}$$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch$1$0ghz$\large=$$C_{A}$ghz$a_{1}$$X$
mmt$a_{1}$$Z$ mmt$1$

⋮

$\theta$$x=0$$y=0$$x=1$$y=1$$x=N$$y=N$$Z$$X$ Figure 4: Directions of qubit
measurements in the $Z$-$X$ plane that yield a value of the Braunstein-Caves
quantity $\operatorname{BC}_{N}$ converging to the algebraic maximum.

$T$$C$$C$$T$$\mathcal{E}$switch$\mathcal{F}$$\mathcal{E}$$T$$T$,$\mathcal{F}$$T$$T$$\longmapsto$switchghz$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch$x_{1}$$a_{1}$0$a_{3}$$T_{B}$$C_{B}$$C_{B}$$T_{B}$switch0$T_{C}$$C_{C}$$C_{C}$$T_{C}$switch0$\lambda_{A}$$\lambda_{B}$$\lambda_{C}$$\mathcal{A}_{3}$$\mathcal{A}_{1}$$x_{2}$$a_{2}$$\mathcal{A}_{2}$$z_{1}$$c_{1}$$\mathcal{C}_{1}$$z_{2}$$c_{2}$$\mathcal{C}_{2}$$y_{1}$$b_{1}$$\mathcal{B}_{1}$$y_{2}$$b_{2}$$\mathcal{B}_{2}$$b_{3}$$\mathcal{B}_{3}$$c_{3}$$\mathcal{C}_{3}$$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch0ghz$\large=$$C_{A}$ghz$a_{3}$$a_{3}$$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch$1$0ghz$\large=$$C_{A}$ghz$a_{1}$$X$
mmt$a_{1}$$Z$ mmt$1$

⋮

$\theta$$x=0$$y=0$$x=1$$y=1$$x=N$$y=N$$Z$$X$$\Phi^{+}$$T_{A}$$C_{A}$$C_{A}$$T_{A}$switch$x_{1}$$a_{1}$0$a_{3}$$\mathcal{A}_{3}$$\mathcal{A}_{1}$$x_{2}$$a_{2}$$\mathcal{A}_{2}$$x_{3}$$B$$b$$\mathcal{B}$$y$

…

…

Figure 5: Quantum switch setup producing correlations that violate the causal
Braunstein-Caves inequality (47) to the algebraic maximum in the limit of
large $N$. The measurement directions of $\mathcal{A}_{3}$ and $\mathcal{B}$
are as in Figure 5.

We then get the following theorem. As in the main text, the conditions (44)
are motivated by the assumptions of free interventions, definite causal order,
and relativistic causality.

######  Theorem 3.

Let $\lambda$ be a random variable with domain $\\{0,1\\}$. Suppose the
probability distribution $P(a_{1}a_{2}a_{3}bx_{1}x_{2}x_{3}y\lambda)$
satisfies

$\displaystyle\forall x_{1}x_{2}x_{3}y:P(x_{1}x_{2}$ $\displaystyle
x_{3}y)>0;$ (44a)
$\displaystyle\lambda\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}x_{1}x_{2}$
$\displaystyle x_{3}y;$ (44b) $\displaystyle
a_{1}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}x_{2}\mid\lambda=0;\qquad$
$\displaystyle
a_{2}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}x_{1}\mid\lambda=1;$
(44c) $\displaystyle\lambda
b\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}x_{1}x_{2}x_{3}\mid
y;\qquad\lambda
a_{1}a_{2}a_{3}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}y$
$\displaystyle\mid x_{1}x_{2}x_{3};\qquad\lambda
a_{1}a_{2}\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{P}x_{3}y\mid
x_{1}x_{2},$ (44d)

and let

$R_{P}(ab\lambda\mid x_{3}y)\coloneqq\begin{cases}P(a_{1}=a,b,\lambda\mid
x_{1}=x_{2}=1,x_{3},y)&\quad\text{if }x_{3}=0;\\\ P(a_{3}=a,b,\lambda\mid
x_{1}=x_{2}=0,x_{3},y)&\quad\text{if }x_{3}\neq 0\end{cases}$ (45)

and

$\alpha[P]\coloneqq P(a_{1}=1\mid x_{1}x_{2}=10)+P(a_{2}=1\mid
x_{1}x_{2}=01)+P(a_{1}a_{2}=00\mid x_{1}x_{2}=11).$ (46)

Then $P$ satisfies the inequality

$\operatorname{BC}_{N}[R_{P}]-2N\alpha[P]\leq 2N.$ (47)

The quantum value of this expression is

$\operatorname{BC}_{N}[R_{Q}]-2N\alpha[Q]=(N+1)\left(\cos\frac{\pi}{N+1}+1\right)-1.$
(48)

###### Proof.

$R_{P}$ satisfies measurement and parameter independence, i.e. the conditions

$\lambda\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{R_{P}}x_{3}y,\quad
a\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{R_{P}}y\mid
x_{3}\lambda,\quad\text{ and }\quad
b\mathrel{\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}}_{R_{P}}x_{3}\mid
y\lambda.$ (49)

This means we can use the monogamy inequality of Ref. [20] to obtain

$\operatorname{CHSH}_{0,i;i-1,i}[R_{P}]\leq
4-2R_{P}(a=\lambda|x_{3}=0)\quad\text{ for any }i\in\\{0,1,\dots,N-1\\}.$ (50)

But by definition of $R_{P}$ and the definite causal order assumption (44c),
we get, via an argument similar to that for (31a),

$R_{P}(a=\lambda|x_{3}=0)=P(a_{1}=\lambda|x_{1}=x_{2}=1)\geq 1-\alpha[P].$
(51)

Thus

$\operatorname{CHSH}_{0,i;i-1,i}[R_{P}]-2\alpha[P]\leq 2,$ (52)

and summing over $i$ implies the sought-after inequality (47).

The quantum switch correlations $Q$, on the other hand, yield—by virtue of
versions of Observations 1 and 2 or Lemmas 2 and 3 in Appendix A—a value of
$\operatorname{BC}_{N}[R_{Q}]$ identical to that given in (43), and a value of
0 for $\alpha[Q]$, thus giving (48). ∎

######  Corollary 1.

Suppose $Q(a_{1}a_{2}a_{3}bx_{1}x_{2}x_{3}y)$ satisfies (48) and also admits a
hidden variable model $Q(a_{1}a_{2}a_{3}bx_{1}x_{2}x_{3}y\lambda)$ satisfying
(44), but where $\lambda$ now ranges over $\\{0,1,\bot\\}$. Here
$\lambda=\bot$ denotes the absence of a (relativistically well-behaved) causal
order. Then the fraction of runs with a definite causal order is

$Q(\lambda\in\\{0,1\\})\leq(N+1)\left(1-\cos\frac{\pi}{N+1}\right)\to
0\quad\text{ as }\quad N\to\infty.$ (53)

###### Proof.

Write $Q$ as the convex sum
$Q=Q(\lambda\in\\{0,1\\})Q^{\\{0,1\\}}+Q(\lambda=\bot)Q^{\bot}$, where

$\displaystyle Q^{\\{0,1\\}}(a_{1}a_{2}a_{3}bx_{1}x_{2}x_{3}y\lambda)$
$\displaystyle\coloneqq
Q(a_{1}a_{2}a_{3}bx_{1}x_{2}x_{3}y\lambda\mid\lambda\in\\{0,1\\})$ (54)
$\displaystyle\text{and\quad}Q^{\bot}(a_{1}a_{2}a_{3}bx_{1}x_{2}x_{3}y\lambda)$
$\displaystyle\coloneqq
Q(a_{1}a_{2}a_{3}bx_{1}x_{2}x_{3}y\lambda\mid\lambda=\bot).$ (55)

Theorem 3 gives

$\operatorname{BC}_{N}\left[R_{Q^{\\{0,1\\}}}\right]-2N\operatorname{\alpha}\left[Q^{\\{0,1\\}}\right]\leq
2N.$ (56)

Because the algebraic maximum of $\operatorname{BC}_{N}$ is $2N+1$ and the
inequality is linear, this implies

$\operatorname{BC}_{N}\left[R_{Q}\right]-2N\operatorname{\alpha}\left[Q\right]\leq
2N+Q(\lambda=\bot)=2N+1-Q(\lambda\in\\{0,1\\}).$ (57)

Inserting (48) and rearranging gives the result. ∎