# Quantum Query Complexity of Boolean Functions under Indefinite Causal Order

Alastair A. Abbott, Mehdi Mhalla, Pierre Pocreau

► To cite this version:

Alastair A. Abbott, Mehdi Mhalla, Pierre Pocreau. Quantum Query Complexity of Boolean Functions under Indefinite Causal Order. QPL2023, Jul 2023, Paris, France. 10.48550/arXiv.2307.10285 [hal-04169582v2]

HAL Id: hal-04169582

https://inria.hal.science/hal-04169582v2

Submitted on 14 Nov 2023

**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>

Distributed under a Creative Commons Attribution 4.0 International License
# Quantum Query Complexity of Boolean Functions under Indefinite Causal Order

Alastair A. Abbott,¹ Mehdi Mhalla,² and Pierre Pocreau¹,²

¹Univ. Grenoble Alpes, Inria, 38000 Grenoble, France

²Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG, 38000 Grenoble, France

(Dated: October 26, 2023)

The standard model of quantum circuits assumes operations are applied in a fixed sequential “causal” order. In recent years, the possibility of relaxing this constraint to obtain causally indefinite computations has received significant attention. The quantum switch, for example, uses a quantum system to coherently control the order of operations. Several ad hoc computational and information-theoretical advantages have been demonstrated, raising questions as to whether advantages can be obtained in a more unified complexity theoretic framework. In this paper, we approach this problem by studying the query complexity of Boolean functions under general higher order quantum computations. To this end, we generalise the framework of query complexity from quantum circuits to quantum supermaps to compare different models on an equal footing. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity, and that any potential advantage arising from causally indefinite supermaps can be bounded by the polynomial method, as is the case with quantum circuits. Nevertheless, we find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps.

**Introduction.**—The query model of computation is a simplified framework that offers a way to evaluate the complexity of different computational problems and to probe and compare different computational frameworks. Notably, it has been used to prove various separations between classical and quantum computations, and to provide non-trivial lower bounds on some important computational problems, such as the optimality of Grover’s algorithm or the complexity of graph problems [1–3]. This model was thus far only studied in the context of quantum circuits, in which queries and unitary operations are performed in a fixed sequential order, implying an underlying fixed causal structure. Several recent works have proposed ways of computing beyond fixed causal structures using, for example, the quantum switch [4], where a quantum control system can put different sequences of operations into superposition, leading to what is called an indefinite causal order. Such scenarios can be studied in the higher order framework of quantum supermaps [4] (or “process matrices” [5]) which describes the most general transformations taking some given input operations into a valid output operation in a consistent manner. Although some quantum supermaps are compatible with a fixed causal order, and thus represent quantum circuits [6], others, like the quantum switch, have indefinite causal order or, more formally, are *causally nonseparable* [5, 7, 8].

Causal indefiniteness was shown to provide advantages over quantum circuits in several ad hoc tasks in quantum information theory [9–15]. However, much less is known about its potential advantages in a general complexity theoretic sense except that its computational complexity is upper bound by PP (which includes both NP and BQP) [16].

In this letter, we address this problem by proposing query complexity as a natural way of comparing the relative power of quantum circuits and causally indefinite

supermaps. After recalling the standard query model of computation in terms of quantum circuits, we formulate three different families of quantum supermaps that can be understood as query computations with different causal structures. We show that allowing for superpositions or coherent control of the order of queries in so-called quantum circuits with quantum control of causal order [17] cannot reduce the query complexity of Boolean functions compared to quantum circuits. Furthermore, through a generalisation of the polynomial method to general quantum supermaps, we give a lower bound on any possible reduction that could be obtained with causally indefinite supermaps. Then, using semidefinite programming techniques, we show that an advantage can be obtained with some such supermaps: for some functions, causal indefiniteness can reduce the minimum error with which they can be computed given a fixed number of queries.

**The query model of computation.**—In the quantum query model of computation (see [18] or [19] for a survey), the goal is to compute a Boolean function $f: \{0,1\}^n \to \{0,1\}$ with a quantum circuit having access to an oracle $O_x$. Here without loss of generality we use the phase oracle [19, 20], defined as the unitary that takes as input a state $|i\rangle$ in an $(n+1)$-dimensional Hilbert space $\mathcal{H}^Q$, with $i$ serving as an index, $0 \le i \le n$ such that:

$$O_x |i\rangle = \begin{cases} (-1)^{x_i} |i\rangle & \text{if } i \neq 0, \\ |i\rangle & \text{otherwise.} \end{cases} \quad (1)$$

Note that the special case $|i\rangle = |0\rangle$ is needed to ensure $O_x$ is equivalent to the more common form oracle $O'_x |j,b\rangle = |j,b \oplus x_j\rangle$, with $1 \le j \le n$, $b \in \{0,1\}$ and $\oplus$ denoting addition modulo 2. A quantum circuit with $T$ queries to the oracle is specified by a series of $T+1$ unitaries $(U_1, \dots, U_{T+1})$ each acting on the space $\mathcal{H}^{Q\alpha} = \mathcal{H}^Q \otimes \mathcal{H}^\alpha$, with $\mathcal{H}^\alpha$ an ancillary space of arbitrary
trary dimension. By extending the oracle on the ancil-
lary space, $\tilde{O}_x = O_x \otimes 1^\alpha$, we say the circuit computes
$f$ (exactly) if for all $x$, measuring the left most qubit
of $U_{T+1}\tilde{O}_x U_T \cdots U_1 \tilde{O}_x U_1 |0\cdots0\rangle$ gives the outcome $f(x)$
with probability one. We similarly say that the circuit
computes $f$ with a bounded error $\varepsilon$ if the measurement
result gives, for all $x$, $f(x)$ with a probability at least $1-\varepsilon$
with some fixed $\varepsilon < 1/2$; typically one takes $\varepsilon = 1/3$.
The exact quantum query complexity of a Boolean func-
tion, written $Q_E(f)$, is the minimal value of $T$ for which
there exists a quantum query circuit computing $f$ exactly,
while $Q_2(f)$ is the (two-sided) bounded error quantum
query complexity, defined as the minimal $T$ for which a
quantum query circuit exists computing $f$ with bounded
error $\varepsilon = 1/3$.

This definition of quantum query complexity is the
usual one considered in the literature, and is based on the
standard formalism of quantum circuits. In this letter, we
show that translating this definition into the framework
of quantum supermaps leads to a natural generalisation
of the notion of quantum query complexity to study the
relative power of causal indefiniteness. Let us first intro-
duce the tools and notation we will use throughout this
letter.

Mathematical tools and notation.—We denote the
space of linear operators on a Hilbert space H^X as
L(H^X). To define quantum supermaps we first introduce
quantum channels, which are completely positive (CP)
trace-preserving (TP) maps M : L(H^X) → L(H^Y). A
channel is conveniently represented as a positive semidef-
inite matrix M^{XY} ∈ L(H^{XY}) using the Choi isomor-
phism [21] (see Appendix A), where we adopt the short-
hand H^{XY} = H^X ⊗ H^Y. The composition of two CP
maps, potentially over a subset of their input/output sys-
tems, can be computed directly via their Choi matrices
using the “link product” [6, 22], denoted ‘*’ and defined
for any matrices M^{XY} ∈ L(H^{XY}) and N^{YZ} ∈ L(H^{YZ})
as M^{XY} * N^{YZ} = Tr_Y[(M^{XY} ⊗ 1^Z)^{\top_Y}(1^X ⊗ N^{YZ})] ∈
L(H^{XZ}), where Tr_Y is the partial trace over the sub-
system H^Y and .^{\top_Y} the partial transpose over H^Y. The
link product is commutative and associative and reduces
to the tensor product on maps acting on disjoint Hilbert
spaces (see Appendix B).

A T-input quantum supermap S is then a T-linear,
completely CP-preserving, and TP-preserving map [23].
That is, a supermap is the most general transfor-
mation that transforms any T input channels M_t :
L(H_k^{A_t}) → L(H_k^{A_t^O}) into another quantum channel:
S(M_1, ..., M_T) : L(H^P) → L(H^F). Writing H_k^{A_t^O} =
H_k^{A_t^I} H_k^{A_t^O} and, with T := {1, ..., T}, H_T^{A_t^O} =
⊗_{k∈T} H_k^{A_t^O},
a supermap can be represented in the Choi picture
as a “process matrix” [5], a positive semidefinite ma-
trix W ∈ L(H^{PA_k^O T^O F}) belonging to a specific sub-
space L^Gen (see Appendix C) and normalised such that
Tr W = d^P ∏_{k=1}^T d_k^O, with d^P = dim(H^P) and d_k^O =
dim(H_k^{A_t^O}) [8, 24]. We denote the set of all such pro-
cess matrices W^Gen. The process matrix W fully char-

acterises S, and the Choi matrix of the channel resulting
from applying S to some input channels ($M_1, \dots, M_T$)
is obtained as $S(M_1, \dots, M_T) = (M_1 \otimes \dots \otimes M_T) * W \in
\mathcal{L}(\mathcal{H}^{PF})$.

Fixed order and quantum controlled supermaps.—The general framework of quantum supermaps allows us to compare, on an equal footing, specific classes of quantum supermaps of particular interest, and to understand their computational capabilities. Here we present two sub-classes of particular interest: supermaps with a fixed causal order (sometimes termed quantum combs [6] and which are equivalent to quantum circuits), and quantum supermaps with quantum control of causal order [17].

The class of supermaps compatible with a fixed causal
order (or FO-supermaps) has been extensively studied.
Any such T-input supermap S can be described by T+1
channels $V_1: \mathcal{L}(\mathcal{H}^P) \to \mathcal{L}(\mathcal{H}^{A_t^I \alpha_1})$, $V_t: \mathcal{L}(\mathcal{H}^{A_t^O \alpha_t}) \to \mathcal{L}(\mathcal{H}^{A_{t+1}^I \alpha_{t+1}})$ for $2 \le t \le T$, and $V_{T+1}: \mathcal{L}(\mathcal{H}^{A_T^O \alpha_T}) \to \mathcal{L}(\mathcal{H}^F)$ composed sequentially in a circuit structure [6].
Here, the $\mathcal{H}^{\alpha_t}$ are an ancillary spaces, and $\mathcal{H}^P$ and $\mathcal{H}^F$ are the input and output spaces of the circuit. In
the Choi picture, the action of S on T input channels $(M_1, \dots, M_T)$ is

$$
\begin{align}
S(\mathcal{M}_1, \dots, \mathcal{M}_T) &= V_{T+1} * \mathcal{M}_T * V_T * \dots * V_2 * \mathcal{M}_1 * V_1 \nonumber \\
&= (\mathcal{M}_1 \otimes \dots \otimes \mathcal{M}_T) * W \in \mathcal{L}(\mathcal{H}^{PF}), \tag{2}
\end{align}
$$

where $W = V_{T+1} * \dots * V_1 \in \mathcal{L}(\mathcal{H}^{PA_T^{IO}F})$ is the process
matrix of $S$. Process matrices of this specific form—
which can be decomposed as the link product of quantum
channels—belong to a subset $W^{FO} \subset W^{Gen}$ [6, 17, 22]
(see Appendix D). It is easy to see that quantum query
circuits, as defined above, can readily be represented as
FO-supermaps.

Another family of supermaps, those with quantum con-
trol of causal order (or QC-supermaps), can be formu-
lated as generalised quantum circuits in which a quantum
system controls the order of application of the different
input operations [17]. QC-supermaps are of particular
interest as they are the most general type of quantum
supermap with a clear physical realisation [17, 25, 26],
and include supermaps such as the quantum switch that
are causally indefinite [4].

A QC-supermap alternates between applying some
controlled “internal” operations on a “target” system and
some ancillary systems, potentially correlating these sys-
tems with the quantum control, and using this control
system to control which input operations to apply to the
target system at time-step t. More precisely, through-
out the computation the control system, at time-step
t, has basis states |K<sub>t−1</sub>, k<sub>t</sub>⟩ specifying that operation
k<sub>t</sub> ∉ K<sub>t−1</sub> will be applied next and that the operations
K<sub>t−1</sub> ⊊ T have already been applied. This system con-
trols coherently the application of the different input op-
erations M<sub>k<sub>t</sub></sub> at time-step t and the pure internal op-
erations V<sub>k<sub>t+1</sub></sub><sup>→</sup> : L(H<sub>k<sub>t</sub></sub><sup>A<sub>k</sub><sup>O</sup></sub> <sup>α<sub>t</sub></sup>) → L(H<sub>k<sub>t+1</sub></sub><sup>A<sub>k</sub><sup>I</sup></sup> <sup>α<sub>t+1</sub></sup>) between
time-steps, and is the minimal control system required to
ensure that no operation is applied more than once, while maintaining the possibility for superpositions of causal orders and interference of different causal histories (i.e., permutations of the operations in $K_{t-1}$); see Appendix E or [17] for a more detailed description of QC-supermaps. Process matrices of QC-supermaps belong to a subset $W^{QC} \subset W^{Gen}$ [17], whose characterisation is also given in Appendix E.

**Quantum query complexity under indefinite causal order.**—We can now define what it means for a quantum supermap to compute a Boolean function $f: \{0,1\}^n \to \{0,1\}$, in order to compare the relative computational power of the different types of supermaps.

Let us consider a T-input supermap $S^C$ of class $C \in \{\text{FO}, \text{QC}, \text{Gen}\}$, with trivial input space $\dim(\mathcal{H}^P) = 1$ and output space of dimension $\dim(\mathcal{H}^F) = 2$. These dimensional constraints reflect the fact that, as in the initial definition of quantum query complexity, any fixed input to the supermap can be absorbed directly into it, and only a single output qubit—that will be measured to define the output of the computation—is needed.

To differentiate the different input and output spaces of each query, we label (without imposing a particular order) the T queries to the phase oracle (1) as $O_x^{(1)}, \dots, O_x^{(T)}$, with $O_x^{(i)}: \mathcal{L}(\mathcal{H}^{A_i^I}) \to \mathcal{L}(\mathcal{H}^{A_i^O})$, where $\mathcal{H}^{A_i^I}$ and $\mathcal{H}^{A_i^O}$ are of dimension $n+1$. (Here $O_x$ is the quantum channel corresponding to the unitary oracle $O_x$.) Then for every $x$, the output of $S^C$ is the qubit state $S^C(O_x^{(1)}, \dots, O_x^{(T)}) \in \mathcal{L}(\mathcal{H}^F)$. The probability that one obtains $f(x)$ when measuring this qubit in the computational basis is then given by the Born rule as

$$p(f(x)) = \mathrm{Tr} \left[ S^C(O_x^{(1)}, \dots, O_x^{(T)}) \cdot \Pi_{f(x)} \right] \quad (3)$$

$$= \mathrm{Tr} \left[ (O_x^{\otimes T} * W^C) \cdot \Pi_{f(x)} \right] \quad (4)$$

$$= \mathrm{Tr} \left[ (O_x^{\otimes T} \otimes \Pi_{f(x)}) \cdot W^C \right], \quad (5)$$

