# 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. Physical Review Research, 2024, 6 (3), pp.L032020. 10.1103/Phys-RevResearch.6.L032020. hal-04672768

HAL Id: hal-04672768

https://inria.hal.science/hal-04672768v1

Submitted on 19 Aug 2024

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

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

(Received 26 October 2023; revised 13 February 2024; accepted 1 July 2024; published 26 July 2024)

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 generalize 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.

DOI: 10.1103/PhysRevResearch.6.L032020

*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 nontrivial 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 studies 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 generalization 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} \qquad (1)$$

<footnote>Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.</footnote>
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 dimension. By extending the oracle on the ancillary 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}_xU_T \cdots U_1\tilde{O}_xU_1|0\cdots 0\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 function, 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 generalization of the notion of quantum query complexity to study the relative power of causal indefiniteness. Let us first introduce 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 $\mathcal{H}^X$ as $\mathcal{L}(\mathcal{H}^X)$. To define quantum supermaps we first introduce quantum channels, which are completely positive (CP) trace-preserving (TP) maps $\mathcal{M} : \mathcal{L}(\mathcal{H}^X) \to \mathcal{L}(\mathcal{H}^Y)$. A channel is conveniently represented as a positive semidefinite matrix $\mathcal{M}^{XY} \in \mathcal{L}(\mathcal{H}^{XY})$ using the Choi isomorphism [21,22], where we adopt the shorthand $\mathcal{H}^{XY} = \mathcal{H}^X \otimes \mathcal{H}^Y$. The composition of two CP maps, potentially over a subset of their input/output systems, can be computed directly via their Choi matrices using the “link product” [6,23], denoted “*” and 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)^{\text{T}_Y}(1^X \otimes \mathcal{N}^{YZ})] \in \mathcal{L}(\mathcal{H}^{XZ})$, where $\text{Tr}_Y$ is the partial trace over the subsystem $\mathcal{H}^Y$ and $^{\text{T}_Y}$ the partial transpose over $\mathcal{H}^Y$. The link product is commutative and associative and reduces to the tensor product on maps acting on disjoint Hilbert spaces (see the Supplemental Material, SM [24]).

