# Simulating the quantum switch with quantum circuits is computationally hard

Jessica Bavaresco, Hlér Kristjánsson, Mio Murao, Tatsuki Odake, Marco Túlio

Quintino, Philip Taranto, Satoshi Yoshida

► To cite this version:

Jessica Bavaresco, Hlér Kristjánsson, Mio Murao, Tatsuki Odake, Marco Túlio Quintino, et al. Simulating the quantum switch with quantum circuits is computationally hard. Nature Communications, 2025, 16, pp.10216. 10.1038/s41467-025-64996-6. hal-04722809

HAL Id: hal-04722809

https://hal.science/hal-04722809v1

Submitted on 10 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Simulating the quantum switch with quantum circuits is computationally hard

Jessica Bavaresco,¹,² Hlér Kristjánsson,³,⁴,⁵,⁶ Mio Murao,⁵,⁷ Tatsuki Odake,⁵

Marco Túlio Quintino,²,\* Philip Taranto,⁸,⁵ and Satoshi Yoshida⁵

¹Department of Applied Physics, University of Geneva, 1205 Geneva, Switzerland

²Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

³Perimeter Institute for Theoretical Physics, 31 Caroline Street North, Waterloo, Ontario, N2L 2Y5, Canada

⁴Institute for Quantum Computing, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, N2L 3G1, Canada

⁵Department of Physics, Graduate School of Science, The University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-0033, Japan

⁶Department of Computer Science and Operations Research, Université de Montréal, Montréal, Québec, H3T 1J4, Canada

⁷Trans-scale Quantum Science Institute, The University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-0033, Japan

⁸Department of Physics & Astronomy, University of Manchester, Manchester M13 9PL, United Kingdom

(Dated: 8th December 2025)

Higher-order transformations acting on input quantum channels in an indefinite causal order—such as the quantum switch—cannot be described by quantum circuits using the same number of calls to the input channels. A natural question is whether they can be simulated, i.e., whether their action can be exactly and deterministically reproduced by a quantum circuit with more calls to the input channels. Here, we prove that the quantum switch acting on two *n*-qubit channels cannot be simulated by any quantum circuit using *k* calls to one channel and one to the other, if *k* < 2ⁿ. This establishes an exponential separation in quantum query complexity between processes with indefinite causal order and quantum circuits. Moreover, even with one extra call to both input channels, such a simulation remains impossible. We further demonstrate the robustness of this separation by extending the result to probabilistic and approximate simulations scenarios.

# I. INTRODUCTION

Indefinite causal order is a fundamental property that emerges in the exploration of higher-order transformations within quantum theory [1–5]. Higher-order quantum transformations are operations whose inputs and outputs are not quantum states, but rather transformations that themselves act on quantum states, such as quantum channels. An example of such a transformation is a quantum circuit with open slots where arbitrary quantum channels can be inserted and acted upon in a sequential, temporally ordered manner [1, 3]. Remarkably, there also exist well-defined higher-order transformations that act on their input quantum channels in an indefinite causal order [6–8]. Such transformations cannot be described by any quantum circuit that uses the same number of calls, or queries, of the input quantum channels, challenging the standard notion of computation in which operations are performed on a system in a fixed order.

The ability to perform operations in such an indefinite order has been shown to provide advantages in a variety of information-processing settings, such as quantum channel discrimination [9–11], quantum metrology [12–15], quantum computational complexity [16, 17], quantum query complexity [18], transformations of black-box unitaries and isometries [19–23], among others.

A prominent example of indefinite causal order that is responsible for several of these theoretically predicted advantages is the quantum switch [6], a higher-order transformation that coherently controls the causal order of two quantum channels. The information-processing advantages of the quantum switch have mostly been shown via comparison with higher-order transformations that act in a fixed order on a single call of each input channel [8–10, 12]. However, their true practical significance hinges on the extent to which these advantages would still hold when comparing the quantum switch with quantum circuits that use a larger number of calls to its inputs.

In the context of quantum computation, whether the quantum switch exhibits a true complexity-theoretic advantage depends upon whether its action can be efficiently reproduced by using quantum circuits, given extra queries to the input channels. Until now, no exponential separation has been demonstrated between the query complexity of computations using indefinite causal order versus quantum circuits. In fact, for unitary channels, the action of the quantum switch can be reproduced by a quantum circuit with just one extra query [6], significantly limiting the computational power of the quantum switch in this case. However, a crucial open question is whether this limitation extends to general quantum channels.

More concretely, this question can be phrased in terms of the simulability of the quantum switch, or more generally, of any higher-order transformation with indefinite causal order:

<footnote>\* Marco.Quintino@lip6.fr</footnote>
Can a higher-order transformation with indefinite causal order that acts on arbitrary quantum channels be simulated by quantum circuits that have access to more calls of the input quantum channels?

In the case where the quantum circuit performing the simulation has access to an infinite number of calls of the input channels, the answer is: yes. In this case, a process tomography protocol [3, 24, 25] can completely characterize the input channels and simply prepare the output channel expected from the higher-order transformation with indefinite causal order. However, such a simulation requires infinite resources. Another possible way that the quantum switch can be simulated is using post-selection [6, 26]. However, such a simulation does not work deterministically. Additionally, in the particular case where the input channels are restricted to being unitary channels, it has been shown that a simulation of the quantum switch exists [6]. However, such a simulation is not universal, inasmuch as it only works for a restricted set of input channels.

We hence ask the question, which has remained largely unexplored so far: does any finite number of extra calls of the input channels suffice to deterministically and universally simulate the action of the quantum switch with a quantum circuit?

In this work, we prove that the quantum switch acting on arbitrary channels A and B cannot be deterministically and universally simulated by a quantum circuit (or even a quantum circuit with classical control of the causal order [27]) that has access to $k_A < 2^n$ calls of A and $k_B = 1$ call of B, where A and B are arbitrary n-qubit quantum channels. Our theorem demonstrates an exponential separation in quantum query complexity for computational tasks using quantum processes with indefinite causal order versus quantum circuits with fixed or classically-controlled causal order, in terms of the number of qubits. We moreover prove that when one extra call of each quantum channel is available ($k_A = k_B = 2$), it remains impossible to simulate the action of the quantum switch, even for single-qubit channels. We demonstrate the extent of the robustness of these results in two different ways: with probabilistic and approximate simulations. We show that even when approximate simulations are considered, the probability of simulating a higher-order operation which is $\epsilon$-close to the quantum switch is significantly below one for an $\epsilon$ significantly above zero. We furthermore thoroughly analyze the problem of simulating the quantum switch when it acts only on part of its input quantum channels or on quantum instruments. Finally, we show some new particular (non-universal) cases in which simulations of the quantum switch are possible. In

light of these results, we conjecture that a deterministic simulation of the quantum switch, if possible, would require a number of queries to both quantum channels that grows at least exponentially with the size of the system they act upon. If our conjecture holds true, it would imply that processes with indefinite causal order cannot be efficiently simulated even by quantum circuits with classically-controlled causal order.

## II. RESULTS

### Quantum switch simulation

The quantum switch $\mathcal{S}$ is a higher-order transformation that takes two arbitrary quantum channels (i.e. completely positive, trace-preserving maps) A and B as input, where $A: \mathcal{L}(\mathcal{H}^{A_I}) \to \mathcal{L}(\mathcal{H}^{A_O})$ and $B: \mathcal{L}(\mathcal{H}^{B_I}) \to \mathcal{L}(\mathcal{H}^{B_O})$ are channels that act on qudit systems, and transforms them into a channel $\mathcal{S}(A, B): \mathcal{L}(\mathcal{H}^{c_I} \otimes \mathcal{H}^{t_I}) \to \mathcal{L}(\mathcal{H}^{c_O} \otimes \mathcal{H}^{t_O})$ that acts on a qubit control system and a qudit target system. The output channel resulting from the action of the quantum switch [6] on its input channels is defined as

$$ \mathcal{S}(A, B)[\sigma_c \otimes \rho_t] := \sum_{i,j} S_{ij}(\sigma_c \otimes \rho_t)S_{ij}^{\dagger}, \quad (1) $$

where $\sigma_c \in \mathcal{L}(\mathcal{H}^{c_I})$ is the state of the input qubit control system, $\rho_t \in \mathcal{L}(\mathcal{H}^{t_I})$ is that of the qudit target system, and $S_{ij}$ is given by

$$ S_{ij} := |0\rangle\langle 0| \otimes B_j A_i + |1\rangle\langle 1| \otimes A_i B_j, \quad (2) $$

where $A_i: \mathcal{H}^{A_I} \to \mathcal{H}^{A_O}$ and $B_j: \mathcal{H}^{B_I} \to \mathcal{H}^{B_O}$ are Kraus operators [28] of the channels A and B, respectively; i.e., $A[\rho] = \sum_i A_i \rho A_i^{\dagger}$ and $B[\rho] = \sum_i B_i \rho B_i^{\dagger}$. This transformation is depicted in Fig. 1. The quantum switch acts on its input channels in an order that is conditioned on the state of a quantum control system. Since the quantum control system may be initiated in a superposition state, such as $|+\rangle := \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$, the overall quantum switch transformation may be understood as a conditioned superposition of two different circuits, one with the control system in state $|0\rangle$ and the quantum channels being applied in the order A before B, and another with the control system in state $|1\rangle$ and the quantum channels being applied in the order B before A.

A deterministic and exact simulation of the quantum switch is a higher-order transformation $\mathcal{C}$ that obeys causal constraints and that acts on a finite number $k_A$ and $k_B$ of calls to the channels A and B, respectively, in such a way that the channel $\mathcal{C}(A^{\otimes k_A}, B^{\otimes k_B}): \mathcal{L}(\mathcal{H}^{c_I} \otimes \mathcal{H}^{t_I}) \to$
<figure><img src="image_2.png" /><figcaption>Figure 1. **The quantum switch transformation.** The quantum switch $\mathcal{S}$ is a higher-order transformation that takes as input any two quantum channels $A$ and $B$ and transforms them into a another quantum channel $\mathcal{S}(A, B)$. The resulting channel $\mathcal{S}(A, B)$ acts on a qubit control system and a qudit target system.</figcaption></figure>

$\mathcal{L}(\mathcal{H}^{co} \otimes \mathcal{H}^{to})$ resulting from this transformation satisfies

$$C(A^{\otimes k_A}, B^{\otimes k_B}) = \mathcal{S}(A, B) \quad \forall A, B, \quad (3)$$

where $A, B$ are arbitrary quantum channels. Natural causal constraints that one might impose on the simulation is to require that $\mathcal{C}$ be described by a fixed-order quantum circuit with open slots, called a quantum comb [1, 3] (see App. A2 for a formal definition). A more general strategy for the simulation—which could nevertheless be interpreted as having a definite causal order—would be to impose that $\mathcal{C}$ is described by open-slot quantum circuits that have classical control of causal order. This class of higher-order transformations, proposed in Ref. [27] and called “QC-CCs”, is larger than the set of quantum combs, allowing for classical mixtures of open-slot quantum circuits as well as for classically-controlled dynamical causal orders. Hence, permitting this class gives more power to the simulation as compared to quantum combs, while still allowing for a causally ordered interpretation of the simulation (see App. A3 for a formal definition). We furthermore require the simulation to be universal: the same simulation $\mathcal{C}$ must work for all input pairs of quantum channels. See Fig. 2 for a graphical representation of Eq. (3). The question of simulability then boils down to whether there exists, for some finite number of calls $k_A$ and $k_B$, a simulation $\mathcal{C}$ that obeys causal constraints and that satisfies Eq. (3).

This notion of computation, where the inputs and outputs are quantum rather than classical, is suitable to treat inherently quantum problems and has been employed beyond the higher-order quantum computing paradigm explored here in problems ranging from the SWAP test [29, 30] to Hamiltonian simulations [31, 32] and quantum property testing [33].

## Go theorem: An explicit non-universal simulation

For a particular case of input channels, it is known that a non-universal simulation of the quantum switch exists. As first shown in the paper that originally defined the quantum switch [6], in the particular case where the input channels are unitary (i.e. reversible), a simulation of the quantum switch by a quantum circuit is possible, requiring only an extra use of one of the input channels.

The simulation presented in Ref. [6] is given by the quantum circuit

<figure><img src="image_3.png" /></figure>