with $\Pi_{f(x)} = |f(x)\rangle\langle f(x)|$ and $O_x^{\otimes T} = \bigotimes_{i=1}^T O_x^{(i)}$. We say that $S^C$ computes $f$ with a bounded error $\varepsilon$ if for all $x$, $p(f(x)) \ge 1 - \varepsilon$. We can now define $Q_E^C(f)$ as the minimum value $T$ for which there exists a quantum supermap $S^C$ computing $f$ exactly (i.e., with error $\varepsilon = 0$). Similarly, the corresponding bounded-error complexity $Q_2^C(f)$ is the minimum $T$ for which there exists a quantum supermap $S^C$ computing $f$ with bounded error $\varepsilon = 1/3$. By definition we have the following inequalities:

$$Q_E^{\mathrm{Gen}}(f) \le Q_E^{\mathrm{QC}}(f) \le Q_E^{\mathrm{FO}}(f) = Q_E(f), \quad (6)$$

$$Q_2^{\mathrm{Gen}}(f) \le Q_2^{\mathrm{QC}}(f) \le Q_2^{\mathrm{FO}}(f) = Q_2(f). \quad (7)$$

To compare the power of the different classes of quantum supermaps in terms of query complexity, we need to understand how these inequalities can be refined.

**Quantum control over T copies of the same unitary channel.**—QC-supermaps are known to provide advantages over FO-supermaps in several tasks, some of which are sometimes expressed as query complexity advantages

(albeit of a different kind than studied here), such as in the discrimination between pairs of commuting and anti-commuting unitaries [9] and generalisations of that task [10, 12]. Here we show that they cannot provide any advantage in query complexity of Boolean functions through the generalisation of a recent result for “switch-like” supermaps, a strict subclass of QC-supermaps which generalises the quantum switch. In particular, we build on a result of Ref. [13] showing that such supermaps are equivalent to FO-supermaps when acting on T copies of the same unitary channel. Here we prove the following theorem.

**Theorem 1.** For any T-input QC-supermap $S^{QC}$, there exists an FO-supermap $S^{FO}$ such that $S^{QC}$ and $S^{FO}$ have the same action whenever applied to T copies of the same unitary channel. That is, for all unitary channels $U$, $S^{QC}(U, \dots, U) = S^{FO}(U, \dots, U)$.

The proof of Theorem 1 is detailed in Appendix F. A direct corollary is that $Q_E^{QC} = Q_E^{FO}$ and $Q_2^{QC} = Q_2^{FO}$. Thus, no advantage in query complexity can be found using QC-supermaps instead of FO-supermaps, and for that matter, in any task where T copies of the same unitary channel are considered, such as the reversal of unknown unitary transformations [27] or unitary channel discrimination [13]. In both these tasks, however, advantages were obtained using more general causally indefinite quantum supermaps beyond QC-supermaps. This raises the prospect of nevertheless obtaining advantages in query complexity from causally indefinite supermaps. In order to better target where to look for such an advantage, we first provide a lower bound on any potential reduction of query complexity of Boolean functions with general supermaps by generalising a well-studied bound for quantum circuits, the polynomial method.

**Polynomial bound for general quantum supermaps.**— The polynomial method makes a connection between the output of an FO-supermap and a multivariate polynomial $g$, and is an important method for proving lower bounds on the quantum query complexity of Boolean functions [28]. A polynomial $g$ is said to represent a Boolean function $f$ if for all $x \in \{0,1\}^n$, $f(x) = g(x)$. As an example, consider the polynomial $g(x_1, x_2) = x_1+x_2-x_1x_2$, which represents the Boolean OR function. This polynomial has degree 2, and we denote $\deg(f)$ the smallest degree of any polynomial representing $f$. Similarly, we write $\widetilde{\deg}(f)$ the degree of the smallest polynomial approximating $f$ with a bounded error $\varepsilon = 1/3$, i.e., such that for all $x$, $|g(x) - f(x)| \le 1/3$. The polynomial method states that for all Boolean functions we have $\deg(f)/2 \le Q_E^{FO}(f)$, and likewise for the bounded-error counterpart, that $\widetilde{\deg}(f)/2 \le Q_2^{FO}(f)$. Here, we generalise this lower bound to general supermaps and thereby bound the potential advantage obtainable with causally indefinite supermaps over standard quantum circuits.

**Theorem 2.** For any Boolean function $f$, we have $\deg(f)/2 \le Q_E^{\mathrm{Gen}}(f)$ and $\widetilde{\deg}(f)/2 \le Q_2^{\mathrm{Gen}}(f)$.
The proof is similar to that of the original result; we provide the full details in Appendix G and simply outline the argument here. Supposing that $Q_E^{\text{Gen}}(f) = T$, there is a T-input supermap $S^{\text{Gen}}$ with process matrix $W^{\text{Gen}}$ such that $f(x) = \text{Tr}[(\mathcal{O}_x^{\otimes T} * W^{\text{Gen}}) \cdot \Pi_1]$. Proceeding by induction, one finds that the Choi matrix of the T queries, $\mathcal{O}_x^{\otimes T}$, has elements that are multivariate polynomials of degree at most $2T$. Since both the trace and link product are linear, it immediately follows that $f(x)$ is also a multivariate polynomial of degree at most $2T$, completing the proof. An analogous proof gives us the bounded error version of the statement.

These results mean that for functions whose polynomial bound is tight for FO-supermaps, i.e., when $\deg(f)/2 = Q_E^{\text{FO}}(f)$ or $\widetilde{\deg}(f)/2 = Q_2^{\text{FO}}(f)$, causal indefiniteness cannot provide any advantage. This is the case, for example, of the OR function [28] (which is computed with a bounded error by Grover's algorithm). Theorems 1 and 2 thus allow us to refine the inequalities (6) and (7) as follows:

$$ \frac{\deg(f)}{2} \le Q_E^{\text{Gen}}(f) \le Q_E^{\text{QC}}(f) = Q_E^{\text{FO}}(f) = Q_E(f) \quad (8) $$

$$ \frac{\widetilde{\deg}(f)}{2} \le Q_2^{\text{Gen}}(f) \le Q_2^{\text{QC}}(f) = Q_2^{\text{FO}}(f) = Q_2(f). \quad (9) $$

Still, it is known that some Boolean functions do not have a tight polynomial bound [29], meaning that Theorem 2 does not rule out a potential advantage from causal indefiniteness using general supermaps. This motivates us to study explicit Boolean functions to look for such an advantage. We note that some bounds can be immediately put on the extent of any possible separation: since $Q_E(f) = \tilde{O}(\deg(f)^3)$ and $Q_2(f) = \tilde{O}(\deg(f)^4)$ [30, 31], one cannot hope for an exponential advantage from causal indefiniteness.<fnref n="1" />

In general, we lack an understanding of general supermaps beyond QC-supermaps, so trying to develop analytically supermaps providing such an advantage for general n-bit Boolean functions is extremely challenging. Instead, we study exhaustively Boolean functions up to 4 bits, building on the extensive literature on the optimisation of quantum supermaps using semidefinite programs (SDPs) [8, 24].

**Advantage of general supermaps over FO-supermaps.**—In the remainder of this letter, we show an advantage of causally indefinite supermaps over fixed order ones by considering the minimum bounded error computation of a function $f$. Let us denote by $\varepsilon_T^{\text{FO}}(f)$ (resp. $\varepsilon_T^{\text{Gen}}(f)$) the minimum error $\varepsilon$ for which there exists a T-query FO-supermap (resp. a general supermap) computing $f$ with a bounded error $\varepsilon$. We prove the following theorem for $T = 2$.

**Theorem 3.** *There exists some function $f$ for which $\varepsilon_2^{\text{Gen}}(f) < \varepsilon_2^{\text{FO}}(f)$.*

To prove Theorem 3, we use SDPs to look for such a gap on all Boolean functions up to 4 input bits. A systematic study for quantum circuits of the minimum bounded error computation of functions using SDPs was already performed in Ref. [32] for functions up to 4 bits, and for symmetric functions up to 6 bits. Their SDP formulation keeps track of the evolution of the state through the quantum circuit by defining T Gram matrices, one for each additional query [33]. Unfortunately this methods fails to extend to general supermaps as it exploits the sequential structure of a FO-supermap which has no analogue in generic quantum supermaps.<fnref n="2" /> Here, using the characterisation of supermaps in the Choi picture as process matrices $W$, we give an SDP formulation of the minimum error bound for both FO-supermaps and general ones.

Let us consider a Boolean function $f$ and a T-query supermap $S^C$ with $C \in \{\text{FO}, \text{Gen}\}$. Because we measure the output of the supermap to obtain the value of $f(x)$, it is convenient to consider, instead of the process matrix $W$, the quantum superinstrument $\{W^{[i]}\}_{i \in \{0,1\}}$ such that $W^{[i]} = W * \Pi_i$ [17], so that $p(f(x)) = \text{Tr}[W^{[f(x)]} \cdot \mathcal{O}_x^{\otimes T}]$. This has the advantage of reducing the size of the matrices being optimised numerically; for $T = 2$ and $n = 4$, $W$ is a matrix of size 1250, whereas the $W^{[i]}$ are of size 625, a difference crucial for rendering the SDPs we present below tractable. Writing $F^{[i]} = \{x : f(x) = i\}$, the minimum error bound $\varepsilon_T^C(f)$ is given by the SDP

$$ \begin{align} \varepsilon_T^C(f) &= \max_{\varepsilon, W^{[0]}, W^{[1]}} 1 - \varepsilon \nonumber \\ \text{s.t.} \quad & \forall x \in F^{[0]}, \text{Tr}[W^{[0]} \cdot \mathcal{O}_x^{\otimes T}] \ge 1 - \varepsilon, \nonumber \\ & \forall x \in F^{[1]}, \text{Tr}[W^{[1]} \cdot \mathcal{O}_x^{\otimes T}] \ge 1 - \varepsilon, \tag{10} \\ & W^{[0]} \ge 0, W^{[1]} \ge 0, \varepsilon \ge 0, \nonumber \\ & W^{[0]} + W^{[1]} \in W^C. \nonumber \end{align} $$

Note that the size of the $W^{[i]}$'s scale as $(n+1)^{2T}$ making the SDP difficult to solve for even moderate $n$ and $T$. We solved it numerically for 2 queries and for all Boolean functions up to 4 bits (including constant functions and functions depending on fewer bits). By exploiting the symmetries inherent in the SDP, one can further reduce the number of variables and constraints, but we were still unable to solve it for 3 queries or 5 bits.

For 3 bits and 2 queries it is known that FO-supermaps are sufficient to exactly compute all functions except the AND function [32] which has an exact query complexity

<footnote n="1">¹ A function $f(x) = \tilde{O}(g(x))$ if $f(x) = O(g(x) \log^k x)$ for some constant $k$.</footnote>

<footnote n="2">² Indeed, for the same reason a more powerful method of bounding query complexity for quantum circuits, the adversarial method [20, 34], is not readily generalisable to generic supermaps, in contrast to the polynomial bound.</footnote>
$Q_E^{FO}(AND) = n$. For this function, no advantage was found with 2-query general supermaps.

For 4-bit functions, as in Ref. [32], we reduced the number of functions to look at by considering the so-called negate, permute, negate (NPN) equivalence relation. We say that two Boolean functions are equivalent if they are the same up to negation and permutation of the input bits, and negation of the output. These transformations correspond to a relabelling of the input and output bits, leaving unchanged the query complexity of a function.

The results are summarised in Table I of Appendix J where the ID of a function corresponds to its truth table converted into an integer, and the results of the SDPs for both FO- and general supermaps are rounded to the fifth decimal place. Our results for FO-supermaps coincide, as expected, with those of Ref. [32]. Out of the 222 NPN representatives, we observe a gap between the minimum error bounds $\epsilon_2^{FO}(f)$ and $\epsilon_2^{Gen}(f)$ for 179 functions, the maximum gap being 0.00947 (close to 1%) for the functions with IDs 5783, 5865 and 6630. The simplest of the three functions (ID 5865), can be written as the polynomial $f(x) = x_1 + x_2x_3 + x_2x_4 + x_3x_4 + x_2x_3x_4$.

This numerical evidence is not an analytical proof of Theorem 3 as the constraints of the SDPs are only satisfied up to numerical precision. However, extracting an FO- or general supermap that rigorously verifies the constraints is possible by rationalising the numerical results and perturbing the SDPs' solutions. Such a method was developed in Ref. [35] and allows us to obtain upper bounds with the primal SDP (10), and lower bounds with the corresponding dual SDP which can be derived with Lagrangian method (see Appendix H). Using the extraction methods (detailed in Appendix I) for the function ID 5865, we find the bounds

$$0.0324 \le \epsilon_2^{Gen}(f) \le 0.0377 < 0.0465 \le \epsilon_2^{FO}(f) \le 0.0467, \quad (11)$$

which proves Theorem 3.

*Discussion.* —By generalising the notion of query complexity to general supermaps, we provide a natural tool to probe, in a unified complexity theoretic framework and on equal footing, the power and the potential advantages that different types of causal structure can provide. Until now, it was unclear whether causal indefiniteness

could provide any advantage in such a fundamental model of computation. We found a separation between FO-supermaps and general, potentially causally indefinite, supermaps in the minimum error probability with which they can compute a Boolean function using two queries. While this separation does not directly translate into an asymptotic query complexity separation, it is a crucial first step in this direction. One possible such approach would be to explore whether the separation we found can be amplified by recursively composing supermaps in a suitably well-defined manner [36, 37], similar to the advantage in query complexity obtained with quantum circuits in Ref. [29]. These results also raise the question of whether it is possible to find a separation in exact query complexity.

Along the way, we also showed some important results limiting the power of causal indefiniteness, by generalising the polynomial method which constrain any possible asymptotic separation, and by proving the equivalence of FO-supermaps and QC-supermaps on certain problems, including query complexity. This raises natural questions about the power of specific classes of supermaps beyond QC-supermaps, such as that of purifiable processes [38].

With QC-supermaps being the most general supermaps we currently know how to implement, it will be interesting to study further settings. For instance, can advantages over quantum circuits be obtained when given multiple different oracles, and can our results be used to obtain advantages in quantum communication complexity in more standard settings than those studied with causal indefiniteness previously [39]?

ACKNOWLEDGMENTS

The authors acknowledge funding from the French National Research Agency projects ANR-15-IDEX-02 and ANR-22-CE47-0012, and the Plan France 2030 projects ANR-22-CMAS-0001 and ANR-22-PETQ-0007. For the purpose of open access, the authors have applied a CC-BY public copyright licence to any Author Accepted Manuscript (AAM) version arising from this submission.

[1] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing 26, 1510 (1997), arXiv:quant-ph/9701001 [quant-ph].

[2] L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing - STOC '96 (ACM Press, Philadelphia, Pennsylvania, United States, 1996) pp. 212-219, arXiv:quant-ph/9605043 [quant-ph].

[3] C. Dürr, M. Heiligman, P. HOyer, and M. Mhalla, Quantum query complexity of some graph problems, SIAM

Journal on Computing 35, 1310 (2006), arXiv:quant-ph/0401091 [quant-ph].

[4] 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].

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