A $T$-input quantum supermap $S$ is then a $T$-linear, completely CP-preserving, and TP-preserving map [25]. That is, a supermap is the most general transformation that transforms any $T$ input channels $M_t : \mathcal{L}(\mathcal{H}^{A_t^I}) \to \mathcal{L}(\mathcal{H}^{A_t^O})$ into another quantum channel: $S(M_1, \dots, M_T) : \mathcal{L}(\mathcal{H}^P) \to \mathcal{L}(\mathcal{H}^F)$. Writing $\mathcal{H}^{A_t^I} = \mathcal{H}^{A_t^I A_t^O}$ and, with $T := \{1, \dots, T\}$, $\mathcal{H}^{A_t^I} = \bigotimes_{k \in T} \mathcal{H}^{A_k^I}$, a supermap can be represented in the Choi picture as a “process matrix” [5], a positive semidefinite matrix $W \in \mathcal{L}(\mathcal{H}^{PA^I_F})$ belonging to a specific subspace $\mathcal{L}^{\text{Gen}}$ and normalized such that $\text{Tr}W = d^P \prod_{k=1}^T d_k^O$, with $d^P = \text{dim}(\mathcal{H}^P)$ and $d_k^O = \text{dim}(\mathcal{H}^{A_k^O})$ [8,26] (see SM [24] for further details). We denote the set of all such process matrices $\mathcal{W}^{\text{Gen}}$. The process matrix $W$ fully characterizes $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 \cdots \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 subclasses 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_1^I\alpha_1})$, $V_t : \mathcal{L}(\mathcal{H}^{A_t^I\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+1}^I\alpha_T}) \to \mathcal{L}(\mathcal{H}^F)$ composed sequentially in a circuit structure [6]. Here, the $\mathcal{H}^{A_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{aligned} S(M_1, \dots, M_T) &= V_{T+1} * M_T * V_T * \cdots * V_2 * M_1 * V_1 \\ &= (M_1 \otimes \cdots \otimes M_T) * W \in \mathcal{L}(\mathcal{H}^{PF}), \end{aligned} \quad (2) $$

where $W = V_{T+1} * \cdots * V_1 \in \mathcal{L}(\mathcal{H}^{PA^I_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 $\mathcal{W}^{\text{FO}} \subset \mathcal{W}^{\text{Gen}}$ [6,17,23] (see also the SM [24]). 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 control of causal order (or QC supermaps), can be formulated as generalized quantum circuits in which a quantum system controls the order of application of the different input operations [17]. This clear interpretation and the potential realizability of QC supermaps [17,27,28] makes it a class of particular interest, and which includes 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 systems 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, throughout the computation the control system, at time-step $t$, has basis states $|K_{t-1}, k_t\rangle$ specifying that operation $k_t \notin K_{t-1}$ will be applied next and that the operations $K_{t-1} \subsetneq T$ have already been applied. This system controls coherently the application of the different input operations $M_{k_t}$ at time-step $t$ and the pure internal operations $\mathcal{V}_{k_{t+1}} : \mathcal{L}(\mathcal{H}^{A_k^I\alpha_t}) \to \mathcal{L}(\mathcal{H}^{A_{k+1}^I\alpha_{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}$) [17]. Process matrices of QC supermaps belong to a subset $\mathcal{W}^{\text{QC}} \subset \mathcal{W}^{\text{Gen}}$; see [17] or the SM [24] for a more detailed description of QC supermaps and their process matrices.
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, QC, 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}_x^{A_i}) \to \mathcal{L}(\mathcal{H}_x^{A_i})$, where $\mathcal{H}_x^{A_i}$ and $\mathcal{H}_x^{A_i}$ 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}[(\mathcal{O}_x^{\otimes T} * W^C) \cdot \Pi_{f(x)}], \quad (3)$$

with $\Pi_{f(x)} = |f(x)\rangle\langle f(x)|$ and $\mathcal{O}_x^{\otimes T} = \bigotimes_{i=1}^T \mathcal{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 (4)$$

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

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 anticommuting unitaries [9] and generalizations of that task [10,12]. Here, we show that they cannot provide an advantage in query complexity of Boolean functions. In particular, building on a result of Ref. [13] for “switch-like” supermaps, as strict subclass of QC supermaps generalising the quantum switch, we show that QC supermaps are equivalent to FO supermaps when acting on T copies of the same unitary channel.

**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)$.

The proof is detailed in the SM [24]. While the theorem may appear intuitive, the result exploits subtly both the specific structure of QC supermaps and the unitarity of the operation. Indeed, the analogous result for nonunitary channels is known to be false, and concrete advantages are known in that setting [29–32].

A direct corollary of Theorem 1 is that $Q_E^{\mathrm{QC}} = Q_E^{\mathrm{FO}}$ and $Q_2^{\mathrm{QC}} = Q_2^{\mathrm{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 [29] 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 [33]. A polynomial $g$ is said to represent a Boolean function $f$ if for all $x \in \{0, 1\}^n$, $f(x) = g(x)$, we denote $\mathrm{deg}(f)$ the smallest degree of any polynomial representing $f$. Similarly, we write $\widetilde{\mathrm{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 $\mathrm{deg}(f)/2 \le Q_E^{\mathrm{FO}}(f)$, and likewise for the bounded-error counterpart, that $\mathrm{deg}(f)/2 \le Q_2^{\mathrm{FO}}(f)$. Here, we generalize 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 $\mathrm{deg}(f)/2 \le Q_E^{\mathrm{Gen}}(f)$ and $\widetilde{\mathrm{deg}}(f)/2 \le Q_2^{\mathrm{Gen}}(f)$.

The proof follows a generalization of the original result [33] into the process matrix framework; we provide the full details in the SM [24].

Theorems 1 and 2 thus allow us to refine the inequalities (4) and (5) as follows:

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

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

These results mean that for functions whose polynomial bound is tight for FO supermaps, i.e., when $\mathrm{deg}(f)/2 = Q_E^{\mathrm{FO}}(f)$ or $\mathrm{deg}(f)/2 = Q_2^{\mathrm{FO}}(f)$, causal indefiniteness cannot provide any advantage. But not all Boolean functions have a tight polynomial bound [34], motivating 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}(\mathrm{deg}(f)^3)$ and $Q_2(f) = \tilde{O}(\mathrm{deg}(f)^4)$ [35,36], one cannot hope for an exponential
advantage from causal indefiniteness [here, $f(x) = \tilde{O}(g(x))$ if $f(x) = O(g(x) \log^k x)$ for some constant $k$].

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 optimization of quantum supermaps using semidefinite programs (SDPs) [8,26].

**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 four input bits. A systematic study for quantum circuits of the minimum bounded error computation of functions using SDPs was already performed in Ref. [37] for functions up to four bits, and for symmetric functions up to six bits. The SDP formulation used therein (based on that of [38]) fails to extend to general supermaps as it exploits the sequential structure of a FO supermap, which has no analog in generic quantum supermaps.

Here, using the characterization 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]}$ where $W^{[i]} = W * \Pi_i$ [17], so that $p(f(x)) = \text{Tr}[W^{[i]} \cdot \mathcal{O}_x^{\otimes T}]$. Writing $F^{[i]} = \{x : f(x) = i\}$, the minimum-error bound $\varepsilon_T^C(f)$ is given by the SDP

$$ \begin{gathered} \varepsilon_T^C(f) = \max_{\varepsilon, W^{[0]}, W^{[1]}} 1 - \varepsilon \\ \text{s.t. } \forall i \in \{0, 1\}, \forall x \in F^{[i]}, \text{Tr}[W^{[i]} \cdot \mathcal{O}_x^{\otimes T}] \ge 1 - \varepsilon, \quad (8) \\ \forall i \in \{0, 1\}, W^{[i]} \ge 0, \varepsilon \ge 0, \sum_{i \in [0,1]} W^{[i]} \in W^C. \end{gathered} $$

Note that the size of the $W^{[i]}$'s scale as $(n+1)^{2T}$ making the SDP difficult to solve even for moderate $n$ and $T$. We managed to solve it numerically for $T = 2$ and up to $n = 4$ [39,40].

We studied all three- and four-bit Boolean functions, using the so-called negate, permute, negate (NPN) equivalence relation [37] to reduce the number of functions to consider. No advantage was found for three-bit Boolean functions. For four-bit functions, a table of the results is given in the SM [24]. Out of the 222 NPN representatives, we observe a gap between the minimum error bounds $\varepsilon_2^{\text{FO}}(f)$ and $\varepsilon_2^{\text{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. [30] and allows us to obtain upper bounds with the primal SDP (8), and lower bounds with the corresponding dual SDP, which can be derived with Lagrangian method (see the SM [24] for further details). Using the extraction methods for the function ID 5865, we find the bounds $0.0324 \le \varepsilon_2^{\text{Gen}}(f) \le 0.0377 < 0.0452 \le \varepsilon_2^{\text{FO}}(f) \le 0.0472$, 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 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 [41,42], similar to the advantage in query complexity obtained with quantum circuits in Ref. [34]. These results also raise the question of whether it is possible to find a separation in exact query complexity.

Our proof that QC supermaps cannot provide any advantage over FO supermaps when a single unitary is repeatedly queried has implications beyond query complexity. For instance, it also implies that this important class of supermaps cannot provide advantages in quantum metrology of unitary dynamics [15,43]. It likewise raises natural questions about the power of specific classes of supermaps beyond QC supermaps, such as that of purifiable processes [44]. The prospect that some such supermaps may be realizable [45] leaves open the possibility of exploiting causal indefiniteness in the standard query complexity setting. It would similarly be interesting to study whether supermaps, including QC supermaps, can be exploited in related scenarios. 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 [46]?

**Acknowledgments.** The authors acknowledge funding from the French National Research Agency Projects No. ANR-15-IDEX-02 and No. ANR-22-CE47-0012, and the Plan France 2030 Projects No. ANR-22-CMAS-0001 and No. ANR-22-PETQ-0007.
[1] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and weaknesses of quantum computing, SIAM J. Comput. 26, 1510 (1997).

[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, PA, 1996), pp. 212–219.

[3] C. Dürr, M. Heiligman, P. HOyer, and M. Mhalla, Quantum query complexity of some graph problems, SIAM J. Comput. 35, 1310 (2006).

[4] G. Chiribella, G. M. D'Ariano, P. Perinotti, and B. Valiron, Quantum computations without definite causal structure, Phys. Rev. A 88, 022318 (2013).

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

[6] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Quantum circuit architecture, Phys. Rev. Lett. 101, 060401 (2008).

[7] O. Oreshkov and C. Giarmatzi, Causal and causally separable processes, New J. Phys. 18, 093020 (2016).

[8] J. Wechs, A. A. Abbott, and C. Branciard, On the definition and characterisation of multipartite causal (non)separability, New J. Phys. 21, 013027 (2019).

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

[10] M. Araújo, F. Costa, and Č. Brukner, Computational advantage from quantum-controlled ordering of gates, Phys. Rev. Lett. 113, 250402 (2014).

[11] M. J. Renner and Č. Brukner, Computational advantage from a quantum superposition of qubit gate orders, Phys. Rev. Lett. 128, 230503 (2022).

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

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

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

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

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

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

[18] H. Buhrman and R. de Wolf, Complexity measures and decision tree complexity: A survey, Theor. Comput. Sci. 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, Singapore, 2018), pp. 3265–3285.

[20] A. Ambainis, Quantum lower bounds by quantum arguments, J. Comput. Syst. Sci. 64, 750 (2002).

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

[22] A. Jamiołkowski, Linear transformations which preserve trace and positive semidefiniteness of operators, Rep. Math. Phys. 3, 275 (1972).

[23] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Theoretical framework for quantum networks, Phys. Rev. A 80, 022339 (2009).

[24] See Supplemental Material at http://link.aps.org/supplemental/10.1103/PhysRevResearch.6.L032020 for a more complete technical presentation of supermaps, detailed proofs of our theorems and additional numerical results.

[25] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Transforming quantum operations: Quantum supermaps, Europhys. Lett. 83, 30004 (2008).

[26] M. Araújo, C. Branciard, F. Costa, A. Feix, C. Giarmatzi, and Č. Brukner, Witnessing causal nonseparability, New J. Phys. 17, 102001 (2015).

[27] T. Purves and A. J. Short, Quantum theory cannot violate a causal inequality, Phys. Rev. Lett. 127, 110402 (2021).

[28] M. Salzger, Connecting indefinite causal order processes to composable quantum protocols in a spacetime, arXiv:2304.06735.

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

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

[31] Q. Liu, Z. Hu, H. Yuan, and Y. Yang, Optimal strategies of quantum metrology with a strict hierarchy, Phys. Rev. Lett. 130, 070803 (2023).

[32] R. Mothe, C. Branciard, and A. A. Abbott, Reassessing the advantage of indefinite causal orders for quantum metrology, Phys. Rev. A 109, 062435 (2024).

[33] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf, Quantum lower bounds by polynomials, J. ACM 48, 778 (2001).

[34] A. Ambainis, Polynomial degree vs. quantum query complexity, J. Comput. Syst. Sci. 72, 220 (2006).

[35] 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) (Association for Computing Machinery, New York, 2016), pp. 863–876.

[36] 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 (Association for Computing Machinery, New York, 2021), pp. 1330–1342.

[37] A. Montanaro, R. Jozsa, and G. Mitchison, On exact quantum query complexity, Algorithmica 71, 775 (2015).

[38] H. Barnum, M. Saks, and M. Szegedy, Quantum query complexity and semi-definite programming, in 18th IEEE Annual
*Conference on Computational Complexity, Proceedings* (IEEE Computer Society, Los Alamitos, CA, USA, 2003), pp. 179–193.

[39] J. Lofberg, Yalmip: A toolbox for modeling and optimization in matlab, in *2004 IEEE International Symposium on Computer Aided Control Systems Design* (IEEE Computer Society, Taipei, Taiwan, 2004), pp. 284–289.

[40] B. O'Donoghue, E. Chu, N. Parikh, and S. Boyd, Conic optimization via operator splitting and homogeneous self-dual embedding, *J. Optim. Theory Appl.* **169**, 1042 (2016).

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

[42] A. Kissinger and S. Uijlen, A categorical semantics for causal structure, *Logical Methods Comput. Sci.* **15**, 4426 (2019).

[43] V. Giovannetti, S. Llyod, and L. Maccone, Advances in quantum metrology, *Nat. Photon.* **5**, 222 (2011).

[44] M. Araújo, A. Feix, M. Navascués, and Č. Brukner, A purification postulate for quantum mechanics with indefinite causal order, *Quantum* **1**, 10 (2017).

[45] J. Wechs, C. Branciard, and O. Oreshkov, Existence of processes violating causal inequalities on time-delocalised subsystems, *Nat. Commun.* **14**, 1471 (2023).

[46] P. A. Guérin, A. Feix, M. Araújo, and Č. Brukner, Exponential communication complexity advantage from quantum superposition of the direction of communication, *Phys. Rev. Lett.* **117**, 100502 (2016).