where $\text{---} \text{---} \text{---} \text{---} \text{---} \text{---} \text{---}$ := $\text{---} \text{---} \text{---} \text{---} \text{---} \text{---}$ and $\text{---} \text{---} \text{---} \text{---} \text{---} \text{---}$ is the NOT gate. Here, the first circuit line corresponds to the control qubit system, the second to an auxiliary system, and the third to the target qudit system. This circuit can equivalently be represented by the Kraus operators $\{C_{ij i'}\}_{ij i'}$, where

$$C_{ij i'} := |0\rangle\langle 0| \otimes A_{i'} \otimes B_j A_i + |1\rangle\langle 1| \otimes A_i \otimes A_{i'} B_j. \quad (5)$$

Since in general $i \neq i'$, the transformation acting on the auxiliary system does not typically factor out from the transformation acting on the qubit and control systems. By comparison with Eq. (2), it is straightforward to see that the resulting transformation does not simulate the quantum switch for arbitrary quantum channels. However, in the case where $A$ and $B$ are unitary channels, and hence are described by a single Kraus operator (i.e. $i = i' = j = 0$), the transformation on the auxiliary system factorizes from that on the control and target systems. In this particular case, it is straightforward to see that, for any input state of the auxiliary system, when the output auxiliary system is discarded, the quantum circuit in Eq. (4) performs a (non-universal) simulation of the quantum switch.

A crucial point to note is that the circuit in Eq. (4) acts on the input channels in the order “ABA”. If one were to change the order of the input channels to either “AAB” or “BAA”, this circuit no longer simulates the quantum switch, even if the input channels are unitary. In fact, for these different orders, we prove that there does not exist any quantum circuit that can simulate the action of the quantum switch, even when acting only on unitary channels. We present more details in App. E.

Here, we show that an extension of the circuit in Eq. (4) allows one to perform a simulation of the quantum switch in a more general—albeit not fully general—scenario.
<figure><img src="image_4.png" /><figcaption>Figure 2. **Simulating the quantum switch.** A higher-order transformation $\mathcal{C}$ corresponding to an open-slot quantum circuit with fixed or classically-controlled causal order, which acts on several copies of the input quantum channels $A$ and $B$, is a simulation of the quantum switch $S$ if it reproduces the action of the quantum switch on all arbitrary channels $A$ and $B$.</figcaption></figure>

This is the case where the quantum switch acts only on part of a quantum channel $A$ that is unitary and part of a quantum channel $B$ that is general.

In this simulation scenario, the quantum switch acts only on part of bipartite channels $A: \mathcal{L}(\mathcal{H}^{A_I} \otimes \mathcal{H}^{A'_I}) \to \mathcal{L}(\mathcal{H}^{A_O} \otimes \mathcal{H}^{A'_O})$ and $B: \mathcal{L}(\mathcal{H}^{B_I} \otimes \mathcal{H}^{B'_I}) \to \mathcal{L}(\mathcal{H}^{B_O} \otimes \mathcal{H}^{B'_O})$, both of which have two input and two output spaces. The extra input/output systems of these bipartite channels can be interpreted as environments that are not accessible to the local parties Alice and Bob. The output channel from the quantum switch transformation is then given by $S \otimes \mathcal{I}(A, B) : \mathcal{L}(\mathcal{H}^{A'_I} \otimes \mathcal{H}^{c_I} \otimes \mathcal{H}^{t_I} \otimes \mathcal{H}^{B'_I}) \to \mathcal{L}(\mathcal{H}^{A'_O} \otimes \mathcal{H}^{c_O} \otimes \mathcal{H}^{t_O} \otimes \mathcal{H}^{B'_O})$, where $\mathcal{I}$ is the identity higher-order transformation acting on the primed spaces. This transformation is depicted in Fig. 3. Since the quantum switch higher-order transformation is uniquely defined by its action on single-party unitary channels [34], there is no risk of ambiguity when considering such extended quantum switch transformations.

When the input channels $A$ and $B$ are general, i.e., not restricted to being unitary, this scenario is the strongest possible simulation scenario. In other words, a simulation $\mathcal{C}$ that is able to prepare, with some finite number of calls $k_A$ and $k_B$, a channel $\mathcal{C}(A^{\otimes k_A}, B^{\otimes k_B})$ such that

$$ \mathcal{C}(A^{\otimes k_A}, B^{\otimes k_B}) = S \otimes \mathcal{I}(A, B) \quad \forall A, B, \quad (6) $$

where $A, B$ are arbitrary quantum channels, is a higher-order transformation that can simulate the action of the quantum switch in its most general form. We discuss further details concerning general simulations in App. B1, as well as simulations of the action of the quantum switch on quantum instruments in App. B2.

In this general simulation scenario, we prove the following theorem, regarding the existence of a non-universal simulation of the action of the quantum switch on part of bipartite channels—in the particular case where $A$ is restricted to being a unitary channel and $B$ is a fully general quantum channel:

**Theorem 1.** *The action of the quantum switch on part*

of bipartite quantum channels can be deterministically simulated by a quantum circuit that has access to an extra call to one the input channels, as long as that channel is restricted to being unitary.

In other words, if $A$ is a bipartite unitary channel and $B$ is a bipartite general channel, there exists a quantum circuit described by a higher-order transformation $\mathcal{C}$ that satisfies Eq. (6) for $k_A = 2$ and $k_B = 1$.

We prove this result by explicitly constructing the quantum circuit that performs this simulation, which is given by

<figure><img src="image_5.png" /></figure>

Here, the first circuit line represents the qubit control, the second and third lines represent auxiliary systems, the fourth line represents Alice's primed system, the fifth line represents the target system, and the sixth line represents Bob's primed system. In App. B4, we prove Thm. 1 explicitly, showing how it recovers the action of the quantum switch when $A$ is a unitary channel, and how it fails when $A$ is a general channel.

Given that every quantum channel can be seen as the marginal channel of a unitary channel acting on a higher-dimensional space, implemented with the use of an auxiliary system—via the Stinespring dilation theorem—it may seem counter-intuitive that the circuit in Eq. (7) fails to simulate the quantum switch for general channels. However, this is due to the fact that unitary channels acting on higher-dimensional spaces only correspond to general, non-unitary channels mapping the input to the
<figure><img src="image_6.png" /><figcaption>Figure 3. The extended quantum switch transformation. The quantum switch S is a higher-order transformation that takes as input any two quantum channels A and B and transforms them into another quantum channel, $S \otimes \mathcal{I}(A, B)$, even when acting only on part of these channels.</figcaption></figure>

output systems if the auxiliary system is not accessible. One way to enforce this is by requiring that the auxiliary systems be discarded. If the auxiliary system were discarded, and hence not available to be exploited during the simulation, it is straightforward to see that the circuit in Eq. (7) would fail. In App. B3, we discuss in detail how Thm. 1 relates to the Stinespring dilation of non-unitary quantum channels.

### No-go theorems: Deterministic exact simulations

We now show that the go theorem from the previous section does not generalize: not only does the circuit in Eq. (7) not work for arbitrary quantum channels A, but there does not exist any other quantum circuit that can simulate the quantum switch, even when a higher number of calls of the input channel A are available. In order to do so, we prove an even stronger statement: one which demonstrates an exponential separation in quantum query complexity between a higher-order transformation with indefinite causal order and quantum circuits that have a fixed or classically-controlled causal order.

**Theorem 2.** There is no $(k_A+1)$-slot higher-order transformation $\mathcal{C}$, described by a quantum circuit with fixed or classically-controlled causal order, that can simulate the quantum switch, i.e., that satisfies

$$ \mathcal{C}(A^{\otimes k_A}, B) = \mathcal{S}(A, B) \qquad (8) $$

for all n-qubit mixed unitary channels A and unitary channels B, if

$$ k_A \le \max(2, 2^n - 1). \qquad (9) $$

Therefore, such a simulation also does not exist for all n-qubit quantum channels A and B.

We provide a sketch of the proof in Sec. IV, with the full proof presented in App. C. While Thm. 2 forbids a deterministic exact simulation of the quantum switch, it also prevents arbitrarily good probabilistic approximate simulations of it. That is because it guarantees that any probabilistic approximate simulation will necessarily have a maximal probability of success p strictly less than one or minimum approximation error $\epsilon$ strictly greater than zero, for any notion of metric distance.

This result can be interpreted as an exponential advantage of indefinite causal order over definite causal order for a specific task, namely that of simulating the action of the quantum switch on arbitrary quantum channels A and B when only one call of B is available. In order to formalize this result in the context of computation, consider a classical description of a function f which takes a pair of quantum channels A, B as input and outputs a quantum channel f(A, B). Consider also a higher-order transformation $\mathcal{C}$ that simulates the function f deterministically and exactly—that is, such that $\mathcal{C}(A^{\otimes k_A}, B^{\otimes k_B}) = f(A, B)$ for all A, B—for some number $k_A$ and $k_B$ of black-box queries to the quantum channels A and B, respectively. In the case where one of the channels is fixed to being called $k_B = 1$ times, we can define a simple notion of quantum query complexity that depends only on the number of calls to the other channel, $k_A$. We define the one-sided quantum query complexity of a function f, with respect to a class of higher-order quantum transformations $\mathcal{C}$, as the minimum number of queries $k_A$ while $k_B = 1$, over all higher-order quantum transformations $\mathcal{C} \in \mathcal{C}$ such that $\mathcal{C}$ simulates f. This definition can be seen as a step towards a fully quantum generalization of the notion of query complexity. While the standard notion of quantum query complexity has so far typically been defined for classical (e.g. boolean) functions [18], here we consider the query complexity of functions whose inputs and outputs are themselves quantum channels (see also [35]). This is similar in spirit to recent works on the complexity of preparing quantum states [36, 37].

In this context, we see that Thm. 2 implies that the one-sided quantum query complexity of the action of the quantum switch, with respect to all QC-CC transformations, is lower-bounded by $2^n$.

### No-go theorems: Probabilistic simulations

Following from the above discussion, one might wonder whether a simulation remains impossible if more than one call of the quantum channel B is allowed. Here, we also prove a no-go theorem for the simulation of the quantum
switch when 2 calls of each input quantum channel is available (i.e., $k_A = k_B = 2$). In fact, we prove an even stronger result: such a simulation is impossible even for single-qubit channels, and even in a probabilistic and restricted simulation scenario.

Let us start by defining the restricted simulation scenario. Fixing the input control system to be in state $\sigma_c = |+\rangle\langle+|$ and the input target system to be in state $\rho_t = |0\rangle\langle0|$, a restricted simulation of the switch is possible if, for some finite number of calls $k_A$ and $k_B$, there exists a quantum comb or QC-CC $\mathcal{C}$ such that

$$ \begin{aligned} & \mathrm{tr}_{t_O} (\mathcal{C}(A^{\otimes k_A}, B^{\otimes k_B})[|+\rangle\langle+| \otimes |0\rangle\langle0|]) \\ & = \mathrm{tr}_{t_O} (\mathcal{S}(A, B)[|+\rangle\langle+| \otimes |0\rangle\langle0|]) \quad \forall A, B, \end{aligned} \quad (10) $$

where $A$ and $B$ are arbitrary channels. Notice that Eq. (10) is an equality between two qubit quantum states, namely the output control systems. Notice that, while the impossibility of a simulation in the restricted case implies the impossibility of simulation in the general case, a possibility of simulating the quantum switch in the restricted case would not imply the existence of a more general simulation.

Let us now define a probabilistic heralded simulation of the quantum switch. A probabilistic heralded simulation is a quantum comb or QC-CC $\mathcal{C}$ that compared to the deterministic simulation in Eq. (3), outputs an extra classical bit corresponding to either the success or failure outcome of the simulation, each with a certain probability. When the value of this bit corresponds to the success outcome, the implemented simulation is exactly $\mathcal{S}(A, B)$. Such transformations can be implemented by either a quantum comb or as a QC-CC that additionally outputs a flag system encoding the success or failure outcome, followed by a dichotomic quantum measurement of the flag system. Mathematically, a probabilistic heralded simulation is a higher-order transformation $\mathcal{C} = \mathcal{C}_s + \mathcal{C}_f$, where $\mathcal{C}_s$ and $\mathcal{C}_f$ are higher-order maps that completely preserve completely positive inputs—one associated to the success and the other with the failure outcome of the transformation—and where $\mathcal{C}$ is described as either a quantum comb or as a QC-CC. In this case, $\mathcal{C} = \mathcal{C}_s + \mathcal{C}_f$ is a probabilistic simulation of the quantum switch that uses $k_A$ calls of channel $A$ and $k_B$ calls of channel $B$ if it satisfies

$$ \mathcal{C}_s(A^{\otimes k_A}, B^{\otimes k_B}) = p \mathcal{S}(A, B) \quad \forall A, B, \quad (11) $$

where $A$ and $B$ are general quantum channels, and $p$ is the probability of a successful simulation. In the case where $\mathcal{C}$ is a quantum comb, no normalization conditions need to be imposed on $\mathcal{C}_s$. However, when $\mathcal{C}$ is a QC-CC,

then normalization conditions must be imposed on $\mathcal{C}_s$ to ensure that $\mathcal{C}$ is a proper QC-CC transformation [27]. We present these constraints explicitly in App. A3.

Combining Eqs. (10) and (11), we define a probabilistic restricted simulation of the quantum switch via

$$ \begin{aligned} & \mathrm{tr}_{t_O} (\mathcal{C}_s(A^{\otimes k_A}, B^{\otimes k_B})[|+\rangle\langle+| \otimes |0\rangle\langle0|]) \\ & = p \mathrm{tr}_{t_O} (\mathcal{S}(A, B)[|+\rangle\langle+| \otimes |0\rangle\langle0|]) \quad \forall A, B. \end{aligned} \quad (12) $$

It is known that any higher-order transformation with indefinite causal order can be simulated by a quantum comb in a probabilistic heralded manner with $p > 0$, even without any extra calls of the input channels [20, 26]. For the particular case of the quantum switch, Ref. [6] presents a probabilistic circuit based on quantum teleportation that simulates the quantum switch with $p = 1/d^2$, where $d$ is the dimension of the target system, without any extra calls. Here, we will analyze the maximal probability of success for simulating the quantum switch when extra calls are available.

As we prove in Sec. IV, for any fixed finite $d := \dim(\mathcal{H}^{t_I}) = \dim(\mathcal{H}^{t_O}) = \dim(\mathcal{H}^{A_I}) = \dim(\mathcal{H}^{A_O}) = \dim(\mathcal{H}^{B_I}) = \dim(\mathcal{H}^{B_O})$, $k_A$, and $k_B$, the maximum probability of success $p$ of simulating the quantum switch acting on all general quantum channels $A$ and $B$ can be computed with a semidefinite program (SDP). This is because if a simulation exists for a finite subset of channels that form a basis for the linear subspace spanned by $k_A$ copies of a quantum channel $A$, and equivalently for $B$, then said simulation is also valid for all channels $A$ and $B$, due to the linearity of higher-order transformations. Crucially, in the case where $\mathcal{C}$ is a quantum comb, the maximum probability of success of a simulation of the quantum switch may depend on the order of the input channels $A$ and $B$. In the case where $\mathcal{C}$ is a QC-CC, all possible fixed and dynamical orders are automatically optimized over.

We are now ready to state this result.

**Theorem 3.** There is no quantum circuit that can deterministically simulate the action of the quantum switch on all quantum channels when $(k_A, k_B) \in \{(1, 1), (2, 1), (2, 2), (3, 1)\}$, where $k_A$ is the number of calls of input channel $A$ and $k_B$ is the number of calls of input channel $B$.

Moreover, even for a restricted simulation—i.e., for fixed input systems and discarded output target system—the action on the quantum switch on general qubit channels, when $(k_A, k_B) \in \{(1, 1), (2, 1), (2, 2), (3, 1)\}$, can be simulated with at most a probability $p < 1$, with upper bounds given in Table 1.

We prove this theorem using a method that we de-
<table><caption>**Table 1. Maximum probability of a restricted simulation of the qubit quantum switch.** Rigorous upper bounds for the maximum probability *p* of a restricted simulation of the quantum switch acting on a pair of arbitrary qubit quantum channels *A*, *B*, using open-slot quantum circuits that take *k*<sub>*A*(*B*)</sub> calls of an arbitrary quantum channel *A*(*B*) in a certain order. All bounds were derived via computer-assisted proofs.</caption><thead><tr><th>(k<sub>A</sub>, k<sub>B</sub>)</th><th>order</th><th>probability</th></tr></thead><tbody><tr><td>(1, 1)</td><td>AB</td><td>p &lt; <sup>4001</sup>&frasl;<sub>10000</sub></td></tr><tr><td rowspan="3">(2, 1)</td><td>AAB</td><td>p &lt; <sup>5715</sup>&frasl;<sub>10000</sub></td></tr><tr><td>ABA</td><td>p &lt; <sup>4919</sup>&frasl;<sub>10000</sub></td></tr><tr><td>BAA</td><td>p &lt; <sup>5001</sup>&frasl;<sub>10000</sub></td></tr><tr><td rowspan="3">(2, 2)</td><td>AABB</td><td>p &lt; <sup>8307</sup>&frasl;<sub>10000</sub></td></tr><tr><td>ABAB</td><td>p &lt; <sup>8484</sup>&frasl;<sub>10000</sub></td></tr><tr><td>ABBA</td><td>p &lt; <sup>8695</sup>&frasl;<sub>10000</sub></td></tr><tr><td rowspan="4">(3, 1)</td><td>AAAB</td><td>p &lt; <sup>8373</sup>&frasl;<sub>10000</sub></td></tr><tr><td>AABA</td><td>p &lt; <sup>6909</sup>&frasl;<sub>10000</sub></td></tr><tr><td>ABAA</td><td>p &lt; <sup>7597</sup>&frasl;<sub>10000</sub></td></tr><tr><td>BAAA</td><td>p &lt; <sup>6845</sup>&frasl;<sub>10000</sub></td></tr></tbody></table>

Develop for computer-assisted proofs that transforms the numerically imperfect solution of an SDP into a rigorous upper-bound for the probability of success that can be expressed in terms of rational numbers. The method is presented in Sec. IV with further details provided in App. F.

Still in the restricted simulation scenario, we found three different particular cases where a deterministic simulation is possible for qubit channels, but nevertheless impossible in the more general scenario. In the following we discuss these three cases, with more details being provided in App. D.

The first case of this kind is when the quantum switch acts on arbitrary, yet identical, qubit quantum channels, i.e., *A* = *B*. Although the input channels in this case are identical, it is straightforward to see from Eq. (1) that the action of the switch is non-trivial, namely, that the output channel *S*(*A*, *A*) is not equivalent to *A* applied twice on the target system when *A* is not a unitary channel. A remarkable example of this point is the case where *A* is the depolarizing channel [38]. We find that a restricted deterministic quantum comb simulation exists for qubit channels in the “AAAA” scenario, i.e., with 4 identical calls of the arbitrary qubit quantum channel *A*. Since in this case the maximum probability of success is *p* = 1,

<table><caption>**Table 2. Bounds for the maximum probability of a restricted simulation of the qubit quantum switch acting on identical channels.** Rigorous upper bounds for the maximum probability *p* of a restricted simulation of the quantum switch that acts on a pair of identical qubit quantum channels, using open-slot quantum circuits that take *k* ∈ {2, 3} calls of an arbitrary quantum channel *A*. All bounds were derived via computer-assisted proofs. (*) For the case of *k* = 4, we numerically find that a deterministic simulation is possible, i.e., that *p* = 1 up to an numerical precision of 10<sup>-9</sup>.</caption><thead><tr><th>k</th><th>order</th><th>probability</th></tr></thead><tbody><tr><td>2</td><td>AA</td><td>p &lt; <sup>4001</sup>&frasl;<sub>10000</sub></td></tr><tr><td>3</td><td>AAA</td><td>p &lt; <sup>6534</sup>&frasl;<sub>10000</sub></td></tr><tr><td>4</td><td>AAAA</td><td>p = 1 (*)</td></tr></tbody></table>

one cannot certify this result with a computer-assisted proof, which can yield upper and lower bounds for *p* with arbitrary yet only finite precision. Instead, we obtain this result by numerically evaluating an SDP with very high precision, ensuring that all positivity constraints are strictly satisfied and that all equality constraints are satisfied up to an error of at most 10<sup>-9</sup> in the operator norm. Furthermore, 4 identical calls of the arbitrary qubit quantum channel *A* are not only sufficient, but necessary for a deterministic restricted simulation: if only 2 or 3 calls are allowed, we prove upper bounds for the maximum probability of simulation that are always strictly less than 1 (see Table 2). However, this only holds in the restricted simulation case. When the output target system is not discarded, we find numerically that a deterministic simulation of the AAAA scenario is no longer possible (see App. D for more details). This shows how highly nontrivial the action of the quantum switch is even when acting on identical quantum channels.

The other two restricted cases where a deterministic restricted simulation is possible concern qubit unitary channels applied in the order ABBB and BAAA, two cases where trivial extensions of the circuit in Eq. (4) fail. Similarly to the case of identical qubit channels, such simulations no longer exist if the output target system is not discarded. More details in App. D.

## No-go theorems: Approximate simulations

By exhibiting concrete upper bounds for the probability of successful simulation of the quantum switch that are significantly below 1, we demonstrate the extent of the robustness of our results with respect to a figure of merit related to a probabilistic simulation. Another pertinent
<figure><img src="image_7.png" /><figcaption>Figure 4. Robustness of the impossibility of simulation. Maximum probability of success p of simulating any higher-order transformation that is $\epsilon$-close to the quantum switch using quantum combs of different orders or QC-CCs, as a function of $\epsilon$. In plot (a), we show the case where $k_A = k_B = 1$. Note how the QC-CC simulation curve numerically coincides with the comb simulation curve. In plot (b), we show the case where $k_A = 2$ and $k_B = 1$. In this case, for some values of $\epsilon$, QC-CCs show an advantage with respect to quantum combs.</figcaption></figure>

notion of robustness in this context is that of an approximate simulation—although the quantum switch may not be able to be exactly simulated, it could still be the case that other higher-order transformations that are $\epsilon$-close to the quantum switch can be simulated. This question is particularly relevant for experimental scenarios, where noise and imprecision hinder the ability of preparing any specific transformation exactly. Here, we prove that even in the approximate case a simulation of the quantum switch is not possible, for some particular number of calls $(k_A, k_B)$. We do so by exhibiting values of $\epsilon$ that are significantly above zero for which even a probabilistic simulation, for some $p < 1$ that we also exhibit, is not possible.

For an approximate simulation of the quantum switch, it is useful to consider a partly restricted scenario that

is required to hold for fixed input control and target systems, but without discarding the output target system. Similarly to the restricted simulation case, proving the impossibility of a simulation in this partly restricted case also implies the impossibility of a simulation in more general scenarios. Let $\sigma_c = |+\rangle\langle+|$ be the state of the input control system, $\rho_t = |0\rangle\langle0|$ be the state of the input target system, and $\tilde{S}$ be a higher-order transformation that acts on the same space as the quantum switch. We define a simulation $\mathcal{C}$ to be $\epsilon$-close to the quantum switch $\mathcal{S}$ in this scenario if there exists an $\tilde{S}$ such that

$$ \mathcal{C}(A^{\otimes k_A}, B^{\otimes k_B})[|+\rangle\langle+| \otimes |0\rangle\langle0|] \\ = \tilde{S}(A, B)[|+\rangle\langle+| \otimes |0\rangle\langle0|] \quad \forall A, B, \qquad (13) $$

where A and B are arbitrary quantum channels and, for $S_{+0}(\cdot, \cdot) := S(\cdot, \cdot)[|+\rangle\langle+| \otimes |0\rangle\langle0|]$ and $\tilde{S}_{+0}(\cdot, \cdot) := \tilde{S}(\cdot, \cdot)[|+\rangle\langle+| \otimes |0\rangle\langle0|]$, it holds that

$$ F(S_{+0}, \tilde{S}_{+0}) \ge 1 - \epsilon, \qquad (14) $$

where $F(\mathcal{M}, \mathcal{N})$ is the normalized fidelity between the Choi operators associated to the higher-order transformations $\mathcal{M}$ and $\mathcal{N}$ (see App. A1).

Combining probabilistic-heralded and approximate protocols of simulation, for a fixed $\epsilon$, $(k_A, k_B)$, and $d$, the maximum probability of successful simulation can also be computed via an SDP. We show that, for a range of values of $\epsilon > 0$, the probability of simulating the quantum switch in this partly restricted scenario is $p < 1$ for the cases where $(k_A, k_B) \in \{(1, 1), (2, 1)\}$, considering simulations using quantum combs of all possible orders as well as QC-CCs. We present our numerical findings in Fig. 4 for the case where $d = 2$. In the first plot [Fig. 4(a)], where $(k_A, k_B) = (1, 1)$, the QC-CC simulation curve numerically coincides with the quantum comb simulation curve. Here, $p < 1$ for $0 \le \epsilon \lesssim 0.3$. In the second plot [Fig. 4(b)], where $(k_A, k_B) = (2, 1)$, each of the three possible quantum comb orders and QC-CC yield different values for the maximum probability of success for different values of $\epsilon$. Here, $p < 1$ for $0 \le \epsilon \lesssim 0.18$, after which point a QC-CC simulation exists. Notice that for an exact simulation, i.e., when $\epsilon = 0$, a QC-CC simulation yields a probability of success that coincides with the highest among all possible orders, but as $\epsilon$ increases, it shows an advantage in the probability of success as compared to quantum combs.

## A conjecture

Taken together, our results indicate the hardness of simulating the quantum switch. Considering all the evid-
ence we have gathered here supporting a high cost, if not altogether the impossibility, of simulating the quantum switch deterministically, we are motivated to propose the following conjecture:

**Conjecture 1.** There is no $(k_A + k_B)$-slot higher-order transformation $\mathcal{C}$, described by a quantum circuit with fixed or classically-controlled causal order, that can simulate the quantum switch, i.e., that satisfies

$$ \mathcal{C}(A^{\otimes k_A}, B^{\otimes k_B}) = \mathcal{S}(A, B) \qquad (15) $$

for all n-qubit quantum channels A and B, if $\max(k_A, k_B) \le g(n)$, for some $g(n) = \Theta(2^n)$.

Our rationale behind conjecturing that no simulation is possible even with multiple (albeit a sub-exponential number of) calls to both input channels is the following. As mentioned above, there exists a deterministic and exact simulation of the quantum switch with a single query to a general channel B and two queries to a unitary channel A. However, simulating the quantum switch for general channels A and B requires correlating each Kraus operator $A_k$ on the $|0\rangle$ branch—which can be obtained by querying A before B—with the same $A_k$ on the $|1\rangle$ branch—which can be obtained by querying A after B [see Eq. (2)]. In this view, B can be considered as a fixed channel [39], and therefore the intuition is that querying it multiple times is no better than querying it once. The rational for the bound to be $\Theta(2^n)$ is that all the main steps in the proof of Thm. 2 except one hold for a bound of $\Theta(2^n)$ with $(k_A+k_B)$-slot higher-order transformations, and only for Lemma 4 were we only able to prove the $(k_A + 1)$-slot case. It remains to be seen whether the action of the quantum switch can be simulated with any finite number of queries to one or both input channels.

### III. DISCUSSION

In this work, we have concretely formulated the problem of simulating higher-order transformations with indefinite causal order using higher-order transformations that obey causal constraints and have access to more calls of the input operations. Our case study for this problem was the quantum switch. We defined the problem in its full generality, considering also cases where the quantum switch acts only on part of its input quantum channels.

We showed that the (one-sided) quantum query complexity of the action of the quantum switch on n-qubit channels, with respect to all quantum circuits with fixed and classically-controlled causal order, is lower bounded by $2^n$ (Thm. 2). Notably, the exponential separation that we prove is formulated with respect to a computational

task where the inputs and outputs of the computation are given by black-box quantum channels [1, 2, 6, 40]. This is in contrast to previous works on the query complexity of the quantum switch, where the output of the computation is a bit representing the evaluation of a classical function, in which case no such exponential separation has been found [9, 16–18, 41].

We additionally proved that an extra copy of each input quantum channel, i.e., $(k_A, k_B) = (2, 2)$, is not sufficient to deterministically simulate the quantum switch with a quantum circuit. Considering probabilistic simulations, we proved a range of rigorous strict upper bounds on the probability of successful simulation in various different scenarios (Thm. 3). In order to do so, we developed and applied a general method of computer-assisted proofs based on semidefinite programming. We also explored approximate simulations in some cases, showing that the switch cannot be simulated even approximately for some $\epsilon > 0$ with probability $p = 1$.

Finally, we showed that for some particular kinds of input, non-universal simulations exist. The most general such case is when A is a bipartite unitary channel, B is a bipartite general channel, and the quantum switch acts only on part of the input channels. Such a simulation exists a requires only an extra call of A (Thm. 1). A simulation also exists for the particular case where the input pair of channels of the switch are identical qubit quantum channels, $A = B$. Here, 4 calls of the input channel are necessary and sufficient for a restricted deterministic simulation, where the input states are fixed and the target output system is discarded. However, this result does not hold for more general simulation scenarios, where the output target system is not discarded. This possibility of simulation in the restricted case, but not in more general cases, is also true for the simulation of the action of the switch on qubit unitary channels with the orders Aabb and Baaa.

Our results have implications for the analysis of the experiments based on the quantum switch [42], particularly the ones that make use of non-unitary channels, such as those reported in Refs. [43–47]. A long-standing debate in the community is whether these experiments are a genuine realization or some form of simulation of the quantum switch. One important criticism is that several experimental setups leave room for the interpretation that there are two independent calls of each input quantum channel available in the transformation. Here, we have proven that such access still does not allow for a causally ordered explanation for the observed data. On the other hand, an alternative causal model that can reproduce the action of the quantum switch is one that, instead of considering the inputs to be two independent calls of a general channel, considers inputs that can be
described as bipartite channels with memory, which can be interpreted as two correlated uses of a general quantum channel [48, 49]. As a corollary of our result in Thm. 3, we observe that there does not exist a quantum circuit that can take two independent uses of an arbitrary channel as input and output a bipartite channel with memory that corresponds to two correlated uses of the input quantum channels. Therefore, a causal model based on correlated inputs is not compatible with a simulation scenario that considers black-box inputs, as considered here. However, this point alone is not sufficient to rule out this model is a fair description of the experiments. It is our hope that our results will encourage further rigorous analysis of potential loopholes in the quantum switch experiments.

Our work opens up the study of query complexity in the context of higher-order quantum computation where the inputs and outputs of the computation are general quantum channels. The question of whether any finite number of calls suffices to perform a simulation of the switch is of high relevance and remains open. Further investigation of this topic will be crucial to determine, for example, whether advantages in specific tasks that have been previously demonstrated can persist in the asymptotic limit of the available number of calls. Should it ever be shown that the quantum switch can be simulated with a finite number of calls, a relevant follow-up question is related to the scaling of the necessary number of calls, and to whether or not the switch can be efficiently simulated in a deterministic setting.

The existence of efficient deterministic and exact simulation of quantum processes with indefinite causal order may pose itself as an interesting physical guideline to help us understand on the one hand which kinds of higher-order transformations can be realistically implemented, and on the other hand, what advantages they may provide.

## IV. METHODS

**Preliminaries.** In our technical calculations, we make use of the Choi-Jamiolkowski isomorphism [50, 51] and the link product [1].

Using this isomorphism, any linear map $M: \mathcal{L}(\mathcal{H}^I) \to \mathcal{L}(\mathcal{H}^O)$ that maps linear operators acting on an input space to linear operators acting on an output space can be represented by a linear operator $J^M \in \mathcal{L}(\mathcal{H}^I \otimes \mathcal{H}^O)$ that acts on the joint input and output space, called the Choi operator, which is given by

$$J^M := \sum_{ij} |i\rangle\langle j| \otimes M(|i\rangle\langle j|), \quad (16)$$

where $\{|i\rangle\}_i$ is the computational basis. A linear map $M$ is completely positive (CP) if and only if its Choi operator

$J^M$ is positive semidefinite, and is trace-preserving (TP) if and only if $J^M$ satisfies $\text{tr}_O(J^M) = 1^I$, where $1^I$ is the identity operator in $\mathcal{L}(\mathcal{H}^I)$. Hence, the Choi operator of general quantum channels satisfy these conditions.

Any linear operator $U: \mathcal{H}^I \to \mathcal{H}^O$ can be represented by its Choi vector $|U\rangle\langle U| \in \mathcal{H}^I \otimes \mathcal{H}^O$, where

$$|U\rangle\langle U| := \sum_i |i\rangle \otimes U |i\rangle. \quad (17)$$

Hence, a unitary channel $U$ such that $U[\rho] = U\rho U^\dagger$, where $U$ is a unitary operator that corresponds to the single Kraus operator of the channel $U$, has Choi operator $J^U = |U\rangle\langle U|\langle U|\rangle$.

Using this representation, the composition $G \circ F$ of two maps $F: \mathcal{L}(\mathcal{H}^1) \to \mathcal{L}(\mathcal{H}^2)$ and $G: \mathcal{L}(\mathcal{H}^2) \to \mathcal{L}(\mathcal{H}^3)$, with respective Choi operators $J^F \in \mathcal{L}(\mathcal{H}^1 \otimes \mathcal{H}^2)$ and $J^G \in \mathcal{L}(\mathcal{H}^2 \otimes \mathcal{H}^3)$, is given by the link product $J^F * J^G \in \mathcal{L}(\mathcal{H}^1 \otimes \mathcal{H}^3)$, according to

$$J^F * J^G := \text{tr}_2[(J^F \otimes 1^3)(1^1 \otimes (J^G)^{T_2})], \quad (18)$$

where $(\cdot)^{T_2}$ denotes partial transposition on the space $\mathcal{L}(\mathcal{H}^X)$.

The link product for Choi vectors $|Q\rangle\langle Q| \in \mathcal{H}^1 \otimes \mathcal{H}^2$ and $|R\rangle\langle R| \in \mathcal{H}^2 \otimes \mathcal{H}^3$ is given by $|Q\rangle\langle Q| * |R\rangle\langle R| \in \mathcal{H}^1 \otimes \mathcal{H}^3$, defined as

$$|Q\rangle\langle Q| * |R\rangle\langle R| := \sum_i (1^1 \otimes \langle i|) |Q\rangle\langle Q| \otimes (\langle i| \otimes 1^3) |R\rangle\langle R|. \quad (19)$$

**Sketch of the proof of Theorem 2.** While we provide the full proof of Thm. 2 in App. C, here we give a sketch of the proof for the case where $k_A = 2$.

Here we adopt a slightly different notation from the main text, and write the higher-order transformation $\mathcal{C}$ as a function $\mathcal{C}(A, B, C)$ that takes three arguments, each corresponding to a quantum channel that can be plugged into one of its three slots. Hence, instead of writing, e.g., $\mathcal{C}(A^{\otimes 2}, B)$ we will use $\mathcal{C}(A, A, B)$.

Let $\mathcal{C}(A, A, B)$ be a simulation of the action of the quantum switch $\mathcal{S}(A, B)$ on all mixed unitary quantum channels $A$ and unitary channels $B$. Then, for arbitrary unitary channels $U_1, U_2, V$, the simulation $\mathcal{C}$ necessarily respects

$$\mathcal{C} \left( \frac{U_1 + U_2}{2}, \frac{U_1 + U_2}{2}, V \right) = \mathcal{S} \left( \frac{U_1 + U_2}{2}, V \right). \quad (20)$$
By linearity, Eq. (20) implies that

$$ \sum_{i,j=1}^{2} C(U_i, U_j, V) = 2 \sum_{k=1}^{2} S(U_k, V). \quad (21) $$

Let $C$ be the Choi operator of the simulation $C$, $S = |S\rangle\langle S|$ be the Choi operator of the quantum switch transformation $S$, defined by Eq. (1) and written explicitly in App. A1, and $|U_l\rangle\langle U_l|$ denote the Choi operator of a unitary channel $U_l$. Then, Eq. (21) can be expressed as

$$ \sum_{i,j=1}^{2} C * (|U_i\rangle\langle U_i| \otimes |U_j\rangle\langle U_j| \otimes |V\rangle\langle V|) = 2 \sum_{k=1}^{2} |S\rangle\langle S| * (|U_k\rangle\langle U_k| \otimes |V\rangle\langle V|). \quad (22) $$

Assuming that $C$ is positive semidefinite, it accepts a decomposition $C = \sum_a |C^{(a)}\rangle\langle C^{(a)}|$ where $|C^{(a)}\rangle\langle C^{(a)}| \ge 0$ for all $a$. From the positivity of $|U_l\rangle\langle U_l|$ and $|V\rangle\langle V|$, it follows that

$$ |C^{(a)}\rangle\langle C^{(a)}| * (|U_1\rangle\langle U_1| \otimes |U_2\rangle\langle U_2| \otimes |V\rangle\langle V|) \le 2|S\rangle\langle S| * \left[ (|U_1\rangle\langle U_1| + |U_2\rangle\langle U_2|) \otimes |V\rangle\langle V| \right], \quad (23) $$

for every $a$.

Following the definition of the link product for Choi vectors, $|Q\rangle\langle Q|*|R\rangle\langle R|$ is given by $(|Q\rangle*|R\rangle)(|Q\rangle*|R\rangle)^{\dagger}$ (see, e.g., Lemma 1 of Ref. [52]). Thus, the support of the right-hand side of Eq. (23) is given by $\text{span}\{|S\rangle\rangle * (|U_k\rangle\rangle \otimes |V\rangle\rangle)\}_{k=1}^2$ and that of the left-hand side of Eq. (23) is the one-dimensional subspace spanned by $|C^{(a)}\rangle\rangle * (|U_1\rangle\rangle \otimes |U_2\rangle\rangle \otimes |V\rangle\rangle)$. Therefore, one can write

$$ |C^{(a)}\rangle\rangle * (|U_1\rangle\rangle \otimes |U_2\rangle\rangle \otimes |V\rangle\rangle = \sum_{k=1}^{2} \xi_k^{(a)}(U_1, U_2, V)|S\rangle\rangle * (|U_k\rangle\rangle \otimes |V\rangle\rangle), \quad (24) $$

for some coefficients $\xi_k^{(a)}(U_1, U_2, V) \in \mathbb{C}$. The proof of this fact uses Lemma 1 from App. C1 and Lemma 2 from App. C2.

We now invoke Lemma 3 from App. C3 and Lemma 4 from App. C4 to ensure that, when Eq. (24) is satisfied, there exist vectors $|\xi_1^{(a)}\rangle\rangle \in \mathcal{H}^{I_2} \otimes \mathcal{H}^{O_2}$ and $|\xi_2^{(a)}\rangle\rangle \in \mathcal{H}^{I_1} \otimes \mathcal{H}^{O_1}$, such that

$$ |C^{(a)}\rangle\rangle = \sum_{k=1}^{2} |S\rangle\rangle \otimes |\xi_k^{(a)}\rangle\rangle, \quad (25) $$

for all $a$, where $|\xi_1^{(a)}\rangle\rangle$ and $|\xi_2^{(a)}\rangle\rangle$ are independent of $U_1$,

$U_2$, and $V$.

Next, we argue why this is the case.

The basic idea for this part of the proof is based on differentiation with respect to a parametrization of the input unitary operators, a technique introduced in Ref. [35] by some of the present authors. Suppose that $U_1, U_2$, and $V$ are taken from the set $\{I, X, Y, Z\}$ of Pauli operators. If $U_1 \neq U_2$, then $|S\rangle\rangle * (|U_1\rangle\rangle \otimes |V\rangle\rangle)$ and $|S\rangle\rangle * (|U_2\rangle\rangle \otimes |V\rangle\rangle)$ are linearly independent. In this case, we can show using linearity that $\xi_1^{(a)}(U_1, U_2, V)$ is independent of $U_1, V$ and $\xi_2^{(a)}(U_1, U_2, V)$ is independent of $U_2, V$. If on the other hand $U_1 = U_2 = \sigma$, then $|S\rangle\rangle * (|U_1\rangle\rangle \otimes |V\rangle\rangle)$ and $|S\rangle\rangle * (|U_2\rangle\rangle \otimes |V\rangle\rangle)$ are not linearly independent.

In such cases, it turns out that $\xi_1^{(a)}(\sigma, \sigma, V)$ and $\xi_2^{(a)}(\sigma, \sigma, V)$ can be suitably chosen as $\xi_1^{(a)}(\sigma', \sigma, V)$ and $\xi_2^{(a)}(\sigma, \sigma', V)$, respectively, where $\sigma' \neq \sigma$ is a Pauli operator. Note that $\xi_1^{(a)}(\sigma', \sigma, V)$ and $\xi_2^{(a)}(\sigma, \sigma', V)$ do not depend on the choice of $\sigma'$ as long as $\sigma' \neq \sigma$ holds. The fact that such a redefinition is consistent with Eq. (24) can be proven by differentiating the expression $\xi_i^{(a)}(\tilde{\sigma}(\theta), \tilde{\sigma}(\theta), V)$, where $\tilde{\sigma}(\theta)$ is a parameterized unitary operator satisfying $\tilde{\sigma}(0) = \sigma$ and $\frac{d}{d\theta}|_{\theta=0} \tilde{\sigma}(\theta) \propto \sigma'$. This redefinition implies that that $\xi_1^{(a)}(U_1, U_2, V)$ and $\xi_2^{(a)}(U_1, U_2, V)$ are independent of $U_1$ and $U_2$, respectively. By linearity, we can show that for $i \in \{1, 2\}$, $\xi_k^{(a)}(U_1, U_2, V)$ is independent of $V$.

The independence relations above imply that we can write $\xi_1^{(a)}(U_1, U_2, V) = |\xi_1^{(a)}\rangle\rangle * |U_2\rangle\rangle$ and $\xi_2^{(a)}(U_1, U_2, V) = |\xi_2^{(a)}\rangle\rangle * |U_1\rangle\rangle$ for some vectors $|\xi_1^{(a)}\rangle\rangle, |\xi_2^{(a)}\rangle\rangle$. Substituting this into Eq. (24) gives

$$ |C^{(a)}\rangle\rangle * (|U_1\rangle\rangle \otimes |U_2\rangle\rangle \otimes |V\rangle\rangle) = \sum_{k=1}^{2} |S\rangle\rangle \otimes |\xi_k^{(a)}\rangle\rangle * (|U_1\rangle\rangle \otimes |U_2\rangle\rangle \otimes |V\rangle\rangle). \quad (26) $$

Since this holds for all combinations of Pauli operators $U_1, U_2, V$, we obtain Eq. (25).

Hence, we have shown that the assumption of a simulation of the quantum switch given by a higher-order transformation with Choi operator $C = \sum_a |C^{(a)}\rangle\rangle\langle C^{(a)}| \ge 0$ implies the existence of vectors $|\xi_1^{(a)}\rangle\rangle$ and $|\xi_2^{(a)}\rangle\rangle$ that satisfy Eq. (25). Finally, we invoke Lemma 5 from App. C5, which states that such a higher-order transformation does not satisfy the QC-CC conditions.

**Semidefinite programming.** Here we show that the problem of simulating the quantum switch can be phrased as an SDP.

Let $S$ be the Choi operator of the quantum switch transformation $S$, defined in Eq. (1), written explicitly in App. A1. Let $J^A$ and $J^B$ be the Choi operators of the
quantum channels A and B. Finally, let C be the Choi operator of the deterministic higher-order transformation C, which corresponds to a quantum comb, and C_s be the Choi operator of the higher-order transformation C_s associated with the success outcome of a probabilistic transformation. Then, the maximum probability of simulating the action of the quantum switch S on a set of N_A channels {$J_i^A$}$_{i=1}^{N_A}$ and a set of N_B channels {$J_j^B$}$_{j=1}^{N_B}$ using a quantum comb C that acts on k_A calls of $J_i^A$ and k_B calls of $J_j^B$ is given by the following SDP:

**given** {$J_i^A$}$_{i}$, {$J_j^B$}$_{j}$, k_A, k_B

**max** p

$$
\begin{array}{ll}
\text{s.t.} & C_s * [(J_i^A)^{\otimes k_A} \otimes (J_j^B)^{\otimes k_B}] = p S * (J_i^A \otimes J_j^B) \quad \forall i, j \\
& C_s \ge 0, \quad C - C_s \ge 0, \\
& \mathbb{P}(C) = C, \quad \text{tr}(C) = d_{c_I} d_{t_I} d_{A_O}^{k_A} d_{B_O}^{k_B},
\end{array}
\tag{27}
$$

where $\mathbb{P}$ is the projector onto the linear subspace spanned by valid quantum combs [1, 5, 8] (explicitly written in App. A2), and $d_X := \dim(\mathcal{H}^X)$. For a simulation given by QC-CC transformations, the constraint $\mathbb{P}(C) = C$ should be substituted by the appropriate linear constraints that define a proper QC-CC transformations, as well as additional normalization constraints on $C_s$ [27]. These constraints are explicitly written in App. A3 for the cases of 2 and 3 slots. Notice that, following results from Sec. III of Ref. [20], the variables $C$ and $C_s$ in this SDP can be restricted to the field of real numbers without loss of generality, a feature that improves numerical performance.

The dual problem associated to this SDP can be found
by combining standard methods [53] with dual affine
techniques (see, e.g., the derivation of a similar dual
problem in Appendix B of Ref. [10], inspired by Ref. [54]).
It is given by

given {$J_i^A$}$_{i}$, {$J_j^B$}$_{j}$, k_A, k_B

$$
\min \frac{1}{d_{A_I}^{k_A} d_{B_I}^{k_B} d_{c_O} d_{t_O}} \operatorname{tr}(\Gamma)
$$

$$
\text{s.t.} \quad \sum_{i,j} \operatorname{tr}[R_{ij} (S * (J_i^A \otimes J_j^B))] = 1 \tag{28}
$$

$$
\Gamma - \sum_{i,j} R_{ij} \otimes [(J_i^A)^{\otimes k_A} \otimes (J_j^B)^{\otimes k_B}]^T \ge 0
$$

$$
\Gamma \ge 0, \quad \bar{\mathbb{P}}(\Gamma) = \Gamma,
$$

where $\bar{\mathbb{P}}$ is the projector onto the linear subspace spanned by the dual affine of valid combs [5, 10, 54] (also explicitly written in App. A2). In the case of this dual SDP problem, the variable $\Gamma$ may also be restricted to the field of real numbers, since it is the Lagrange multiplier associated

to the constraint $\mathbb{P}(C) = C$ (an equality between real
matrices); however, the same is not true for the variables
$\{R_{ij}\}$, which are the Lagrange multipliers associated to
the constraints $C_s * [(J_i^A)^{\otimes k_A} \otimes (J_j^B)^{\otimes k_B}] = p S * (J_i^A \otimes J_j^B)$, an equality between complex matrices. Nonetheless,
restricting $\{R_{ij}\}$ to real values still allows for feasible
points that yield a valid upper bound for the optimal
solution of this problem.

Finally, the SDPs (27) and (28) satisfy the condition of
strong duality, which is implied by the fact that a strictly
feasible point for the primal problem can be created from
the probabilistic simulation of Ref. [6] that requires no
extra calls.

**Basis design.** For any input set of channels, the solution of SDP (27), or equivalently of SDP (28), corresponds to the maximum probability of success of a simulation of the action of the quantum switch on the specific given inputs, with a simulation that has access to the specified number of calls of the input channels and that satisfies the specified causal constraints. Then, the maximum probability of success of a universal switch simulation—one that works for all possible input channels and not only for the given inputs—can be obtained by setting {$\{ (J_i^A) \}_i$} to be a set of operators that forms a basis for the span($\{ (J_i^A)^{\otimes k_A} \}_i$), i.e., the subspace spanned by $k_A$ copies of an arbitrary quantum channel, and equivalently for $\{ (J_j^B) \}$. In this case, if the constraint $C_s * [(J_i^A)^{\otimes k_A} \otimes (J_j^B)^{\otimes k_B}] = p S * (J_i^A \otimes J_j^B)$ holds for all $i, j$, then it also holds for arbitrary quantum channels. In other words, it implies that $C_s * [(J_i^A)^{\otimes k_A} \otimes (J_j^B)^{\otimes k_B}] = p S * (J_i^A \otimes J_j^B)$ holds for all channels $J^A$ and $J^B$, thereby implying the existence of a universal probabilistic simulator with success probability $p$.

There are a few properties that the elements $J_i^A$ and $J_j^B$ of these bases must satisfy in order to be valid inputs of the SDPs (27) and (28). The first is that it is necessary to ensure that the operators $J_i^A$ and $J_j^B$ individually correspond to TP maps, in order for the total trace of both sides of the constraint $C_s * [(J_i^A)^{\otimes k_A} \otimes (J_j^B)^{\otimes k_B}] = p S * (J_i^A \otimes J_j^B)$ to match. However, they do not need to correspond to CP maps, i.e., to be positive semidefinite operators. That is because all elements of the span($\{J_i^A\}_i$) can be written as linear combinations of the elements of a set $\{J'_i\}_i$ which correspond to TP maps (but not necessarily CP maps) and form a basis for the space spanned by quantum channels. Finally, it is also necessary that these operators can be themselves expressed as a tensor power of a TP map, because they play the role of the inputs of the quantum switch, which takes only a single call of each input. That is, they appear on both sides of the constraint $C_s * [(J_i^A)^{\otimes k_A} \otimes (J_j^B)^{\otimes k_B}] =$
$p S * (J_i'^A \otimes J_j'^B).$

We now construct a convenient basis for the linear space spanned by the set of $k$ copies of any quantum channel, which will be used in the computer-assisted proofs presented subsequently.

First, note that an arbitrary self-adjoint two-qubit operator $M \in \mathcal{L}(\mathcal{H}^I \otimes \mathcal{H}^O) \cong \mathcal{L}(\mathbb{C}^2 \otimes \mathbb{C}^2)$ can always be written as

$$M = \lambda \mathbf{1} \otimes \mathbf{1} + \sum_i \alpha_i \sigma_i \otimes \mathbf{1} + \sum_j \beta_j \mathbf{1} \otimes \sigma_j + \sum_{ij} \gamma_{ij} \sigma_i \otimes \sigma_j, \quad (29)$$

where all $\sigma_i \in \{X, Y, Z\}$ are Pauli operators, and $\lambda, \alpha_i, \beta_j, \gamma_{ij} \in \mathbb{R}$. Since operators $M$ that correspond to a TP map satisfy $\text{tr}_O(M) = \mathbf{1}^I$, in this case one has that $\lambda = 1/2$ and $\alpha_i = 0$. This implies that the dimension of the linear space spanned by the set of qubit quantum channels is $3+9+1=13$. One can then construct a convenient basis for the subspace spanned by qubit quantum channels, given by

$$\mathcal{B}_1 := \left\{ \begin{array}{l} \mathbf{1} \otimes \frac{\mathbf{1}}{2}, \\ \mathbf{1} \otimes \frac{\mathbf{1}}{2} + \mathbf{1} \otimes \sigma_i, \\ \mathbf{1} \otimes \frac{\mathbf{1}}{2} + \sigma_j \otimes \sigma_k \end{array} \right\}_{i,j,k}. \quad (30)$$

Notice that all elements of the basis set $\mathcal{B}_1$ correspond to TP maps, even if they are not necessarily positive semidefinite.

We now consider the linear space spanned by the set of $k$ copies of any arbitrary qubit channel, i.e., the span of the set of all $J^{\otimes k}$ such that $\text{tr}_O(J) = \mathbf{1}^I$. If a linear subspace $V$ has dimension $d_V$, then the dimension of the space span($\{J^{\otimes k} | J \in V\}$) is given by $(\frac{d_V-1+k}{k})$ [28]. By setting $d_V = 13$ and $k = 2$, we see that the space spanned by the set of two identical copies of qubit channels has dimension 91. Hence, in order to find a basis for two identical copies of qubit channels, it is enough to exhibit a set of 91 operators $J_i$, all respecting $\text{tr}_O(J_i) = \mathbf{1}^I$, such that the set $\{J_i^{\otimes 2}\}_{i=1}^{91}$ is composed of linearly independent operators.

Let $\rho_i \in \{\mathbf{1} \otimes \frac{\mathbf{1}}{2}, 2|\phi^+\rangle\langle\phi^+|, \mathbf{1} \otimes |0\rangle\langle0|, \mathbf{1} \otimes |+\rangle\langle+|, \mathbf{1} \otimes |+Y\rangle\langle+Y|\}$, where $|\phi^\pm\rangle := \frac{1}{\sqrt{2}}(|00\rangle \pm |11\rangle)$ are maximally entangled two-qubit states and $|\pm Y\rangle := \frac{1}{\sqrt{2}}(|0\rangle \pm |1\rangle)$. Then, let $\sigma_i^I \in \{\mathbf{1}, X, Y, Z\}$ and $\sigma_i^O \in \{X, Y, Z\}$. We

define the set of operators

$$\mathcal{B}_2 := \left\{ \begin{aligned} & \left(\mathbf{1} \otimes \frac{\mathbf{1}}{2}\right)^{\otimes 2}, \\ & (\rho_i \pm \sigma_j^I \otimes \sigma_k^O)^{\otimes 2}, \\ & (\rho_l + \sigma_m^I \otimes \sigma_n^O + \sigma_p^I \otimes \sigma_q^O)^{\otimes 2} \end{aligned} \right\}_{i,j,k,l, \substack{m,n,p,q}} \quad (31)$$

which can be shown to contain a subset of 91 linearly independent operators by standard computational methods. Hence, the set $\mathcal{B}_2$ forms an overcomplete basis, from which one can obtain a standard basis (containing only 91 operators) by discarding any operators that are not linearly independent. This set of 91 operators forms a basis for the linear subspace spanned by two identical copies of any arbitrary qubit channel.

For the case of $k = 3$, we begin by calculating the dimension of the space spanned by three identical copies of arbitrary qubit channels, by setting $d_V = 13$ and $k = 3$, obtaining that the dimension of the relevant space is 455. Again, in order to find a basis for three identical copies of qubit channels, it is enough to exhibit 455 operators $J_i$ respecting $\text{tr}_O(J_i) = \mathbf{1}^I$, such that such that the set $\{J_i^{\otimes 3}\}_{i=1}^{455}$ is composed of linearly independent operators.

Let $\rho_i \in \{\mathbf{1} \otimes \frac{\mathbf{1}}{2}, 2|\phi^+\rangle\langle\phi^+|, 2|\phi^-\rangle\langle\phi^-|, 2|\psi^+\rangle\langle\psi^+|, 2|\psi^-\rangle\langle\psi^-|, \mathbf{1} \otimes |0\rangle\langle0|, \mathbf{1} \otimes |1\rangle\langle1|, \mathbf{1} \otimes |+\rangle\langle+|, \mathbf{1} \otimes |-\rangle\langle-|, \mathbf{1} \otimes |+Y\rangle\langle+Y|\}, \mathbf{1} \otimes |-i\rangle\langle-i|\}$, where $|\psi^\pm\rangle := \frac{1}{\sqrt{2}}(|01\rangle \pm |10\rangle)$ are maximally entangled two-qubit states and $|-\rangle := \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$. Then, let $\sigma_i^I \in \{\mathbf{1}, X, Y, Z, X + Z, X + Y\}$ and $\sigma_i^O \in \{X, Y, Z, X + Z, X + Y\}$. We define the set of operators

$$\mathcal{B}_3 := \left\{ (\rho_i \pm \sigma_j^I \otimes \sigma_k^O + \sigma_l^I \otimes \sigma_m^O)^{\otimes 3} \right\}_{l,m, \substack{i,j,k, \\ l,m}} \quad (32)$$

which can be shown to contain a subset of 455 linearly independent operators by standard computational methods. This set of 455 operators forms a basis for the linear subspace spanned by three identical copies of arbitrary qubit channels.

In general, one can always construct a basis for the space spanned by $k \in \mathbb{N}$ copies of arbitrary qubit channels by finding coefficients $\alpha_{i|l}, \gamma_{ij|l} \in \mathbb{R}$, such that the set

$$\left\{ \left( \mathbf{1} \otimes \frac{\mathbf{1}}{2} + \sum_i \alpha_{i|l} \mathbf{1} \otimes \sigma_i + \sum_{ij} \gamma_{ij|l} \sigma_i \otimes \sigma_j \right)^{\otimes k} \right\}_l \quad (33)$$

contains $(\frac{13-1+k}{k})$ linearly independent operators. One simple way to find such coefficients is simply to choose them at random.

To evaluate the SDPs (27) and (28) when the
inputs form a basis for the space spanned by $k_A$ copies of channel A and $k_B$ copies of channel B, the overall number of input pairs of channels are: for $(k_A, k_B) = (1, 1)$, $N_A N_B = 13 \cdot 13 = 169$; for $(k_A, k_B) = (2, 1)$, $N_A N_B = 91 \cdot 13 = 1183$; for $(k_A, k_B) = (3, 1)$, $N_A N_B = 455 \cdot 13 = 5915$; and finally for $(k_A, k_B) = (2, 2)$, $N_A N_B = 91 \cdot 91 = 8281$, making these SDPs very computationally demanding.

**Computer-assisted proofs.** While floating-point arithmetic provides an efficient and powerful numerical method to treat real numbers, it suffers from some fundamentally unavoidable issues. For instance, addition and multiplication of floats is not associative and equality and inequality constraints are not satisfied exactly, but only up to some numerical precision. We now show how efficient numerical solvers that make use of floating-point arithmetic can be used to obtain a rigorous upper bound on the maximal success probability of simulating the quantum switch, hence leading to a bona-fide computer-assisted proof. Our methods are based on Ref. [10].

The duality aspects of semidefinite programming [53] ensure that any feasible point of the dual problem, presented in SDP (28), yields an upper bound for the solution of the maximisation problem in the primal SDP (27). That is, any set of operators $\{R_{ij}\}_{ij}$ and $\Gamma$ that respects $\sum_{i,j} \text{tr}[R_{ij} (S * (J_i^A \otimes J_j^B))] = 1$, $\Gamma - \sum_{i,j} R_{ij} \otimes [(J_i^A)^{\otimes k_A} \otimes (J_j^B)^{\otimes k_B}]^T \ge 0$, $\Gamma \ge 0$, and $\overline{\mathbb{P}}(\Gamma) = \Gamma$, implies that the probability of simulating the quantum switch is necessarily $p \le \text{tr}(\Gamma)/d_{cI} d_{tI} d_{AO}^{k_A} d_{BO}^{k_B}$. Standard numerical SDP solvers can be used to find a floating-point solution for the dual problem in SDP (28), and to provide explicit operators $\{R_{ij}^{\text{float}}\}_{ij}$ and $\Gamma^{\text{float}}$ that approximately satisfy the SDP constraints. We now show how the operators $\{R_{ij}^{\text{float}}\}_{ij}$ and $\Gamma^{\text{float}}$ can be used as a good initial ansatz to construct symbolic operators $R_{ij}^{\text{OK}}$ and $\Gamma^{\text{OK}}$, which are not stored as floating-point variables and which satisfy the SDP constraints exactly, ensuring that $\text{tr}(\Gamma^{\text{OK}})/d_{cI} d_{tI} d_{AO}^{k_A} d_{BO}^{k_B}$ is a legitimate upper bound for the probability of success of simulating the quantum switch. In order to do so, we use the bases presented in Eqs. (30), (31), (32), and (33), which only contain small rational numbers. In the following, we present an algorithm to extract a computer-assisted proof from numerical solvers.

**Algorithm:**

1. Construct symbolic non-floating-point operators $\Gamma^{\text{sym}}$ and $R_{ij}^{\text{sym}}$ by truncating $\Gamma^{\text{float}}$ and $R_{ij}^{\text{float}}$ to obtain symbolic operators expressed only in terms of rational numbers.

This allows us to work with fractions and to avoid numerical imprecision.

2. Force the operators $\Gamma^{\text{sym}}$ and $R_{ij}^{\text{sym}}$ to be self-adjoint by making use of the expression $(M + M^{\dagger})/2$, which is self-adjoint for any $M$.

This ensures that we are dealing with self-adjoint operators.

3. Evaluate $t^{\text{sym}} := \sum_{i,j} \text{tr}[R_{ij}^{\text{sym}} (S * (J_i^A \otimes J_j^B))],$ where $S, J_i^A$, and $J_j^B$ are also symbolic operators. Define $R_{ij}^{\text{OK}} := R_{ij}^{\text{sym}}/t^{\text{sym}}$ for all $i, j$.

Here, we use the basis with rational coefficients constructed earlier to ensure that the operators $R_{ij}^{\text{OK}}$ satisfy the SDP equality constraint exactly.

4. Project $\Gamma^{\text{sym}}$ onto the appropriate subspace to obtain $\overline{\mathbb{P}}(\Gamma^{\text{sym}})$.

This ensures that the resulting operator $\overline{\mathbb{P}}(\Gamma^{\text{sym}})$ is in the correct linear subspace.

5. Find $\eta \in \mathbb{R}$ such that $\Gamma^{\text{OK}} := \overline{\mathbb{P}}(\Gamma^{\text{sym}}) + \eta \mathbb{1} \ge 0$ and $\Gamma^{\text{OK}} - \sum_{i,j} R_{ij}^{\text{OK}} \otimes (J_i^{A \otimes k_A} \otimes J_j^{B \otimes k_B})^T \ge 0$

This ensures the positivity constraints in the dual SDP (28) are satisfied.

6. Output the quantity $\text{tr}(\Gamma^{\text{OK}})/d_{cI} d_{tI} d_{AO}^{k_A} d_{BO}^{k_B}$, which is a rigorous upper bound of the primal problem.

All equality and inequality constraints hold without relying on floating point precision, and the operators $\Gamma^{\text{OK}}$ and $R_{ij}^{\text{OK}}$ yield a proof certificate that $p \le \text{tr}(\Gamma^{\text{OK}})/d_{cI} d_{tI} d_{AO}^{k_A} d_{BO}^{k_B}$.

The algorithm described above deserves two clarifications. First, since the projector $\overline{\mathbb{P}}$ is unital, i.e., $\overline{\mathbb{P}}(\mathbb{1}) = \mathbb{1}$, for any $\eta \in \mathbb{R}$ and any operator $M$, we have that $\overline{\mathbb{P}}(M) + \eta \mathbb{1} = \overline{\mathbb{P}}(M + \eta \mathbb{1})$. Second, checking if an operator is positive semidefinite can be done efficiently through the Cholesky decomposition—more details are provided in App. F.

## DATA AVAILABILITY

No data sets were generated or analyzed during the current study.

## CODE AVAILABILITY

All code developed for this work is available at our online repository in Ref. [55]. For numerically evaluating our SDPs, we used the Splitting Conic Solver (SCS) [56, 57] and MOSEK [58].
[1] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Quantum Circuit Architecture, Phys. Rev. Lett. 101, 060401 (2008), arXiv:0712.1325 [quant-ph].

[2] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Transforming quantum operations: Quantum supermaps, EPL 83, 30004 (2008), arXiv:0804.0180 [quant-ph].

[3] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Theoretical framework for quantum networks, Phys. Rev. A 80, 022339 (2009), arXiv:0904.4483 [quant-ph].

[4] A. Bisio and P. Perinotti, Theoretical framework for higher-order quantum theory, Proc. R. Soc. A 475, 20180706 (2019), arXiv:1806.09554 [quant-ph].

[5] S. Milz and M. T. Quintino, Characterising transformations between quantum objects, 'completeness' of quantum properties, and transformations without a fixed causal order, Quantum 8, 1415 (2024), arXiv:2305.01247 [quant-ph].

[6] G. Chiribella, G. M. D'Ariano, P. Perinotti, and B. Valiron, Quantum computations without definite causal structure, Phys. Rev. A 88, 022318 (2013), arXiv:0912.0195 [quant-ph].

[7] O. Oreshkov, F. Costa, and Č. Brukner, Quantum correlations with no causal order, Nat. Commun. 3, 1092 (2012), arXiv:1105.4464 [quant-ph].

[8] M. Araújo, C. Branciard, F. Costa, A. Feix, C. Giarmatzi, and Č. Brukner, Witnessing causal nonseparability, New J. Phys. 17, 102001 (2015), arXiv:1506.03776 [quant-ph].

[9] G. Chiribella, Perfect discrimination of no-signalling channels via quantum superposition of causal structures, Phys. Rev. A 86, 040301 (2012), arXiv:1109.5154 [quant-ph].

[10] J. Bavaresco, M. Murao, and M. T. Quintino, Strict Hierarchy between Parallel, Sequential, and Indefinite-Causal-Order Strategies for Channel Discrimination, Phys. Rev. Lett. 127, 200504 (2021), arXiv:2011.08300 [quant-ph].

[11] J. Bavaresco, M. Murao, and M. T. Quintino, Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies, J. Math. Phys. 63, 042203 (2022), arXiv:2105.13369 [quant-ph].

[12] X. Zhao, Y. Yang, and G. Chiribella, Quantum Metrology with Indefinite Causal Order, Phys. Rev. Lett. 124, 190503 (2020), arXiv:1912.02449 [quant-ph].

[13] R. Mothe, C. Branciard, and A. A. Abbott, Reassessing the advantage of indefinite causal orders for quantum metrology, Phys. Rev. A 109, 062435 (2024), arXiv:2401.10137 [quant-ph].

[14] Q. Liu, Z. Hu, H. Yuan, and Y. Yang, Optimal strategies of quantum metrology with a strict hierarchy, Phys. Rev. Lett. 130, 070803 (2023), arXiv:2203.09758 [quant-ph].

[15] P. Yin, X. Zhao, Y. Yang, Y. Guo, W.-H. Zhang, G.-C. Li, Y.-J. Han, B.-H. Liu, J.-S. Xu, G. Chiribella, et al., Experimental super-Heisenberg quantum metrology with indefinite gate order, Nat. Phys. 19, 1122 (2023), arXiv:2303.17223 [quant-ph].

[16] M. Araújo, F. Costa, and Č. Brukner, Computational Advantage from Quantum-Controlled Ordering of Gates, Phys. Rev. Lett. 113, 250402 (2014), arXiv:1401.8127 [quant-ph].

[17] M. J. Renner and Č. Brukner, Computational Advantage from a Quantum Superposition of Qubit Gate Orders, Phys. Rev. Lett. 128, 230503 (2022), arXiv:2112.14541 [quant-ph].

[18] A. A. Abbott, M. Mhalla, and P. Pocreau, Quantum query complexity of boolean functions under indefinite causal order, Phys. Rev. Res. 6, L032020 (2024), arXiv:2307.10285 [quant-ph].

[19] M. T. Quintino, Q. Dong, A. Shimbo, A. Soeda, and M. Murao, Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations, Phys. Rev. Lett. 123, 210502 (2019), arXiv:1810.06944 [quant-ph].

[20] M. T. Quintino, Q. Dong, A. Shimbo, A. Soeda, and M. Murao, Probabilistic exact universal quantum circuits for transforming unitary operations, Phys. Rev. A 100, 062339 (2019), arXiv:1909.01366 [quant-ph].

[21] M. T. Quintino and D. Ebler, Deterministic transformations between unitary operations: Exponential advantage with adaptive quantum circuits and the power of indefinite causality, Quantum 6, 679 (2022), arXiv:2109.08202 [quant-ph].

[22] S. Yoshida, A. Soeda, and M. Murao, Universal construction of decoders from encoding black boxes, Quantum 7, 957 (2023), arXiv:2110.00258 [quant-ph].

[23] S. Yoshida, A. Soeda, and M. Murao, Universal adjointation of isometry operations using conversion of quantum supermaps, Quantum 9, 1750 (2025), arXiv:2401.10137 [quant-ph].

[24] J. F. Poyatos, J. I. Cirac, and P. Zoller, Complete Characterization of a Quantum Process: The Two-Bit Quantum Gate, Phys. Rev. Lett. 78, 390 (1997), arXiv:quant-ph/9611013 [quant-ph].

[25] I. L. Chuang and M. A. Nielsen, Prescription for experimental determination of the dynamics of a quantum black box, J. Mod. Opt. 44, 2455 (1997).

[26] S. Milz, F. A. Pollock, T. P. Le, G. Chiribella, and K. Modi, Entanglement, non-Markovianity, and causal non-separability, New J. Phys. 20, 033033 (2018), arXiv:1711.04065 [quant-ph].

[27] J. Wechs, H. Dourdent, A. A. Abbott, and C. Branciard, Quantum Circuits with Classical Versus Quantum Control of Causal Order, PRX Quantum 2, 030335 (2021), arXiv:2101.08796 [quant-ph].

[28] J. Watrous, The Theory of Quantum Information (Cambridge University Press, 2018).

[29] A. Barenco, A. Berthiaume, D. Deutsch, A. Ekert, R. Jozsa, and C. Macchiavello, Stabilization of quantum computations by symmetrization, SIAM Journal on Computing 26, 1541 (1997), arXiv:quant-ph/9604028.
[30] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, *Quantum Fingerprinting*, Phys. Rev. Lett. **87**, 167902 (2001), arXiv:quant-ph/0102001.

[31] D. W. Berry and A. M. Childs, *Black-box Hamiltonian simulation and unitary implementation*, Quantum Information and Computation **12**, 29 (2012), arXiv:0910.4157 [quant-ph].

[32] D. W. Berry, A. M. Childs, and R. Kothari, *Hamiltonian simulation with nearly optimal dependence on all parameters*, IEEE 56th Annual Symposium on Foundations of Computer Science **56**, 792 (2015), arXiv:1501.01715 [quant-ph].

[33] A. Montanaro and R. d. Wolf, *A survey of quantum property testing*, Theory of Computing Library Graduate Surveys, **7**, 1 (2016), arXiv:1310.2035 [quant-ph].

[34] Q. Dong, M. T. Quintino, A. Soeda, and M. Murao, *The quantum switch is uniquely defined by its action on unitary operations*, Quantum **7**, 1169 (2023), arXiv:2106.00034 [quant-ph].

[35] T. Odake, S. Yoshida, and M. Murao, *Analytical lower bound on the number of queries to a black-box unitary operation in deterministic exact transformations of unknown unitary operations*, Phys. Rev. Lett. **10.1103/drp2-rzzw** (2025), arXiv:2405.07625 [quant-ph].

[36] G. Rosenthal and H. Yuen, *Interactive proofs for synthesizing quantum states and unitaries*, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), 112:1 (2022), arXiv:2108.07192 [quant-ph].

[37] T. Metger and H. Yuen, *stateQIP = statePSPACE*, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 1349 (2023), arXiv:2301.07730 [quant-ph].

[38] D. Ebler, S. Salek, and G. Chiribella, *Enhanced Communication with the Assistance of Indefinite Causal Order*, Phys. Rev. Lett. **120**, 120502 (2018), arXiv:1711.10165 [quant-ph].

[39] P. A. Guérin and Č. Brukner, *Observer-dependent locality of quantum events*, New J. Phys. **20**, 103031 (2018), arXiv:1805.12429 [quant-ph].

[40] G. Chiribella, M. Banik, S. S. Bhattacharya, T. Guha, M. Alimuddin, A. Roy, S. Saha, S. Agrawal, and G. Kar, *Indefinite causal order enables perfect quantum communication with zero capacity channels*, New J. Phys. **23**, 033039 (2021), arXiv:1810.10457 [quant-ph].

[41] M. M. Taddei, J. Cariñe, D. Martínez, T. García, N. Guerreiro, A. A. Abbott, M. Araújo, C. Branciard, E. S. Gómez, S. P. Walborn, et al., *Computational advantage from the quantum superposition of multiple temporal orders of photonic gates*, PRX Quantum **2**, 010320 (2021), arXiv:2002.07817 [quant-ph].

[42] L. A. Rozema, T. Strömberg, H. Cao, Y. Guo, B.-H. Liu, and P. Walther, *Experimental aspects of indefinite causal order in quantum mechanics*, Nature Reviews Physics **6**, 483 (2024), arXiv:2405.00767 [quant-ph].

[43] G. Rubino, L. A. Rozema, D. Ebler, H. Kristjánsson, S. Salek, P. A. Guérin, A. A. Abbott, C. Branciard, Č. Brukner, G. Chiribella, et al., *Experimental quantum communication enhancement by superposing trajector-

ies, Phys. Rev. Res. **3**, 013093 (2021), arXiv:2007.05005 [quant-ph].

[44] H. Cao, J. Bavaresco, N.-N. Wang, L. A. Rozema, C. Zhang, Y.-F. Huang, B.-H. Liu, C.-F. Li, G.-C. Guo, and P. Walther, *Semi-device-independent certification of indefinite causal order in a photonic quantum switch*, Optica **10**, 561 (2023), arXiv:2202.05346 [quant-ph].

[45] M. Antesberger, M. T. Quintino, P. Walther, and L. A. Rozema, *Higher-Order Process Matrix Tomography of a Passively-Stable Quantum Switch*, PRX Quantum **5**, 010325 (2024), arXiv:2305.19386 [quant-ph].

[46] K. Goswami, Y. Cao, G. A. Paz-Silva, J. Romero, and A. G. White, *Increasing communication capacity via superposition of order*, Phys. Rev. Res. **2**, 033292 (2020), arXiv:1807.07383 [quant-ph].

[47] Y. Guo, X.-M. Hu, Z.-B. Hou, H. Cao, J.-M. Cui, B.-H. Liu, Y.-F. Huang, C.-F. Li, G.-C. Guo, and G. Chiribella, *Experimental Transmission of Quantum Information Using a Superposition of Causal Orders*, Phys. Rev. Lett. **124**, 030502 (2020), arXiv:1811.07526 [quant-ph].

[48] G. Chiribella and H. Kristjánsson, *Quantum Shannon theory with superpositions of trajectories*, Proc. R. Soc. A **475**, 20180903 (2019), arXiv:1812.05292 [quant-ph].

[49] H. Kristjánsson, W. Mao, and G. Chiribella, *Witnessing latent time correlations with a single quantum particle*, Phys. Rev. Res. **3**, 043147 (2021), arXiv:2004.06090 [quant-ph].

[50] A. Jamiolkowski, *Linear transformations which preserve trace and positive semidefiniteness of operators*, Rep. Math. Phys. **3**, 275 (1972).

[51] M.-D. Choi, *Completely positive linear maps on complex matrices*, Linear Algebra Its Appl. **10**, 285 (1975).

[52] W. Yokojima, M. T. Quintino, A. Soeda, and M. Murao, *Consequences of preserving reversibility in quantum superchannels*, Quantum **5**, 441 (2021), arXiv:2003.05682 [quant-ph].

[53] P. Skrzypczyk and D. Cavalcanti, *Semidefinite Programming in Quantum Information Science* (IOP Publishing, 2023).

[54] G. Chiribella and D. Ebler, *Optimal quantum networks and one-shot entropies*, New J. Phys. **18**, 093053 (2016), arXiv:1606.02394 [quant-ph].

[55] M. T. Quintino and J. Bavaresco, Zenodo, mtcq/switch_simulation: switch_simulation_v1 (2025), https://doi.org/10.5281/zenodo.17170679.

[56] B. O'Donoghue, E. Chu, N. Parikh, and S. Boyd, *Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding*, J. Optim. Theory Appl. **169**, 1042 (2016), arXiv:1312.3039 [math.OC].

[57] B. O'Donoghue, E. Chu, N. Parikh, and S. Boyd, SCS: Splitting conic solver, version 3.2.6, https://github.com/cvxgrp/scs (2023).

[58] MOSEK ApS, *The MOSEK optimization toolbox for MATLAB manual*. Version 10.1. (2024).

[59] M. Ozawa, *Quantum measuring processes of continuous observables*, J. Math. Phys. **25**, 79 (1984).

[60] M. M. Wilde, *Quantum Information Theory*, 2nd ed. (Cambridge University Press, 2017) arXiv:1106.1445
[quant-ph].

[61] F. Buscemi, K. Kobayashi, S. Minagawa, P. Perinotti, and A. Tosini, Unifying different notions of quantum incompatibility into a strict hierarchy of resource theories of communication, *Quantum* 7, 1035 (2023), arXiv:2211.09226 [quant-ph].

[62] S. Yoshida, A. Soeda, and M. Murao, Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly, *Phys. Rev. Lett.* 131, 120602 (2023), arXiv:2209.02907 [quant-ph].

[63] The MathWorks Inc., MATLAB version: 9.13.0 (R2022b) (2022).

[64] N. Johnston, QETLAB: A MATLAB toolbox for quantum entanglement, version 0.9, https://qetlab.com (2016).

[65] A. Roy and A. J. Scott, Unitary designs and codes, *Des. Codes Cryptogr.* 53, 13–31 (2009), arXiv:0809.3813 [math.CO].

[66] https://en.wikipedia.org/wiki/cholesky_decomposition (accessed on 26 Sep 2024).

[67] S. M. Rump, Verification of positive definiteness, *BIT Numer. Math.* 46, 433 (2006).

[68] https://en.wikipedia.org/wiki/arbitrary-precision_arithmetic (accessed on 26 Sep 2024).

Innovation, Science and Economic Development and by the Province of Ontario through the Ministry of Colleges and Universities.

## AUTHOR CONTRIBUTIONS

MM conceived the main idea and initiated the project. HK, MM, TO, PT, and SY developed the results related to deterministic exact simulations. These authors contributed equally: HK, TO, and SY. JB and MTQ developed the results related to probabilistic and approximate simulations. Code: JB developed the SDP-related code; MTQ developed the code for the computer-assisted proofs. All authors contributed to discussions, refining of the proofs, and writing the paper.

## COMPETING INTERESTS

The authors declare no competing interests.

## ACKNOWLEDGEMENTS

We would like to thank Alastair Abbott, Emanuel-Cristian Boghiu, Cyril Branciard, Anne Broadbent, Giulio Chiribella, Arthur Mehta, Simon Milz, Pierre Pocreau, Louis Salvail, Mykola Semenyakin, Jacopo Surace and Matt Wilson for helpful discussions. We are also grateful to Denis Rosset and Siegfried M. Rump for helpful discussions regarding computer-assisted proofs. JB acknowledges funding from the Swiss National Science Foundation (SNSF) through the funding schemes Swiss Postdoctoral Fellowship (project 216979), NCCR Swiss-MAP (project 182902), and project 192244; PT acknowledges funding from the Japan Society for the Promotion of Science (JSPS) Postdoctoral Fellowships for Research in Japan. SY acknowledges support by Japan Society for the Promotion of Science (JSPS) KAKENHI Grant Number 23KJ0734, FoPM, WINGS Program, the University of Tokyo, and DAIKIN Fellowship Program, the University of Tokyo. This work was supported by the MEXT Quantum Leap Flagship Program (MEXT QLEAP) JP-MXS0118069605, JPMXS0120351339, the Japan Society for the Promotion of Science (JSPS) KAKENHI Grant Number 21H03394 and 23K21643, and IBM Quantum. We acknowledge the Japanese-French Laboratory for Informatics (JFLI) for the support on organizing the Japanese-French Quantum Information 2023 workshop. Research at Perimeter Institute is supported in part by the Government of Canada through the Department of
# APPENDIX

The Appendix is organized in the following way:

<table><tbody><tr><td>• Appendix A: Definitions and Choi operators</td><td>18</td></tr><tr><td>- A1. The quantum switch Choi operator and Choi operator fidelity</td><td>18</td></tr><tr><td>- A2. Quantum combs, probabilistic quantum combs, and projectors</td><td>19</td></tr><tr><td>- A3. QC-CCs and probabilistic QC-CCs</td><td>20</td></tr><tr><td>• Appendix B: General simulation scenarios</td><td>21</td></tr><tr><td>- B1. The action of the quantum switch on bipartite quantum channels</td><td>21</td></tr><tr><td>- B2. The action of the quantum switch on quantum instruments</td><td>22</td></tr><tr><td>- B3. The relationship with Stinespring dilation of quantum channels</td><td>23</td></tr><tr><td>- B4. Theorem 1: A simulation for bipartite unitary channels U<sub>A</sub> and bipartite general channels B</td><td>25</td></tr><tr><td>• Appendix C: Full proof of Theorem 2</td><td>27</td></tr><tr><td>- C1. Lemma 1</td><td>29</td></tr><tr><td>- C2. Lemma 2 (for M, N ∈ N<sup>+</sup>)</td><td>29</td></tr><tr><td>- C3. Lemma 3 (for M, N ∈ N<sup>+</sup>)</td><td>31</td></tr><tr><td>- C4. Lemma 4 (for M &lt; 4<sup>n</sup>/2 + 2 and N = 1)</td><td>32</td></tr><tr><td>- C5. Lemma 5 (for max{M, N} ≤ max{2, d − 1})</td><td>39</td></tr><tr><td>- C6. Lemma 6</td><td>42</td></tr><tr><td>- C7. Lemma 7</td><td>42</td></tr><tr><td>• Appendix D: Possible restricted simulations for qubit channels</td><td>44</td></tr><tr><td>• Appendix E: No-go results for unitary channels</td><td>45</td></tr><tr><td>• Appendix F: Efficient certification that a matrix is positive semidefinite</td><td>46</td></tr></tbody></table>

## Appendix A: Definitions and Choi operators

In this section, we explicitly define the key higher-order transformations used in the main text in terms of their Choi operators, which are crucial for the SDP implementation of our methods.

### A1. The quantum switch Choi operator and Choi operator fidelity

We begin with the Choi operator of the quantum switch transformation [8]. The quantum switch higher-order transformation $S$ defined in the main text in terms of its Kraus decomposition [Eqs. (1) and (2)], can be equivalently expressed by its associated Choi operator $S \in \mathcal{L}(\mathcal{H}^{cI} \otimes \mathcal{H}^{tI} \otimes \mathcal{H}^{A_I} \otimes \mathcal{H}^{A_O} \otimes \mathcal{H}^{B_I} \otimes \mathcal{H}^{B_O} \otimes \mathcal{H}^{t_O} \otimes \mathcal{H}^{c_O})$. Let the vector $|S\rangle$ be defined as

$$|S\rangle := |0\rangle^{cI} |1\rangle^{tIA_I} |1\rangle^{AOB_I} |1\rangle^{BOTO} |0\rangle^{cO} + |1\rangle^{cI} |1\rangle^{tIB_I} |1\rangle^{BOA_I} |1\rangle^{AOTO} |1\rangle^{cO}, \quad (A1)$$

where $|1\rangle^{XY} := \sum_i |i\rangle^X |i\rangle^Y$ is the vector related to the Choi operator $|1\rangle\langle 1|$ of an identity channel from space $X$ to $Y$. Then, the Choi operator of the quantum switch is defined as

$$S := |S\rangle\langle S|. \quad (A2)$$
This is the operator $S$ that appears in the first constraint of the SDPs associated to the primal problem [SDP (27)] and dual problem [SDP (28)] in the main text.

The Choi operator of the quantum channel $S(A, B)$ that results from the action of the quantum switch transformation $S$ on input channels $A$ and $B$ can be expressed in terms of their respective Choi operators $S, J^A$, and $J^B$, as $S * (J^A \otimes J^B) \in \mathcal{L}(\mathcal{H}^{cI} \otimes \mathcal{H}^{tI} \otimes \mathcal{H}^{to} \otimes \mathcal{H}^{co})$, where * is the link product defined in the Methods section of the main text [Eq. (18)].

In the case considered in the main text where the quantum switch has a fixed input state for its control and target systems, respectively given by $\sigma_c = |+\rangle\langle+| \in \mathcal{L}(\mathcal{H}^{cI})$ and $\rho_t = |0\rangle\langle0| \in \mathcal{L}(\mathcal{H}^{tI})$, we defined the resulting transformation as $S_{+0}(\cdot, \cdot) := S(\cdot, \cdot)[|+\rangle\langle+| \otimes |0\rangle\langle0|]$. This higher-order operation has an associated Choi operator $S_{+0} \in \mathcal{L}(\mathcal{H}^{A_I} \otimes \mathcal{H}^{A_O} \otimes \mathcal{H}^{B_I} \otimes \mathcal{H}^{B_O} \otimes \mathcal{H}^{t_O} \otimes \mathcal{H}^{c_O})$ given by

$$S_{+0} := (|+\rangle\langle+| \otimes |0\rangle\langle0|) * S \quad (A3)$$

$$= |S_{+0}\rangle\langle S_{+0}|, \quad (A4)$$

where

$$|S_{+0}\rangle := (\langle+|^{cI} \langle0|^{tI} \otimes 1)|S\rangle = \frac{1}{\sqrt{2}} (|0\rangle^{A_I} |1\rangle^{A_O B_I} |1\rangle^{B_O t_O} |0\rangle^{c_O} + |1\rangle^{B_I} |1\rangle^{B_O A_I} |1\rangle^{A_O t_O} |1\rangle^{c_O}). \quad (A5)$$

We now define the Choi operator fidelity. Let $\tilde{S}$ be a higher-order transformation that acts on the same spaces as the quantum switch $S$, and let $\tilde{S}_{+0} := \tilde{S}(\cdot, \cdot)[|+\rangle\langle+| \otimes |0\rangle\langle0|]$ be $\tilde{S}$ with fixed input states for its control and target systems. The Choi operator fidelity between $S_{+0}$ and any higher-order operation $\tilde{S}_{+0}$, with Choi operator $\tilde{S}_{+0}$ is given by

$$F(S_{+0}, \tilde{S}_{+0}) := \frac{1}{(d_{AO} d_{BO})^2} \mathrm{tr}(S_{+0} \tilde{S}_{+0}) = \frac{1}{(d_{AO} d_{BO})^2} |\langle s_{+0} | \tilde{S}_{+0} | s_{+0} \rangle|, \quad (A6)$$

where the factor $d_{AO}d_{BO} = \mathrm{tr}(S_{+0}) = \mathrm{tr}(\tilde{S}_{+0})$ ensures that $F(S_{+0}, \tilde{S}_{+0}) \in [0, 1]$.

## A2. Quantum combs, probabilistic quantum combs, and projectors

A probabilistic quantum comb is a quantum comb that yields a classical output with a certain probability. In our case, we consider probabilistic quantum combs that have two possible classical outcomes, success or failure. We recall that such transformations can be implemented by a quantum comb that additionally output a flag system that encodes the success or failure outcome, followed by a dichotomic quantum measurement of the flag system. In the case of a quantum comb $C = C_s + C_f$ that performs a probabilistic simulation of the quantum switch, its associated Choi operator is given by $C = C_s + C_f$, where $C, C_s, C_f \in \mathcal{L}(\mathcal{H}^{cI} \otimes \mathcal{H}^{tI} \otimes (\mathcal{H}^{A_I} \otimes \mathcal{H}^{A_O})^{\otimes k_A} \otimes (\mathcal{H}^{B_I} \otimes \mathcal{H}^{B_O})^{\otimes k_B} \otimes \mathcal{H}^{t_O} \otimes \mathcal{H}^{c_O})$. These operators are characterised by

$$C_s \geq 0 \quad (A7)$$

$$C_f = C - C_s \geq 0 \quad (A8)$$

$$\mathrm{tr}(C) = d_{cI} d_{tI} d_{AO}^{k_A} d_{BO}^{k_B} \quad (A9)$$

$$C = \mathbb{P}_k(C), \quad (A10)$$

where $k = k_A + k_B$ is the total number of slots in the quantum comb $C$, and $\mathbb{P}_k$ is the projector onto the subspace spanned by $k$-slot quantum combs.

The projector $\mathbb{P}_k$ is defined in full generality in Ref. [5]. For sake of completeness, we explicitly write $\mathbb{P}_k$ here in the cases where $k \in \{2, 3, 4\}$, which are the ones involved in our numerical calculations. To simplify the notation in the definition of the projector, let us define a $k$-slot quantum comb by its Choi operator $C \in \mathcal{L}(\mathcal{H}^P \otimes \mathcal{H}^{I_1} \otimes \mathcal{H}^{O_1} \otimes \dots \otimes \mathcal{H}^{I_k} \otimes \mathcal{H}^{O_k} \otimes \mathcal{H}^F)$. Then, let us define the trace-and-replace operation acting on the subspace $\mathcal{H}^X$ of an operator $C$ as

$$xC := \mathrm{tr}_X(C) \otimes \frac{1^C}{d_C}. \quad (A11)$$
We are now ready to explicitly write the projector $\mathbb{P}_k$ for $k \in \{2, 3, 4\}$. For the case where $k = 2$,

$$ \mathbb{P}_2(C) = C - _F C + _{O_2F} C - _{I_2O_2F} C + _{O_1I_2O_2F} C - _{I_1O_1I_2O_2F} C + _{PI_1O_1I_2O_2F} C. \quad (A12) $$

For the case where $k = 3$,

$$ \mathbb{P}_3(C) = C - _F C + _{O_3F} C - _{I_3O_3F} C + _{O_2I_3O_3F} C - _{I_2O_2I_3O_3F} C + _{O_1I_2O_2I_3O_3F} C \\ - _{I_1O_1I_2O_2I_3O_3F} C + _{PI_1O_1I_2O_2I_3O_3F} C. \quad (A13) $$

Finally, for the case where $k = 4$,

$$ \mathbb{P}_4(C) = C - _F C + _{O_4F} C - _{I_4O_4F} C + _{O_3I_4O_4F} C - _{I_3O_3I_4O_4F} C + _{O_2I_3O_3I_4O_4F} C - _{I_2O_2I_3O_3I_4O_4F} C \\ + _{O_1I_2O_2I_3O_3I_4O_4F} C - _{I_1O_1I_2O_2I_3O_3I_4O_4F} C + _{PI_1O_1I_2O_2I_3O_3I_4O_4F} C. \quad (A14) $$

For convenience, we also define the dual affine projector used in the dual formulation of the SDP in the main text [Eq. (28)]. Given a set of operators $\mathcal{A}$, its dual affine set $\mathcal{B}$ is the set of all operators $\mathcal{B}$ such that $\mathrm{tr}(A^\dagger \mathcal{B}) = 1$ for all $A \in \mathcal{A}$. Hence, the dual affine set of the set of Choi operators of quantum combs $C \in \mathcal{L}(\mathcal{H}^P \otimes \mathcal{H}^{I_1} \otimes \mathcal{H}^{O_1} \otimes \dots \otimes \mathcal{H}^{I_k} \otimes \mathcal{H}^{O_k} \otimes \mathcal{H}^F)$ is the set of all operators $\Gamma \in \mathcal{L}(\mathcal{H}^P \otimes \mathcal{H}^{I_1} \otimes \mathcal{H}^{O_1} \otimes \dots \otimes \mathcal{H}^{I_k} \otimes \mathcal{H}^{O_k} \otimes \mathcal{H}^F)$ such that $\mathrm{tr}(C\Gamma) = 1$. The operators in the dual affine set of quantum combs are themselves a particular case of quantum combs, and can be characterized by projectors $\bar{\mathbb{P}}_k$ given by [5]

$$ \bar{\mathbb{P}}_k(\Gamma) = \Gamma - \mathbb{P}_k(\Gamma) + _{PI_1I_2\dots I_kO_kF}\Gamma. \quad (A15) $$

In our numerical calculations, we used the code available in the repository of Ref. [5] to generate the above projector constraints.

### A3. QC-CCs and probabilistic QC-CCs

We now present the explicit constraints for QC-CC transformations. QC-CCs and probabilistic QC-CCs have been defined in full generality and for any number of slots in Ref. [27]. Here, we write these definitions explicitly for the cases of $k = 2$ and $k = 3$ slots, which were used in our numerical calculations. Since we only evaluated the maximal probability of simulating the quantum switch with a QC-CC in the restricted simulation scenario, where the input control and target systems are fixed, we write the explicit constraints for a probabilistic QC-CC with fixed input systems (compared to the definition of quantum combs in this section, this is the equivalent of a scenario where $d_P = 1$).

Unlike the case of quantum combs, to define the Choi operator $W = W_s + W_f$ associated to a probabilistic QC-CC, where $W, W_s, W_f \in \mathcal{L}(\mathcal{H}^{I_1} \otimes \mathcal{H}^{O_1} \otimes \dots \otimes \mathcal{H}^{I_k} \otimes \mathcal{H}^{O_k} \otimes \mathcal{H}^F)$, it is necessary but not sufficient to say that $W_s \ge 0$, $W_f = W - W_s \ge 0$ and $W$ is a QC-CC, as individual constraints must be applied to $W_s$ and $W_f$ as well to ensure validity of the overall transformation.

In the case where $k = 2$, we have that

$$ W = W_s + W_f \quad (A16) $$

$$ \mathrm{tr}(W) = d_{O_1} d_{O_2}, \quad (A17) $$

where

$$ W_s = W_s^{12F} + W_s^{21F}, \quad W_f = W_f^{12F} + W_f^{21F}, \quad (A18) $$

such that $W_s^{12F} \ge 0$, $W_s^{21F} \ge 0$, $W_f^{12F} \ge 0$, and $W_f^{21F} \ge 0$, and additionally $W^{12F} := W_s^{12F} + W_f^{12F}$ must be a quantum comb with the order $I_1O_1I_2O_2F$, and $W^{21F} := W_s^{21F} + W_f^{21F}$ must be a quantum comb with the order $I_2O_2I_1O_1F$.
In the case where $k = 3$, we have that

$$W = W_s + W_f \qquad (A19)$$

$$\mathrm{tr}(W) = d_{O_1} d_{O_2} d_{O_3}. \qquad (A20)$$

where

$$W_s = W_s^{123F} + W_s^{132F} + W_s^{213F} + W_s^{231F} + W_s^{312F} + W_s^{321F} \qquad (A21)$$

$$W_f = W_f^{123F} + W_f^{132F} + W_f^{213F} + W_f^{231F} + W_f^{312F} + W_f^{321F}, \qquad (A22)$$

where $W_s^{xyzF} \ge 0$ and $W_f^{xyzF} \ge 0$ for all $xyz \in \mathrm{Perm}(1, 2, 3)$. Moreover, we define $W^{xyzF} := W_s^{xyzF} + W_f^{xyzF}$ for all $xyz \in \mathrm{Perm}(1, 2, 3)$ and impose that the operators $W^{123F}$ and $W^{132F}$ must satisfy

$$F W^{123F} = O_3 F W^{123F}, \qquad F W^{132F} = O_2 F W^{132F} \qquad (A23)$$

$$I_3 O_3 F W^{123F} = O_2 I_3 O_3 F W^{123F}, \qquad I_2 O_2 F W^{132F} = O_3 I_2 O_2 F W^{132F} \qquad (A24)$$

$$I_2 O_2 I_3 O_3 F W^{123F} + I_3 O_3 I_2 O_2 F W^{132F} = O_1 (I_2 O_2 I_3 O_3 F W^{123F} + I_3 O_3 I_2 O_2 F W^{132F}). \qquad (A25)$$

Similarly, $W^{213F}$ and $W^{231F}$ must satisfy

$$F W^{213F} = O_3 F W^{213F}, \qquad F W^{231F} = O_1 F W^{231F} \qquad (A26)$$

$$I_3 O_3 F W^{213F} = O_1 I_3 O_3 F W^{213F}, \qquad I_1 O_1 F W^{231F} = O_3 I_1 O_1 F W^{231F} \qquad (A27)$$

$$I_1 O_1 I_3 O_3 F W^{213F} + I_3 O_3 I_1 O_1 F W^{231F} = O_2 (I_1 O_1 I_3 O_3 F W^{213F} + I_3 O_3 I_1 O_1 F W^{231F}). \qquad (A28)$$

Finally, $W^{312F}$ and $W^{321F}$ must satisfy

$$F W^{312F} = O_2 F W^{312F}, \qquad F W^{321F} = O_1 F W^{321F} \qquad (A29)$$

$$I_2 O_2 F W^{312F} = O_1 I_2 O_2 F W^{312F}, \qquad I_1 O_1 F W^{321F} = O_2 I_1 O_1 F W^{321F} \qquad (A30)$$

$$I_1 O_1 I_2 O_2 F W^{312F} + I_2 O_2 I_1 O_1 F W^{321F} = O_3 (I_1 O_1 I_2 O_2 F W^{312F} + I_2 O_2 I_1 O_1 F W^{321F}). \qquad (A31)$$

## Appendix B: General simulation scenarios

In this section, we discuss the differences between simulation scenarios where the quantum switch acts on general quantum channels, on only part of general quantum channels, or on quantum instruments, highlighting how they relate to the action of the quantum switch on unitary channels. We also demonstrate how the switch simulation that we introduced in the circuit in Eq. (7) related to Thm. 1 fits into this context.

### B1. The action of the quantum switch on bipartite quantum channels

The first simulation scenario discussed in the main text is the one where the quantum switch $S$ acts on the “entire” quantum channels $A$ and $B$, as represented in Fig. 2, in the main text. Formally, this is the case where the quantum switch $S$ acts on a pair of single-party (single input system, single output system) channels $A : \mathcal{L}(\mathcal{H}^{A_t}) \to \mathcal{L}(\mathcal{H}^{A_o})$ and $B : \mathcal{L}(\mathcal{H}^{B_t}) \to \mathcal{L}(\mathcal{H}^{B_o})$, and outputs another channel $S(A, B) : \mathcal{L}(\mathcal{H}^{c_t} \otimes \mathcal{H}^{t_t}) \to \mathcal{L}(\mathcal{H}^{c_o} \otimes \mathcal{H}^{t_o})$. However, quantum theory also allows one to apply the quantum switch on parts of bipartite (two input systems, two output systems) channels $A : \mathcal{L}(\mathcal{H}^{A_t} \otimes \mathcal{H}^{A'_t}) \to \mathcal{L}(\mathcal{H}^{A_o} \otimes \mathcal{H}^{A'_o})$ and $B : \mathcal{L}(\mathcal{H}^{B_t} \otimes \mathcal{H}^{B'_t}) \to \mathcal{L}(\mathcal{H}^{B_o} \otimes \mathcal{H}^{B'_o})$, where the dimension of the primed spaces is arbitrary. This results in the quantum channel $S \otimes \mathcal{I}(A, B) : \mathcal{L}(\mathcal{H}^{A'_t} \otimes \mathcal{H}^{c'_t} \otimes \mathcal{H}^{t'_t} \otimes \mathcal{H}^{B'_t}) \to \mathcal{L}(\mathcal{H}^{A'_o} \otimes \mathcal{H}^{c'_o} \otimes \mathcal{H}^{t'_o} \otimes \mathcal{H}^{B'_o})$, where $\mathcal{I}$ is the identity higher-order transformation. Since the dimension of the primed spaces is arbitrary, all multi-partite channels can be described in this context as bipartite channels, which are the most general kinds of deterministic transformations between quantum states one can consider. This case is illustrated in Fig. 3 of the main text.
<figure><img src="image_8.png" /><figcaption>Figure B1. General simulation of the quantum switch. A higher-order transformation $\mathcal{C}$, which can be a quantum comb or a QC-CC, that acts on part of several copies of input bipartite quantum channels A and B is a simulation of the quantum switch S if it reproduces the action of the quantum switch on all arbitrary pairs of bipartite channels A and B.</figcaption></figure>

As mentioned in the main text, the impossibility of simulating the action of the quantum switch on all single-party quantum channels, for some number of calls $k_A$ and $k_B$, implies the impossibility of simulating the action of the quantum switch on all bipartite channels with the same number of calls. Hence, when focusing on no-go simulation proofs, we can restrict ourselves to considering only single-party channels. However, conversely, should a simulation of the action of the quantum switch on all single-party channels exist for some number of calls $k_A$ and $k_B$, this does not necessarily imply that a simulation would also exists for the action of the quantum switch on all bipartite channels.

For this reason, in order to have a fully general simulation of the quantum switch, one must consider the case where the quantum switch acts on only part of a bipartite channel, as illustrated in Fig. B1. That is, a full simulation of the quantum switch is only obtained when, for every pair of bipartite channels $A: \mathcal{L}(\mathcal{H}^{A_I} \otimes \mathcal{H}^{A'_I}) \to \mathcal{L}(\mathcal{H}^{A_O} \otimes \mathcal{H}^{A'_O})$ and $B: \mathcal{L}(\mathcal{H}^{B_I} \otimes \mathcal{H}^{B'_I}) \to \mathcal{L}(\mathcal{H}^{B_O} \otimes \mathcal{H}^{B'_O})$, there exists $k_A, k_B \in \mathbb{N}$ such that,

$$ \mathcal{C}(A^{\otimes k_A}, B^{\otimes k_B}) = S \otimes \mathcal{I}(A, B) \qquad (B1) $$

where $\mathcal{C}$ is a quantum comb, or a QC-CC. This most general simulation scenario is depicted in Fig. B1.

In the next section, we show how a simulation of the action of the quantum switch on all pairs of bipartite channels indeed covers all possible quantum operations the quantum switch could take as input, including the probabilistic ones, such as quantum instruments.

## B2. The action of the quantum switch on quantum instruments

Higher-order transformations like the quantum switch can also be applied to quantum instruments, which describe the most general probabilistic transformation between quantum states.

Quantum instruments are transformations that map a quantum state to another quantum state with a certain probability, also outputting a classical outcome. Physically, this describes, for instance, a measurement process where both a classical outcome and a post-measurement quantum state are produced. They can be described by a collection of CP maps $\{I_a\}_a$ which add to a CPTP map, i.e., such that $\sum_a I_a$ is CPTP. A quantum instrument takes a quantum state $\rho$ as input, and outputs a classical outcome $a$, together with the quantum state $\rho_a := I_a[\rho]/\text{tr}(I_a[\rho])$, with probability $p_a := \text{tr}(I_a[\rho])$. Quantum instruments can be equivalently represented by deterministic quantum channels, which instead of yielding a classical outcome, prepare an additional output pure quantum state $|a\rangle$ that encodes the value of the instrument's classical outcome $a$ in a perfectly discriminable manner [59–61]. In other words, a quantum instrument with $N \in \mathbb{N}$ outcomes $\{I_a\}_{a=1}^N$ with $I_a: \mathcal{L}(\mathcal{H}^I) \to \mathcal{H}(\mathcal{H}^O)$ is equivalent to a quantum channel $A: \mathcal{L}(\mathcal{H}^I) \to \mathcal{H}(\mathcal{H}^O \otimes \mathbb{C}^N)$ given by

$$ A[\rho] := \sum_{a=1}^{N} I_a[\rho] \otimes |a\rangle\langle a|, \qquad (B2) $$
<figure><img src="image_9.png" /><figcaption>Figure B2. General quantum channels and quantum instruments. (a) Quantum circuit representation of the Stinespring dilation $U_A$ of the general quantum channel $A$ presented in Eq. (B3). (b) Quantum circuit representation of a quantum instrument $\{I_a\}_a$ by a quantum channel $A[\rho] := \sum_a I_a[\rho] \otimes |a\rangle\langle a|$, which is then represented by its Stinespring dilation $U_A$.</figcaption></figure>

and illustrated in Fig. B2(b). By representing a quantum instrument as a particular case of a bipartite quantum channel, namely one with a single input system and two output systems, it is straightforward to see that the action of the quantum switch on a pair of instruments $\{I_a^A\}_a$ and $\{I_b^B\}_b$ constitutes a special case of its action on arbitrary bipartite channels $A$ and $B$. Hence, a simulation of the quantum switch for all bipartite channels can be used for a simulation of the quantum switch for all instruments.

Lastly, one might also consider the scenario where the quantum switch acts on a part of bipartite instruments. Notice, however, that from the channel representation of instruments, it is clear that this scenario is included in that of arbitrary bipartite channels discussed in the previous section.

## B3. The relationship with Stinespring dilation of quantum channels

The Stinespring dilation theorem [28] states that the action of every general quantum channel, i.e, CPTP map, $A: \mathcal{L}(\mathcal{H}^I) \to \mathcal{L}(\mathcal{H}^O)$ can be written as

$$A[\rho] = \text{tr}_{\text{aux}_O} (U_A[\rho^I \otimes |0\rangle\langle 0|]), \quad (B3)$$

for some unitary channel $U_A: \mathcal{L}(\mathcal{H}^I \otimes \mathcal{H}^{\text{aux}_I}) \to \mathcal{L}(\mathcal{H}^O \otimes \mathcal{H}^{\text{aux}_O})$ that acts jointly on the input system and an auxiliary system (of sufficiently large dimension), which can be initialized to the state $|0\rangle$ without loss of generality. We emphasize that the discarding of the output auxiliary system is necessary for the equivalence between non-unitary channels and their unitary channel dilation. This equivalence between arbitrary quantum channels and their unitary channel dilation is depicted in Fig. B2(a). Additionally, note that the Stinespring dilation can be combined with the channel representation of a quantum instrument presented in Eq. (B2), so that all instruments can also be viewed as a unitary channel that makes use of an auxiliary system which is later discarded, as depicted in Fig. B2(b).

Exploiting the Stinespring dilation of general quantum instruments and general quantum channels into bipartite unitary channels that discard their auxiliary system, one can express the action—and consequently the simulation—of the quantum switch solely in terms of unitary channels. However, in order to do so, it is necessary to keep track of exactly which systems are acted upon, preserved, and discarded. In Fig. B3, we show precisely how the action of the quantum switch on the different kinds of inputs discussed so far can be expressed in terms of its action on unitary channels.

In Fig. B3(a), we depict the action of the quantum switch on general single-party channels. In Fig. B3(b), we represent the action of the quantum switch on single-party quantum instruments. In Fig. B3(c), we show the action of the switch in its most general case: when it acts on only part of bipartite general channels. Finally, in Fig. B3(d), the action of the switch on part of bipartite instruments is pictured. Trivially, the case in Fig. B3(a) is a particular case of Fig. B3(c). Notice, moreover, how both the cases of Fig. B3(b) and (d), concerning quantum instruments, are also particular cases of Fig. B3(c). In the latter case in particular, this is because the dimension of the primed spaces of the input bipartite channels—the ones that the switch does not act upon—are arbitrary, and hence, the quantum outputs $|a\rangle$ and $|b\rangle$ of the instruments can be absorbed into the other output system of the unitary channels that is not acted upon by the quantum switch.
<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /><figcaption>Figure B3. **The action of the quantum switch.** Depiction of the action of the quantum switch on (a) general single-party quantum channels; (b) general single-party quantum instruments; (c) part of general bipartite quantum channels, and; (d) part of general bipartite quantum instruments; as a function of the action of the quantum switch on the Stinespring dilation of the input channels.</figcaption></figure>
## B4. Theorem 1: A simulation for bipartite unitary channels $U_A$ and bipartite general channels $B$

In this section, we prove Thm. 1 from the main text and discuss how this particular-case simulation compares to more general simulation scenarios. We start by reproducing Eq. (6) of the main text which defines a general simulation of the quantum switch. Namely, a simulation $\mathcal{C}$ that is able to prepare, with some finite number of calls $k_A$ and $k_B$, a channel $\mathcal{C}(A^{\otimes k_A}, B^{\otimes k_B})$ such that

$$ \mathcal{C}(A^{\otimes k_A}, B^{\otimes k_B}) = \mathcal{S} \otimes \mathcal{I}(A, B) \quad \forall A, B, \qquad (B4) $$

where $A, B$ are arbitrary quantum channels, is a higher-order transformation that can simulate the action of the quantum switch in its most general form.

We are now ready to restate and prove Theorem 1:

**Theorem 1.** The action of the quantum switch on part of bipartite quantum channels can be deterministically simulated by a quantum circuit that has access to an extra call to one the input channels, as long as that channel is restricted to being unitary.

In other words, if $A$ is a bipartite unitary channel and $B$ is a bipartite general channel, there exists a quantum circuit described by a higher-order transformation $\mathcal{C}$ that satisfies Eq. (B4) for $k_A = 2$ and $k_B = 1$.

The proof is based on the explicit construction of the following quantum circuit, presented as Eq. (7) in the main text and repeated here for convenience:

<figure><img src="image_14.png" /></figure>

*Proof.* Let $A : \mathcal{L}(\mathcal{H}^{A_I} \otimes \mathcal{H}^{A'_I}) \to \mathcal{L}(\mathcal{H}^{A_O} \otimes \mathcal{H}^{A'_O})$ be a bipartite channel with Kraus operators $\{A_i\}$ where $A_i : \mathcal{H}^{A_I} \otimes \mathcal{H}^{A'_I} \to \mathcal{H}^{A_O} \otimes \mathcal{H}^{A'_O}$. Similarly, let $B : \mathcal{L}(\mathcal{H}^{B_I} \otimes \mathcal{H}^{B'_I}) \to \mathcal{L}(\mathcal{H}^{B_O} \otimes \mathcal{H}^{B'_O})$ be a bipartite channel with Kraus operators $\{B_j\}$ where $B_j : \mathcal{H}^{B_I} \otimes \mathcal{H}^{B'_I} \to \mathcal{H}^{B_O} \otimes \mathcal{H}^{B'_O}$. The action of the quantum switch $\mathcal{S}$ on part of these bipartite channels results in the quantum channel $\mathcal{S} \otimes \mathcal{I}(A, B) : \mathcal{L}(\mathcal{H}^{c_I} \otimes \mathcal{H}^{t_I} \otimes \mathcal{H}^{A'_I} \otimes \mathcal{H}^{B'_I}) \to \mathcal{L}(\mathcal{H}^{c_O} \otimes \mathcal{H}^{t_O} \otimes \mathcal{H}^{A'_O} \otimes \mathcal{H}^{B'_O})$, whose definition is implied by the action of the quantum switch on single-party channels and linearity. It is given by

$$ \mathcal{S} \otimes \mathcal{I}(A, B)[\sigma_c \otimes \rho_t \otimes \omega_{A'B'}] = \sum_{i,j} S_{ij}(\sigma_c \otimes \rho_t \otimes \omega_{A'B'}) S_{ij}^{\dagger}, \qquad (B6) $$

where $\omega_{A'B'} \in \mathcal{L}(\mathcal{H}^{A'_I} \otimes \mathcal{H}^{B'_I})$ is an arbitrary state of the quantum system in the primed spaces of Alice and Bob, which are not acted upon by the quantum switch. Before explicitly writing the $S_{ij}$, it is convenient to decompose the Kraus operators $A_i$ and $B_i$ into linear combinations of operators that factorize between the primed and nonprimed spaces, which can always be done without loss of generality. It follows from linearity that one can always write

$$ A_i = \sum_a \alpha_{a|i} A(a) \otimes A'(a) \qquad (B7) $$

for some $\alpha_{a|i} \in \mathbb{C}$, $A(a) : \mathcal{H}^{A_I} \to \mathcal{H}^{A_O}$, and $A'(a) : \mathcal{H}^{A'_I} \to \mathcal{H}^{A'_O}$. Similarly, one can write

$$ B_j = \sum_b \beta_{b|j} B(b) \otimes B'(b) \qquad (B8) $$
for some $\beta_{b|j} \in \mathbb{C}$, $\mathbf{B}(b) : \mathcal{H}^{B_i} \to \mathcal{H}^{B_o}$, and $\mathbf{B}'(b) : \mathcal{H}^{B'_i} \to \mathcal{H}^{B'_o}$. Then, the Kraus operators $\{S_{ij}\}$ in Eq. (B6) take the form

$$S_{ij} = |0\rangle\langle 0| \otimes \sum_{ab} \alpha_{a|i} \beta_{b|j} \mathbf{B}(b) \mathbf{A}(a) \otimes \mathbf{A}'(a) \otimes \mathbf{B}'(b) + |1\rangle\langle 1| \otimes \sum_{ab} \alpha_{a|i} \beta_{b|j} \mathbf{A}(a) \mathbf{B}(b) \otimes \mathbf{A}'(a) \otimes \mathbf{B}'(b), \quad (B9)$$

where the order of the spaces from left to right in each term is control, target, and Alice and Bob's primed systems.

The transformation of the quantum circuit in Eq. (B5) that uses two calls of the quantum channel A and a single call of the quantum channel B in the order ABA results in a quantum channel $\mathcal{C}(A^{\otimes 2}, B)$ which has Kraus operators

$$C_{ijk} = |0\rangle\langle 0| \otimes \mathbf{A}_k \otimes \sum_{ab} \alpha_{a|i} \beta_{b|j} \mathbf{A}'(a) \otimes \mathbf{B}(b) \mathbf{A}(a) \otimes \mathbf{B}'(b) + |1\rangle\langle 1| \otimes \mathbf{A}_i \otimes \sum_{ab} \alpha_{a|k} \beta_{b|j} \mathbf{A}'(a) \otimes \mathbf{A}(a) \mathbf{B}(b) \otimes \mathbf{B}'(b), \quad (B10)$$

where the order of the spaces from left to right in each term coincides with the order of the wires from top to bottom in the quantum circuit in Eq. (B5) (i.e., control, first auxiliary, second auxiliary, Alice's primed, target, and Bob's primed systems).

Whenever the bipartite channel $A = U_A$ is unitary, it has a single Kraus operator, i.e., $A[\rho] = A_0\rho A_0^\dagger$. Hence, following Eq. (B9), in this case the quantum channel resulting from action of the quantum switch $S \otimes \mathcal{I}(U_A, B)$ has Kraus operators

$$S_j = |0\rangle\langle 0| \otimes \sum_{ab} \alpha_{a|0} \beta_{b|j} \mathbf{B}(b) \mathbf{A}(a) \otimes \mathbf{A}'(a) \otimes \mathbf{B}'(b) + |1\rangle\langle 1| \otimes \sum_{ab} \alpha_{a|0} \beta_{b|j} \mathbf{A}(a) \mathbf{B}(b) \otimes \mathbf{A}'(a) \otimes \mathbf{B}'(b). \quad (B11)$$

Also in this case, following Eq. (B10), the quantum channel resulting from action of the quantum circuit in Eq. (B5) is described by the Kraus operators

$$C_j = |0\rangle\langle 0| \otimes \mathbf{A}_0 \otimes \sum_{ab} \alpha_{a|0} \beta_{b|j} \mathbf{A}'(a) \otimes \mathbf{B}(b) \mathbf{A}(a) \otimes \mathbf{B}'(b) + |1\rangle\langle 1| \otimes \mathbf{A}_0 \otimes \sum_{ab} \alpha_{a|0} \beta_{b|j} \mathbf{A}'(a) \otimes \mathbf{A}(a) \mathbf{B}(b) \otimes \mathbf{B}'(b) \quad (B12)$$

$$= \left( |0\rangle\langle 0| \otimes \sum_{ab} \alpha_{a|0} \beta_{b|j} \mathbf{B}(b) \mathbf{A}(a) \otimes \mathbf{A}'(a) \otimes \mathbf{B}'(b) + |1\rangle\langle 1| \otimes \sum_{ab} \alpha_{a|0} \beta_{b|j} \mathbf{A}(a) \mathbf{B}(b) \otimes \mathbf{A}'(a) \otimes \mathbf{B}'(b) \right) \otimes \mathbf{A}_0. \quad (B13)$$

where, in the last line, we reordered the spaces from control, first auxiliary, second auxiliary, Alice's primed, target, and Bob's primed systems to control, target, and Alice and Bob's primed, first auxiliary, and second auxiliary systems.

Note that the term in parenthesis is equal to that of Eq. (B11). Hence, the action of the quantum switch on part of a bipartite unitary channel $A = U_A$ and a bipartite general channel $B$ is equivalent to the action of the quantum circuit in Eq. (B5) that uses two calls of bipartite unitary channel $A = U_A$ and a single call of bipartite general channel $B$ in the order ABA. Moreover, note that one call of $A = U_A$ in the quantum circuit in Eq. (B5) is recovered, since $A_0$ factorizes in Eq. (B12). This phenomenon is referred to as a catalytic higher-order transformation in the literature [62], since the extra use of $A = U_A$ is recovered after the completion of the process. $\square$

We now contrast the different scenarios of the action of the quantum switch presented in Secs. B1–B3 with the particular-case simulation of Theorem 1.

Let us begin with the circuit from Ref. [6], reproduced in Eq. (4) of the main text, and depicted here as the quantum comb in Fig. B4(a). This circuit simulates the action of the quantum switch on unitary channels by making use of one extra call to one of the input channels. Although every general quantum channel can be dilated into a unitary channel acting on a larger space, the simulation of the quantum switch on unitary channels in the case depicted in Fig. B4(a) is not the most general case, because here the entire unitary channel is “plugged into” the open slots of the quantum switch and of the quantum comb that performs its simulation.

The simulation presented in Ref. [6], here in Fig. B4(a), is a particular case of the simulation scenario we proved possible via the explicit construction of the quantum circuit in Eq. (B5). Our generalization addresses the case where the quantum switch acts on only part of a unitary channel and part of a general quantum channel, with the simulation also requiring only one extra copy of the input unitary channel. We depict this scenario and our quantum circuit simulation as a quantum comb in Fig. B4(b). Although more general than the previous result from Ref. [6], this simulation result still does not hold in the most general case, depicted in Fig. B1(c), because the input quantum channel $U_A$ is required to be a unitary channel.
<figure><img src="image_15.png" /><figcaption>**Figure B4.** **Quantum comb representation of possible quantum switch simulations.** (a) Representation of the simulation of the action of the quantum switch on single-party unitary channels as a quantum comb, presented in Ref. [6] and reproduced in the main text as the quantum circuit in Eq. (4). (b) Representation of the simulation of the action of the quantum switch on part of a bipartite unitary channel and part of a bipartite general quantum channel by a quantum comb, which we have shown to be possible by explicitly constructing the quantum circuit in Eq. (B5) in Thm. 1.</figcaption></figure>

The quantum switch simulation presented in Fig. B4(b) is also useful to illustrate the crucial aspect of the partial trace involved in the Stinespring dilation. Notice that this simulation covers the scenario where *B* is an arbitrary bipartite channel, and *U*<sub>A</sub> is an arbitrary bipartite unitary channel. Naïvely, one could expect that—since our simulation covers all bipartite unitary channels *U*<sub>A</sub>—due to the Stinespring dilation theorem, this simulation would also apply to the case where *A* is a single-party arbitrary quantum channel, as in Fig. B3(a). However, this line of argumentation is false, as it is not possible to simulate the quantum switch for a pair of single-party arbitrary quantum channels, as proven in the main text. The logical gap in the argument is a misuse of the Stinespring dilation theorem, which requires the auxiliary system to be discarded, whereas in the simulation presented in Fig. B4(b), there is no partial trace after the unitary operation *U*<sub>A</sub>. When the auxiliary system of the Stinespring dilation is not discarded, the corresponding operation is not equivalent to the quantum channel in question. From this circuit simulation perspective, keeping track of the auxiliary systems may be viewed as a “loophole”, since the auxiliary system may carry additional information that is not provided by the channel *A*. To see this intuitively, consider a quantum channel *A* with a Kraus decomposition given by $A[\rho] = \sum_i K_i \rho K_i^\dagger$ and which is dilated by the isometry $V = \sum_i K_i \otimes |i\rangle\langle i|$, where $|i\rangle$ is a quantum state on the auxiliary system. The quantum state $|i\rangle$ may be viewed as a flag that indicates which Kraus operator was applied to $\rho$. If the flag state is not discarded, one could use this information to correlate Kraus elements between a first and a second call of the channel *A*, which cannot be done when the auxiliary system is traced out.

## Appendix C: Full proof of Theorem 2

This section alone will adopt a slightly different notation from the main text and the remainder of the Appendix. This is due to the fact that the proof technique of this particular theorem is different from those applied to prove and present the other results, and it benefits from a different notation. Below is a summary of the changes, to facilitate the transition into this next section:
* We will denote a Hilbert space simply by the label of the system it describes, according to $X := \mathcal{H}^X$. In particular, the input and output Hilbert spaces of the control and target systems in the quantum switch higher-order transformation will be denoted instead as “past” and “future”, using the notation $P_C := \mathcal{H}^{c_I}$, $P_T := \mathcal{H}^{t_I}$, $F_C := \mathcal{H}^{c_O}$, $F_T := \mathcal{H}^{t_O}$, and collectively as $P := P_C \otimes P_T$ and $F := F_C \otimes F_T$.

* Quantum channels will be denoted by cursive letters $\mathcal{A}$ and $\mathcal{B}$ instead of $\mathcal{A}$ and $\mathcal{B}$. Kraus operators and unitary operators will be denoted by $A_i$, $B_j$ and $U$, $V$ instead of $A_i$, $B_j$ and $U$, $V$. Higher-order transformations will continue to be denoted with cursive letters, such as $\mathcal{S}$ for the quantum switch and $\mathcal{C}$ for quantum combs or QC-CC simulators, as in the remainder of the Appendix.

* Higher-order transformations that correspond to the simulator, be it a quantum comb or a QC-CC, will be denoted as a function $\mathcal{C}$ that has as many arguments as there are slots in the transformation (e.g., $\mathcal{C} = \mathcal{C}(\mathcal{A}, \mathcal{B}, \mathcal{C})$ for a 3-slot higher-order transformation). The number of available calls to channel $\mathcal{A}$ and $\mathcal{B}$ will be denoted as $M$ (instead of $k_A$) and $N$ (instead of $k_B$). Hence, what would be written as $\mathcal{C}(A^{\otimes k_A}, B^{\otimes k_B})$ in the remainder of the Appendix, in this section becomes instead $\mathcal{C}(\underbrace{\mathcal{A}, \dots, \mathcal{A}}_M, \underbrace{\mathcal{B}, \dots, \mathcal{B}}_N)$.

* Choi operators, Choi vectors, and the link product will be used as defined in Sec. IV Methods of the main text.

We are now ready to restate and prove Thm. 2.

**Theorem 2 (expanded).** Let $\mathcal{S}: [\mathcal{L}(I) \to \mathcal{L}(O)] \otimes [\mathcal{L}(I') \to \mathcal{L}(O')] \to [\mathcal{L}(P) \to \mathcal{L}(F)]$, where $I, O, I', O'$ are n-qubit Hilbert spaces and $P, F$ are $(n+1)$-qubit Hilbert spaces, be the quantum switch.

There is no $(M+1)$-slot quantum circuit with classical control of causal order (QC-CC) higher-order transformation $\mathcal{C}: \bigotimes_{i=1}^M [\mathcal{L}(I_i) \to \mathcal{L}(O_i)] \otimes [\mathcal{L}(I'_1) \to \mathcal{L}(O'_1)] \to [\mathcal{L}(P) \to \mathcal{L}(F)]$, where $\{I_i\}_i, \{O_i\}_i, I'_1, O'_1$ are n-qubit Hilbert spaces, satisfying

$$ \mathcal{C}(\underbrace{\mathcal{A}, \dots, \mathcal{A}}_M, \mathcal{B}) = \mathcal{S}(\mathcal{A}, \mathcal{B}) \qquad (C1) $$

for all mixed unitary channels $\mathcal{A}$ and unitary channels $\mathcal{B}$, if $M \le \max(2, 2^n - 1)$.

*Proof.* The proof is based upon a series of lemmas, proven below. First, we assume that $\mathcal{C}$ is a multilinear higher-order transformation whose Choi operator $\mathcal{C}$ is positive semidefinite, and hence can be written as

$$ C = \sum_a |C^{(a)}\rangle\langle C^{(a)}| \qquad (C2) $$

with $|C^{(a)}\rangle\langle C^{(a)}| \ge 0$ for all $a$.

Let us write the mixed unitary channel $\mathcal{A}$ in Eq. (C1) as $\mathcal{A} = \frac{1}{M} \sum_{i=1}^M \mathcal{A}_i$, for some $M \in \mathbb{N}^+$, where $\{\mathcal{A}_i\}_i$ are unitary channels with associated unitary operators $\{U_i\}_i$, and let unitary channel $\mathcal{B}$ be associated to unitary operator $V_1$. We then invoke Lemma 2 (which requires Lemma 1 for its proof) for $N=1$ to say that, since it is assumed that $\mathcal{C}$ satisfies Eq. (C1), each $|C^{(a)}\rangle\langle C^{(a)}|$ satisfies

$$ |C^{(a)}\rangle\langle C^{(a)}| * \left( \bigotimes_{k=1}^{M} |U_k\rangle\langle U_k| \otimes |V_1\rangle\langle V_1| \right) = \sum_{k=1}^{M} \xi_{k1}^{(a)}(\{U_i\}_i, V_1) |S\rangle\langle S| * \left( |U_k\rangle\langle U_k| \otimes |V_1\rangle\langle V_1| \right) \qquad (C3) $$

for some coefficients $\xi_{k1}^{(a)}(\{U_i\}_i, V_1) \in \mathbb{C}$, where $|S\rangle\langle S|$ is the Choi vector of the quantum switch.

From Lemma 3, we know that if there exist coefficients $\xi_{k1}^{(a)} \leftarrow \tilde{\xi}_{k1}^{(a)}$ such that, for all $k \in \{1, \dots, M\}$, $\tilde{\xi}_{k1}^{(a)}$ is simultaneously

1. independent of $U_k$ and $V_1$, and

2. linear in $U_{k'}$ for all $k' \ne k$,
then, there exist vectors $|\tilde{\xi}^{(a)}\rangle\langle I_1 O_1, \dots, I_M O_M\rangle\{|I_k O_k\}$ independent of $\{U_i\}_i$ and $V_1$ such that

$$|C^{(a)}\rangle\langle PI_1 O_1 \cdots I_M O_M I'_1 O'_1 F\rangle = \sum_{k=1}^{M} |S\rangle\langle PI_k O_k I'_1 O'_1 F\rangle \otimes |\tilde{\xi}_{k1}^{(a)}\rangle\langle I_1 O_1, \dots, I_M O_M\rangle\{|I_k O_k\} \quad (C4)$$

for all $a$. Such conditions are guaranteed to be satisfied via Lemma 4 when $M < 4^n/2 + 2$ [which is implied by $M \le \max(2, 2^n - 1)$].

Finally, invoking Lemma 5 (which requires Lemmas 6 and 7 for its proof), we find that if $M \le \max(2, 2^n - 1)$, a higher-order transformation with Choi operator $C = \sum_a |C^{(a)}\rangle\langle C^{(a)}|$ , where $|C^{(a)}\rangle$ satisfies Eqs. (C4) for all $a$ does not satisfy the conditions of a QC-CC transformation. $\square$

### C1. Lemma 1

**Lemma 1.** Let $|\phi\rangle$ and $\{|\psi_i\rangle\}_i$ be vectors in $\mathbb{C}^d$.

$$\text{If } |\phi\rangle\langle\phi| \le \sum_i |\psi_i\rangle\langle\psi_i|, \text{ then } |\phi\rangle \in \text{span}(\{|\psi_i\rangle\}). \quad (C5)$$

That is, there exist complex numbers $\alpha_i$ such that $|\phi\rangle = \sum_i \alpha_i |\psi_i\rangle$.

*Proof.* The proof will go by contradiction. We start by pointing out that any vector $|\phi\rangle \in \mathbb{C}^d$ can be decomposed as

$$|\phi\rangle = |\psi\rangle + |\psi_{\perp}\rangle, \quad (C6)$$

where $|\psi\rangle \in \text{span}(\{|\psi_i\rangle\})$, $|\psi_{\perp}\rangle \notin \text{span}(\{|\psi_i\rangle\})$. Also, since $|\psi_{\perp}\rangle \notin \text{span}(\{|\psi_i\rangle\})$, we have that $\langle\psi_{\perp}|\psi_i\rangle = 0$ for every $i$.

Now, assume that $|\phi\rangle \notin \text{span}(\{|\psi_i\rangle\})$. In this case, we necessarily have that $|\psi_{\perp}\rangle \ne 0$. Using this decomposition $|\phi\rangle = |\psi\rangle + |\psi_{\perp}\rangle$, we can write the inequality $|\phi\rangle\langle\phi| \le \sum_i |\psi_i\rangle\langle\psi_i|$, as

$$|\psi\rangle\langle\psi| + |\psi\rangle\langle\psi_{\perp}| + |\psi_{\perp}\rangle\langle\psi| + |\psi_{\perp}\rangle\langle\psi_{\perp}| \le \sum_i |\psi_i\rangle\langle\psi_i|. \quad (C7)$$

We then apply $\langle\psi_{\perp}|$ and $|\psi_{\perp}\rangle$ on both sides of operator inequality in Eq. (C7) to obtain the real number inequality

$$\langle\psi_{\perp}|\psi_{\perp}\rangle \langle\psi_{\perp}|\psi_{\perp}\rangle \le 0. \quad (C8)$$

However, since $|\psi_{\perp}\rangle \ne 0$, $\langle\psi_{\perp}|\psi_{\perp}\rangle \langle\psi_{\perp}|\psi_{\perp}\rangle$ is strictly positive, hence we have arrived at a contradiction. Therefore, $|\phi\rangle$ must belong to the span($\{|\psi_i\rangle\}$). $\square$

### C2. Lemma 2 (for $M, N \in \mathbb{N}^+$)

**Lemma 2.** Let $S: [\mathcal{L}(I) \to \mathcal{L}(O)] \otimes [\mathcal{L}(I') \to \mathcal{L}(O')] \to [\mathcal{L}(P) \to \mathcal{L}(F)]$, where $I, O, I', O'$ correspond to $d$-dimensional Hilbert spaces and $P, F$ correspond to $(2 \times d)$-dimensional Hilbert spaces, be a multilinear higher-order transformation that acts on two quantum channels and has a rank-1 Choi operator $S = |S\rangle\langle S|$ (such as, e.g., the quantum switch). Furthermore, let $C: \bigotimes_{i=1}^M [\mathcal{L}(I_i) \to \mathcal{L}(O_i)] \otimes \bigotimes_{j=1}^N [\mathcal{L}(I'_j) \to \mathcal{L}(O'_j)] \to [\mathcal{L}(P) \to \mathcal{L}(F)]$, where $M, N \in \mathbb{N}^+$ and $\{I_i\}_i, \{O_i\}_i, \{I'_j\}_j, \{O'_j\}_j$ correspond to $d$-dimensional Hilbert spaces, be a multilinear higher-order transformation that acts on $M + N$ quantum channels with a positive semidefinite Choi operator $C$, which, therefore, can be written as

$$C = \sum_a |C^{(a)}\rangle\langle C^{(a)}|, \quad (C9)$$

where each $|C^{(a)}\rangle\langle C^{(a)}| \ge 0$. Finally, let $A$ and $B$ be mixed unitary channels, such that $A = \frac{1}{K} \sum_{i=1}^K A_i$ and $B = \frac{1}{L} \sum_{j=1}^L B_j$ for some $K, L \in \mathbb{N}^+$, where $\{A_i\}_i$ and $\{B_j\}_j$ are unitary channels with associated unitary operators $\{U_i\}_i$ and $\{V_j\}_j$, respectively.
If $\mathcal{C}$ corresponds to a simulation of the action of $\mathcal{S}$ on mixed unitary channels $\mathcal{A}$ and $\mathcal{B}$, i.e., if $\mathcal{C}$ satisfies

$$ \mathcal{C}(\underbrace{\mathcal{A}, \dots, \mathcal{A}}_{M}, \underbrace{\mathcal{B}, \dots, \mathcal{B}}_{N}) = \mathcal{S}(\mathcal{A}, \mathcal{B}) \qquad (\text{C10}) $$

for all mixed unitary channels $\mathcal{A}$ and $\mathcal{B}$ (or, if $N=1$, for all mixed unitary channels $\mathcal{A}$ and unitary channels $\mathcal{B}$), then, for every $a$, there exist coefficients $\{\xi_{kl}^{(a)}(\{U_i\}_i, \{V_j\}_j)\}_{kl} \in \mathbb{C}$ such that

$$ |C_a\rangle\rangle * (|U_1\rangle\rangle \otimes \dots \otimes |U_M\rangle\rangle \otimes |V_1\rangle\rangle \otimes \dots \otimes |V_N\rangle\rangle) = \sum_{k=1}^{M} \sum_{l=1}^{N} \xi_{kl}^{(a)}(\{U_i\}_i, \{V_j\}_j) |S\rangle\rangle * (|U_k\rangle\rangle \otimes |V_l\rangle\rangle). \qquad (\text{C11}) $$

*Proof.* Since, by assumption, Eq. (C10) holds for all mixed unitary channels $\mathcal{A}, \mathcal{B}$, for any sets of unitary channels $\{\mathcal{A}_1, \dots, \mathcal{A}_K\}$ and $\{\mathcal{B}_1, \dots, \mathcal{B}_L\}$ with $K, L \ge 1$, one has that

$$ \mathcal{C} \left( \sum_{i_1=1}^{K} \frac{\mathcal{A}_{i_1}}{K}, \dots, \sum_{i_M=1}^{K} \frac{\mathcal{A}_{i_M}}{K}; \sum_{j_1=1}^{L} \frac{\mathcal{B}_{j_1}}{L}, \dots, \sum_{j_N=1}^{L} \frac{\mathcal{B}_{j_N}}{L} \right) = \mathcal{S} \left( \sum_{k=1}^{K} \frac{\mathcal{A}_k}{K}, \sum_{l=1}^{L} \frac{\mathcal{B}_l}{L} \right). \qquad (\text{C12}) $$

Note that for $N=1$, it is sufficient to assume that Eq. (C10) holds for all mixed unitary channels $\mathcal{A}$ and unitary channels $\mathcal{B}$, in which case we take $L=1$.

From the multilinearity of $\mathcal{C}$ and $\mathcal{S}$, it follows that

$$ \frac{1}{K^M L^N} \sum_{i_1, \dots, i_M = 1}^{K} \sum_{j_1, \dots, j_N = 1}^{L} \mathcal{C}(\mathcal{A}_{i_1}, \dots, \mathcal{A}_{i_M}; \mathcal{B}_{j_1}, \dots, \mathcal{B}_{j_N}) = \frac{1}{KL} \sum_{k=1}^{K} \sum_{l=1}^{L} \mathcal{S}(\mathcal{A}_k, \mathcal{B}_l). \qquad (\text{C13}) $$

Rewriting this expression in the Choi representation—using the convention that $C, S, A_i, B_j$ are the Choi matrices of $\mathcal{C}, \mathcal{S}, \mathcal{A}_i, \mathcal{B}_j$, respectively—gives

$$ \sum_{i_1, \dots, i_M = 1}^{K} \sum_{j_1, \dots, j_N = 1}^{L} C * (A_{i_1} \otimes \dots \otimes A_{i_M} \otimes B_{j_1} \otimes \dots \otimes B_{j_N}) = (K^{M-1} L^{N-1}) \sum_{k=1}^{K} \sum_{l=1}^{L} S * (A_k \otimes B_l). \qquad (\text{C14}) $$

Now, using the decomposition of $C$ given by Eq. (C9), and $S = |S\rangle\rangle\langle S|$, one has that

$$ \sum_a |C^{(a)}\rangle\rangle\langle\langle C^{(a)}| * \sum_{i_1, \dots, i_M=1}^{K} \sum_{j_1, \dots, j_N=1}^{L} \left( \bigotimes_{k=1}^{M} A_{i_k} \otimes \bigotimes_{l=1}^{N} B_{j_l} \right) = (K^{M-1} L^{N-1}) |S\rangle\rangle\langle\langle S| * \sum_{k=1}^{K} \sum_{l=1}^{L} (A_k \otimes B_l). \qquad (\text{C15}) $$

The positivity of each $|C^{(a)}\rangle\rangle\langle\langle C^{(a)}|$ implies that

$$ |C^{(a)}\rangle\rangle\langle\langle C^{(a)}| * \sum_{i_1, \dots, i_M=1}^{K} \sum_{j_1, \dots, j_N=1}^{L} \left( \bigotimes_{k=1}^{M} A_{i_k} \otimes \bigotimes_{l=1}^{N} B_{j_l} \right) \le (K^{M-1} L^{N-1}) |S\rangle\rangle\langle\langle S| * \sum_{k=1}^{K} \sum_{l=1}^{L} (A_k \otimes B_l) \qquad (\text{C16}) $$

for all $a$.

Consider now the case where $K=M, L=N$. Since $A_i$ and $B_j$ are Choi operators of unitary channels, they can be expressed as $A_i = |U_i\rangle\rangle\langle U_i|$ and $B_j = |V_j\rangle\rangle\langle V_j|$. Since the left-hand side of Eq. (C16) is a sum of positive operators, the inequality also holds for the sum of any subset of the terms on the left-hand side. Then, by considering only the term in the sum over $i_1, \dots, i_M, j_1, \dots, j_N$ that corresponds to $i_k=k, j_l=l$ for all $k, l$, we obtain that

$$ |C^{(a)}\rangle\rangle\langle\langle C^{(a)}| * \left( \bigotimes_{k=1}^{M} |U_k\rangle\rangle\langle U_k| \otimes \bigotimes_{l=1}^{N} |V_l\rangle\rangle\langle V_l| \right) \le (M^{(M-1)} N^{(N-1)}) |S\rangle\rangle\langle\langle S| * \sum_{k=1}^{M} \sum_{l=1}^{N} (|U_k\rangle\rangle\langle U_k| \otimes |V_l\rangle\rangle\langle V_l|), \qquad (\text{C17}) $$

for all $a$. Following the link product rule for vectors, as in, e.g., Lemma 1 of Ref. [52], the above equation can be
rewritten as

$$ \bigotimes_{k=1}^{M} \bigotimes_{l=1}^{N} (|C^{(a)}\rangle * |U_k\rangle) \otimes |V_l\rangle) (\langle\langle C^{(a)}| * \langle\langle U_k| \otimes \langle\langle V_l| \rangle \le (M^{(M-1)}N^{(N-1)}) \sum_{k=1}^{M} \sum_{l=1}^{N} (|S\rangle * |U_k\rangle) \otimes |V_l\rangle) (\langle\langle S| * \langle\langle U_k| \otimes \langle\langle V_l|). \tag{C18} $$

Now, invoking Lemma 1, we arrive at the conclusion that

$$ |C^{(a)}\rangle * \left( \bigotimes_{k=1}^{M} |U_k\rangle \right) \otimes \left( \bigotimes_{j=1}^{N} |V_j\rangle \right) \in \operatorname{span}(\{|S\rangle * (|U_k\rangle \otimes |V_l\rangle)\}_{kl}), \tag{C19} $$

for all a. Therefore, for every a, we have that

$$ |C^{(a)}\rangle * \left( \bigotimes_{k=1}^{M} |U_k\rangle \right) \otimes \left( \bigotimes_{j=1}^{N} |V_j\rangle \right) = \sum_{k=1}^{M} \sum_{l=1}^{N} \xi_{kl}^{(a)} (\{U_i\}_i, \{V_j\}_j) |S\rangle * (|U_k\rangle \otimes |V_l\rangle), \tag{C20} $$

for some coefficients $\xi_{kl}^{(a)}(\{U_i\}_i, \{V_j\}_j) \in \mathbb{C}$ for all $k, l$.

<figure><img src="image_16.png" /></figure>

### C3. Lemma 3 (for $M, N \in \mathbb{N}^+$)

**Lemma 3.** Let $|S\rangle \in P \otimes I \otimes O \otimes I' \otimes O' \otimes F$, where $I, O, I', O'$ correspond to $d$-dimensional Hilbert spaces and $P, F$ correspond to $(2 \times d)$-dimensional Hilbert spaces, and let $|C\rangle \in P \otimes I_1 \otimes O_1 \otimes \cdots \otimes I_M \otimes O_M \otimes I'_1 \otimes O'_1 \otimes \cdots \otimes I'_N \otimes O'_N \otimes F$, where $M, N \in \mathbb{N}^+$ and $\{I_i\}_i, \{O_i\}_i, \{I'_j\}_j, \{O'_j\}_j$ correspond to $d$-dimensional Hilbert spaces.

If, for a given $M, N$, for all $(M+N)$-tuples of $n$-qubit unitary operators $(U_1, \dots, U_M, V_1, \dots, V_N)$,

$$ |C\rangle * |U_1\rangle^{I_1 O_1} \otimes \cdots \otimes |U_M\rangle^{I_M O_M} \otimes |V_1\rangle^{I'_1 O'_1} \otimes \cdots \otimes |V_N\rangle^{I'_N O'_N} = \sum_{k=1}^{M} \sum_{l=1}^{N} \tilde{\xi}_{kl}(\{U_i\}_i, \{V_j\}_j) |S\rangle * |U_k\rangle^{I_k O_k} \otimes |V_l\rangle^{I'_l O'_l} \tag{C21} $$

for some coefficients $\tilde{\xi}_{kl}(\{U_i\}_i, \{V_j\}_j) \in \mathbb{C}$ for all $k, l$ that are simultaneously

1. independent of $U_k$ and $V_l$, and

2. linear in $U_i$ and $V_j$ for all $i \neq k, j \neq l$,

then

$$ |C\rangle^{PI_1 O_1 \dots I_M O_M I'_1 O'_1 \dots I'_N O'_N F} = \sum_{k=1}^{M} \sum_{l=1}^{N} |S\rangle^{PI_k O_k I'_k O'_k F} \otimes |\tilde{\xi}_{kl}\rangle \{I_1 O_1 \dots I_M O_M I'_1 O'_1 \dots I'_N O'_N\} \setminus \{I_k O_k I'_k O'_k\} \tag{C22} $$

for some vectors $|\tilde{\xi}_{kl}\rangle \{I_1 O_1 \dots I_M O_M I'_1 O'_1 \dots I'_N O'_N\} \setminus \{I_k O_k I'_k O'_k\}$ that are independent of $\{U_i\}_i$ and $\{V_j\}_j$.

*Proof.* The first condition (independence) implies that we can write $\tilde{\xi}_{kl}(\{U_i\}_i, \{V_j\}_j) = \tilde{\xi}_{kl}(\{U_i\}_{i \neq k}, \{V_j\}_{j \neq l})$. The second condition (linearity) combined with the Riesz representation theorem implies that we can write the linear functions $\tilde{\xi}_{kl}(\{U_i\}_{i \neq k}, \{V_j\}_{j \neq l})$ using vectors $|\tilde{\xi}_{kl}\rangle$ according to

$$ \tilde{\xi}_{kl}(\{U_i\}_{i \neq k}, \{V_j\}_{j \neq l}) = |\tilde{\xi}_{kl}\rangle * \bigotimes_{i \neq k} |U_i\rangle \otimes \bigotimes_{j \neq l} |V_j\rangle, \tag{C23} $$

where the definition of the link product of two vectors $|\psi\rangle, |\phi\rangle \in \mathbb{C}^d$ acting on the same space implies that $|\psi\rangle * |\phi\rangle = \langle\psi| |\phi\rangle$, where the bar denotes complex conjugation.
Then, by explicitly writing in the system labels, for any sets of n-qubit unitaries {$U_i$}$_{i=1}^M$ and {$V_j$}$_{j=1}^N$, Eq. (C21) becomes

$$
\begin{align}
& |C\rangle\rangle^{PI_1 O_1 \dots I_M O_M I'_1 O'_1 \dots I'_N O'_N F} * \left[ \bigotimes_{i=1}^{M} |U_i\rangle\rangle I_i O_i \otimes \bigotimes_{j=1}^{N} |V_j\rangle\rangle I'_j O'_j \right] \nonumber \\
& = \left[ \sum_{k=1}^{M} \sum_{l=1}^{N} |\tilde{\xi}_{kl}\rangle\rangle \{I_1 O_1 \dots I_M O_M I'_1 O'_1 \dots I'_N O'_N\} \setminus \{I_k O_k I'_k O'_k\} \otimes |S\rangle\rangle^{PI_k O_k I'_k O'_k F} \right] * \left[ \bigotimes_{i=1}^{M} |U_i\rangle\rangle I_i O_i \otimes \bigotimes_{j=1}^{N} |V_j\rangle\rangle I'_j O'_j \right], \tag{C24}
\end{align}
$$

for some vectors $|\tilde{\xi}_{kl}\rangle\rangle\{I_1 O_1 \dots I_M O_M I'_1 O'_1 \dots I'_N O'_N\} \setminus \{I_k O_k I'_k O'_k\}$.

Since the equation is true for all unitaries {$U_i$} and {$V_j$}, and the span($\{|U\rangle\rangle | U \in SU(d)\}$) = $\mathbb{C}^d \otimes \mathbb{C}^d$, it implies that

$$
|C\rangle\rangle^{PI_1 O_1 \dots I_M O_M I'_1 O'_1 \dots I'_N O'_N F} = \sum_{k=1}^{M} \sum_{l=1}^{N} |S\rangle\rangle^{PI_k O_k I'_k O'_k F} \otimes |\tilde{\xi}_{kl}\rangle\rangle \{I_1 O_1 \dots I_M O_M I'_1 O'_1 \dots I'_N O'_N\} \setminus \{I_k O_k I'_k O'_k\} \quad (C25)
$$

for some vectors $|\tilde{\xi}_{kl}\rangle\rangle\{I_1 O_1 \dots I_M O_M I'_1 O'_1 \dots I'_N O'_N\} \setminus \{I_k O_k I'_k O'_k\}$.

<figure><img src="image_17.png" /></figure>

C4. Lemma 4 (for $M < 4^n/2 + 2$ and $N = 1$)

**Lemma 4.** Let $|S\rangle\rangle \in P \otimes I \otimes O \otimes I' \otimes O' \otimes F$, where $I, O, I', O'$ correspond to n-qubit Hilbert spaces for some $n \in \mathbb{N}^+$ and $P, F$ correspond to $(n+1)$-qubit Hilbert spaces, and let $|C\rangle\rangle \in P \otimes I_1 \otimes O_1 \otimes \cdots \otimes I_M \otimes O_M \otimes I'_1 \otimes O'_1 \otimes F$, where $M \in \mathbb{N}^+$ and $\{I_i\}_{i, I'_1, O'_1} \in \mathbb{N}^+$ correspond to n-qubit Hilbert spaces.

If, for all $(M + 1)$-tuples of n-qubit unitary operators $(U_1, \dots, U_M, V_1)$, it holds that

$$
|C\rangle\rangle * |U_1\rangle\rangle^{I_1 O_1} \otimes \dots \otimes |U_M\rangle\rangle^{I_M O_M} \otimes |V_1\rangle\rangle^{I'_1 O'_1} = \sum_{k=1}^{M} \xi_{k1} |S\rangle\rangle * |U_k\rangle\rangle^{I_k O_k} \otimes |V_1\rangle\rangle^{I'_1 O'_1} \quad (C26)
$$

for some complex numbers $\xi_{k1} := \xi_{k1}(\{U_i\}_{i, V_1} \in \mathbb{C}, \text{ then there exist complex numbers } \tilde{\xi}_{k1} := \tilde{\xi}_{k1}(\{U_i\}_{i, V_1} \in \mathbb{C} \text{ such that Eq. (C26) with } \{\xi_{k1}\}_{k=1}^M \leftarrow \{\tilde{\xi}_{k1}\}_{k=1}^M \text{ remains satisfied and, for all } k \in \{1, \dots, M\}, \tilde{\xi}_{k1} \text{ is simultaneously}$

1. independent of $U_k$ and $V_1$ (independence condition), and

2. linear in $U_i$ for all $i \neq k$ (linearity condition),

as long as $M < 4^n/2 + 2$.

*Proof.* Assume that Eq. (C26) holds. Then, in particular, it holds for the choice $U_i = \sigma_{\vec{r}_i}$ for $i \in \{1, \dots, M\}$ and $V_1 = \sigma_{\vec{q}_1}$, where $\vec{r}_i, \vec{q}_1 \in \{0, 1, 2, 3\}^{\times n}$ and $\{\sigma_{\vec{r}_i}\}_{i, \vec{q}_1}$ are n-qubit Pauli operators. Here, the set of n-qubit Pauli operators is defined by

$$
\left\{ \sigma_{\vec{r}} := \bigotimes_{i=1}^{n} \sigma_{r_i} \middle| \vec{r} \in \{0, 1, 2, 3\}^{\times n} \right\}, \qquad (C27)
$$

where $\sigma_0, \sigma_1, \sigma_2, \sigma_3$ are 1-qubit Pauli operators defined by

$$
\sigma_0 := \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad \sigma_1 := \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad \sigma_2 := \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \quad \sigma_3 := \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}. \qquad (C28)
$$

Thus,

$$
|C\rangle\rangle * |\sigma_{\vec{r}_1}\rangle\rangle^{I_1 O_1} \otimes \dots \otimes |\sigma_{\vec{r}_M}\rangle\rangle^{I_M O_M} \otimes |\sigma_{\vec{q}_1}\rangle\rangle^{I'_1 O'_1} = \sum_{k=1}^{M} \xi_{k1} |S\rangle\rangle * |\sigma_{\vec{r}_k}\rangle\rangle^{I_k O_k} \otimes |\sigma_{\vec{q}_1}\rangle\rangle^{I'_1 O'_1}. \quad (C29)
$$
Now suppose that $F \ge 1$ elements of the $\{\sigma_{\vec{r}_i}\}_{i=1}^M$ are equal to some fixed $n$-qubit Pauli operator $\sigma_{\vec{w}}$. Let the set of integers labeling those Pauli operators be denoted by $\mathbb{F} := \{1 \le i \le M | \sigma_{\vec{r}_i} = \sigma_{\vec{w}}\}$, such that $|\mathbb{F}| = F$. Equation (C26) then reads

$$|C\rangle\rangle * \bigotimes_{i \in \mathbb{F}} |\sigma_{\vec{w}}\rangle\rangle^{I_i O_i} \otimes \bigotimes_{i \in \{1, \dots, M\} \setminus \mathbb{F}} |\sigma_{\vec{r}_i}\rangle\rangle^{I'_i O'_i} = \sum_{k=1}^{M} \xi_{k1}^{\{\vec{r}_i\}_{l, \vec{q}_1}} |S\rangle\rangle * |\sigma_{\vec{r}_k}\rangle\rangle^{I_k O_k} \otimes |\sigma_{\vec{q}_1}\rangle\rangle^{I'_1 O'_1}, \quad (C30)$$

where, for the input unitaries chosen as $n$-qubit Paulis, we define

$$\xi_{k1}^{\{\vec{r}_i\}_{l, \vec{q}_1}} := \xi_{k1}(\{U_i = \sigma_{\vec{r}_i}\}_{i=1}^M, V_1 = \sigma_{\vec{q}_1}). \quad (C31)$$

In the following, we will adopt the shorthand convention that any changes to the dependence of $\xi_{k1}$ from $\xi_{k1}^{\{\vec{r}_i\}_{l, \vec{q}_1}}$ will be specified as $\xi_{k1}^{\{\vec{r}_i\}_{l, \vec{q}_1}}[U_i = (\dots), V_j = (\dots)]$, with all unspecified arguments $U_i, V_1$ defined to be the same as for $\xi_{k1}^{\{\vec{r}_i\}_{l, \vec{q}_1}}$ defined above. A key point that we note for later is that the value of each individual variable $\xi_{k1}^{\{\vec{r}_i\}_{l, \vec{q}_1}}$ for $k \in \mathbb{F}$ is not uniquely determined from Eq. (C26), so we can take a different set of variables $\tilde{\xi}_{k1}$ still satisfying Eq. (C26).

We now show that for all $k \in \{1, \dots, M\}$, the variables $\xi_{k1}$ can be replaced by $\tilde{\xi}_{k1}$ defined by

$$\tilde{\xi}_{k1}(\{U_i = \sigma_{\vec{r}_i}\}_{i=1}^M, V_1 = \sigma_{\vec{q}_1}) := \xi_{k1}^{\{\vec{r}_i\}_{l, \vec{q}_1}} [U_k = \sigma_{\vec{r}_k^*}, V_1 = \sigma_{\vec{q}^*}], \quad (C32)$$

$$\tilde{\xi}_{k1} \left( \left\{ U_i = \sum_{\vec{r}_i} \alpha_{\vec{r}_i}^i \sigma_{\vec{r}_i} \right\}_{i=1}^M, V_1 = \sum_{\vec{q}_1} \beta_{\vec{q}_1}^1 \sigma_{\vec{q}_1} \right) := \sum_{\{\vec{r}_i\}_{l \neq k}} \left( \prod_{j \neq k} \alpha_{\vec{r}_j}^j \right) \tilde{\xi}_{k1}(\{U_i = \sigma_{\vec{r}_i}\}_{i=1}^M, V_1 = \sigma_{\vec{q}_1}), \quad (C33)$$

where $\vec{r}_k^* \in \{0, 1, 2, 3\}^{\times n}$ is an arbitrary vector outside of the set $\{\vec{r}_1, \dots, \vec{r}_{k-1}, \vec{r}_{k+1}, \dots, \vec{r}_M\}$, $\vec{q}^* \in \{0, 1, 2, 3\}^{\times n}$ is an arbitrary fixed vector, and $\alpha_{\vec{r}_i}^i, \beta_{\vec{q}_1}^1$ are complex numbers. In the discussion below, we pick one choice of $\vec{r}_k^*$ defined as a function of $\vec{r}_1, \dots, \vec{r}_{k-1}, \vec{r}_{k+1}, \dots, \vec{r}_M$, i.e., $\vec{r}_k^* = \vec{r}_k^*(\vec{r}_1, \dots, \vec{r}_{k-1}, \vec{r}_{k+1}, \dots, \vec{r}_M)$. Such an $\vec{r}_k^*$ always exists for $M < 4^n$.

By construction, if the definition in Eqs. (C32)–(C33) satisfies Eq. (C26), then $\tilde{\xi}_{k1}$ satisfies both the linearity and independence conditions outlined in the statement of the lemma. We now proceed to show that the definition in Eqs. (C32)–(C33) indeed satisfies Eq. (C26). We do this by considering the dependence of $\xi_{k1}^{\{\vec{r}_i\}_{l, \vec{q}_1}}$ on the unitaries $\{U_i = \sigma_{\vec{r}_i}\}_{i=1}^M$ and $V_1 = \sigma_{\vec{q}_1}$ in turn.

### Dependence on $\{U_i\}_{i=1}^M$

We focus on the case where $\{U_i\}_i$, $V_1$ are chosen from the set of Pauli operators. For every $k \in \{1, \dots, M\}$, we choose one $\sigma_{\vec{r}_k^*}$ and take $\sigma$ to be the unique $n$-qubit Pauli operator such that $\sigma\sigma_{\vec{r}_k} = \beta\sigma_{\vec{r}_k^*}$, where $\beta \in \{-1, 1, i, -i\}$. We then consider the following expression

$$\mathbf{E} := \left. \frac{d}{d\theta} \right|_{\theta=0} \left[ |C\rangle\rangle * \bigotimes_{m \in \mathbb{F}_k} |e^{i\theta\sigma} \sigma_{\vec{r}_m}\rangle\rangle^{I_m O_m} * \bigotimes_{m=1|m \notin \mathbb{F}_k}^{M} |\sigma_{\vec{r}_m}\rangle\rangle^{I_m O_m} * |\sigma_{\vec{q}_1}\rangle\rangle^{I'_1 O'_1} \right], \quad (C34)$$

where $\mathbb{F}_k := \{1 \le i \le M | \sigma_{\vec{r}_i} = \sigma_{\vec{r}_k}\}$. Due to linearity, this expression can be evaluated in two ways: either by first computing the derivative and then applying Eq. (C26), or by first applying Eq. (C26) and then computing the
derivative. The former method gives

$$
\begin{align}
\mathbf{E} &= i\beta \sum_{m \in \mathbb{F}_k} \left[ |C\rangle\rangle * |\sigma_{\vec{r}_k^*}\rangle\rangle^{I_m O_m} * \bigotimes_{i \in \mathbb{F}_k, i \neq m} |\sigma_{\vec{r}_i}\rangle\rangle^{I_i O_i} * \bigotimes_{i=1, i \notin \mathbb{F}_k}^{M} |\sigma_{\vec{r}_i}\rangle\rangle^{I_i O_i} * |\sigma_{\vec{q}_1}\rangle\rangle^{I_1 O_1'} \right] \nonumber \\
&= i\beta \sum_{m \in \mathbb{F}_k} \left[ \begin{aligned}[t]
& \xi_{m1}^{\{\vec{r}_1\}_1, \vec{q}_1} [U_m = \sigma_{\vec{r}_k^*}] |S\rangle\rangle * |\sigma_{\vec{r}_k^*}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle \\
& + \sum_{i \in \mathbb{F}_k, i \neq m} \xi_{i1}^{\{\vec{r}_1\}_1, \vec{q}_1} [U_m = \sigma_{\vec{r}_k^*}] |S\rangle\rangle * |\sigma_{\vec{r}_k^*}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle \\
& + \sum_{i=1, i \notin \mathbb{F}_k}^{M} \xi_{i1}^{\{\vec{r}_1\}_1, \vec{q}_1} [U_m = \sigma_{\vec{r}_k^*}] |S\rangle\rangle * |\sigma_{\vec{r}_i}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle
\end{aligned} \right], \tag{C35}
\end{align}
$$

while the latter gives

$$
\begin{align}
\mathbf{E} = \frac{d}{d\theta} \Big|_{\theta=0} & \left[ \sum_{m \in \mathbb{F}_k} \xi_{m1}^{\{\vec{r}_1\}_1, \vec{q}_1} [\{U_i = e^{i\theta\sigma} \sigma_{\vec{r}_k}\}_{i \in \mathbb{F}_k}] |S\rangle\rangle * |e^{i\theta\sigma} \sigma_{\vec{r}_k}\rangle\rangle^{I_m O_m} * |\sigma_{\vec{q}_1}\rangle\rangle^{I_1' O_1'} \right. \nonumber \\
& \left. + \sum_{m=1, m \notin \mathbb{F}_k}^{M} \xi_{m1}^{\{\vec{r}_1\}_1, \vec{q}_1} [\{U_i = e^{i\theta\sigma} \sigma_{\vec{r}_k}\}_{i \in \mathbb{F}_k}] |S\rangle\rangle * |\sigma_{\vec{r}_m}\rangle\rangle^{I_m O_m} * |\sigma_{\vec{q}_1}\rangle\rangle^{I_1' O_1'} \right] \nonumber \\
& = i\beta \sum_{m \in \mathbb{F}_k} \xi_{m1}^{\{\vec{r}_1\}_1, \vec{q}_1} |S\rangle\rangle * |\sigma_{\vec{r}_k^*}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle \nonumber \\
& \qquad + \frac{d}{d\theta} \Big|_{\theta=0} \left[ \sum_{m \in \mathbb{F}_k} \xi_{m1}^{\{\vec{r}_1\}_1, \vec{q}_1} [\{U_i = e^{i\theta\sigma} \sigma_{\vec{r}_k}\}_{i \in \mathbb{F}_k}] |S\rangle\rangle * |\sigma_{\vec{r}_k}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle \right. \nonumber \\
& \qquad \left. + \sum_{\vec{v} \in \{\vec{r}_1, \dots, \vec{r}_M\} \setminus \{\vec{r}_k\}} \frac{d}{d\theta} \Big|_{\theta=0} \left[ \sum_{m \in \mathbb{F}_{\vec{v}}} \xi_{m1}^{\{\vec{r}_1\}_1, \vec{q}_1} [\{U_i = e^{i\theta\sigma} \sigma_{\vec{r}_k}\}_{i \in \mathbb{F}_k}] |S\rangle\rangle * |\sigma_{\vec{v}}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle, \right. \tag{C36}
\end{align}
$$

where $\mathbb{F}_{\vec{v}} := \{1 \le m \le M \mid \vec{r}_m = \vec{v}\}$. Note that the vector

$$
|S\rangle\rangle * |\sigma_{\vec{r}_m}\rangle\rangle^{I_m O_m} * |\sigma_{\vec{q}_1}\rangle\rangle^{I_1' O_1'} \quad (C37)
$$

belongs to the Hilbert space $P \otimes F$, which is independent of $I_m, O_m, I'_1, O'_1$, thus the superscripts $I_m, O_m, I'_1, O'_1$ can be omitted. Also, note that

$$
\sum_{m \in \mathbb{F}_k} \xi_{m1}^{\{\vec{r}_1\}_1, \vec{q}_1} [\{U_i = e^{i\theta\sigma} \sigma_{\vec{r}_k}\}_{i \in \mathbb{F}_k}] \quad (C38)
$$

and

$$
\sum_{m \in \mathbb{F}_{\vec{v}}} \xi_{m1}^{\{\vec{r}_1\}_1, \vec{q}_1} [\{U_i = e^{i\theta\sigma} \sigma_{\vec{r}_k}\}_{i \in \mathbb{F}_k}] \quad (C39)
$$
are differentiable since their values are uniquely determined from

$$
\begin{align}
& |C\rangle\rangle * \bigotimes_{m \in \mathbb{F}_k} |e^{i\theta\sigma} \sigma_{\vec{r}_m}\rangle\rangle^{I_m O_m} * \bigotimes_{m=1|m \notin \mathbb{F}_k}^{M} |\sigma_{\vec{r}_m}\rangle\rangle^{I_m O_m} * |\sigma_{\vec{q}_1}\rangle\rangle^{I_1 O_1'} \nonumber \\
& = \left( \sum_{m \in \mathbb{F}_k} \xi_{m1}^{\{\vec{r}_1\}_{l_1}, \vec{q}_1} [\{U_i = e^{i\theta\sigma} \sigma_{\vec{r}_k}\}_{i \in \mathbb{F}_k}] \right) |S\rangle\rangle * |e^{i\theta\sigma} \sigma_{\vec{r}_k}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle \nonumber \\
& + \sum_{\vec{v} \in \{\vec{r}_1, \dots, \vec{r}_M\} \setminus \{\vec{r}_k\}} \left( \sum_{m \in \mathbb{F}_{\vec{v}}} \xi_{m1}^{\{\vec{r}_1\}_{l_1}, \vec{q}_1} [\{U_i = e^{i\theta\sigma} \sigma_{\vec{r}_k}\}_{i \in \mathbb{F}_k}] \right) |S\rangle\rangle * |\sigma_{\vec{v}}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle, \tag{C40}
\end{align}
$$

and thus can be obtained from the inner product of the vector on the left-hand side of Eq. (C40) and vectors $|S\rangle\rangle * |e^{i\theta\sigma} \sigma_{\vec{r}_k}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle$ or $|S\rangle\rangle * |\sigma_{\vec{v}}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle$ (which are mutually orthogonal), which are polynomials of $e^{\pm i\theta}$.

By comparing the coefficients for $|S\rangle\rangle * |\sigma_{\vec{r}_k^*}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle$, we find that

$$
\sum_{m \in \mathbb{F}_k} \xi_{m1}^{\{\vec{r}_1\}_{l_1}, \vec{q}_1} = \sum_{m \in \mathbb{F}_k} \xi_{m1}^{\{\vec{r}_1\}_{l_1}, \vec{q}_1} [U_m = \sigma_{\vec{r}_k^*}]. \quad (C41)
$$

Dependence on V₁

In this part of the proof, we adopt the following shorthand notations. For any unitary operators U, V,

$$
\begin{align}
|C[V]\rangle\rangle &:= |C\rangle\rangle * \bigotimes_{i=1}^{M} |\sigma_{\vec{r}_i}\rangle\rangle^{I_i O_i} * |V\rangle\rangle^{I_1 O_1'} \nonumber \\
|S(U, V)\rangle\rangle &:= |S\rangle\rangle * |U\rangle\rangle * |V\rangle\rangle \nonumber \\
b(\sigma_{\vec{v}}, V) &:= \sum_{m \in \mathbb{F}_{\vec{v}}} \xi_{m1}^{\{\vec{r}_1\}_{l_1}, \vec{q}_1} [V_1 = V], \tag{C42}
\end{align}
$$

where $\mathbb{F}_{\vec{v}} := \{1 \le i \le M \mid \vec{r}_i = \vec{v}\}$.

For any two n-qubit Pauli operators $\sigma_A, \sigma_B$, either the operator $(\sigma_A + \sigma_B)/\sqrt{2}$ or the operator $(\sigma_A + i\sigma_B)/\sqrt{2}$ is unitary. When $U := (\sigma_A + \beta\sigma_B)/\sqrt{2}$ with $\beta \in \{1, i\}$ is unitary, the following equality holds for any $\{\vec{r}_1, \dots, \vec{r}_M\}, \sigma_A, \sigma_B$:

$$
\begin{align}
0 &= |C[U]\rangle\rangle - \frac{1}{\sqrt{2}} (|C[\sigma_A]\rangle\rangle + \beta |C[\sigma_B]\rangle\rangle) \nonumber \\
  &= \frac{1}{\sqrt{2}} \sum_{\vec{v} \in \{\vec{r}_1, \dots, \vec{r}_M\}} [\{b(\sigma_{\vec{v}}, U) - b(\sigma_{\vec{v}}, \sigma_A)\} |S(\sigma_{\vec{v}}, \sigma_A)\rangle\rangle + \beta \{b(\sigma_{\vec{v}}, U) - b(\sigma_{\vec{v}}, \sigma_B)\} |S(\sigma_{\vec{v}}, \sigma_B)\rangle\rangle]. \tag{C43}
\end{align}
$$

We now calculate the inner product

$$
\langle\langle S(\sigma_{\vec{v}}, \sigma_A) | S(\sigma_{\vec{v}'}, \sigma_B) \rangle\rangle = \operatorname{tr}(\sigma_B \sigma_A \sigma_{\vec{v}} \sigma_{\vec{v}'}) + \operatorname{tr}(\sigma_{\vec{v}} \sigma_A \sigma_B \sigma_{\vec{v}'}). \quad (C44)
$$

From this, it is clear that $\langle\langle S(\sigma_{\vec{v}}, \sigma_A) | S(\sigma_{\vec{v}'}, \sigma_B) \rangle\rangle = 0$ if $\sigma_{\vec{v}'} \not\subset \sigma_{\vec{v}} \sigma_A \sigma_B$. Therefore, taking an inner product of Eq. (C43) with $|S(\sigma_{\vec{v}}, \sigma_A)\rangle\rangle$, we obtain

$$
\left\{
\begin{array}{l}
\{b(\sigma_{\vec{v}}, U) - b(\sigma_{\vec{v}}, \sigma_A)\} \langle\langle S(\sigma_{\vec{v}}, \sigma_A) | S(\sigma_{\vec{v}}, \sigma_A) \rangle\rangle = 0 \quad \text{if for all } \sigma_{\vec{v}'} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\} : \sigma_{\vec{v}'} \not\subset \sigma_{\vec{v}} \sigma_A \sigma_B \\[2ex]
\{b(\sigma_{\vec{v}}, U) - b(\sigma_{\vec{v}}, \sigma_A)\} \langle\langle S(\sigma_{\vec{v}}, \sigma_A) | S(\sigma_{\vec{v}}, \sigma_A) \rangle\rangle \\
\quad + \beta \{b(\gamma \sigma_{\vec{v}} \sigma_A \sigma_B, U) - b(\gamma \sigma_{\vec{v}} \sigma_A \sigma_B, \sigma_B)\} \langle\langle S(\sigma_{\vec{v}}, \sigma_A) | S(\gamma \sigma_{\vec{v}} \sigma_A \sigma_B, \sigma_B) \rangle\rangle = 0 \quad \text{else,}
\end{array}
\right.
\tag{C45}
$$
where $\gamma \in \{1, -1, i, -i\}$ is defined by the unique choice of $\sigma_{\vec{v}}' \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}$ such that

$$ \sigma_{\vec{v}'} = \gamma \sigma_{\vec{v}} \sigma_A \sigma_B. \qquad (C46) $$

In the first case, i.e., if for all $\sigma_{\vec{v}}' \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\} : \sigma_{\vec{v}'} \not\subset \sigma_{\vec{v}} \sigma_A \sigma_B$, we directly obtain

$$ b(\sigma_{\vec{v}}, U) - b(\sigma_{\vec{v}}, \sigma_A) = 0. \qquad (C47) $$

In the second case, if

$$ \langle\langle S(\sigma_{\vec{v}}, \sigma_A) | S(\gamma \sigma_{\vec{v}} \sigma_A \sigma_B, \sigma_B) \rangle\rangle = \mathrm{tr}(\sigma_B \sigma_A \sigma_{\vec{v}} \gamma \sigma_{\vec{v}} \sigma_A \sigma_B) + \mathrm{tr}(\sigma_{\vec{v}} \sigma_A \sigma_B \gamma \sigma_{\vec{v}} \sigma_A \sigma_B) = 0 \qquad (C48) $$

holds, we also obtain Eq. (C47).

By a similar argument, if for all $\sigma_{\vec{v}''} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\} : \sigma_{\vec{v}''} \not\subset \sigma_{\vec{v}} \sigma_B \sigma_A$, we directly obtain

$$ b(\sigma_{\vec{v}}, U) - b(\sigma_{\vec{v}}, \sigma_B) = 0. \qquad (C49) $$

Alternatively, if

$$ \langle\langle S(\sigma_{\vec{v}}, \sigma_B) | S(\gamma \sigma_{\vec{v}} \sigma_B \sigma_A, \sigma_A) \rangle\rangle = \mathrm{tr}(\sigma_A \sigma_B \sigma_{\vec{v}} \delta \sigma_{\vec{v}} \sigma_B \sigma_A) + \mathrm{tr}(\sigma_{\vec{v}} \sigma_B \sigma_A \delta \sigma_{\vec{v}} \sigma_B \sigma_A) = 0 \qquad (C50) $$

holds, where $\delta \in \{1, -1, i, -i\}$ is defined by the unique choice of $\sigma_{\vec{v}''} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}$ such that

$$ \sigma_{\vec{v}''} = \delta \sigma_{\vec{v}} \sigma_B \sigma_A, \qquad (C51) $$

we also obtain Eq. (C49).

Consider now the conditions for Eq. (C48) to be satisfied. The first term is given by $\mathrm{tr}(\sigma_B \sigma_A \sigma_{\vec{v}} \gamma \sigma_{\vec{v}} \sigma_A \sigma_B) = \gamma \mathrm{tr}1$. For the second term, there are four cases:

* If $\gamma = \pm 1$, then $\pm \sigma_{\vec{v}} \sigma_A \sigma_B$ is an $n$-qubit Pauli operator so the second term is given by $\mathrm{tr}[\sigma_{\vec{v}} \sigma_A \sigma_B \gamma \sigma_{\vec{v}} \sigma_A \sigma_B] = \gamma \mathrm{tr}[(\pm \sigma_{\vec{v}} \sigma_A \sigma_B)(\pm \sigma_{\vec{v}} \sigma_A \sigma_B)] = \gamma \mathrm{tr}1$.

* If $\gamma = \pm i$, then $\pm i \sigma_{\vec{v}} \sigma_A \sigma_B$ is an $n$-qubit Pauli operator so the second term is given by $\mathrm{tr}[(\sigma_{\vec{v}} \sigma_A \sigma_B) \gamma (\sigma_{\vec{v}} \sigma_A \sigma_B)] = -\gamma \mathrm{tr}[(\pm i \sigma_{\vec{v}} \sigma_A \sigma_B)(\pm i \sigma_{\vec{v}} \sigma_A \sigma_B)] = -\gamma \mathrm{tr}1$.

Therefore, Eq. (C48) is satisfied if and only if $\gamma = \pm i$. By a similar argument, Eq. (C50) is satisfied if and only if $\delta = \pm i$.

Note that the following equivalences hold: $\forall \sigma_{\vec{v}''} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\} : \sigma_{\vec{v}''} \not\subset \sigma_{\vec{v}} \sigma_B \sigma_A \iff \forall \sigma_{\vec{v}'} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\} : \sigma_{\vec{v}'} \not\subset \sigma_{\vec{v}} \sigma_A \sigma_B$, and also $\gamma \in \{i, -i\} \iff \delta \in \{i, -i\}$. Therefore, for all $\{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}$, for every tuple $(\sigma_{\vec{v}} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}, \sigma_A, \sigma_B)$, if one of the two following conditions is satisfied:

1. $\forall \sigma_{\vec{v}'} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\} : \sigma_{\vec{v}'} \not\subset \sigma_{\vec{v}} \sigma_A \sigma_B$, or

2. $\exists \sigma_{\vec{v}'}$ such that $\sigma_{\vec{v}'} = \pm i \sigma_{\vec{v}} \sigma_A \sigma_B$,

then

$$ b(\sigma_{\vec{v}}, \sigma_A) = b(\sigma_{\vec{v}}, U), \qquad (C52) $$

$$ b(\sigma_{\vec{v}}, \sigma_B) = b(\sigma_{\vec{v}}, U), \qquad (C53) $$

which implies that

$$ b(\sigma_{\vec{v}}, \sigma_A) = b(\sigma_{\vec{v}}, \sigma_B). \qquad (C54) $$

We now consider the choices of $(\sigma_{\vec{v}}, \sigma_A, \sigma_B)$ where neither of the above two conditions is satisfied.

The case where $\sigma_{\vec{v}} = \sigma_A$ or $\sigma_{\vec{v}} = \sigma_B$: First, note that if $\sigma_{\vec{v}} = \sigma_B$, and Condition 1. is not satisfied, then Eq. (C46) implies that $\sigma_{\vec{v}'} = \sigma_A$ and $\gamma = \pm 1$, so Condition 2. is not satisfied either. In this case, we can take another $n$-qubit
Pauli operator $\sigma_C \notin \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}$ (which implies that $\sigma_C \neq \sigma_A, \sigma_B$), such that $\sigma_B\sigma_A\sigma_C = \pm i\sigma_{BAC}$ for some $n$-qubit Pauli $\sigma_{BAC}$. The existence of such a $\sigma_C$ is guaranteed by:

* the fact that half of the total $4^n$ number of $n$-qubit Pauli operators, when multiplied after $\sigma_B\sigma_A$ (which is not equal to the identity because $\sigma_B \neq \sigma_A$ by construction), gives a Pauli operator times $\pm 1$, and the other half will give a Pauli operator times $\pm i$,

* the fact that the set $\{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}$ contains the operators $\sigma_A, \sigma_B$, which, when multiplied after $\sigma_B\sigma_A$, gives a Pauli operator times $\pm 1$,

* the assumption that $M < 4^n/2 + 2$.

Applying the procedure in Eqs. (C43)-(C54) above to the unitary $U' := (\sigma_C + \beta'\sigma_B)/\sqrt{2}$ (with $\beta' \in \{1, i\}$), we find that there is no $\sigma_{\vec{v}}' \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}$ such that $\sigma_{\vec{v}}' \propto \sigma_{\vec{v}}\sigma_C\sigma_B = \sigma_B\sigma_C\sigma_B \propto \sigma_C$. Therefore, Condition 1. is satisfied for $(\sigma_{\vec{v}} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}, \sigma_C, \sigma_B)$ and we have that

$$b(\sigma_{\vec{v}}, \sigma_C) = b(\sigma_{\vec{v}}, U') = b(\sigma_{\vec{v}}, \sigma_B). \qquad (C55)$$

Applying the procedure in Eqs. (C43)-(C54) above to the unitary $U'' := (\sigma_A + \beta''\sigma_C)/\sqrt{2}$ (with $\beta'' \in \{1, i\}$), we find that either (a) there is no $\sigma_{\vec{v}}'' \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}$ such that $\sigma_{\vec{v}}'' \propto \sigma_{\vec{v}}\sigma_A\sigma_C$, or (b) if there is, then $\sigma_{\vec{v}}\sigma_A\sigma_C = \sigma_B\sigma_A\sigma_C = \pm i\sigma_{BAC}$, i.e. $\sigma_{\vec{v}}'' = \sigma_{BAC}$. Therefore, for $(\sigma_{\vec{v}} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}, \sigma_A, \sigma_C)$, either Condition 1. or 2. is satisfied and we have that

$$b(\sigma_{\vec{v}}, \sigma_A) = b(\sigma_{\vec{v}}, U'') = b(\sigma_{\vec{v}}, \sigma_C). \qquad (C56)$$

Overall, Eq. (C54) is satisfied for $(\sigma_{\vec{v}} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}, \sigma_A, \sigma_B)$. An analogous argument applies if $\sigma_{\vec{v}} = \sigma_A$. The case where $\sigma_{\vec{v}} \neq \sigma_A, \sigma_B$: If neither Condition 1. nor Condition 2. are satisfied, then we can take another $n$-qubit Pauli operator $\sigma_C \neq \sigma_A, \sigma_B$, such that

$$\sigma_{\vec{v}}\sigma_A\sigma_C = \pm i\sigma_{vAC}, \qquad (C57)$$

$$\sigma_{\vec{v}}\sigma_C\sigma_B \in \{\pm i\sigma_{vCB}\} \iff \sigma_{\vec{v}}\sigma_B\sigma_C \in \{\pm i\sigma_{vCB}\}, \qquad (C58)$$

for some $n$-qubit Pauli operators $\sigma_{vAC}, \sigma_{vCB}$. The existence of such a $\sigma_C$ is guaranteed by:

* the fact that for any two different non-identity $n$-qubit Pauli operators $\sigma_E, \sigma_F$, there exists an $n$-qubit Pauli operator $\sigma_Q$ such that both $\sigma_E\sigma_Q$ and $\sigma_F\sigma_Q$ are equal to $+i$ or $-i$ times an $n$-qubit Pauli operator,

* the fact that for any two different non-identity $n$-qubit Pauli operators $\sigma_E, \sigma_F$, there exists an $n$-qubit Pauli operator $\sigma_R$ such that $\sigma_E\sigma_R$ equals $\pm i$ times an $n$-qubit Pauli operator, while $\sigma_F\sigma_R$ equals $\pm 1$ times an $n$-qubit Pauli operator.

This enables $\sigma_C$ to be chosen according to the following strategy:

* if there are $\sigma_E, \sigma_F$ such that $\sigma_E = \pm\sigma_v\sigma_A$ and $\sigma_F = \pm\sigma_v\sigma_B$, then pick $\sigma_C = \sigma_Q$ as defined above,

* if there are $\sigma_E, \sigma_F$ such that either $\sigma_E = \pm\sigma_v\sigma_A$ and $\sigma_F = \pm i\sigma_v\sigma_B$, or $\sigma_F = \pm i\sigma_v\sigma_A$ and $\sigma_E = \pm\sigma_v\sigma_B$, then pick $\sigma_C = \sigma_R$ as defined above,

* if there are $\sigma_E, \sigma_F$ such that $\sigma_E = \pm i\sigma_v\sigma_A$ and $\sigma_F = \pm i\sigma_v\sigma_B$, then pick $\sigma_C = \sigma_F$, in which case $\sigma_{\vec{v}}\sigma_B\sigma_C = \sigma_{\vec{v}}\sigma_B(\pm i\sigma_v\sigma_B) = \mp i\mathbf{1}$ and $\sigma_{\vec{v}}\sigma_A\sigma_C = \pm i\sigma_{\vec{v}}\sigma_A\sigma_{\vec{v}}\sigma_B = \mp i\sigma_{\vec{v}}\sigma_B\sigma_A\sigma_{\vec{v}} = -\sigma_C\sigma_A\sigma_{\vec{v}} = -(\sigma_{\vec{v}}\sigma_A\sigma_C)^\dagger$ (where in the third equality we use the assumption that Conditions 1. and 2. are not satisfied, which implies that $\sigma_{\vec{v}}\sigma_A\sigma_B = \sigma_B\sigma_A\sigma_{\vec{v}}$), and therefore $\sigma_{\vec{v}}\sigma_A\sigma_C$ must be proportional to $\pm i$ times a Pauli.

Applying the procedure in Eqs. (C43)-(C54) above to the unitary $U' := (\sigma_C + \beta'\sigma_B)/\sqrt{2}$ (with $\beta' \in \{1, i\}$), we find that Condition 1. or 2. is satisfied for $(\sigma_{\vec{v}} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}, \sigma_C, \sigma_B)$ and we have that

$$b(\sigma_{\vec{v}}, \sigma_C) = b(\sigma_{\vec{v}}, U') = b(\sigma_{\vec{v}}, \sigma_B). \qquad (C59)$$
Applying the procedure in Eqs. (C43)–(C54) above to the unitary $U'' := (\sigma_A + \beta''\sigma_C)/\sqrt{2}$ (with $\beta'' \in \{1, i\}$), we find that Condition 1. or 2. is satisfied for $(\sigma_{\vec{v}} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}, \sigma_A, \sigma_C)$ and we have that

$$b(\sigma_{\vec{v}}, \sigma_A) = b(\sigma_{\vec{v}}, U'') = b(\sigma_{\vec{v}}, \sigma_C). \qquad (C60)$$

Overall, Eq. (C54) is satisfied for $(\sigma_{\vec{v}} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}, \sigma_A, \sigma_B)$.

Having shown that for all $\{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}$, for every tuple $(\sigma_{\vec{v}} \in \{\sigma_{\vec{r}_1}, \dots, \sigma_{\vec{r}_M}\}, \sigma_A, \sigma_B)$, Eq. (C54) is satisfied, we conclude that $b(\sigma_{\vec{v}}, \sigma_{\vec{q}_1}) := \sum_{m \in \mathbb{F}_{\vec{v}}} \xi_{m1}^{\{\vec{r}_1\}_{l}, \vec{q}_1}$ is independent of the choice of $\sigma_{\vec{q}_1}$. This means that

$$\sum_{m \in \mathbb{F}_{\vec{v}}} \xi_{m1}^{\{\vec{r}_1\}_{l}, \vec{q}_1} = \sum_{m \in \mathbb{F}_{\vec{v}}} \xi_{m1}^{\{\vec{r}_1\}_{l}, \vec{q}_1} [V_1 = \sigma_{\vec{q}^*}], \qquad (C61)$$

for any $n$-qubit Pauli operator $\sigma_{\vec{q}^*}$.

### Proving that the redefinition of Eqs. (C32) and (C33) satisfies Eq. (C26)

Equations (C41) and Eq. (C61) together show that for all $\vec{r}_1, \dots, \vec{r}_M, \vec{q}_1 \in \{0, 1, 2, 3\}^{\times n}$,

$$\begin{aligned}
|C\rangle\rangle * \bigotimes_{i=1}^{M} |\sigma_{\vec{r}_i}\rangle\rangle^{I_i O_i} * |\sigma_{\vec{q}_1}\rangle\rangle^{I'_1 O'_1} &= \sum_{k=1}^{M} \xi_{k1}^{\{\vec{r}_1\}_{l}, \vec{q}_1} |S\rangle\rangle * |\sigma_{\vec{r}_k}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle \\
&= \sum_{\vec{v} \in \{\vec{r}_1, \dots, \vec{r}_M\}} \sum_{m \in \mathbb{F}_{\vec{v}}} \xi_{m1}^{\{\vec{r}_1\}_{l}, \vec{q}_1} |S\rangle\rangle * |\sigma_{\vec{v}}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle \\
&= \sum_{\vec{v} \in \{\vec{r}_1, \dots, \vec{r}_M\}} \sum_{m \in \mathbb{F}_{\vec{v}}} \xi_{m1}^{\{\vec{r}_1\}_{l}, \vec{q}_1} [V_1 = \sigma_{\vec{q}^*}] |S\rangle\rangle * |\sigma_{\vec{v}}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle \\
&= \sum_{\vec{v} \in \{\vec{r}_1, \dots, \vec{r}_M\}} \sum_{m \in \mathbb{F}_{\vec{v}}} \xi_{m1}^{\{\vec{r}_1\}_{l}, \vec{q}_1} [U_m = \sigma_{\vec{v}^*}, V_1 = \sigma_{\vec{q}^*}] |S\rangle\rangle * |\sigma_{\vec{v}}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle \\
&= \sum_{k=1}^{M} \tilde{\xi}_{k1}(\{U_i = \sigma_{\vec{r}_i}\}_{i=1}^{M}, V_1 = \sigma_{\vec{q}_1}) |S\rangle\rangle * |\sigma_{\vec{r}_k}\rangle\rangle * |\sigma_{\vec{q}_1}\rangle\rangle, \qquad (C62)
\end{aligned}$$

where $\mathbb{F}_{\vec{v}} := \{1 \le i \le M \mid \vec{r}_i = \vec{v}\}, \vec{v}^* \in \{0, 1, 2, 3\}^{\times n}$ is an arbitrary vector outside of the set $\{\vec{r}_1, \dots, \vec{r}_M\} \setminus \{\vec{v}\}$, and $\vec{q}^* \in \{0, 1, 2, 3\}^{\times n}$ is an arbitrary fixed vector. Therefore, $\tilde{\xi}_{k1}$ as defined in Eq. (C32) indeed satisfies Eq. (C26).

This also implies that

$$\begin{aligned}
|C\rangle\rangle * \bigotimes_{i=1}^{M} |\sum_{\vec{r}_i} \alpha_{\vec{r}_i}^i \sigma_{\vec{r}_i}\rangle\rangle^{I_i O_i} * |\sum_{\vec{q}_1} \beta_{\vec{q}_1}^1 \sigma_{\vec{q}_1}\rangle\rangle^{I'_1 O'_1} &= \sum_{\{\vec{r}_1\}_{l}, \vec{q}_1} \left(\prod_{j=1}^{M} \alpha_{\vec{r}_j}^j\right) \beta_{\vec{q}_1}^1 |C\rangle\rangle * \bigotimes_{i=1}^{M} |\sigma_{\vec{r}_i}\rangle\rangle^{I_i O_i} * |\sigma_{\vec{q}_1}\rangle\rangle^{I'_1 O'_1} \\
&= \sum_{\{\vec{r}_1\}_{l}, \vec{q}_1} \left(\prod_{j=1}^{M} \alpha_{\vec{r}_j}^j\right) \beta_{\vec{q}_1}^1 \left[\sum_{k=1}^{M} \tilde{\xi}_{k1}(\{U_m = \sigma_{\vec{r}_m}\}_{m}, V_1 = \sigma_{\vec{q}_1}) |S\rangle\rangle * |\sigma_{\vec{r}_k}\rangle\rangle^{I_k O_k} * |\sigma_{\vec{q}_1}\rangle\rangle^{I'_1 O'_1}\right] \\
&= \sum_{k=1}^{M} \left[\sum_{\{\vec{r}_1\}_{l \neq k}} \left(\prod_{j=1}^{M} \alpha_{\vec{r}_j}^j\right) \tilde{\xi}_{k1}(\{U_m = \sigma_{\vec{r}_m}\}_{m}, V_1 = \sigma_{\vec{q}_1}) \right] \sum_{\vec{r}_k, \vec{q}_1} \alpha_{\vec{r}_k}^k \beta_{\vec{q}_1}^1 |S\rangle\rangle * |\sigma_{\vec{r}_k}\rangle\rangle^{I_k O_k} * |\sigma_{\vec{q}_1}\rangle\rangle^{I'_1 O'_1} \\
&= \sum_{k=1}^{M} \tilde{\xi}_{k1} \left(\left\{U_i = \sum_{\vec{r}_i} \alpha_{\vec{r}_i}^i \sigma_{\vec{r}_i}\right\}, V_1 = \sum_{\vec{q}_1} \beta_{\vec{q}_1}^1 \sigma_{\vec{q}_1}\right) |S\rangle\rangle * |\sum_{\vec{r}_k} \alpha_{\vec{r}_k}^k \sigma_{\vec{r}_k}\rangle\rangle^{I_k O_k} * |\sum_{\vec{q}_1} \beta_{\vec{q}_1}^1 \sigma_{\vec{q}_1}\rangle\rangle^{I'_1 O'_1}, \qquad (C63)
\end{aligned}$$

i.e., Eq. (C33) also satisfies Eq. (C26).

□
C5. Lemma 5 (for $\max\{M, N\} \le \max\{2, d-1\}$)

Before proving Lemma 5, we present the definition of a QC-CC higher-order transformation with an arbitrary number of slots $M+N$ [27].

An operator $C \in \mathcal{L}(P \otimes I_1 \otimes O_1 \otimes \dots \otimes I_{M+N} \otimes O_{M+N} \otimes F)$ corresponds to the Choi operator of a $(M+N)$-slot QC-CC higher-order transformation if it satisfies

$$C = \sum_{\vec{r}_{M+N} \in \text{Perm}(1, \dots, M+N)} C_{P\vec{r}_{M+N}F}, \qquad (C64)$$

$$\text{such that} \quad C_{P\vec{r}_{M+N}F} \ge 0 \quad \forall \vec{r}_{M+N}, \qquad (C65)$$

$$\text{tr}_F[C_{P\vec{r}_{M+N}F}] = C_{P\vec{r}_{M+N}} \otimes 1^{O_{r_{M+N}}} \quad \forall \vec{r}_{M+N}, \qquad (C66)$$

$$\sum_{r_{m+1}} \text{tr}_{I_{r_{m+1}}} [C_{P\vec{r}_m} r_{m+1}] = C_{P\vec{r}_m} \otimes 1^{O_{r_m}} \quad \forall m \in \{1, \dots, M+N-1\}, \forall \vec{r}_m := (r_1, \dots, r_m), \qquad (C67)$$

$$\sum_{r_1} \text{tr}_{I_{r_1}} [C_{P r_1}] = 1^P, \qquad (C68)$$

where $\vec{r}_m r_{m+1}$ represents a vector $(r_1, \dots, r_m, r_{m+1})$, with each vector $\vec{r}_m$ composed of elements $r_1, \dots, r_m$, and the operators $C_{P\vec{r}_m} \in \mathcal{L}(P \otimes I_1 \otimes O_1 \otimes \dots \otimes I_{m-1} \otimes O_{m-1} \otimes I_m)$ for $m \in \{1, \dots, M+N\}$ are recursively defined by

$$C_{P\vec{r}_{M+N}} := \frac{1}{d} \text{tr}_{O_{r_{M+N}}} F [C_{P\vec{r}_{M+N}F}], \qquad (C69)$$

$$C_{P\vec{r}_m} := \frac{1}{d} \sum_{r_{m+1}} \text{tr}_{O_{r_m} I_{r_{m+1}}} [C_{P\vec{r}_m} r_{m+1}] \quad \forall m \in \{1, \dots, M+N-1\}. \qquad (C70)$$

These conditions will be referred as the QC-CC conditions. We remark that quantum combs are a subset of QC-CCs. For convenience in the following, we rename the last $N$ input and output systems as

$$I'_k := I_{M+k}, \quad O'_k := O_{M+k} \quad \forall k \in \{1, \dots, N\}. \qquad (C71)$$

**Lemma 5.** Let $|S\rangle\rangle \in P \otimes I \otimes O \otimes I' \otimes O' \otimes F$, where $I, O, I', O'$ correspond to $d$-dimensional Hilbert spaces and $P, F$ correspond to $(2 \times d)$-dimensional Hilbert spaces, be the Choi vector of the quantum switch and let $C \in \mathcal{L}(P \otimes I_1 \otimes O_1 \otimes \dots \otimes I_M \otimes O_M \otimes I'_1 \otimes O'_1 \otimes \dots \otimes I'_N \otimes O'_N \otimes F)$, where $M, N \in \mathbb{N}^+$ and $\{I_i\}_i, \{O_i\}_i, \{I'_j\}_j, \{O'_j\}_j$ correspond to $d$-dimensional Hilbert spaces, be the Choi operator of an $(M+N)$-slot QC-CC higher-order transformation, which we write as

$$C = \sum_{\vec{r}_{M+N}} C_{P\vec{r}_{M+N}F}, \qquad (C72)$$

with $\vec{r}_{M+N} \in \text{Perm}(1, \dots, M+N)$, where all $C_{P\vec{r}_{M+N}F} \ge 0$ and, hence, can be decomposed as

$$C_{P\vec{r}_{M+N}F} = \sum_{a} |C_{P\vec{r}_{M+N}F}^{(a)}\rangle\langle C_{P\vec{r}_{M+N}F}^{(a)}| \qquad (C73)$$

If $\max(M, N) \le \max(2, d-1)$, then the set of operators $|C_{P\vec{r}_{M+N}F}^{(a)}\rangle\langle C_{P\vec{r}_{M+N}F}^{(a)}|$ cannot be such that

$$|C_{P\vec{r}_{M+N}F}^{(a)}\rangle\rangle = \sum_{i=1}^{M} \sum_{k=1}^{N} |S\rangle\rangle^{P I_i O_i I'_k O'_k F} \otimes |\tilde{\xi}_{ik}^{(a), \vec{r}_{M+N}}\rangle\rangle, \qquad (C74)$$

for all $\vec{r}_{M+N}$ and $a$, where $|\tilde{\xi}_{ik}^{(a), \vec{r}_{M+N}}\rangle\rangle \in I_i \otimes O_i \otimes I'_k \otimes O'_k$ for all $i \in \{1, \dots, M\}$ and $k \in \{1, \dots, N\}$, and $I_i := \otimes_{i'=i \neq i} I_{i'}$, $O_i := \otimes_{i'=i \neq i} O_{i'}$, $I'_k := \otimes_{k'=k \neq k} I'_{k'}$, and $O'_k := \otimes_{k'=k \neq k} O'_{k'}$.
Proof. The proof follows by contradiction. To this end, we use Eqs. (C66) and (C67) in the QC-CC conditions to show the following equation for $C_{P\vec{r}_m}$:

$$ \sum_{r_m} \mathrm{tr}_{I_{r_m}} [C_{P\vec{r}_m}] = \sum_{i,j \in A_{\vec{r}_{m-1}}} \sum_{k,l \in B_{\vec{r}_{m-1}}} \left( |0\rangle\langle 0|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I_i \left\langle\left\langle 1|^{P_T} I_j \otimes |1\rangle\right\rangle\right\rangle^{O_i} \right. \\ \left. + |1\rangle\langle 1|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I'_k \left\langle\left\langle 1|^{P_T} I'_l \otimes |1\rangle\right\rangle\right\rangle^{O'_k} \left\langle\left\langle 1|^{O'_l} I_j \otimes 1^{O_j \to O_i}\right\rangle\right\rangle \right) \otimes C_{P\vec{r}_{m-1}}^{(ijkl)} \quad \forall m \in \{1, \dots, M+N+1\}, \qquad (C75) $$

where the summation over $r_m$ for $m = M + N + 1$ is taken as $I_{r_{M+N+1}} := F$, $C_{P\vec{r}_{M+N+1}}$ is defined by $C_{P\vec{r}_{M+N+1}} := C_{P\vec{r}_{M+N}F}$, the set of indices $A_{\vec{r}_{m-1}}$ and $B_{\vec{r}_{m-1}}$ are defined by