[6] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Quantum circuit architecture, Phys. Rev. Lett. 101, 060401 (2008), arXiv:0712.1325 [quant-ph].
[7] O. Oreshkov and C. Giarmatzi, Causal and causally separable processes, New Journal of Physics 18, 093020 (2016), arXiv:1506.05449 [quant-ph].

[8] J. Wechs, A. A. Abbott, and C. Branciard, On the definition and characterisation of multipartite causal (non)separability, New Journal of Physics 21, 013027 (2019), arXiv:1807.10557 [quant-ph].

[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] 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].

[11] 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].

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

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

[14] 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].

[15] X. Zhao, Y. Yang, and G. Chiribella, Quantum metrology with indefinite causal order, Phys. Rev. Lett. 124, 190503 (2020), arXiv:1912.02449 [quant-ph].

[16] M. Araújo, P. A. Guérin, and A. Baumeler, Quantum computation with indefinite causal structures, Phys. Rev. A 96, 052315 (2017), arXiv:1706.09854 [quant-ph].

[17] 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].

[18] H. Buhrman and R. de Wolf, Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288, 21 (2002).

[19] A. Ambainis, Understanding quantum algorithms via query complexity, in Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018 (World Scientific, 2018) pp. 3265–3285, arXiv:1712.06349 [quant-ph].

[20] A. Ambainis, Quantum Lower Bounds by Quantum Algorithms, Journal of Computer and System Sciences 64, 750 (2002), arXiv:quant-ph/0002066 [quant-ph].

[21] M.-D. Choi, Completely positive linear maps on complex matrices, Linear Algebra and its Applications 10, 285 (1975).

[22] 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].

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

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

[25] T. Purves and A. J. Short, Quantum theory cannot violate a causal inequality, Phys. Rev. Lett. 127, 110402 (2021), arXiv:2101.09107 [quant-ph].

[26] M. Salzger, Connecting indefinite causal order processes to composable quantum protocols in a spacetime, arXiv:2304.06735 [quant-ph] (2023).

[27] 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].

[28] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf, Quantum lower bounds by polynomials, Journal of the ACM 48, 778 (2001), arXiv:quant-ph/9802049 [quant-ph].

[29] A. Ambainis, Polynomial degree vs. quantum query complexity, Journal of Computer and System Sciences 72, 220 (2006), arXiv:quant-ph/0305028 [quant-ph].

[30] S. Aaronson, S. Ben-David, and R. Kothari, Separations in query complexity using cheat sheets, in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016) (2016) pp. 863–876, arXiv:1511.01937 [quant-ph].

[31] S. Aaronson, S. Ben-David, R. Kothari, S. Rao, and A. Tal, Degree vs. approximate degree and quantum implications of huang’s sensitivity theorem, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021) pp. 1330–1342, arXiv:2010.12629 [quant-ph].

[32] A. Montanaro, R. Jozsa, and G. Mitchison, On exact quantum query complexity, Algorithmica 71, 775 (2015), arXiv:1111.0475 [quant-ph].

[33] H. Barnum, M. Saks, and M. Szegedy, Quantum query complexity and semi-definite programming, in 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings. (2003) pp. 179–193.

[34] P. Hoyer, T. Lee, and R. Spalek, Negative weights make adversaries stronger, in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing - STOC '07 (ACM Press, San Diego, California, USA, 2007) p. 526, arXiv:quant-ph/0611054 [quant-ph].

[35] 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].

[36] P. A. Guérin, M. Krumm, C. Budroni, and Č. Brukner, Composition rules for quantum processes: a no-go theorem, New J. Phys. 21, 012001 (2019), arXiv:1806.10374 [quant-ph].

[37] A. Kissinger and S. Uijlen, A categorical semantics for causal structure, Logical Methods Comput. Sci. 15, 4426 (2019), arXiv:1701.04732 [quant-ph].

[38] M. Araújo, A. Feix, M. Navascués, and Č. Brukner, A purification postulate for quantum mechanics with indefinite causal order, Quantum 1, 10 (2017), arXiv:1611.08535 [quant-ph].

[39] P. A. Guérin, A. Feix, M. Araújo, and Č. Brukner, Exponential communication complexity advantage from quan-
tum superposition of the direction of communication,
Phys. Rev. Lett. 117, 100502 (2016), arXiv:1605.07372
[quant-ph].

[40] A. Jamiołkowski, Linear transformations which preserve trace and positive semidefiniteness of operators, *Reports on Mathematical Physics* **3**, 275 (1972).

[41] S. Boyd and L. Vandenberghe, *Convex Optimization*
(Cambridge University Press, 2004).

[42] J. Lofberg, Yalmip : a toolbox for modeling and optimization in matlab, in *2004 IEEE International Conference on Robotics and Automation (IEEE Cat. No.04CH37508)* (2004) pp. 284-289.

[43] B. O'Donoghue, E. Chu, N. Parikh, and S. Boyd, Conic optimization via operator splitting and homogeneous self-dual embedding, *Journal of Optimization Theory and Applications* **169**, 1042 (2016), arXiv:1312.3039 [math.OC].
Appendix A: Choi isomorphism

The Choi–Jamiolkowski isomorphism [21, 40] (here we use the “Choi version”) is an isomorphism between two different representations of CPTP maps. The Choi matrix of a linear map $\mathcal{M}: \mathcal{L}(\mathcal{H}^X) \to \mathcal{L}(\mathcal{H}^Y)$ is defined as

$$ \mathcal{M} = \mathcal{I} \otimes \mathcal{M}(|1\rangle\langle 1|^{XX}) = \sum_{i,i'} |i\rangle\langle i'| \otimes \mathcal{M}(|i\rangle\langle i'|) \in \mathcal{L}(\mathcal{H}^X \otimes \mathcal{H}^Y), \quad (A1) $$

where $|1\rangle\langle 1|^{XX} = \sum_i |i\rangle\langle i| \otimes |i\rangle \in \mathcal{H}^{XX}$ is the (unnormalised) maximally entangled state, $\{|i\rangle\}_i$ the computational basis of $\mathcal{H}^X$, and $\mathcal{I}: \mathcal{L}(\mathcal{H}^X) \to \mathcal{L}(\mathcal{H}^X)$ the identity channel. Here, as throughout, we use the shorthand notation $\mathcal{H}^{XY} := \mathcal{H}^X \otimes \mathcal{H}^Y$, etc. Several important properties of a linear map $\mathcal{M}$ can be directly described through its Choi matrix $\mathcal{M}$. In particular, $\mathcal{M}$ is completely positive (CP) if and only if $\mathcal{M}$ is positive semidefinite (i.e., $\mathcal{M} \ge 0$), and $\mathcal{M}$ is trace preserving (TP) if and only if $\text{Tr}_Y \mathcal{M} = 1^X$. These two properties make the Choi isomorphism a useful tool for optimising over quantum channels in semidefinite programs (SDPs). Finally, the action of $\mathcal{M}$ can be described in terms of its Choi matrix via the inverse Choi isomorphism as

$$ \mathcal{M}(\rho) = \text{Tr}_X [(\rho^\top \otimes 1^Y)\mathcal{M}], \quad (A2) $$

where $\cdot^\top$ is the transpose, and $\text{Tr}_X$ denotes the partial trace over the system $X$.

It is often convenient to manipulate unitary (or isometric) channels at the level of their so-called Choi vectors. For an isometric channel $U$, corresponding to the isometry $U: \mathcal{H}^X \to \mathcal{H}^Y$, its Choi vector is given as

$$ |U\rangle\langle U| = 1^X \otimes U(|1\rangle\langle 1|^{XX}) = \sum_i |i\rangle \otimes U |i\rangle \in \mathcal{H}^{XY}, \quad (A3) $$

and its Choi matrix can be recovered as $U = |U\rangle\langle U|$.

Appendix B: Link product

The link product [6, 22] is a useful tool allowing the composition of CP maps, potentially over a subset of their input/output systems, to be computed directly in the Choi picture. It is defined, for any matrices $\mathcal{M}^{XY} \in \mathcal{L}(\mathcal{H}^{XY})$ and $\mathcal{N}^{YZ} \in \mathcal{L}(\mathcal{H}^{YZ})$, as

$$ \mathcal{M}^{XY} * \mathcal{N}^{YZ} = \text{Tr}_Y [ (\mathcal{M}^{XY} \otimes 1^Z)^{\top_Y} (1^X \otimes \mathcal{N}^{YZ}) ] \in \mathcal{L}(\mathcal{H}^{XZ}), \quad (B1) $$

where $\cdot^{\top_Y}$ denotes the partial transpose over the Hilbert space $\mathcal{H}^Y$ with respect to the computational basis. Because of the invariance of the trace under cyclic permutations, the link product is commutative, $\mathcal{M}^{XY} * \mathcal{N}^{YZ} = \mathcal{N}^{YZ} * \mathcal{M}^{XY}$, while in $n$-fold link products it is also associative as long as each Hilbert space appears at most twice in the product. This will notably allow us to write unambiguously, for example, $\mathcal{M}_1 * \cdots * \mathcal{M}_T$, and is likewise why we differentiate, for instance, between the Hilbert spaces $\mathcal{H}^{\alpha_i}$ and $\mathcal{H}^{\alpha_{i'}}$ of the ancillary systems at different places in a quantum circuit (or QC-supermap), even if these spaces are isomorphic.

When $\mathcal{H}^Y$ is trivial (so that $\mathcal{M}^{XY}$ and $\mathcal{N}^{YZ}$ do not share any Hilbert spaces), the link product reduces to the tensor product as $\mathcal{M}^X * \mathcal{N}^Z = \mathcal{M}^X \otimes \mathcal{N}^Z$. If, on the other hand, $\mathcal{H}^X$ and $\mathcal{H}^Z$ are trivial (so that the operations act on the same Hilbert space $\mathcal{H}^Y$), then $\mathcal{M}^Y * \mathcal{N}^Y = \text{Tr}[(\mathcal{M}^Y)^\top \mathcal{N}^Y]$.

A version of the link product can also be formulated for vectors, allowing the composition of unitaries (or, more generally, isometries) to be described directly on their Choi vectors [17]. The link product between two vectors $|U\rangle\langle U| \in \mathcal{H}^{XY}$ and $|V\rangle\langle V| \in \mathcal{H}^{YZ}$ is given as

$$ |U\rangle\langle U| * |V\rangle\langle V| = (|U\rangle\langle U|^{\top_Y} \otimes 1^Z) |V\rangle\langle V| \in \mathcal{H}^{XZ}. \quad (B2) $$

Appendix C: Characterisation of general supermaps

Recall that, as described in the main text, a general $T$-input quantum supermap $\mathcal{S}$ is a $T$-linear completely CP-preserving and TP-preserving map. Such a supermap can be represented in the Choi picture by its process matrix $W \in \mathcal{L}(\mathcal{H}^{PA^I_T^O_F})$ [5, 24]. Let us write the set of all process matrices of general $T$-input quantum supermaps$^3$ as $\mathcal{W}^{\text{Gen}}$.

<footnote>$^3$ For a given (in general, implicitly) scenario, i.e., specification of $T$ and the dimensions of the Hilbert spaces $\mathcal{H}^P, \mathcal{H}^{A_k^I}, \mathcal{H}^{A_k^O}, \mathcal{H}^F$.</footnote>
The process matrices of quantum supermaps are positive semidefinite matrices normalised to satisfy Tr W = d^O with d^O = d^P \prod_{k=1}^T d_k^O (where d^P = \dim(H^P) and d_k^O = \dim(H_k^{AO})), and which belong to a specific linear subspace L^Gen. This subspace can be nicely characterised through linear constraints on W^Gen, allowing one to optimise over general supermaps in SDPs. This characterisation can be nicely expressed using the "trace-out-and-replace" notation [24] defined as

$$ xW = \frac{1^X}{d_X} \otimes \mathrm{Tr}_X W \quad \text{and} \quad [1-x]W = W - \frac{1^X}{d_X} \otimes \mathrm{Tr}_X W, \qquad (C1) $$

with $d_X = \dim(H^X)$. Let us also define the "reduced" process matrices $W^{[P]} = \mathrm{Tr}_{A_T^{IO}F} W \in \mathcal{L}(H^P)$ and, for any nonempty subset $K \subseteq T$,

$$ W^{[PK]} = \mathrm{Tr}_{A_T^{IO}F} W \in \mathcal{L}(H^{PA_K^{IO}}). \qquad (C2) $$

**Proposition 1** (From [17, 24]). A matrix $W \in \mathcal{L}(H^{PA_T^{IO}F})$ is the process matrix of a T-input quantum supermap (i.e., $W \in W^{Gen}$) if and only if $W$ is positive semidefinite ($W \ge 0$), $\mathrm{Tr} W = d^O$, and $W \in \mathcal{L}^{Gen}$, where the linear subspace $\mathcal{L}^{Gen}$ is defined as

$$ W \in \mathcal{L}^{Gen} \iff \forall \emptyset \subsetneq K \subseteq T, \quad \Pi_{k \in K}[1-A_k^{IO}]W^{[PK]} = 0 \quad \text{and} \quad [1-P]W^{[P]} = 0. \qquad (C3) $$

## Appendix D: Characterisation of FO-supermaps

In a T-input fixed order quantum supermap, the input operations are applied in a fixed sequential order. For example, the order $(1, \dots, T)$ means that the input operations are applied in the order they are passed as arguments. Such a supermap can be represented in the Choi picture by its process matrix $W \in \mathcal{L}(H^{PA_T^{IO}F})$ [6, 22], which can be decomposed as the link product of some quantum channels, $W = V_{T+1} * \dots * V_1$, with the $V_i$'s, for $2 \le t \le T$, being the Choi matrices of quantum channels $V_t : \mathcal{L}(H_{t}^{A_t^O}) \to \mathcal{L}(H_{t+1}^{A_{t+1}^O})$, and $V_1 : \mathcal{L}(H^P) \to \mathcal{L}(H_{1}^{A_1^O})$ and $V_{T+1} : \mathcal{L}(H_{T}^{A_{T}^O}) \to \mathcal{L}(H^F)$, where the $H_{t}^{A_t^O}$ are ancillary Hilbert spaces and can, without loss of generality, be taken to be isomorphic (we differentiate them for clarity and to write unambiguously the link product of all $V_t$ as above). Let us write the set of all process matrices of T-input FO-supermaps as $W^{FO}$.

A nice characterisation of the set $W^{FO}$ is obtained by combining the trace-preserving conditions on the Choi matrices of the $V_t$ and the decomposition of $W$ into their link product.

**Proposition 2** (From [6, 17]). A matrix $W \in \mathcal{L}(H^{PA_T^{IO}F})$ is the process matrix of a T-input quantum supermap with fixed order $(1, \dots, T)$ (i.e, $W \in W^{FO}$) if and only if it is positive semidefinite and its reduced matrices, defined for $1 \le t \le T$ as

$$ W_{(t)} = \frac{1}{d_t^O d_{t+1}^O \cdots d_T^O} \mathrm{Tr}_{A_t^{O} A_{\{t+1, \dots, T\}}^{IO} F} W \in \mathcal{L}(H^{PA_{\{1, \dots, t-1\}}^{IO} A_t^I}), \qquad (D1) $$

satisfy

$$ \begin{align} \mathrm{Tr}_{A_1^I} W_{(1)} &= 1^P, \notag \\ \forall n = 1, \dots, T-1, \mathrm{Tr}_{A_{t+1}^I} W_{(t+1)} &= W_{(t)} \otimes 1^{A_t^O}, \tag{D2} \\ \text{and } \mathrm{Tr}_F W &= W_{(T)} \otimes 1^{A_T^O}. \notag \end{align} $$

Note that the linear constraints (D1) and (D2) both enforce the normalisation constraints Tr W = d^O and define a linear subspace $\mathcal{L}^{FO}$, so that, in analogy to the characterisation of $W^{Gen}$ in Proposition 1, a matrix $W \in \mathcal{L}(H^{PA_T^{IO}F})$ is in $W^{FO}$ if and only if $W \ge 0$, Tr W = d^O and $W \in \mathcal{L}^{FO}$ [8].

## Appendix E: Description and characterisation of QC-supermaps

Supermaps with quantum control of causal order (or QC-supermaps) are a form of generalised quantum circuits where a quantum system is used to coherently control the order in which the input operations are applied. For simplicity, we will assume throughout the presentation of QC-supermaps here that the input operations are unitaries
$(U_1, \dots, U_T)$. For a more detailed presentation and the (rather simple) generalisation to generic channels as input operations (which leads to the same set of corresponding process matrices), see [17].

A QC-supermap alternates between applying some controlled “internal” operations on a “target” system and some ancillary systems, potentially correlating these systems with the quantum control, and using this control system to control which input operations to apply at time-step $t$. More precisely, throughout the computation the control system takes, at time-step $t$, the basis states $|K_{t-1}, k_t\rangle^{C_t^{(t)}} \in \mathcal{H}^{C_t^{(t)}}$, specifying that operation $k_t \notin K_{t-1}$ will be applied and that the operations $K_{t-1} \subsetneq \mathcal{T}$ have already been applied. This control system controls the application of the different $U_{k_t}$ and the pure operations $V_{K_{t-1}, k_t}^{\to k_{t+1}}$ between time-steps, and is the minimal control system required to ensure that no operation is applied more than once, while maintaining the possibility for superpositions of causal orders and interference of different causal histories (i.e., permutations of the operations in $K_{t-1}$).

A QC-supermap is completely specified by the composants of the internal operations, $V_{\emptyset, \emptyset}^{\to k_1} : \mathcal{H}^P \to \mathcal{H}^{A_{k_1}^I \alpha_1}$, $V_{K_{t-1}, k_t}^{\to k_{t+1}} : \mathcal{H}^{A_{k_t}^O \alpha_t} \to \mathcal{H}^{A_{k_{t+1}}^I \alpha_{t+1}}$ (for $1 \le t \le T-1$) and $V_{K_{T-1}, k_T}^{\to F} : \mathcal{H}^{A_{k_T}^O \alpha_T} \to \mathcal{H}^{F \alpha_F}$, where the $\mathcal{H}^{\alpha_t}$ and $\mathcal{H}^{\alpha_F}$ are again ancillary spaces which, without loss of generality, can be assumed to be isomorphic at each time-step. In order to formally express the control of both the internal and external (input) operations – which act on a priori different spaces – it is necessary to embed these operations in some generic input and output spaces $\mathcal{H}^{\tilde{A}_t^I}$ and $\mathcal{H}^{\tilde{A}_t^O}$ for each time-step $t$ [17]. We denote the corresponding operators $\tilde{U}_{k_t}^{[t]} : \mathcal{H}^{\tilde{A}_t^I} \to \mathcal{H}^{\tilde{A}_t^O}$ (for each $k_t \in \mathcal{T}$), $\tilde{V}_{\emptyset, \emptyset}^{\to k_1} : \mathcal{H}^P \to \mathcal{H}^{\tilde{A}_1^I \alpha_1}$, $\tilde{V}_{K_{t-1}, k_t}^{\to k_{t+1}} : \mathcal{H}^{\tilde{A}_t^O \alpha_t} \to \mathcal{H}^{\tilde{A}_{t+1}^I \alpha_{t+1}}$ (for $1 \le t \le T-1$) and $\tilde{V}_{K_{T-1}, k_T}^{\to F} : \mathcal{H}^{\tilde{A}_T^O \alpha_T} \to \mathcal{H}^{F \alpha_F}$.

A QC-supermap thus proceeds by applying, at each time-step $t$, the coherently controlled input operations

$$ \tilde{U}^{[t]} = \sum_{K_{t-1}, k_t} \tilde{U}_{k_t}^{[t]} \otimes |K_{t-1}, k_t\rangle^{C_t'} \langle K_{t-1}, k_t|^{C_t}, \quad (E1) $$

while between time-steps it applies the internal operations,

$$ \tilde{V}_1 = \sum_{k_1} \tilde{V}_{\emptyset, \emptyset}^{\to k_1} \otimes |\emptyset, k_1\rangle^{C_1} : \mathcal{H}^P \to \mathcal{H}_{\emptyset, \emptyset}^{A_1^I \alpha_1 C_1}, \quad (E2) $$

$$ \tilde{V}_{t+1} = \sum_{\substack{K_{t-1}, \\ k_t, k_{t+1}}} \tilde{V}_{K_{t-1}, k_t}^{\to k_{t+1}} \otimes |K_{t-1} \cup k_t, k_{t+1}\rangle^{C_{t+1}} \langle K_{t-1}, k_t|^{C_t'} : \mathcal{H}^{\tilde{A}_t^O \alpha_t C_t'} \to \mathcal{H}^{\tilde{A}_{t+1}^I \alpha_{t+1} C_{t+1}}, \quad (E3) $$

$$ \tilde{V}_{T+1} = \sum_{k_T} \tilde{V}_{T \setminus k_T, k_T}^{\to F} \otimes \langle T \setminus k_T, k_T|^{C_T'} : \mathcal{H}^{\tilde{A}_T^O \alpha_T C_T'} \to \mathcal{H}^{F \alpha_F}, \quad (E4) $$

which are required to be pure isometries.

The process matrix is obtained from the internal operations as

$$ W = \mathrm{Tr}_{\alpha_F} |w_{(\mathcal{T}, F)}\rangle\langle w_{(\mathcal{T}, F)}| \in \mathcal{L}(\mathcal{H}^{PA_T^{IO}F}), \quad (E5) $$

with $|w_{(\mathcal{T}, F)}\rangle = \sum_{(k_1, \dots, k_T)} |w_{(k_1, \dots, k_T, F)}\rangle$ and

$$ |w_{(k_1, \dots, k_T, F)}\rangle = |V_{\emptyset, \emptyset}^{\to k_1}\rangle * |V_{\emptyset, k_1}^{\to k_2}\rangle * |V_{\{k_1\}, k_2}^{\to k_3}\rangle * \dots * |V_{\{k_1, \dots, k_{T-2}\}, k_{T-1}}^{\to k_T}\rangle * |V_{\{k_1, \dots, k_{T-1}\}, k_T}^{\to F}\rangle \in \mathcal{H}^{PA_T^{IO}F \alpha_F}. \quad (E6) $$

Let us write the set of all process matrices of T-input QC-supermaps as $\mathcal{W}^{\mathrm{QC}}$.

One can readily verify that the action of a QC-supermap $\mathcal{S}$ on input operations $(U_1, \dots, U_T)$, as calculated through the process matrix, indeed coincides with that obtained by applying iteratively the internal operations $\tilde{V}_t$ and controlled operations $\tilde{U}^{[t]}$ in the generic input and output spaces. That is,

$$ \mathcal{S}(U_1, \dots, U_T) = (U_1 \otimes \dots \otimes U_T) * W \quad (E7) $$

$$ = \mathrm{Tr}_{\alpha_F} [\tilde{V}_{T+1} * \tilde{U}^{[T]} * \tilde{V}_T * \dots * \tilde{V}_2 * \tilde{U}^{[1]} * \tilde{V}_1]. \quad (E8) $$

As for the other classes of supermaps we presented, one can obtain a nice characterisation of $\mathcal{W}^{\mathrm{QC}}$ from the requirement for the internal operations (E2) to be trace-preserving isometries.

**Proposition 3** (From [17]). A matrix $W \in \mathcal{L}(\mathcal{H}^{PA_T^{IO}F})$ is the process matrix of a T-input QC-supermap (i.e, $W \in \mathcal{W}^{\mathrm{QC}}$) if and only if there exist some positive semidefinite matrices $W_{(K_{t-1}, k_t)} \in \mathcal{L}(\mathcal{H}^{PA_{K_{t-1}}^{IO} A_{k_t}^I})$, for all strict
subsets $K_{t-1}$ of $\mathcal{T}$ and all $k_t \in \mathcal{T} \setminus K_{t-1}$, satisfying

$$ \sum_{k_1 \in \mathcal{T}} \mathrm{Tr}_{A_{k_1}^I} W(\emptyset, k_1) = 1^P, \\ \forall \emptyset \subsetneq K_t \subsetneq \mathcal{T}, \quad \sum_{k_{t+1} \in \mathcal{T} \setminus K_t} \mathrm{Tr}_{A_{k_{t+1}}^I} W(\mathcal{K}_t, k_{t+1}) = \sum_{k_t \in \mathcal{K}_t} W(\mathcal{K}_t \setminus k_t, k_t) \otimes 1^{A_{k_t}^O}, \qquad (E9) \\ \text{and } \mathrm{Tr}_F W = \sum_{k_T \in \mathcal{T}} W(\mathcal{T} \setminus k_T, k_T) \otimes 1_{k_T}^O. $$

## Appendix F: Proof of Theorem 1

In this appendix, we give a proof of Theorem 1. This theorem states that for any $T$-input QC-supermap, one can define a $T$-input FO-supermap such that their action on $T$ copies of any unitary $U$ is the same.

**Theorem 1.** For any $T$-input QC-supermap $S^{\mathrm{QC}}$, there exists an FO-supermap $S^{\mathrm{FO}}$ such that $S^{\mathrm{QC}}$ and $S^{\mathrm{FO}}$ have the same action whenever applied to $T$ copies of the same unitary channel. That is, for all unitary channels $U$, $S^{\mathrm{QC}}(U, \dots, U) = S^{\mathrm{FO}}(U, \dots, U)$.

*Proof.* Let us consider a $T$-input QC-supermap $S^{\mathrm{QC}}$, as well as $T$ copies of some unitary $U$ labelled from 1 to $T$ as $(U^{(1)}, \dots, U^{(T)})$, with $U^{(t)}: \mathcal{H}^{A_t^I} \to \mathcal{H}^{A_t^O}$ (for $1 \le t \le T$) to distinguish which Hilbert spaces they act on. We emphasise that all the $\mathcal{H}^{A_t^I}$ and $\mathcal{H}^{A_t^O}$ are isomorphic, and the $U^{(t)}$ have formally the same action on their respective spaces. Following Eqs. (E2)–(E4), the QC-supermap $S^{\mathrm{QC}}$ can be represented as a generalised quantum circuit whose internal operations are defined on some generic input and output spaces $\mathcal{H}^{\tilde{A}_t^I}$ and $\mathcal{H}^{\tilde{A}_t^O}$ (which again are here all isomorphic to the $\mathcal{H}^{A_{k_t}^I}$ and $\mathcal{H}^{A_{k_t}^O}$) for each time-step $t$:

$$ \tilde{V}_1 = \sum_{k_1} \tilde{V}_{\emptyset, \emptyset}^{k_1} \otimes |\emptyset, k_1\rangle^C_1 : \mathcal{H}^P \to \mathcal{H}^{\tilde{A}_1^I \alpha_1 C_1}, \qquad (F1) $$

$$ \tilde{V}_{t+1} = \sum_{\substack{\mathcal{K}_{t-1}, \\ k_t, k_{t+1}}} \tilde{V}_{\mathcal{K}_{t-1}, k_t}^{k_{t+1}} \otimes |\mathcal{K}_{t-1} \cup k_t, k_{t+1}\rangle^C_{t+1} \langle \mathcal{K}_{t-1}, k_t|^C_t : \mathcal{H}^{\tilde{A}_t^O \alpha_t C'_t} \to \mathcal{H}^{\tilde{A}_{t+1}^I \alpha_{t+1} C_{t+1}}, \qquad (F2) $$

$$ \tilde{V}_{T+1} = \sum_{k_T} \tilde{V}_{T \setminus k_T, k_T}^F \otimes \langle T \setminus k_T, k_T |^{C'_T} : \mathcal{H}^{\tilde{A}_T^O \alpha_T C'_T} \to \mathcal{H}^{F \alpha_F}. \qquad (F3) $$

From these internal operations let us define an FO-supermap $S^{\mathrm{FO}}$, independent of $U$, whose action on $T$ copies of any unitary $U$ will be the same as that of the QC-supermap $S^{\mathrm{Gen}}$. Recall (see Appendix D) that, to define $S^{\mathrm{FO}}$, it suffices to specify the $T+1$ quantum channels (or, equivalently, their Choi matrices) $V_t$ (for $1 \le t \le T$) and $V_{T+1}$ which are applied in alternation with the input operations. To this end, let us consider the operations $V_{\emptyset, \emptyset}^{k_1}: \mathcal{H}^P \to \mathcal{H}^{A_1^I \alpha_1}$, $V_{\mathcal{K}_{t-1}, k_t}^{k_{t+1}}: \mathcal{H}^{A_t^O \alpha_t} \to \mathcal{H}^{A_{t+1}^I \alpha_{t+1}}$ and $V_{T \setminus k_T, k_T}^{F}: \mathcal{H}^{A_T^O \alpha_T} \to \mathcal{H}^F$ which have the same action as the corresponding operations in Eqs. (F1)–(F3) but act now on the non-tilded spaces $\mathcal{H}^{A_t^I} \cong \mathcal{H}^{\tilde{A}_t^I}$ and $\mathcal{H}^{A_t^O} \cong \mathcal{H}^{\tilde{A}_t^O}$ (for $1 \le t \le T$). Note that this is possible precisely because all the input and output spaces are isomorphic. By relabelling the control spaces $C'_t$ to $C_t$ (since, in a FO-supermap, the input operations are not controlled and there is thus no need to distinguish the control system before and after it is used), we hence define the isometries

$$ V'_1 = \sum_{k_1} V'_{\emptyset, \emptyset}^{k_1} \otimes |\emptyset, k_1\rangle^C_1 : \mathcal{H}^P \to \mathcal{H}^{A_1^I \alpha_1 C_1}, \qquad (F4) $$

$$ V'_{t+1} = \sum_{\substack{\mathcal{K}_{t-1}, \\ k_t, k_{t+1}}} V'_{\mathcal{K}_{t-1}, k_t}^{k_{t+1}} \otimes |\mathcal{K}_{t-1} \cup k_t, k_{t+1}\rangle^C_{t+1} \langle \mathcal{K}_{t-1}, k_t|^C_t : \mathcal{H}^{A_t^O \alpha_t C_t} \to \mathcal{H}^{A_{t+1}^I \alpha_{t+1} C_{t+1}}, \qquad (F5) $$

$$ \hat{V}'_{T+1} = \sum_{k_T} V'_{T \setminus k_T, k_T}^F \otimes \langle T \setminus k_T, k_T |^C_T : \mathcal{H}^{A_T^O \alpha_T C_T} \to \mathcal{H}^{F \alpha_F}. \qquad (F6) $$

For the FO-supermap we then reinterpret the control systems $\mathcal{H}^{C_t}$ as part of the ancillary spaces, taking $\mathcal{H}^{\alpha'_t} := \mathcal{H}^{\alpha_t C_t}$, so that the Choi matrices of the channels defining $S^{\mathrm{FO}}$ are $V'_t = |V'_t\rangle\langle V'_t|$ (for $1 \le t \le T$) and $V'_{T+1} =$
Tr$_{\alpha_F}$ |$\hat{V}'_{T+1}$|〉〈$\hat{V}'_{T+1}$| . The fact that these are indeed valid channels follows from the fact that Eqs. (F1)–(F3) specify valid isometries and the isomorphisms between the generic (tilded) and specific (non-tilded) input and output spaces. The action of S FO on T copies of U , according to Eq. (2), is

$$
S^{\text{FO}}(U^{(1)}, \dots, U^{(T)}) = V'_{T+1} * U^{(T)} * \dots * V'_2 * U^{(1)} * V'_1. \tag{F7}
$$

We now show that the action of the QC-supermap S QC on T -copies of U is equivalent to that of S FO given by Eq. (F7). Recall (see Appendix E) that, at each time-step t , S QC proceeds by applying the coherently controlled operations ˜ U [ t ] = ∑ K$_{t}$$_{−}$$_{1}$$_{,k}$$_{t}$ ˜ U [ t ] k$_{t}$ ⊗ | K$_{t}$$_{−}$$_{1}$, k$_{t}$ 〉 C ′ t 〈 K$_{t}$$_{−}$$_{1}$, k$_{t}$ | C$_{t}$ , where ˜ U [ t ] k$_{t}$ : H ˜ A I t → H ˜ A O t (for 1 ≤ k$_{t}$ ≤ T ) is an embedding of U ( k$_{t}$ ) into the generic spaces. Since each U ( k$_{t}$ ) has formally the same action, all the ˜ U [ t ] k$_{t}$ (for a given t ) are in fact identically the same operation; let us denote these unitary ˜ U ( t ) : H ˜ A I t → H ˜ A O t . The coherently controlled operations ˜ U [ t ] : H ˜ A I t C$_{t}$ → H ˜ A O t C ′ t can thus be written in the factorised form

$$
\tilde{U}^{[t]} = \tilde{U}^{(t)} \otimes \sum_{\mathcal{K}_{t-1}, k_t} |\mathcal{K}_{t-1}, k_t\rangle^{C'_t} \langle \mathcal{K}_{t-1}, k_t|^{C_t} \quad (\text{F8})
$$

$$
= \tilde{U}^{(t)} \otimes \mathbb{1}^{C_t \to C'_t}. \qquad (\text{F9})
$$

Then following Eq. (E8), the action of the QC-supermap on the T copies of U is

$$
\mathcal{S}^{\mathrm{QC}}(\mathcal{U}^{(1)}, \dots, \mathcal{U}^{(T)}) = \mathrm{Tr}_{\alpha_F} [\tilde{V}_{T+1} * \tilde{U}^{[T]} * \tilde{V}_2 * \tilde{U}^{[1]} * \tilde{V}_1] \quad (\mathrm{F10})
$$

$$
= \mathrm{Tr}_{\alpha_F} [\tilde{V}_{T+1} * (\tilde{U}^{(T)} * |1\rangle\langle1|^{[C_t \to C'_t)}) * \tilde{V}_2 * (\tilde{U}^{(1)} * |1\rangle\langle1|^{[C_1 \to C'_1)}) * \tilde{V}_1] \quad (\text{F11})
$$

$$
= \mathrm{Tr}_{\alpha_F} [\tilde{V}_{T+1} * |1\rangle\langle1|^{[C_t \to C'_t]} * \tilde{U}^{(T)} * \tilde{V}_T * \dots * \tilde{V}_2 * |1\rangle\langle1|^{[C_1 \to C'_1]} * \tilde{U}^{(1)} * \tilde{V}_1] \quad (\text{F12})
$$

$$
= \mathrm{Tr}_{\alpha_F} [\tilde{V}_{T+1} * |1\rangle\langle1|^{[C_t \to C'_t]} * \tilde{U}^{(T)} * \tilde{V}_T * \dots * \tilde{V}_2 * |1\rangle\langle1|^{[C_1 \to C'_1]} * \tilde{U}^{(1)} * \tilde{V}_1, \quad (\text{F13})
$$

where the second line follows from Eq. (F9), the third from the commutation of the link product, and the fourth from the fact that only ˜ V$_{T}$$_{+1}$ is defined on H α$_{F}$ . Now by defining ˜ V ′ T +1 = Tr$_{α}$$_{F}$ [ ˜ V$_{T}$$_{+1}$ ∗ | 1 〉〈 1 | C$_{t}$ → C ′ t ] , ˜ V ′ t +1 = ˜ V$_{t}$$_{+1}$ ∗ | 1 〉〈 1 | C$_{t}$ → C ′ t (for 1 ≤ t ≤ T − 1 ) and ˜ V ′ 1 = ˜ V$_{1}$ , we have

$$
\mathcal{S}^{\mathrm{QC}}(\mathcal{U}^{(1)}, \dots, \mathcal{U}^{(T)}) = \tilde{V}'_{T+1} * \tilde{U}^{(T)} * \dots * \tilde{V}'_2 * \tilde{U}^{(1)} * \tilde{V}'_1. \qquad (\mathrm{F14})
$$

For 1 < t ≤ T , the link product ˜ V$_{t}$$_{+1}$ ∗ | 1 〉〈 1 | C$_{t}$ → C ′ t is the composition of ˜ V$_{t}$$_{+1}$ : H ˜ A O t α$_{t}$C ′ t → H ˜ A I t $_{α$_{t}$$_{+1}$C$_{t}$$_{+1}$}$and an identity channel between H C$_{t}$ and H C ′ t , which effectively relabels H C ′ t to H C$_{t}$ in ˜ V$_{t}$$_{+1}$ . Finally, because the spaces H ˜ A I t and H ˜ A O t are isomorphic to H A I t and H A O t , we have that

$$
\mathcal{S}^{\mathrm{QC}}(\mathcal{U}^{(1)}, \dots, \mathcal{U}^{(T)}) = V'_{T+1} * \mathcal{U}^{(T)} * \dots * V'_2 * \mathcal{U}^{(1)} * V'_1 \quad (\mathrm{F15})
$$

$$
= S^{\text{FO}}(U^{(1)}, \dots, U^{(T)}), \qquad (\text{F16})
$$

as desired.

□

One way to understand more intuitively the FO-supermap S FO defined above from a S QC is to return to the expression (E5) writing the process matrix W QC of S QC as W QC = Tr$_{α}$$_{F}$ | w$_{(}$$_{T,F}$$_{)}$ 〉〈 w$_{(}$$_{T,F}$$_{)}$ | where | w$_{(}$$_{T,F}$$_{)}$ 〉 = ∑ ( k$_{1}$,...,k$_{T}$ ) | w$_{(}$$_{k}$$_{1}$$_{,...,k}$$_{T,F}$$_{)}$ 〉 with | w$_{(}$$_{k}$$_{1}$$_{,...,k}$$_{T,F}$$_{)}$ 〉 defined as in Eq. (E6). The process matrix W FO of S FO can be then seen to be given as W FO = Tr$_{α}$$_{F}$ | w ′ ( T,F ) 〉〈 w ′ ( T,F ) | where | w ′ ( T,F ) 〉 = ∑ ( k$_{1}$,...,k$_{T}$ ) | w ′ ( k$_{1}$,...,k$_{T,F}$ ) 〉 and where the vec- tors | w ′ ( k$_{1}$,...,k$_{T,F}$ ) 〉 are the same as | w$_{(}$$_{k}$$_{1}$$_{,...,k}$$_{T,F}$$_{)}$ 〉 but with each space H A I O kt now relabelled as H A I O t so that each | w ′ ( k$_{1}$,...,k$_{T,F}$ ) 〉 corresponds to the fixed order (1 , . . . , T ) instead of ( k$_{1}$, . . . , k$_{T}$ ).

Note that while the implementation of a QC-supermap is not unique (i.e., different choices of internal operations V −→ k$_{t}$$_{+1}$ K$_{t}$$_{−}$$_{1}$$_{,k}$$_{t}$ may give the same process matrix W QC ), the process matrix W FO obtained from the above mapping in general depends on the implementation one takes. Consider for example the QC-supermap with process matrix W = | w 〉〈 w | where

$$
|w\rangle = |\psi_1\rangle^{A_1^I} |\psi_2\rangle^{A_2^I} |1\rangle^{A_1^O F_1} |1\rangle^{A_2^O F_2}, \qquad (\text{F17})
$$

with F := F$_{1}$F$_{2}$ and implicit tensor products. This supermap is compatible with both possible fixed orders, (1 , 2) and (2 , 1) (i.e., it can be implemented in parallel). Two non-trivial implementations as QC-supermaps can be obtained
by taking $|\bar{V}_{\emptyset, \emptyset}^{\rightarrow 1}\rangle = |\psi_1\rangle^{A_1^I}$, $|\bar{V}_{\emptyset, 1}^{\rightarrow 2}\rangle = |1\rangle^{A_1^O \alpha}$ $|\psi_2\rangle^{A_2^I}$ and $|\bar{V}_{\{1\}, 2}^{\rightarrow F}\rangle = |1\rangle^{\alpha F_1}$ $|1\rangle^{A_2^O F_2}$ or $|\bar{V}_{\emptyset, \emptyset}^{\rightarrow 2}\rangle = |\psi_2\rangle^{A_2^I}$, $|\bar{V}_{\emptyset, 2}^{\rightarrow 1}\rangle = |1\rangle^{A_2^O \alpha}$ $|\psi_1\rangle^{A_1^I}$ and $|\bar{V}_{\{2\}, 1}^{\rightarrow F}\rangle = |1\rangle^{\alpha F_2}$ $|1\rangle^{A_1^O F_1}$, which gives

$$|\bar{w}\rangle = |w_{(1,2,F)}\rangle = |\bar{V}_{\emptyset, \emptyset}^{\rightarrow 1}\rangle * |\bar{V}_{\emptyset, 1}^{\rightarrow 2}\rangle * |\bar{V}_{\{1\}, 2}^{\rightarrow F}\rangle \quad (F18)$$

$$|\bar{w}\rangle = |w_{(2,1,F)}\rangle = |\bar{V}_{\emptyset, \emptyset}^{\rightarrow 2}\rangle * |\bar{V}_{\emptyset, 2}^{\rightarrow 1}\rangle * |\bar{V}_{\{2\}, 1}^{\rightarrow F}\rangle. \quad (F19)$$

One can immediately verify that $|w\rangle = |\bar{w}\rangle = |\bar{w}\rangle$, so that these implementations define the same supermap. However, applying the mapping used in the proof of Theorem 1 to these two implementations, one obtains two FO-supermaps defined by the process vectors

$$|\bar{w}'\rangle = |\psi_1\rangle^{A_1^I} |\psi_2\rangle^{A_2^I} |1\rangle^{A_1^O F_1} |1\rangle^{A_2^O F_2} \quad (F20)$$

$$|\bar{w}'\rangle = |\psi_2\rangle^{A_1^I} |\psi_1\rangle^{A_2^I} |1\rangle^{A_1^O F_2} |1\rangle^{A_2^O F_1}, \quad (F21)$$

which define two distinct supermaps that, nonetheless, indeed will always have the same action (as each other and the original QC-supermap $W^{QC}$) when applied to two copies of the same unitary channel.

## Appendix G: Proof of Theorem 2

In this appendix, we prove a generalisation of the polynomial bound from FO-supermaps (or quantum circuits) to general supermaps.

**Theorem 2.** For any Boolean function $f$, we have $\deg(f)/2 \le Q_E^{\text{Gen}}(f)$ and $\widetilde{\deg}(f)/2 \le Q_2^{\text{Gen}}(f)$.

The proof is similar to that of the original statement of the polynomial bound for FO-supermaps [28]. Let us first prove the following lemma.

**Lemma 4.** For $x \in \{0, 1\}^n$, $|O_x^{\otimes T}\rangle$ is a vector whose coefficients are multivariate polynomials in $x$ of degree at most $T$.

*Proof.* We proceed by induction. If $T = 1$ we have

$$|O_x\rangle = \sum_i |i\rangle \otimes O_x |i\rangle = \sum_i (-1)^{x_i} |i\rangle \otimes |i\rangle = \sum_i (1 - 2x_i) |i\rangle \otimes |i\rangle, \quad (G1)$$

which is indeed a multivariate polynomial of degree 1. Let us note that, for any $T \ge 1$, $|O_x^{\otimes T}\rangle$ is of the form $|O_x^{\otimes T}\rangle = \sum_z \alpha_z(x) |z\rangle \otimes |z\rangle$. Now let us suppose, for some $T$, that the coefficients $\alpha_z(x)$ are multivariate polynomials of degree at most $T$. Then

$$|O_x^{\otimes (T+1)}\rangle = |O_x^{\otimes T}\rangle \otimes |O_x\rangle \quad (G2)$$

$$= \sum_z \alpha_z(x) |z\rangle \otimes |z\rangle \otimes \sum_i (1 - 2x_i) |i\rangle \otimes |i\rangle \quad (G3)$$

$$= \sum_{z,i} (1 - 2x_i) \alpha_z(x) |z\rangle \otimes |z\rangle \otimes |i\rangle \otimes |i\rangle. \quad (G4)$$

But $(1 - 2x_i)\alpha_z(x)$ is then a multivariate polynomial of degree at most $T + 1$, which concludes the proof of the lemma. $\square$

The proof of the theorem is now straightforward. Let $f$ be a Boolean function on $n$ bits and $S$ a supermap with trivial input space and a qubit output space characterised by a process matrix $W$. Let us define, for $x \in \{0, 1\}^n$,

$$g(x) = \text{Tr}[(O_x^{\otimes T} * W) \cdot \Pi_1], \quad (G5)$$

where $\Pi_1 = |1\rangle\langle 1|$. The function $g$ corresponds to the probability of obtaining the outcome 1 when measuring the qubit $S(O_x^{(1)}, \dots, O_x^{(T)})$ in the computational basis (cf. Eq. (3)). Now, it follows from Lemma 4 that $O_x^{\otimes T} = |O_x^{\otimes T}\rangle\langle O_x^{\otimes T}|$ is a matrix whose coefficient are multivariate polynomials in $x$ of degree at most $2T$, and, since the trace and link product are linear, $g(x)$ is also a multivariate polynomial in $x$ of degree at most $2T$. If $S$ computes $f$ then $g(x) = f(x)$ for all $x$, so that $g$ represents $f$, and hence $2Q_E^{\text{Gen}}(f) \ge \deg(f)$. Similarly, in the bounded error case, if $S$ computes $f$ with bounded error $\varepsilon = 1/3$, then $|g(x) - f(x)| \le 1/3$ for all $x$ and $g$ approximates $f$ with bounded error $\varepsilon = 1/3$ also, from which we likewise obtain $2Q_2^{\text{Gen}}(f) \ge \widetilde{\deg}(f)$.
Appendix H: Dual form of the SDP

In this appendix, we derive the dual form of the primal SDP (10) computing the minimum error $\epsilon_T^C(f)$ with which $f$ can be computed by a $T$ query supermap in the class $\mathcal{C}$.

The dual SDP will be used in Appendix I to convert the numerical solutions of the SDP (10) into analytic proofs that $\epsilon_T^C(f)$ lies within a given interval. We obtain the dual form using the Lagrangian method and some techniques previously used in Ref. [35] for a slightly different SDP.

First, for any class $\mathcal{C} \in \{\text{FO, QC, Gen}\}$, by identifying $\mathcal{L}(H^{PA_T^{IO}F})$ with its dual space, one can define the dual affine space of $W^C \subseteq \mathcal{L}(H^{PA_T^{IO}F})$ as

$$ \overline{W}^C = \{ \overline{W} \in \mathcal{L}(H^{PA_T^{IO}F}) : \mathrm{Tr}[\overline{W} \cdot W] = 1 \ \forall W \in \mathcal{W}^C \}. \qquad (H1) $$

Note that the elements $\overline{W}$ of $\overline{W}^C$ are normalised such that $\mathrm{Tr} \overline{W} = d^I$, with $d^I = d^F \prod_{k=1}^T d_k^I$ (where $d^F = \dim(\mathcal{H}^F)$ and $d_k^I = \dim(\mathcal{H}_k^{A_k^I})$). For finite dimensional spaces (as is the case here), because $\mathcal{W}^C$ is an affine set we have $\overline{W}^C = \mathcal{W}^C$. Taking $\overline{W}_B^C = \{\overline{W}_k\}_k$ to be an affine basis of $\overline{W}^C$, we can thus write $\mathcal{W}^C$ as

$$ \mathcal{W}^C = \{ W \in \mathcal{L}(H^{PA_T^{IO}F}) : \mathrm{Tr}[W \cdot \overline{W}_k] = 1 \ \forall \overline{W}_k \in \overline{W}_B^C \}. \qquad (H2) $$

Using this characterisation of $\mathcal{W}^C$ and writing the primal (10) in a different but equivalent form (see [41], p. 264) one obtains the following canonical form of the primal SDP,

$$ \begin{array}{ll} \min_{\epsilon, W^{[0]}, W^{[1]}} & -(1 - \epsilon), \\ \text{s.t.} & \forall x \in F^{[0]}, \ 1 - \epsilon - \mathrm{Tr}[W^{[0]} \mathcal{O}_x^{\otimes T}] \le 0, \\ & \forall x \in F^{[1]}, \ 1 - \epsilon - \mathrm{Tr}[W^{[1]} \mathcal{O}_x^{\otimes T}] \le 0, \\ & -W^{[0]} \le 0, -W^{[1]} \le 0, -\epsilon \le 0, \\ & \mathrm{Tr}[(W^{[0]} + W^{[1]})\overline{W}_k] = 1, \forall \overline{W}_k \in \overline{W}_B^C. \end{array} \qquad (H3) $$

To write the Lagrangian of (H3) we introduce, for $i = 0, 1$ and for all $x \in F^{[i]}$, the scalar dual variables $\lambda_x^{[i]} \ge 0$, and for each basis element $\overline{W}_k \in \overline{W}_B^C$, the scalar dual variable $\mu_k$. We also introduce, as slack variables, the scalar $\delta \ge 0$ and two real matrices $\Gamma^{[i]} \ge 0$. Writing $\lambda := \{\lambda_x^{[i]}\}_{i=0,1; x \in F^{[i]}}$, $\Gamma := \{\Gamma^{[i]}\}_{i=0,1}$ and $\mu := \{\mu_k\}_k$, the Lagrangian is then a function of the primal, dual, and slack variables given as

$$ \begin{aligned} & \mathcal{L}(\epsilon, W^{[0]}, W^{[1]}, \delta, \lambda, \Gamma, \mu) \\ &= -(1 - \epsilon) - \delta\epsilon - \sum_{i=0}^{1} \mathrm{Tr}[W^{[i]}\Gamma^{[i]}] + \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]}(1 - \epsilon - \mathrm{Tr}[W^{[i]}\mathcal{O}_x^{\otimes T}]) + \sum_k \mu_k(\mathrm{Tr}[(W^{[0]} + W^{[1]})\overline{W}_k] - 1) \\ &= -1 + \epsilon(1 - \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]} - \delta) + \sum_{i=0}^{1} \mathrm{Tr}[W^{[i]}(-\Gamma^{[i]} - \sum_{x \in F^{[i]}} \lambda_x^{[i]}\mathcal{O}_x^{\otimes T} + \sum_k \mu_k \overline{W}_k)] + \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]} - \sum_k \mu_k. \end{aligned} \qquad (H4) $$

Because any optimal solution $(\epsilon^*, W^{[0]*}, W^{[1]*})$ of the primal SDP necessarily satisfies the constraints of (H3), for any positive $(\delta, \lambda, \Gamma)$ and any $\mu$, we have $\mathcal{L}(\epsilon^*, W^{[0]*}, W^{[1]*}, \delta, \lambda, \Gamma, \mu) \le -(1 - \epsilon^*)$. Therefore, by considering the function obtained when minimising over all possible values of $(\epsilon, W^{[0]}, W^{[1]})$ (even those not corresponding to feasible solutions of (H3)), one obtains a lower bound on the objective function $-(1 - \epsilon^*)$ as

$$ g(\delta, \lambda, \Gamma, \mu) = \min_{\epsilon, W^{[0]}, W^{[1]}} \mathcal{L}(\epsilon, W^{[0]}, W^{[1]}, \delta, \lambda, \Gamma, \mu) \le -(1 - \epsilon^*). \qquad (H5) $$

To obtain non-trivial lower bounds, i.e., finite values of $g$, certain conditions must be satisfied, as $g$ can be rewritten

$$ g(\delta, \lambda, \Gamma, \mu) = \begin{cases} \sum_i \sum_{x \in F^{[i]}} \lambda_x^{[i]} - 1 - \sum_k \mu_k & \text{if } \begin{cases} 1 - \sum_i \sum_{x \in F^{[i]}} \lambda_x^{[i]} - \delta = 0, \\ -\Gamma^{[i]} - \sum_{x \in F^{[i]}} \lambda_x^{[i]} \mathcal{O}_x^{\otimes T} + \sum_k \mu_k \overline{W}_k = 0, \end{cases} \text{ and} \\ -\infty & \text{otherwise.} \end{cases} \qquad (H6) $$
Then, the solution to the primal SDP $\epsilon_T^C(f)$ can be alternatively obtained by maximising this lower bound, which can be cast as the optimisation problem

$$
\begin{equation}
\begin{aligned}
& \max_{\delta, \lambda, \Gamma, \mu} && \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]} - 1 - \sum_{k} \mu_k, \\
& \text{s.t.} && \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]} + \delta = 1, \\
& && \Gamma^{[i]} + \sum_{x \in F^{[i]}} \lambda_x^{[i]} \mathcal{O}_x^{\otimes T} = \sum_{k} \mu_k \bar{W}_k, \quad i \in \{0, 1\}, \\
& && \lambda \ge 0, \quad \Gamma \ge 0, \quad \delta \ge 0,
\end{aligned}
\tag{H7}
\end{equation}
$$