$$ A_{\vec{r}_{m-1}} := \{r_1, \dots, r_{m-1}\} \cap \{1, \dots, M\}, \qquad (C76) $$

$$ B_{\vec{r}_{m-1}} := \{r_1 - M, \dots, r_{m-1} - M\} \cap \{1, \dots, N\}, \qquad (C77) $$

and $C_{P\vec{r}_{m-1}}^{(ijkl)}$ is an operator. If this equation holds, since $A_{\vec{r}_0}$ and $B_{\vec{r}_0}$ are the empty sets, we obtain

$$ \sum_{r_1} \mathrm{tr}_{I_{r_1}} [C_{P r_1}] = 0, \qquad (C78) $$

which contradicts with the normalization condition in Eq. (C68) of the QC-CC conditions. In the rest of the proof, we show Eq. (C75) by induction with respect to $m$.

First, we show Eq. (C75) for $m = M + N + 1$ as follows. Since the operator $C_{P\vec{r}_{M+N}F}$ can be written as

$$ C_{P\vec{r}_{M+N}F} = \sum_{i,j,k,l} |S\rangle\langle S|^{PI_i O_i I'_k O'_k F} \left\langle\left\langle S|^{PI_j O_j I'_l O'_l F} \otimes C_{P\vec{r}_{M+N}}^{(ijkl)} \right\rangle\right\rangle \qquad (C79) $$