where $\lambda \ge 0$ means that $\lambda_x^{[i]} \ge 0$ for all $i = 0, 1$ and $x \in F^{[i]}$, similarly for $\Gamma \ge 0$. This can be simplified through the removal of the slack variables $\Gamma$ and $\delta$ to obtain

$$
\begin{equation}
\begin{aligned}
& \min_{\lambda, \mu} && 1 + \sum_k \mu_k - \sum_{i=0}^1 \sum_{x \in F^{[i]}} \lambda_x^{[i]}, \\
& \text{s.t.} && \sum_{i=0}^1 \sum_{x \in F^{[i]}} \lambda_x^{[i]} \le 1, \\
& && \sum_{x \in F^{[i]}} \lambda_x^{[i]} \mathcal{O}_x^{\otimes T} \le \sum_k \mu_k \bar{W}_k, \quad i \in \{0, 1\}, \\
& && \lambda \ge 0.
\end{aligned}
\tag{H8}
\end{equation}
$$

This SDP can be further simplified by writing $\nu = \sum_k \mu_k$ and $\bar{W} = \frac{1}{\nu} \sum_k \mu_k \bar{W}_k$, where $\bar{W} \in \bar{W}^C$ since $\bar{W}_B^C = \{\bar{W}_k\}_k$ is an affine basis of this space.<fnref n="4" /> One then obtains

$$
\begin{equation}
\begin{aligned}
& \min_{\lambda, \nu, \bar{W}} && 1 + \nu - \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]}, \\
& \text{s.t.} && \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]} \le 1, \\
& && \sum_{x \in F^{[i]}} \lambda_x^{[i]} \mathcal{O}_x^{\otimes T} \le \nu \bar{W}, \quad i \in \{0, 1\}, \\
& && \lambda \ge 0 \\
& && \bar{W} \in \bar{W}^C.
\end{aligned}
\tag{H9}
\end{equation}
$$

The above optimisation problem is no longer an SDP due to the nonlinear term $\nu \bar{W}$. However, one can absorb $\nu$ into the unnormalised operator $\bar{W}_* = \nu \bar{W}$, which then satisfies $\frac{1}{dT} \text{Tr} \bar{W}_* = \nu$. Writing the cone generated by $\bar{W}^C$ as

<footnote n="4">⁴ One can easily check that $\nu \ge \sum_{x \in F^{[i]}} \lambda_x^{[i]} \ge 0$ by taking the trace of each side of the second constraint in (H8) and recalling that $\lambda \ge 0$. The case where $\nu = 0$ therefore corresponds to the trivial solution to the SDP. One can readily check that this</footnote>

<footnote>trivial solution is also a feasible solution to (H9) so that these two formulations of the problem are indeed equivalent.</footnote>
$\overline{W}_*^C = \{\nu \overline{W} : \nu \ge 0, \overline{W} \in \overline{W}^C\}$, one then obtains the SDP

$$
\begin{equation}
\begin{aligned}
& \min_{\lambda, \overline{W}_*} \quad 1 + \frac{1}{d^I} \operatorname{Tr} \overline{W}_* - \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]}, \\
& \text{s.t.} \quad \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]} \le 1, \\
& \phantom{\text{s.t.} \quad \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]}} \sum_{x \in F^{[i]}} \lambda_x^{[i]} \mathcal{O}_x^{\otimes T} \le \overline{W}_*, \quad i \in \{0, 1\}, \\
& \phantom{\text{s.t.} \quad \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]}} \lambda \ge 0, \\
& \phantom{\text{s.t.} \quad \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_x^{[i]}} \overline{W}_* \in \overline{W}_*,
\end{aligned}
\tag{H10}
\end{equation}
$$

which is the dual of (H3). This dual SDP minimises an objective function whose optimal value is $1 - \epsilon_T^C(f)$, and so for any solution of (H10) we have $\sum_{i=0}^1 \sum_{x \in F^{[i]}} \lambda_x^{[i]} - \frac{1}{d^I} \operatorname{Tr} \overline{W}_* \le \epsilon_T^C(f)$. That is, any feasible solution to (H10) provides a lower bound on $\epsilon_T^C(f)$, while any feasible solution to the primal SDP (10) (or, equivalently, (H3)) provides an upper bound on $\epsilon_T^C(f)$.

Finally, let us give a characterisation of $\overline{W}_*$ for $\mathcal{C} \in \{\text{FO, Gen}\}$. Recall that $\overline{W}_*$ is the cone generated by the dual affine space $\overline{W}^C$ defined in Eq. (H1), and which, since $\operatorname{Tr} \overline{W} = d^I$ for $\overline{W} \in \overline{W}^C$, can be rewritten as

$$ \overline{W}_*^C = \left\{ \overline{W}_* \in \mathcal{L}(H^{PA_T^{IO}F}) : \operatorname{Tr}[\overline{W}_* \cdot W] = \frac{\operatorname{Tr}\overline{W}_*}{d^I}, \forall W \in \mathcal{W}^C \right\}. \quad (H11) $$

Recalling also that any $W \in \mathcal{W}^C$ is normalised so that $\operatorname{Tr}[\frac{1}{d^O}W] = 1$, where $d^O = d^P \prod_{k=1}^T d_k^O$ (see Appendix C), we then obtain

$$ \overline{W}_*^C = \left\{ \overline{W}_* \in \mathcal{L}(H^{PA_T^{IO}F}) : \operatorname{Tr}\left[\left(\overline{W}_* - \frac{\operatorname{Tr}(\overline{W}_*)}{d^I d^O} 1\right) \cdot W\right] = 0, \forall W \in \mathcal{W}^C \right\}. \quad (H12) $$

This implies that $\overline{W}_* \in \overline{W}_*^C$ if and only if $\overline{W}_* - \frac{\operatorname{Tr}(\overline{W}_*)}{d^I d^O} 1$ is in the orthogonal complement of $\mathcal{W}^C$ within the space of Hermitian operators.

Since $W \in \mathcal{W}^C$ if and only if $W \in \mathcal{P} \cap \mathcal{L}^C$ and $\operatorname{Tr} W = d^O$, we have $(\mathcal{W}^C)^\perp = \mathcal{P}^\perp + (\mathcal{L}^C)^\perp = (\mathcal{L}^C)^\perp$. Therefore, taking $\Pi_{\mathcal{L}^C}$ to be the projector onto $\mathcal{L}^C$, the projector onto $\overline{W}_*$ is given by

$$ \Pi_{\overline{W}_*^C}(\overline{W}_*) = \overline{W}_* - \Pi_{\mathcal{L}^C} \left( \overline{W}_* - \frac{\operatorname{Tr}(\overline{W}_*)}{d^I d^O} 1 \right) \quad (H13) $$

$$ = \overline{W}_* - \Pi_{\mathcal{L}^C}(\overline{W}_*) + \frac{\operatorname{Tr}(\overline{W}_*)}{d^I d^O} 1, \quad (H14) $$

where the second line is obtained from the linearity of $\Pi_{\mathcal{L}^C}$ and because $1 \in \mathcal{L}^C$. We thus have the characterisation