where $C_{P\vec{r}_{M+N}}^{(ijkl)} := \sum_a |\tilde{\xi}_{ik}^{(a),\vec{r}_{M+N}}\rangle\langle\tilde{\xi}_{jl}^{(a),\vec{r}_{M+N}}|$. The partial trace $\mathrm{tr}_F C_{P\vec{r}_{M+N}F}$ is given by

$$ \mathrm{tr}_F [C_{P\vec{r}_{M+N}F}] = \sum_{i,j=1}^{M} \sum_{k,l=1}^{N} \left( |0\rangle\langle 0|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I_i \left\langle\left\langle 1|^{P_T} I_j \otimes |1\rangle\right\rangle\right\rangle^{O_i} \right. \\ \left. + |1\rangle\langle 1|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I'_k \left\langle\left\langle 1|^{P_T} I'_l \otimes |1\rangle\right\rangle\right\rangle^{O'_k} \left\langle\left\langle 1|^{O'_l} I_j \otimes 1^{O_j \to O_i}\right\rangle\right\rangle \right) \otimes C_{P\vec{r}_{M+N}}^{(ijkl)}, \qquad (C80) $$

i.e., Eq. (C75) holds for $m = M + N + 1$.

To complete the proof, we show Eq. (C75) by assuming Eq. (C75) for $m \leftarrow m + 1$, i.e.,