$$ \overline{W}_*^C = \{ \overline{W}_* \in \mathcal{L}(H^{PA_T^{IO}F}) : \Pi_{\overline{W}_*^C}(\overline{W}_*) = \overline{W}_* \}. \quad (H15) $$

## Appendix I: Mathematical proofs from numerical results

In this appendix, we describe two algorithms to extract strictly feasible solutions to the primal SDP (10) and its dual (H10) from numerical solutions to these SDPs. This will allow us to extract analytical bounds on $\epsilon_T^C(f)$ and provide a rigorous mathematical proof of Theorem 3.

The nature of numerical SDP solvers means that the solutions they provide only satisfy the constraints of the SDP up to some numerical precision. Since, strictly speaking, the constraints are not satisfied, we cannot directly conclude anything about the precision of the numerical result of the optimisation problem. In Ref. [35], the authors propose an algorithm that takes a numerical (floating point), approximate solution of an SDP and returns an exact rational solution that is not specified with floating point numbers and rigorously satisfies the constraints of the SDP. While this
alternative solution is no longer guaranteed to be optimal, it gives an upper or lower bound (depending on whether one maximises or minimises the objective function). By applying this approach to both the primal and dual forms of an SDP, one can obtain both lower and upper bounds on the true optimal solutions; i.e., an interval within which that solution is certified to lie. Here we adapt the algorithm described in Ref. [35] to our specific problem.

We start with an algorithm to extract an exact solution from the dual SDP (H10) specified in Appendix H. For a Boolean function $f$, this will provide a lower bound on $\varepsilon_T^C(f)$, i.e., the minimal error with which one can compute $f$ using a fixed number $T$ of queries. A solution of the SDP (H10) consists of a tuple $(\lambda^{[0]}, \lambda^{[1]}, S)$, where for $i = 0, 1$, $\lambda^{[i]} = \{\lambda_x^{[i]}\}_{x \in F^{[i]}}$ and $S$ is a matrix in the cone $\overline{W}_*^C$ generated by the dual affine space $\overline{W}^C$ (see Appendix H and Ref. [35]). The output of the following algorithm will be a tuple $(\lambda_{\text{final}}^{[0]}, \lambda_{\text{final}}^{[1]}, S_{\text{final}})$ with $\lambda_{\text{final}}^{[i]} = \{\lambda_{x,\text{final}}^{[i]}\}_{x \in F^{[i]}}$, which rigorously satisfies the constraints of the SDP (H10). Note that the output of the algorithm depends on the precision to which one rationalises the variables, which is a freely chosen parameter of the algorithm.

**Algorithm 1**

1. Define each $\lambda_{x,\text{frac}}^{[i]}$ as a rationalisation of $\lambda_x^{[i]}$, stored in an exact representation and where any negative $\lambda_x^{[i]}$ are set to 0.

2. Define $\delta = 1 - \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_{x,\text{frac}}^{[i]}$ and let $\lambda_{x,\text{final}}^{[i]} = \begin{cases} \lambda_{x,\text{frac}}^{[i]} + \delta/N & \text{if } \delta < 0 \text{ and } \lambda_{x,\text{frac}}^{[i]} \ge -\delta/N, \\ \lambda_{x,\text{frac}}^{[i]} & \text{otherwise,} \end{cases}$ where $N \le 2^n$ is the maximal number of pairs $(i, x)$ such that $\lambda_{x,\text{frac}}^{[i]} \ge -\delta/N$.

3. Define $S_{\text{frac}}$ as a rationalisation of $S$, stored in an exact representation.

4. Define $S_{\text{Herm}} = \frac{1}{2}(S_{\text{frac}} + S_{\text{frac}}^{\dagger})$.

5. Define $S_{\text{valid}} = \Pi_{\overline{W}_*^C}(S_{\text{Herm}})$, where $\Pi_{\overline{W}_*^C}$ is the projection onto $\overline{W}_*^C$.

6. Find the smallest $\mu$ such that $S_{\text{pos}} = D_{\mu}(S_{\text{valid}})$ is positive semidefinite, where $D_{\mu}(S) = (1 - \mu)S + \mu I$.

7. For $i = 0, 1$, find the smallest non-negative $\eta_i$'s such that $F_{\eta_i}(S_{\text{valid}})$ is positive semidefinite, where $F_{\eta_i}(S) = S + (\eta_i - 1)O^{[i]}$ with $O^{[i]} = \sum_{x \in F^{[i]}} \lambda_{x,\text{final}}^{[i]} O_x^{\otimes T}$, and define $S_{\text{final}} = S + \eta_0 O^{[0]} + \eta_1 O^{[1]}$.

The first and second steps of the algorithm ensure that the final lambdas $\lambda_{x,\text{final}}^{[i]}$ are rational (stored, for example, as fractions that can be manipulated exactly), non-negative, and satisfy the constraints $\sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_{x,\text{final}}^{[i]} \le 1$. Steps 3 to 5 ensure that the matrix $S_{\text{final}}$ is rational, Hermitian and belongs to $\overline{W}_*^C$. Finally, Steps 6 and 7 ensure that, for $i \in \{0, 1\}$, $S_{\text{final}} - O^{[i]}$ is positive semidefinite. Note that Step 6 is needed to ensure that such $\eta_i$ exist in Step 7, and that the minimisation in Step 7 typically needs to be performed numerically and thus approximately. This is not an issue, as one simply needs to find the smallest $\eta_i$ up to some desired precision that make the respective matrices $F_{\eta_i}(S)$ strictly positive semidefinite. Note as well that after Step 7, the matrix $S_{\text{final}}$ remains in $\overline{W}_*^C$, which follows from the linearity of $\Pi_{\overline{W}_*^C}$ and because, for any class $C \in \{\text{FO, Gen}\}$, the $O^{[i]}$'s are elements of $\overline{W}_*^C$ [35]. The output of the algorithm $S_{\text{final}}$ is hence guaranteed to satisfy all the constraints of the dual SDP (H10). Furthermore, as stated in Appendix H, the dual SDP (H10) minimises an objective function whose optimal is $1 - \varepsilon_T^C(f)$, meaning that the output of Algorithm (1) will provide a lower bound on $\varepsilon_T^C(f)$, i.e.,

$$ \sum_{i=0}^{1} \sum_{x \in F^{[i]}} \lambda_{x,\text{final}}^{[i]} - \frac{1}{d^I} \text{Tr}[S_{\text{final}}] \le \varepsilon_T^C(f). \quad (I1) $$

The corresponding upper bound is obtained from a similar algorithm whose input is a solution of the primal SDP (10), which is a superinstrument of two elements $\{W^{[i]}\}_{i=0,1}$ such that $W^{[0]} + W^{[1]} \in W^C$. Then, the output of the following algorithm will be a superinstrument $\{W_{\text{final}}^{[i]}\}_{i=0,1}$ that rigorously satisfies all the constraints of the primal SDP (10).
Algorithm 2

1. Define $W_{\text{frac}}^{[0]}$ and $W_{\text{frac}}^{[1]}$ as rationalisations of $W^{[0]}$ and $W^{[1]}$, stored in an exact representation.

2. For $i = 0, 1$, define $W_{\text{Herm}}^{[i]} = \frac{1}{2}(W_{\text{frac}}^{[i]} + W_{\text{frac}}^{[i]\dagger})$.

3. Define $W_{\text{proj}} = \Pi_{\mathcal{L}C}(W_{\text{Herm}}^{[0]} + W_{\text{Herm}}^{[1]})$, where $\Pi_{\mathcal{L}C}$ is the projection onto $\mathcal{L}^C$.

4. Define $W_{\text{corr}} = W_{\text{proj}} - W_{\text{Herm}}^{[0]} - W_{\text{Herm}}^{[1]}$.

5. Define for $i = 0, 1$, $W_{\text{valid}}^{[i]} = W_{\text{Herm}}^{[i]} + \frac{1}{2}W_{\text{corr}}$.

6. Find the smallest $\mu$ such that for $i = 0, 1$, $W_{\text{pos}}^{[i]} = D_{\mu}(W_{\text{valid}}^{[i]})$ is positive semidefinite, where $D_{\mu}(W) = (1 - \mu)W + \mu 1$.

7. Re-normalise, for $i = 0, 1$, $W_{\text{final}}^{[i]} = \frac{d^P \prod_{k=1}^{T} d_k^O}{\text{Tr}[W_{\text{pos}}^{[0]} + W_{\text{pos}}^{[1]}]} W_{\text{pos}}^{[i]}$.

The first and second steps of the algorithm make sure that the superinstrument elements $W_{\text{final}}^{[i]}$ are rational and Hermitian. Steps 3 to 5 ensure that their sum lies in the subspace $\mathcal{L}^C$. Step 6 ensures that they are positive semidefinite, while Step 7 ensures that they are properly normalised. The output of the algorithm $\{W_{\text{final}}^{[i]}\}_{i \in \{0,1\}}$ is then a superinstrument that satisfies all the constraints of the primal SDP (10). Because this SDP is a maximisation of the objective function $1 - \varepsilon$ with optimal value $1 - \varepsilon_T^C(f)$, the output of Algorithm (2) provides an upper bound on $\varepsilon_T^C(f)$, i.e.,

$$ \varepsilon_T^C(f) \leq \min_{i \in \{0,1\}} \min_{x \in F^{[i]}} \text{Tr} \left[ W_{\text{final}}^{[i]} \mathcal{O}_x^{\otimes T} \right]. \qquad (12) $$

Appendix J: Numerical results

In Table I we summarise the numerical results obtained by solving the semidefinite program (10) for $n = 4$ and $T = 2$. The ID of a function $f$ corresponds to the integer obtained from its binary truth table, $\varepsilon_2^{\text{FO}}(f)$ is the numerical value corresponding to the minimum probability of error for which it can be computed using two queries with FO-supermaps and $\varepsilon_2^{\text{Gen}}(f)$ with general supermaps. Table I lists the 222 NPN representatives of Boolean functions on 4 input bits (note that it also contains functions that are constants or whose output depends on less than 4 input bits). For $\varepsilon_2^{\text{FO}}(f)$, our results coincide with those obtained in Ref. [32], but we observe that for 179 representatives, $\varepsilon_2^{\text{Gen}}(f) < \varepsilon_2^{\text{FO}}(f)$, with a gap of 0.00947 (close to 1%) for functions of Id: 5783, 5865 and 6630. To solve the SDPs we use the Matlab toolbox Yalmip [42] with the solver SCS [43]; our code is freely accessible on Github.<fnref n="5" />