$$ \sum_{r_{m+1}} \mathrm{tr}_{I_{r_{m+1}}} [C_{P\vec{r}_m r_{m+1}}] = \sum_{i,j \in A_{\vec{r}_m}} \sum_{k,l \in B_{\vec{r}_m}} \left( |0\rangle\langle 0|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I_i \left\langle\left\langle 1|^{P_T} I_j \otimes |1\rangle\right\rangle\right\rangle^{O_i} \right. \\ \left. + |1\rangle\langle 1|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I'_k \left\langle\left\langle 1|^{P_T} I'_l \otimes |1\rangle\right\rangle\right\rangle^{O'_k} \left\langle\left\langle 1|^{O'_l} I_j \otimes 1^{O_j \to O_i}\right\rangle\right\rangle \right) \otimes C_{P\vec{r}_m}^{(ijkl)}. \qquad (C81) $$

By symmetry with $(I_i, O_i)$ and $(I'_k, O'_k)$, it is sufficient to show if $r_m \in \{1, \dots, M\}$ holds. From Eq. (C67) [or Eq. (C66) for $m = M + N$] in the QC-CC conditions and Eq. (C81), we obtain

$$ \sum_{i,j \in A_{\vec{r}_m}} \sum_{k,l \in B_{\vec{r}_m}} \left( |0\rangle\langle 0|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I_i \left\langle\left\langle 1|^{P_T} I_j \otimes |1\rangle\right\rangle\right\rangle^{O_i} \right. \\ \left. + |1\rangle\langle 1|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I'_k \left\langle\left\langle 1|^{P_T} I'_l \otimes |1\rangle\right\rangle\right\rangle^{O'_k} \left\langle\left\langle 1|^{O'_l} I_j \otimes 1^{O_j \to O_i}\right\rangle\right\rangle \right) \otimes C_{P\vec{r}_m}^{(ijkl)} \qquad (C82) \\ = \sum_{i,j \in A_{\vec{r}_m}} \sum_{k,l \in B_{\vec{r}_m}} |0\rangle\langle 0|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I_i \left\langle\left\langle 1|^{P_T} I_j \otimes 1^{O'_l \to O'_k} \otimes A_{ijkl} \right\rangle\right\rangle \\ + |1\rangle\langle 1|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I'_k \left\langle\left\langle 1|^{P_T} I'_l \otimes |1\rangle\right\rangle\right\rangle^{O'_k} \left\langle\left\langle 1|^{O'_l} I_j \otimes B_{ijkl}\right\rangle\right\rangle, $$
where $A_{ijkl}$ and $B_{ijkl}$ are defined by

$$A_{ijkl} := \begin{cases} |1\rangle\rangle^{O_i I'_k} \langle 1|^{O_j I'_l} \otimes \tilde{C}_{P\vec{r}_m}^{(ijkl)} \otimes 1^{O_{r_m}} & (i, j \neq r_m) \\ \frac{1}{d} C_{P\vec{r}_m}^{(ijkl)} |1\rangle\rangle^{I'_k O_{r_m}} \langle 1|^{O_j I'_l} \otimes 1^{O_{r_m}} & (i = r_m \neq j) \\ \frac{1}{d} |1\rangle\rangle^{I'_k O_i} \langle 1|^{O_{r_m} I'_l} C_{P\vec{r}_m}^{(ijkl)} \otimes 1^{O_{r_m}} & (j = r_m \neq i) \\ \frac{1}{d} 1^{O_{r_m} I'_l} \otimes I'_k \otimes C_{P\vec{r}_m}^{(ijkl)} \otimes 1^{O_{r_m}} & (i = j = r_m) \end{cases}, \quad (C83)$$

$$B_{ijkl} := \begin{cases} 1^{O_j \to O_i} \otimes \tilde{C}_{P\vec{r}_m}^{(ijkl)} \otimes 1^{O_{r_m}} & (i, j \neq r_m) \\ \frac{1}{d} C_{P\vec{r}_m}^{(ijkl)} 1^{O_j \to O_{r_m}} \otimes 1^{O_{r_m}} & (i = r_m \neq j) \\ \frac{1}{d} 1^{O_{r_m} \to O_i} C_{P\vec{r}_m}^{(ijkl)} \otimes 1^{O_{r_m}} & (j = r_m \neq i) \\ C_{P\vec{r}_m}^{(ijkl)} \otimes 1^{O_{r_m}} & (i = j = r_m) \end{cases}, \quad (C84)$$

$$\tilde{C}_{P\vec{r}_m}^{(ijkl)} := \frac{1}{d} \mathrm{tr}_{O_{r_m}} C_{P\vec{r}_m}^{(ijkl)}. \quad (C85)$$

Using Lemma 6 for Eq. (C82), we obtain

$$\sum_{k,l \in \mathbb{B}_{\vec{r}_m}} |1\rangle\rangle^{O_i I'_k} \langle 1|^{O_j I'_l} \otimes 1^{O'_l \to O'_k} \otimes C_{P\vec{r}_m}^{(ijkl)} = \sum_{k,l \in \mathbb{B}_{\vec{r}_m}} 1^{O'_l \to O'_k} \otimes A_{ijkl} \quad \forall i, j, \quad (C86)$$

$$1^{O_j \to O_i} \otimes C_{P\vec{r}_m}^{(ijkl)} = B_{ijkl} \quad \forall i, j, k, l. \quad (C87)$$

From Eq. (C87), we obtain

$$C_{P\vec{r}_m}^{(ijkl)} = \begin{cases} \tilde{C}_{P\vec{r}_m}^{(ijkl)} \otimes 1^{O_{r_m}} & (i, j \neq r_m) \\ 0 & (i = r_m \neq j \text{ or } j = r_m \neq i) \end{cases}, \quad (C88)$$

where the cases of $i = r_m \neq j$ and $j = r_m \neq i$ are shown as below. If $i = r_m \neq j$ holds, from Eqs. (C84) and (C87), we obtain

$$1^{O_j \to O_{r_m}} \otimes C_{P\vec{r}_m}^{(ijkl)} = \frac{1}{d} C_{P\vec{r}_m}^{(ijkl)} 1^{O_j \to O_{r_m}} \otimes 1^{O_{r_m}}. \quad (C89)$$

By taking the inner product of Eq. (C89) with $1^{O_j \to O_{r_m}}$, we obtain

$$d C_{P\vec{r}_m}^{(ijkl)} = \frac{1}{d} C_{P\vec{r}_m}^{(ijkl)}, \quad (C90)$$

i.e., $C_{P\vec{r}_m}^{(ijkl)} = 0$ holds for $i = r_m \neq j$. We can similarly show that $C_{P\vec{r}_m}^{(ijkl)} = 0$ for $j = r_m \neq i$. From Eq. (C86) for $i = j = r_m$, we obtain

$$\sum_{k,l \in \mathbb{B}_{\vec{r}_m}} |1\rangle\rangle^{O_{r_m} I'_k} \langle 1|^{O_{r_m} I'_l} \otimes 1^{O'_l \to O'_k} \otimes C_{P\vec{r}_m}^{(ijkl)} = \sum_{k,l \in \mathbb{B}_{\vec{r}_m}} 1^{O'_l \to O'_k} \otimes 1^{O'_l \to I'_k} \otimes \frac{1^{O_{r_m}}}{d} \otimes C_{P\vec{r}_m}^{(ijkl)} \quad \text{if } i = j = r_m. \quad (C91)$$

Using Lemma 7, we obtain

$$C_{P\vec{r}_m}^{(ijkl)} = 0 \quad \text{if } i = j = r_m. \quad (C92)$$

In conclusion, we obtain

$$C_{P\vec{r}_m}^{(ijkl)} = \begin{cases} \tilde{C}_{P\vec{r}_m}^{(ijkl)} \otimes 1^{O_{r_m}} & (i, j \neq r_m) \\ 0 & (\text{otherwise}) \end{cases}. \quad (C93)$$
Thus, from Eqs. (C67) and (C81), we obtain

$$ C_{P\vec{r}_m} = \sum_{i,j \in A_{\vec{r}_{m-1}}} \sum_{k,l \in B_{\vec{r}_{m-1}}} \left( |0\rangle\langle 0|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I_i \left\langle 1|^{O_i} I'_k \left\langle 1|^{O'_k} I'_l \otimes |1\rangle\right\rangle \right. \right. \tag{C94} $$

$$ + |1\rangle\langle 1|^{P_C} \otimes |1\rangle\langle 1|^{P_T} I'_k \left\langle 1|^{O'_k} I_i \left\langle 1|^{O'_i} I'_j \otimes |1\rangle\right\rangle \left. \right\rangle \otimes \tilde{C}_{P\vec{r}_m}^{(ijkl)}. \tag{C95} $$

Thus, defining $C_{P\vec{r}_{m-1}}^{(ijkl)}$ by

$$ C_{P\vec{r}_{m-1}}^{(ijkl)} := \sum_{r_m} \mathrm{tr}_{I_{r_m}} [\tilde{C}_{P\vec{r}_m}^{(ijkl)}], \tag{C96} $$

we obtain Eq. (C75). We finish the proof by recalling that Eq. (C75) implies Eq. (C78), which contradicts the normalization condition in Eq. (C68) of the QC-CC conditions. □

## C6. Lemma 6

**Lemma 6.** The set of matrices

$$ \left\{ \left| 1 \right\rangle^{P_T I'_k} \left\langle 1 \middle|^{P_T I'_l} \otimes \left| 1 \right\rangle^{O'_k I'_i} \left\langle 1 \middle|^{O'_l I'_j} \otimes \left| \vec{\alpha} \right\rangle^{I'_k} \left\langle \vec{\beta} \middle|^{I'_l} \otimes \left| \vec{\gamma} \right\rangle^{I'_i} \left\langle \vec{\delta} \middle|^{I'_j} \right\rangle \right\} \right\} \quad \begin{array}{l} i,j \in \{1, \dots, M\}, k,l \in \{1, \dots, N\}, \\ \vec{\alpha}, \vec{\beta} \in \{1, \dots, d\}^{N-1}, \vec{\gamma}, \vec{\delta} \in \{1, \dots, d\}^{M-1} \end{array} \tag{C97} $$