<footnote n="5">⁵ https://github.com/pierrepocreau/QuantumQueryComplexity_ICO</footnote>
<table><caption>TABLE I. Numerical results for 2 queries and all Boolean functions of 4 input bits.</caption><thead><tr><th>ID</th><th>ε<sub>2</sub><sup>FO</sup></th><th>ε<sub>2</sub><sup>Gen</sup></th><th>Gap</th></tr></thead><tbody><tr><td>0</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>1</td><td>0.03846</td><td>0.03846</td><td>0.00000</td></tr><tr><td>3</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>6</td><td>0.06897</td><td>0.06897</td><td>0.00000</td></tr><tr><td>7</td><td>0.04620</td><td>0.04620</td><td>0.00000</td></tr><tr><td>15</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>22</td><td>0.09380</td><td>0.09380</td><td>0.00000</td></tr><tr><td>23</td><td>0.07409</td><td>0.07409</td><td>0.00000</td></tr><tr><td>24</td><td>0.06897</td><td>0.06897</td><td>0.00000</td></tr><tr><td>25</td><td>0.03957</td><td>0.03957</td><td>0.00000</td></tr><tr><td>27</td><td>0.03475</td><td>0.03475</td><td>0.00000</td></tr><tr><td>30</td><td>0.04411</td><td>0.04411</td><td>0.00000</td></tr><tr><td>31</td><td>0.03043</td><td>0.02964</td><td>0.00080</td></tr><tr><td>60</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>61</td><td>0.02383</td><td>0.02000</td><td>0.00383</td></tr><tr><td>63</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>105</td><td>0.10000</td><td>0.10000</td><td>0.00000</td></tr><tr><td>107</td><td>0.05936</td><td>0.05919</td><td>0.00016</td></tr><tr><td>111</td><td>0.03254</td><td>0.02853</td><td>0.00400</td></tr><tr><td>126</td><td>0.05263</td><td>0.05263</td><td>0.00000</td></tr><tr><td>127</td><td>0.02858</td><td>0.02858</td><td>0.00000</td></tr><tr><td>255</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>278</td><td>0.11611</td><td>0.11611</td><td>0.00000</td></tr><tr><td>279</td><td>0.10061</td><td>0.10061</td><td>0.00000</td></tr><tr><td>280</td><td>0.09380</td><td>0.09380</td><td>0.00000</td></tr><tr><td>281</td><td>0.04411</td><td>0.04411</td><td>0.00000</td></tr><tr><td>282</td><td>0.06387</td><td>0.06387</td><td>0.00000</td></tr><tr><td>283</td><td>0.04136</td><td>0.04126</td><td>0.00010</td></tr><tr><td>286</td><td>0.06842</td><td>0.06842</td><td>0.00000</td></tr><tr><td>287</td><td>0.05475</td><td>0.05475</td><td>0.00000</td></tr><tr><td>300</td><td>0.06387</td><td>0.06387</td><td>0.00000</td></tr><tr><td>301</td><td>0.03637</td><td>0.03595</td><td>0.00041</td></tr><tr><td>303</td><td>0.03436</td><td>0.02900</td><td>0.00536</td></tr><tr><td>316</td><td>0.03846</td><td>0.03846</td><td>0.00000</td></tr><tr><td>317</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>318</td><td>0.04408</td><td>0.04051</td><td>0.00357</td></tr><tr><td>319</td><td>0.02807</td><td>0.02529</td><td>0.00279</td></tr><tr><td>360</td><td>0.11611</td><td>0.11611</td><td>0.00000</td></tr><tr><td>361</td><td>0.08382</td><td>0.08382</td><td>0.00000</td></tr><tr><td>362</td><td>0.06842</td><td>0.06842</td><td>0.00000</td></tr><tr><td>363</td><td>0.04510</td><td>0.04483</td><td>0.00027</td></tr><tr><td>366</td><td>0.04408</td><td>0.04051</td><td>0.00357</td></tr><tr><td>367</td><td>0.03147</td><td>0.02782</td><td>0.00364</td></tr><tr><td>382</td><td>0.07739</td><td>0.07739</td><td>0.00000</td></tr><tr><td>383</td><td>0.05410</td><td>0.05410</td><td>0.00000</td></tr><tr><td>384</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>385</td><td>0.04620</td><td>0.04620</td><td>0.00000</td></tr><tr><td>386</td><td>0.03957</td><td>0.03957</td><td>0.00000</td></tr><tr><td>387</td><td>0.03475</td><td>0.03475</td><td>0.00000</td></tr><tr><td>390</td><td>0.06387</td><td>0.06387</td><td>0.00000</td></tr><tr><td>391</td><td>0.04136</td><td>0.04126</td><td>0.00010</td></tr><tr><td>393</td><td>0.03475</td><td>0.03475</td><td>0.00000</td></tr><tr><td>395</td><td>0.03679</td><td>0.03679</td><td>0.00000</td></tr><tr><td>399</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>406</td><td>0.08382</td><td>0.08382</td><td>0.00000</td></tr><tr><td>407</td><td>0.05985</td><td>0.05834</td><td>0.00151</td></tr><tr><td>408</td><td>0.04411</td><td>0.04411</td><td>0.00000</td></tr><tr><td>...</td><td>...</td><td>...</td><td>...</td></tr></tbody></table><table><thead><tr><th>ID</th><th>ε<sub>2</sub><sup>FO</sup></th><th>ε<sub>2</sub><sup>Gen</sup></th><th>Gap</th></tr></thead><tbody><tr><td>...</td><td>...</td><td>...</td><td>...</td></tr><tr><td>409</td><td>0.02383</td><td>0.02000</td><td>0.00383</td></tr><tr><td>410</td><td>0.03637</td><td>0.03595</td><td>0.00041</td></tr><tr><td>411</td><td>0.03079</td><td>0.03061</td><td>0.00018</td></tr><tr><td>414</td><td>0.04510</td><td>0.04483</td><td>0.00027</td></tr><tr><td>415</td><td>0.03527</td><td>0.03294</td><td>0.00233</td></tr><tr><td>424</td><td>0.07409</td><td>0.07409</td><td>0.00000</td></tr><tr><td>425</td><td>0.04136</td><td>0.04126</td><td>0.00010</td></tr><tr><td>426</td><td>0.03043</td><td>0.02964</td><td>0.00080</td></tr><tr><td>427</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>428</td><td>0.04136</td><td>0.04126</td><td>0.00010</td></tr><tr><td>429</td><td>0.03079</td><td>0.03061</td><td>0.00018</td></tr><tr><td>430</td><td>0.03436</td><td>0.02900</td><td>0.00536</td></tr><tr><td>431</td><td>0.02351</td><td>0.02304</td><td>0.00047</td></tr><tr><td>444</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>445</td><td>0.03499</td><td>0.03066</td><td>0.00433</td></tr><tr><td>446</td><td>0.03147</td><td>0.02782</td><td>0.00364</td></tr><tr><td>447</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>488</td><td>0.10061</td><td>0.10061</td><td>0.00000</td></tr><tr><td>489</td><td>0.05985</td><td>0.05834</td><td>0.00151</td></tr><tr><td>490</td><td>0.05475</td><td>0.05475</td><td>0.00000</td></tr><tr><td>491</td><td>0.03527</td><td>0.03294</td><td>0.00233</td></tr><tr><td>494</td><td>0.02807</td><td>0.02529</td><td>0.00279</td></tr><tr><td>495</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>510</td><td>0.05410</td><td>0.05410</td><td>0.00000</td></tr><tr><td>828</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>829</td><td>0.02521</td><td>0.02268</td><td>0.00253</td></tr><tr><td>831</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>854</td><td>0.04508</td><td>0.04399</td><td>0.00110</td></tr><tr><td>855</td><td>0.03109</td><td>0.02707</td><td>0.00402</td></tr><tr><td>856</td><td>0.03637</td><td>0.03595</td><td>0.00041</td></tr><tr><td>857</td><td>0.03880</td><td>0.03880</td><td>0.00000</td></tr><tr><td>858</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>859</td><td>0.02652</td><td>0.02587</td><td>0.00065</td></tr><tr><td>862</td><td>0.03430</td><td>0.03065</td><td>0.00366</td></tr><tr><td>863</td><td>0.01396</td><td>0.01122</td><td>0.00274</td></tr><tr><td>872</td><td>0.06842</td><td>0.06842</td><td>0.00000</td></tr><tr><td>873</td><td>0.05375</td><td>0.05059</td><td>0.00316</td></tr><tr><td>874</td><td>0.04508</td><td>0.04399</td><td>0.00110</td></tr><tr><td>875</td><td>0.04884</td><td>0.04358</td><td>0.00526</td></tr><tr><td>876</td><td>0.04408</td><td>0.04051</td><td>0.00357</td></tr><tr><td>877</td><td>0.03870</td><td>0.03674</td><td>0.00196</td></tr><tr><td>878</td><td>0.03430</td><td>0.03065</td><td>0.00366</td></tr><tr><td>879</td><td>0.03434</td><td>0.03279</td><td>0.00155</td></tr><tr><td>892</td><td>0.02521</td><td>0.02268</td><td>0.00253</td></tr><tr><td>893</td><td>0.03399</td><td>0.03175</td><td>0.00224</td></tr><tr><td>894</td><td>0.05258</td><td>0.05063</td><td>0.00194</td></tr><tr><td>960</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>961</td><td>0.03043</td><td>0.02964</td><td>0.00080</td></tr><tr><td>963</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>965</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>966</td><td>0.03436</td><td>0.02900</td><td>0.00536</td></tr><tr><td>967</td><td>0.02351</td><td>0.02304</td><td>0.00047</td></tr><tr><td>975</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>980</td><td>0.05475</td><td>0.05475</td><td>0.00000</td></tr><tr><td>981</td><td>0.03109</td><td>0.02707</td><td>0.00402</td></tr><tr><td>...</td><td>...</td><td>...</td><td>...</td></tr></tbody></table><table><thead><tr><th>ID</th><th>ε<sub>2</sub><sup>FO</sup></th><th>ε<sub>2</sub><sup>Gen</sup></th><th>Gap</th></tr></thead><tbody><tr><td>...</td><td>...</td><td>...</td><td>...</td></tr><tr><td>982</td><td>0.04884</td><td>0.04358</td><td>0.00526</td></tr><tr><td>983</td><td>0.03499</td><td>0.02990</td><td>0.00510</td></tr><tr><td>984</td><td>0.03436</td><td>0.02900</td><td>0.00536</td></tr><tr><td>985</td><td>0.02652</td><td>0.02587</td><td>0.00065</td></tr><tr><td>985</td><td>0.02652</td><td>0.02587</td><td>0.00065</td></tr><tr><td>987</td><td>0.03499</td><td>0.02990</td><td>0.00510</td></tr><tr><td>988</td><td>0.02807</td><td>0.02529</td><td>0.00279</td></tr><tr><td>989</td><td>0.01396</td><td>0.01122</td><td>0.00274</td></tr><tr><td>990</td><td>0.03434</td><td>0.03279</td><td>0.00155</td></tr><tr><td>1020</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>1632</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>1633</td><td>0.03846</td><td>0.03846</td><td>0.00000</td></tr><tr><td>1634</td><td>0.02383</td><td>0.02000</td><td>0.00383</td></tr><tr><td>1635</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>1638</td><td>0.05263</td><td>0.05263</td><td>0.00000</td></tr><tr><td>1639</td><td>0.03499</td><td>0.03066</td><td>0.00433</td></tr><tr><td>1641</td><td>0.06387</td><td>0.06387</td><td>0.00000</td></tr><tr><td>1643</td><td>0.03449</td><td>0.03288</td><td>0.00162</td></tr><tr><td>1647</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>1650</td><td>0.03079</td><td>0.03061</td><td>0.00018</td></tr><tr><td>1651</td><td>0.02652</td><td>0.02587</td><td>0.00065</td></tr><tr><td>1654</td><td>0.03499</td><td>0.03066</td><td>0.00433</td></tr><tr><td>1656</td><td>0.04408</td><td>0.04051</td><td>0.00357</td></tr><tr><td>1657</td><td>0.03568</td><td>0.02975</td><td>0.00593</td></tr><tr><td>1658</td><td>0.03430</td><td>0.03065</td><td>0.00366</td></tr><tr><td>1659</td><td>0.03836</td><td>0.03714</td><td>0.00122</td></tr><tr><td>1662</td><td>0.04641</td><td>0.04247</td><td>0.00394</td></tr><tr><td>1680</td><td>0.10000</td><td>0.10000</td><td>0.00000</td></tr><tr><td>1681</td><td>0.08382</td><td>0.08382</td><td>0.00000</td></tr><tr><td>1683</td><td>0.05375</td><td>0.05059</td><td>0.00316</td></tr><tr><td>1686</td><td>0.06387</td><td>0.06387</td><td>0.00000</td></tr><tr><td>1687</td><td>0.03568</td><td>0.02975</td><td>0.00593</td></tr><tr><td>1695</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>1712</td><td>0.05936</td><td>0.05919</td><td>0.00016</td></tr><tr><td>1713</td><td>0.04510</td><td>0.04483</td><td>0.00027</td></tr><tr><td>1714</td><td>0.05985</td><td>0.05834</td><td>0.00151</td></tr><tr><td>1715</td><td>0.04884</td><td>0.04358</td><td>0.00526</td></tr><tr><td>1716</td><td>0.04510</td><td>0.04483</td><td>0.00027</td></tr><tr><td>1717</td><td>0.03870</td><td>0.03674</td><td>0.00196</td></tr><tr><td>1718</td><td>0.03449</td><td>0.03288</td><td>0.00162</td></tr><tr><td>1719</td><td>0.03836</td><td>0.03714</td><td>0.00122</td></tr><tr><td>1721</td><td>0.03568</td><td>0.02975</td><td>0.00593</td></tr><tr><td>1725</td><td>0.04491</td><td>0.04053</td><td>0.00438</td></tr><tr><td>1776</td><td>0.03254</td><td>0.02853</td><td>0.00400</td></tr><tr><td>1777</td><td>0.03147</td><td>0.02782</td><td>0.00364</td></tr><tr><td>1778</td><td>0.03527</td><td>0.03294</td><td>0.00233</td></tr><tr><td>1782</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>1785</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>1910</td><td>0.04641</td><td>0.04247</td><td>0.00394</td></tr><tr><td>1912</td><td>0.07739</td><td>0.07739</td><td>0.00000</td></tr><tr><td>1913</td><td>0.04491</td><td>0.04053</td><td>0.00438</td></tr><tr><td>1914</td><td>0.05258</td><td>0.05063</td><td>0.00194</td></tr><tr><td>1918</td><td>0.07790</td><td>0.07790</td><td>0.00000</td></tr><tr><td>1968</td><td>0.03254</td><td>0.02853</td><td>0.00400</td></tr><tr><td>1969</td><td>0.03527</td><td>0.03294</td><td>0.00233</td></tr><tr><td>...</td><td>...</td><td>...</td><td>...</td></tr></tbody></table><table><thead><tr><th>ID</th><th>ε<sub>2</sub><sup>FO</sup></th><th>ε<sub>2</sub><sup>Gen</sup></th><th>Gap</th></tr></thead><tbody><tr><td>...</td><td>...</td><td>...</td><td>...</td></tr><tr><td>1972</td><td>0.03147</td><td>0.02782</td><td>0.00364</td></tr><tr><td>1973</td><td>0.03434</td><td>0.03279</td><td>0.00155</td></tr><tr><td>1974</td><td>0.03836</td><td>0.03714</td><td>0.00122</td></tr><tr><td>1980</td><td>0.03399</td><td>0.03175</td><td>0.00224</td></tr><tr><td>2016</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>2017</td><td>0.02807</td><td>0.02529</td><td>0.00279</td></tr><tr><td>2018</td><td>0.02351</td><td>0.02304</td><td>0.00047</td></tr><tr><td>2019</td><td>0.01396</td><td>0.01122</td><td>0.00274</td></tr><tr><td>2022</td><td>0.03499</td><td>0.02990</td><td>0.00510</td></tr><tr><td>2025</td><td>0.03399</td><td>0.03175</td><td>0.00224</td></tr><tr><td>2032</td><td>0.02858</td><td>0.02858</td><td>0.00000</td></tr><tr><td>2033</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>2034</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>2040</td><td>0.05410</td><td>0.05410</td><td>0.00000</td></tr><tr><td>4080</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>5736</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>5737</td><td>0.03846</td><td>0.03846</td><td>0.00000</td></tr><tr><td>5738</td><td>0.02521</td><td>0.02268</td><td>0.00253</td></tr><tr><td>5739</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>5742</td><td>0.05258</td><td>0.05063</td><td>0.00194</td></tr><tr><td>5758</td><td>0.07790</td><td>0.07790</td><td>0.00000</td></tr><tr><td>5761</td><td>0.14045</td><td>0.14045</td><td>0.00000</td></tr><tr><td>5763</td><td>0.09363</td><td>0.09363</td><td>0.00000</td></tr><tr><td>5766</td><td>0.06387</td><td>0.06387</td><td>0.00000</td></tr><tr><td>5767</td><td>0.06735</td><td>0.06296</td><td>0.00440</td></tr><tr><td>5769</td><td>0.09363</td><td>0.09363</td><td>0.00000</td></tr><tr><td>5771</td><td>0.05363</td><td>0.05341</td><td>0.00022</td></tr><tr><td>5774</td><td>0.03449</td><td>0.03288</td><td>0.00162</td></tr><tr><td>5782</td><td>0.03846</td><td>0.03846</td><td>0.00000</td></tr><tr><td>5783</td><td>0.04647</td><td>0.03700</td><td>0.00947</td></tr><tr><td>5784</td><td>0.05375</td><td>0.05059</td><td>0.00316</td></tr><tr><td>5785</td><td>0.06735</td><td>0.06296</td><td>0.00440</td></tr><tr><td>5786</td><td>0.03568</td><td>0.02975</td><td>0.00593</td></tr><tr><td>5787</td><td>0.04518</td><td>0.04286</td><td>0.00232</td></tr><tr><td>5790</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>5801</td><td>0.06735</td><td>0.06296</td><td>0.00440</td></tr><tr><td>5804</td><td>0.03870</td><td>0.03674</td><td>0.00196</td></tr><tr><td>5805</td><td>0.04518</td><td>0.04286</td><td>0.00232</td></tr><tr><td>5820</td><td>0.04491</td><td>0.04053</td><td>0.00438</td></tr><tr><td>5865</td><td>0.04647</td><td>0.03700</td><td>0.00947</td></tr><tr><td>6014</td><td>0.12571</td><td>0.12571</td><td>0.00000</td></tr><tr><td>6030</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>6038</td><td>0.02000</td><td>0.02000</td><td>0.00000</td></tr><tr><td>6040</td><td>0.04884</td><td>0.04358</td><td>0.00526</td></tr><tr><td>6042</td><td>0.03836</td><td>0.03714</td><td>0.00122</td></tr><tr><td>6060</td><td>0.03434</td><td>0.03279</td><td>0.00155</td></tr><tr><td>6120</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>6375</td><td>0.10000</td><td>0.10000</td><td>0.00000</td></tr><tr><td>6625</td><td>0.05363</td><td>0.05341</td><td>0.00022</td></tr><tr><td>6627</td><td>0.04518</td><td>0.04286</td><td>0.00232</td></tr><tr><td>6630</td><td>0.04647</td><td>0.03700</td><td>0.00947</td></tr><tr><td>7128</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>7140</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>7905</td><td>0.10000</td><td>0.10000</td><td>0.00000</td></tr><tr><td>15555</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr><tr><td>27030</td><td>0.00000</td><td>0.00000</td><td>0.00000</td></tr></tbody></table>