is linearly independent if $\max(M, N) \le d$ holds. Similarly, the set of matrices

$$ \left\{ \left| 1 \right\rangle^{P_T I_i} \left\langle 1 \middle|^{P_T I_j} \otimes \left| \vec{\alpha} \right\rangle^{I_i} \left\langle \vec{\beta} \middle|^{I_j} \right\rangle \right\} \quad \begin{array}{l} i,j \in \{1, \dots, M\}, \\ \vec{\alpha}, \vec{\beta} \in \{1, \dots, d\}^{M-1} \end{array} \tag{C98} $$

is linearly independent if $M \le d$ holds.

*Proof.* We consider the equation

$$ \sum_{i,j,k,l, \vec{\alpha}, \vec{\beta}, \vec{\gamma}, \vec{\delta}} A_{ijkl \vec{\alpha} \vec{\beta} \vec{\gamma} \vec{\delta}} |1\rangle^{P_T I'_k} \langle 1|^{P_T I'_l} \otimes |1\rangle^{O'_k I'_i} \langle 1|^{O'_l I'_j} \otimes |\vec{\alpha}\rangle^{I'_k} \langle \vec{\beta}|^{I'_l} \otimes |\vec{\gamma}\rangle^{I'_i} \langle \vec{\delta}|^{I'_j} = 0 \tag{C99} $$

for complex coefficients $A_{ijkl \vec{\alpha} \vec{\beta} \vec{\gamma} \vec{\delta}}$. Since $\max(M, N) \le d$ holds, for all $\vec{\alpha}, \vec{\beta}, \vec{\gamma}, \vec{\delta}$, there exists $\alpha^*, \beta^*, \gamma^*, \delta^* \in \{1, \dots, d\}$ such that $\alpha^*, \beta^*, \gamma^*, \delta^*$ do not appear in $\vec{\alpha}, \vec{\beta}, \vec{\gamma}, \vec{\delta}$, respectively. By taking an inner product of Eq. (C99) with $|\alpha^* \alpha^*\rangle^{P_T I'_k} \langle \beta^* \beta^*|^{P_T I'_l} \otimes |\gamma^* \gamma^*\rangle^{O'_k I'_i} \langle \delta^* \delta^*|^{O'_l I'_j} \otimes |\vec{\alpha}\rangle^{I'_k} \langle \vec{\beta}|^{I'_l} \otimes |\vec{\gamma}\rangle^{I'_i} \langle \vec{\delta}|^{I'_j}$ for any $i, j, k, l, \vec{\alpha}, \vec{\beta}, \vec{\gamma}, \vec{\delta}$, we obtain

$$ A_{ijkl \vec{\alpha} \vec{\beta} \vec{\gamma} \vec{\delta}} = 0, \tag{C100} $$

i.e., the set (C97) is linearly independent. We can similarly show that the set (C98) is linearly independent. □

## C7. Lemma 7

**Lemma 7.** The set of matrices

$$ \left\{ \left( |1\rangle^{O_{r_m} I'_k} \langle 1|^{O_{r_m} I'_l} - \frac{1}{d} \otimes 1^{O_{r_m} I'_k} \right) \otimes 1^{O'_l \to O'_k} \otimes |\vec{\alpha}\rangle^{I'_k} \langle \vec{\beta}|^{I'_l} \otimes |\vec{\gamma}\rangle^{O'_k} \langle \vec{\delta}|^{O'_l} \right\} \quad \begin{array}{l} k,l \in \{1, \dots, N\}, \\ \vec{\alpha}, \vec{\beta}, \vec{\gamma}, \vec{\delta} \in \{1, \dots, d\}^{N-1} \end{array} \tag{C101} $$

is linearly independent if $N \le \max(2, d-1)$ holds.
*Proof.* We numerically check the linear independence for the case $N = d = 2$ (see Listing 1). We prove the linear independence for the case $N \le d - 1$ to complete the proof.

We consider the equation

$$ \sum_{k,l,\vec{\alpha},\vec{\beta},\vec{\gamma},\vec{\delta}} A_{kl\vec{\alpha}\vec{\beta}\vec{\gamma}\vec{\delta}} \left( |1\rangle\rangle^{O_{r_m}} I'_k \langle 1|^{O_{r_m}} I'_l - \frac{1^{O_{r_m}}}{d} \otimes 1^{I'_l \to I'_k} \right) \otimes 1^{O'_l \to O'_k} \otimes |\vec{\alpha}\rangle I'_k \langle \vec{\beta}|^{I'_l} \otimes |\vec{\gamma}\rangle^{O'_k} \langle \vec{\delta}|^{O'_l} = 0 \quad (C102) $$

for complex coefficients $A_{kl\vec{\alpha}\vec{\beta}\vec{\gamma}\vec{\delta}}$. Since $N \le d - 1$ holds, for all $\vec{\alpha}, \vec{\beta}$, there exists $\alpha^*, \beta^* \in \{1, \dots, d\}$ such that $\alpha^* \ne \beta^*$ holds and $\alpha^*, \beta^*$ do not appear in $\vec{\alpha}, \vec{\beta}$, respectively. By taking an inner product of Eq. (C102) with $\frac{1}{d} |\alpha^*\alpha^*\rangle^{O_{r_m}} I'_k \langle \beta^*\beta^*|^{O_{r_m}} I'_l \otimes |\vec{\alpha}\rangle I'_k \langle \vec{\beta}|^{I'_l} \otimes 1^{O'_l \to O'_k} \otimes |\vec{\gamma}\rangle^{O'_k} \langle \vec{\delta}|^{O'_l}$ for any $k,l,\vec{\alpha},\vec{\beta},\vec{\gamma},\vec{\delta}$, we obtain

$$ A_{kl\vec{\alpha}\vec{\beta}\vec{\gamma}\vec{\delta}} = 0, \quad (C103) $$

i.e., the set (C101) is linearly independent. □

Listing 1. MATLAB [63] code to check the linear independency of the set (C101) for the case $d = 2$ and $N = 2$, which uses the functions from QETLAB [64].

1 clear
2
3 d=2;
4 N=2;
5
6 one = Tensor(IsotropicState(d, 1)*d,eye(d));
7 id = Tensor(eye(d)/d,eye(d),eye(d));
8 I = eye(d^(d-1));
9
10 for i = 1:d
11 sys(i)=i;
12 end
13 PP = perms(sys);
14
15 pos=0;
16
17 % Calculate the set of matrices
18 for alpha = 1:d^(d-1)
19 for beta=1:d^(d-1)
20 for gamma = 1:d^(d-1)
21 for delta=1:d^(d-1)
22 for k = 1(PP,1)
23 for l=1: size(PP,1)
24 pos(pos+1);
25 A(:,:,pos) = Tensor(eye(d), PermutationOperator(d, PP(k,:)),
PermutationOperator(d, PP(k,:))) * PermuteSystems(Tensor(one-id, I(:,
alpha)*I beta,:), I(:,gamma)*I delta,:)), [1 2 4 3 5]) * Tensor(eye(
d), PermutationOperator(d, PP(1,:)), PermutationOperator(d, PP(1,:)));
26 end
27 end
28 end
29 end
30 end
31 end
32
33 % Flatten the matrices to vectors
34 for pos = 1: size(A,3)
35 B(:,pos) = reshape(A(:,:,pos), [], 1);
36 end
37
38 rank(B) == size(B,2)
## Appendix D: Possible restricted simulations for qubit channels

From this section onwards, we revert to our original notation.

Using numerical methods, we have found three particular cases where a restricted simulation of the quantum switch acting on qubit channels is possible, exactly and deterministically, using a quantum comb. These are the cases of:

* Four identical calls to general qubit channels, called the order AAAA.

* Two calls to unitary qubit channels A and two calls to unitary qubit channels B, in the order ABBB.

* Three calls to unitary qubit channels A and one call to unitary qubit channels B, in the order BAAA.

All of these results were obtained by numerically evaluating the equivalent of the primal SDP of the main text [Eq. (27)] in the case where the input states are fixed and the output target system is discarded, and finding that $p = 1$ up to a high numerical precision.

Effectively, this scenario amounts to an SDP that is analogous to the primal SDP (27) in the main text, but with the first constraint written as

$$C_s * [(J_i^A)^{\otimes k_A} \otimes (J_j^B)^{\otimes k_B}] = p \operatorname{tr}_{t_o}(S_{+0}) * (J_i^A \otimes J_j^B) \quad \forall i, j, \qquad (D1)$$

where $S_{+0}$ is defined as in Eq. (A3). In this case, we have that $C_s, C \in \mathcal{L}(\mathcal{H}^{A_I} \otimes \mathcal{H}^{A_O} \otimes \mathcal{H}^{B_I} \otimes \mathcal{H}^{B_O} \otimes \mathcal{H}^{c_O})$ and $d_{c_I} = d_{t_I} = 1$.

In the case of 4 identical copies of general qubit channels, the input channels were given as a basis constructed in the form of Eq. (33) of the main text. The dimension of the space spanned by $k = 4$ identical copies of a general qubit channel is $d_I = 1820$, a value that can be obtained from the expression presented in the Methods section of the main text.

In the case of $k$ identical copies of qubit unitary channels, a basis can be constructed numerically by randomly sampling a set of qubit unitaries according to the Haar measure, guaranteeing that they are linearly independent. It is only necessary to know the dimension of this subspace beforehand to determine how many unitaries must be sampled. The dimension of the linear space spanned by $k$ copies of $d$-dimension unitary channels is the quantity $D(d, r, s)$ of Ref. [65] for the case $r = s = k$. For $d = 2$, the dimension of the subspace spanned by $k$ identical copies of a unitary channel is given by $d_U = D(d = 2, k, k) = \binom{2k+3}{3}$, which implies $d_U = 10$ for $k = 1$, $d_U = 35$ for $k = 2$, and $d_U = 84$ for $k = 3$.

By numerically evaluating the appropriate SDP, we obtain that the maximum probability of success is $p = 1$ with very high precision in all aforementioned cases. The numerical precision was evaluated in the following way: In all three cases, all inequality constrains are strictly satisfied; as for the equality constraints, they are satisfied up to an error of at most $10^{-9}$ in the operators norm for the case of identical general qubit channels AAAA, and at most $10^{-7}$ in the cases of qubit unitary channels ABBB and BAAA.

We also found that the maximum probability of success remains $p = 1$, with the same precision, in all three cases when the second and third slots of the quantum comb $C$ are parallelized, as depicted in Fig. D1.

**Impossible partly restricted simulation.** As mentioned in the main text, we also found that when the output target system is not discarded—i.e., the partly restricted simulation scenario—then a deterministic simulation is no longer possible in all 3 aforementioned cases.

More concretely, this is the scenario where the first constraint in the primal SDP (27) in the main text is written as

$$C_s * [(J_i^A)^{\otimes k_A} \otimes (J_j^B)^{\otimes k_B}] = p S_{+0} * (J_i^A \otimes J_j^B) \quad \forall i, j, \qquad (D2)$$

where $S_{+0}$ is defined as in Eq. (A3), $C_s, C \in \mathcal{L}(\mathcal{H}^{A_I} \otimes \mathcal{H}^{A_O} \otimes \mathcal{H}^{B_I} \otimes \mathcal{H}^{B_O} \otimes \mathcal{H}^{t_O} \otimes \mathcal{H}^{c_O})$, and $d_{c_I} = d_{t_I} = 1$.

Evaluating the above SDP, for the partly restricted scenario, we found that $p < 1$ in the AAAA case of identical general qubit channels, the ABBB case of qubit unitary channels, as well as the BAAA case of qubit unitary channels. Due to limitations in computational power, the partly restricted simulation SDP was evaluated in all three cases with an input that corresponds to a subset of the basis that was given as input to the restricted simulation SDP. Therefore, the solutions for the maximal probability of success correspond to upper bounds, and are given by
<figure><img src="image_18.png" /><figcaption>Figure D1. Semi-parallelized strategy for restricted qubit simulations. The quantum switch acting on qubit channels can be deterministically simulated by a 4-slot quantum comb that has its second and third slots parallelized in a restricted scenario where the input control and target systems are fixed and the output target system is discarded in three different cases: for identical general quantum channels (i.e. when $A = B$) called order AAAA, and for unitary channels (i.e. when $A = U_A$ and $B = U_B$) in the orders ABBB and BAAA.</figcaption></figure>

$$ \text{order} = \text{AAAA (qubit, general), } p \lesssim 0.942 \qquad \text{(D3)} $$

$$ \text{order} = \text{AABB (qubit, unitary), } p \lesssim 0.822 \qquad \text{(D4)} $$

$$ \text{order} = \text{BAAA (qubit, unitary), } p \lesssim 0.667. \qquad \text{(D5)} $$

The difference between the two simulation scenarios discussed in this section is whether or not the output target state is discarded. Here we can see that this distinction in the requirements of the simulation is sufficient to transform cases where a deterministic simulation is possible (with a discarded output target system) into cases where a deterministic simulation is no longer possible (without discarding the output target system).

## Appendix E: No-go results for unitary channels

As previously discussed, the simulation of the action of the quantum switch on unitary channels is possible when an extra call of one of the input channels is available. This was first shown by Ref. [6] for the action of the quantum switch on entire single-party unitary channels, and here we have shown this result to extend to a more general scenario where the quantum switch acts only on part of the input bipartite unitary channels (see Theorem 1 in Sec. B4). These results hold in the general simulation scenario, where the input systems are not fixed and the output systems are not discarded, and hold as well for any dimension.

However, this result crucially depends not only on the number of extra calls available, but also on the order in which the quantum unitary channels are applied in the simulation. The cases where a simulation is possible for either single-party or for bipartite unitary channels with $(k_A, k_B) = (2, 1)$ use the order ABA. If the order of the applied channels is instead either AAB or BAA, we find that a deterministic simulation is no longer possible, even in the restricted qubit scenario.

Moreover, the existence of a simulation for unitary channels in the order ABA implies that, when $(k_A, k_B) = (2, 2)$, a simulation with the orders ABAB and ABBA also trivially exists. In Sec. D, we showed that a simulation using the order ABBB also exists for unitary channels, albeit *only* in the restricted qubit case where the output target system is discarded. For the case where $(k_A, k_B) = (3, 1)$, a simulation in the orders AABA and ABAA exists, following trivially from the result for ABA. We showed in Sec. D that a simulation for unitary channels in the order BAAA exists as well, but once again *only* in the restricted qubit case. The one case left to study then is a simulation of the quantum switch acting on unitary channels in the order AAAB. We show such a simulation is not possible.

Hence, our three no-go results for simulations of the quantum switch acting exclusively on unitary channels concern the cases of:

* Two calls of the unitary channels A and one call of unitary channels B, in the order AAB.

* Two calls of the unitary channels A and one call of unitary channels B, in the order BAA.