capbtabboxtable[][] 11institutetext: SIRIUS, Department of Information,
University of Oslo, Norway
11email<EMAIL_ADDRESS>22institutetext: LISN, Univ. Paris-Sud, CNRS,
Université Paris-Saclay, Orsay, France
22email: {ma<EMAIL_ADDRESS>33institutetext: University of Milano-Bicocca,
Milan, Italy
33email<EMAIL_ADDRESS>
# Union and Intersection of all Justifications

Jieying Chen 11 Yue Ma 22 Rafael Peñaloza 33 Hui Yang 22

###### Abstract

We present new algorithms for computing the union and intersection of all
justifications for a given ontological consequence without first computing the
set of all justifications. Through an empirical evaluation, we show that our
approach works well in practice for expressive description logics. In
particular, the union of all justifications can be computed much faster than
with existing justification-enumeration approaches. We further discuss how to
use these results to repair ontologies.

##  1 Introduction

A justification for a consequence $\alpha$ refers to a minimal subset of the
ontology, which still entails $\alpha$. The problem of computing
justifications, also known as axiom pinpointing, has been widely studied in
the context of description logics [27]. Axiom pinpointing methods can be
separated into two main classes, commonly known as black-box and glass-box.

Black-box approaches [18, 19, 26] use existing reasoners as an oracle, and
require no further modification of the reasoning method. Therefore, these
approaches work for ontologies written in any monotonic logical language
(including expressive DLs such as ${\cal SHOIQ}$), as long as a reasoner
supporting it exists. In their most naïve form, black-box methods check all
possible subsets of the ontology for the desired entailment and compute the
justifications from these results. In reality, many optimisations have been
developed to reduce the number of calls needed, and avoid irrelevant work.

Glass-box approaches, on the other hand, modify the reasoning algorithm to
output one or all justifications directly, from only one call. While the
theory for developing glass-box methods has been developed for tableaux and
automata-based reasoners [6, 5, 4, 7], in practice not many of these methods
have been implemented, as they require new implementation efforts and
deactivating the optimisation techniques that make reasoners practical. A
promising approach, first proposed in [32] is to reduce, through a reasoning
simulation, the axiom pinpointing problem to an enumeration problem from a
propositional formula, and use state-of-the-art SAT-solving methods to
enumerate all the justifications. This idea has led to effective axiom
pinpointing systems developed primarily for the lightweight DL
$\mathcal{E\\!L}$ [20, 1, 2, 3, 24].

The interest of axiom pinpointing goes beyond enumerating justifications.
Modelling ontologies is a time-consuming and fallible task. Indeed, during the
modelling phase it is not uncommon to discover unexpected or wrong
entailments. One way to fix these errors is to diagnose the causes by
computing a hitting set of all the justifications. However, as there might
exist exponential many justifications for a given entailment w.r.t. an
ontology, even for $\mathcal{E\\!L}$-ontologies, finding all justifications is
not feasible in general. One approach is to approximate the information by the
union and intersection of all justifications. If the intersection is not
empty, then any axiom in this intersection, when removed, guarantees that the
consequence will not follow anymore. From the union, a knowledge engineer has
a more precise view on the problematic instances, and can make a detailed
analysis.

Although much work has focused on methods for computing one or all
justifications efficiently, to the best of our knowledge there is little work
on computing their intersection or union without enumerating them first,
beyond the approximations presented in [29, 28]. In this paper, we propose an
algorithm of computing the intersection of all justifications. This algorithm
has the same worst-case behaviour as the black-box algorithm of computing one
justification. Additionally, we present two approaches of computing the union
of all justifications, one is based on the black-box algorithm of finding all
justifications and the other approach uses the SAT-tool cmMUS.

The paper is structured as follows. In Section 2 we recall relevant
definitions of description logics and propositional logic. Section 3 presents
the algorithm for computing the intersection of all justifications without
computing any single justification. We propose two methods of computing the
union of all justifications in Section 4. We explain how to use the union and
intersection of all justifications to repair ontologies in Section 5. Before
concluding, an evaluation of our methods on real-world ontologies is presented
in Section 6.

##  2 Justifications and Repairs in ${\cal ALC}$

We briefly recall the notions of justifications and repairs in ${\cal ALC}$.
Let $N_{C}$, $N_{R}$ and $N_{I}$ be mutually disjoint sets of _concept names_
, _role names_ , and _individual names_. The set of ${\cal ALC}$-concepts $C$
is built through the following grammar rule

$\displaystyle C$ $\displaystyle::=\top\mid\bot\mid A\mid C\sqcap C\mid
C\sqcup C\mid\neg C\mid\exists r.C\mid\forall r.C,$

where $A\in N_{C}$ and $r\in N_{R}$. An ${\cal ALC}$-TBox $\mathcal{T}$ is a
finite set of general concept inclusions (GCIs) of the form $C\sqsubseteq D$
and role inclusions $r\sqsubseteq s$, where $C$ and $D$ are ${\cal
ALC}$-concepts and $r,s\in N_{R}$. An ABox is a finite set of concept
assertions of the form $A(a)$ and role assertions $r(a,b)$, where $A\in
N_{C}$, $r\in N_{R}$ and $a,b\in N_{I}$. An ${\cal ALC}$ ontology consists of
an ${\cal ALC}$ TBox and an ABox.

The semantics of this logic is defined in terms of interpretations. An
interpretation is a pair
$\mathcal{I}=(\Delta^{\mathcal{I}},\cdot^{\mathcal{I}})$ where
$\Delta^{\mathcal{I}}$ is a non-empty set called the _domain_ , and
$\cdot^{\mathcal{I}}$ is the _interpretation function_ , which maps each
concept name $A\in N_{C}$ to a subset
$A^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}$, each role name $r\in N_{R}$ to
a binary relation
$r^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}{\times}\Delta^{\mathcal{I}}$ and
each individual $a\in N_{I}$ to a domain element
$a^{\mathcal{I}}\in\Delta^{\mathcal{I}}$. The interpretation function is
extended to ${\cal ALC}$-concepts as usual:
$(\top)^{\mathcal{I}}:=\Delta^{\mathcal{I}}$,
$(\bot)^{\mathcal{I}}:=\emptyset$, $(\neg
C)^{\mathcal{I}}:=\Delta^{\mathcal{I}}\backslash C^{\mathcal{I}}$, $(C\sqcap
D)^{\mathcal{I}}:=C^{\mathcal{I}}\cap D^{\mathcal{I}}$, $(C\sqcup
D)^{\mathcal{I}}:=C^{\mathcal{I}}\cup D^{\mathcal{I}}$, $(\exists
r.C)^{\mathcal{I}}:=\\{x\in\Delta^{\mathcal{I}}\mid\exists y\in
C^{\mathcal{I}}:(x,y)\in r^{\mathcal{I}}\\}$, and $(\forall
r.C)^{\mathcal{I}}:=\\{x\in\Delta^{\mathcal{I}}\mid\forall
y\in\Delta^{\mathcal{I}}.(x,y)\in r^{\mathcal{I}}\Rightarrow y\in
C^{\mathcal{I}}\\}$. The interpretation $\mathcal{I}$ _satisfies_
$C\sqsubseteq D$ iff $C^{\mathcal{I}}\subseteq D^{\mathcal{I}}$ and it
_satisfies_ $r\sqsubseteq s$ iff $r^{\mathcal{I}}\subseteq s^{\mathcal{I}}$.
We write $\mathcal{I}\models\alpha$ if $\mathcal{I}$ satisfies the axiom
$\alpha$. The interpretation $\mathcal{I}$ is a _model_ of an ontology
$\mathcal{O}$ if $\mathcal{I}$ satisfies all axioms in $\mathcal{O}$. An axiom
$\alpha$ _is entailed by $\mathcal{O}$_, denoted as
$\mathcal{O}\models\alpha$, if $\mathcal{I}\models\alpha$ for all models
$\mathcal{I}$ of $\mathcal{O}$. We use $|\mathcal{O}|$ to denote the size of
$\mathcal{O}$, i.e., the number of axioms in $\mathcal{O}$.

For this paper, we are interested in the notions of _justification_ and
_repair_.

######  Definition 1 (Justification, repair)

Let $\mathcal{O}$ be an ontology and $\alpha$ a GCI. A _justification_ for
$\mathcal{O}\models\alpha$ is a subset $\mathcal{M}\subseteq\mathcal{O}$ such
that $\mathcal{M}\models\alpha$ and for any
$\mathcal{M}^{\prime}\subsetneq\mathcal{M}$,
$\mathcal{M}^{\prime}\not\models\alpha$. $\mathrm{Just}(\mathcal{O},\alpha)$
denotes the set of all justifications of $\alpha$ w.r.t. $\mathcal{O}$. A
repair for $\mathcal{O}\models\alpha$ is a subontology
$\mathcal{R}\subseteq\mathcal{O}$ such that $\mathcal{R}\not\models\alpha$,
but $\mathcal{O}^{\prime}\models\alpha$ for any
$\mathcal{R}\subsetneq\mathcal{O}^{\prime}\subseteq\mathcal{O}$. We denote the
set of all repairs as $\mathrm{Rep}(\mathcal{O},\alpha)$.

Briefly, a justification is a minimal subset of an ontology that preserves the
conclusion. Dually, a repair is a maximal sub-ontology that does not preserve
the consequence.

Now we consider a propositional language with a finite set of propositional
variables $L=\\{p_{1},p_{2},\cdots,p_{n}\\}$. A literal is a variable $p_{i}$
or its negation $\neg p_{i}$. A clause $l_{1}\vee l_{2}\vee\cdots\vee l_{k}$
is a disjunction of literals, denoted by $\omega$[10]. A Boolean formula in
Conjunctive Normal Form (CNF) is a conjunction of clauses. A CNF formula
$\phi$ is satisfiable iff there exists a truth assignment
$\mu_{L}:L\rightarrow\\{0,1\\}$ such that $\mu_{L}$ satisfies all clauses in
$\phi$. We can also consider a CNF formula as a set of clauses. A subformula
$\phi^{\prime}\subseteq\phi$ is a Minimally Unsatisfiable Subformula (MUS) iff
$\phi^{\prime}$ is unsatisfiable, but for every
$\phi_{1}^{\prime}\subsetneq\phi^{\prime}$ is satisfiable.

##  3 Computing the Intersection of all Justifications

We first study the problem of computing the intersection of all
justifications, which we often call the _core_. Algorithm 1 provides a method
for finding this core.

Algorithm 1 Computing the intersection of all justifications of $\mathcal{O}$
w.r.t. $\alpha$

1:an Ontology $\mathcal{O}$, a conclusion $\alpha$

2:function Compute-Justification-Core($\mathcal{O},\Sigma$)

3: $\mathcal{C}\coloneqq\emptyset$

4: $\mathcal{M}:=\textsc{Compute-Locality-Based-
Module}(\mathcal{O},\mathsf{sig}(\alpha))$

5: for every axiom $\beta\in\mathcal{M}$ do

6: if $\mathcal{M}\setminus\\{\beta\\}\not\models\alpha$ then

7: $\mathcal{C}\coloneqq\mathcal{C}\cup\\{\beta\\}$

8: return $\mathcal{C}$

The algorithm is inspired by the known black-box approach for finding
justifications [17, 7]. Starting from a justification-preserving module
$\mathcal{M}$ (in this case, the locality-based module, Line 3), we try to
remove one axiom $\beta$ (Line 4). If the removal of the axiom $\beta$ removes
the entailment (Line 5), then $\beta$ must belong to all justifications
($\beta$ is a _sine qua non_ requirement for entailment within $\mathcal{M}$),
and is thus added to the core $\mathcal{C}$ (Line 6).

Algorithm 2, on the other hand, generalises the known algorithm for computing
a single justification, by considering a (fixed) set $\mathcal{C}$ that is
known to be contained in all justifications. If $\mathcal{C}=\emptyset$, the
approach works as usual; otherwise, the algorithm avoids trying to remove any
axiom from $\mathcal{C}$. This reduces the number of calls to the black-box
reasoner, potentially decreasing the overall execution time.

Algorithm 2 Using core to compute a single justification of $\mathcal{O}$
$w.r.t.$ an conclusion

1:an ontology $\mathcal{O}$, a conclusion $\alpha$, the intersection of all
justifications $\mathcal{C}$

2:function Single-Justification($\mathcal{O},\alpha,\mathcal{C}$)

3: $\mathcal{M}\coloneqq\textsc{Compute-Locality-Based-
Module}(\mathcal{O},\mathsf{sig}(\alpha))$

4: for every axiom $\beta\in\mathcal{M}$ and $\beta\not\in\mathcal{C}$ do

5: if $\mathcal{M}\setminus\\{\beta\\}\models\alpha$ then

6: $\mathcal{M}\coloneqq\mathcal{M}\setminus\\{\beta\\}$

7: return $\mathcal{M}$

As mentioned already, the choice for a locality-based module in these
algorithms is arbitrary, and any justification-preserving module would
suffice. In particular, we could compute lean kernel [29, 21] for ${\cal
ALC}$-ontologies, and minimal subsumption modules [11, conf/gcai/ChenL018] for
$\mathcal{E\\!L}$-ontologies instead, which is typically smaller thus reducing
the number of iterations within the algorithms. However, as it could be quite
expensive to compute such modules, it might not be worthwhile in some cases.
The following theorem shows that Algorithm 1 correctly computes the
intersection of all justifications.

###### Theorem 3.1

Let $\mathcal{O}$ be an ontology and $\alpha$ a GCI. Algorithm 1 computes the
intersection of all justifications of $\mathcal{O}$ w.r.t. $\Sigma$.

Algorithm 1, like all black-box methods for computing justifications, calls a
standard reasoner $|\mathcal{M}|$ times. In terms of computational complexity,
computing the core requires as many computational resources as computing a
single justification. However, computing one justification might be faster in
practice, as the size of $\mathcal{M}$ decreases throughout the execution of
Algorithm 2. Clearly, if the core coincides with one justification
$\mathcal{M}$, then $\mathcal{M}$ is the _only_ justification.

###### Corollary 1

Let $\mathcal{O}$ be an ontology, $\alpha$ a GCI; and let $\mathcal{C}$ be the
core and $\mathcal{J}$ a justification for $\mathcal{O}\models\alpha$. If
$\mathcal{C}=\mathcal{J}$, $\mathcal{J}$ is the only justification for
$\mathcal{O}\models\alpha$.

##  4 Computing the Union of all Justifications

We now present two algorithms of computing the union of all justifications.
The first algorithm follows a black-box approach that calls a standard
reasoner as oracle using the core of justifications. This is inspired by
Reiter’s Hitting Set Tree algorithm [30] and partially in line with [17, 34].
For the second algorithm, we reduce the problem of computing the union of all
justifications to the problem of computing the union of MUSes of a
propositional formula. Note that the second algorithm works only for ${\cal
ALC}$-ontologies, while the first algorithm can be applied to ontologies with
any expressivity, as long as a reasoner is available.

###  4.1 Black-box algorithm

The black-box algorithm of computing all justifications [34] was inspired by
the algorithm of computing all minimal hitting sets [30]. Some of the
improvements to prune the search space were already proposed in [30]. Our
method for computing the union of all justifications (Algorithm 3) works in a
similar manner, but with a few key differences.

Algorithm 3 Computing the Union of All Justifications w.r.t. a Conclusion
$\alpha$

1:an Ontology $\mathcal{O}$, a conclusion $\alpha$, the intersection of all
Justifications $\mathcal{C}\subseteq\mathcal{O}$

2:function Union-of-All-Justifications($\mathcal{O},\alpha,\mathcal{C}$)

3: $\mathcal{M}\coloneqq\textsc{Compute-Locality-Based-
Module}$($\mathcal{O},\mathsf{sig}(\alpha))$

4: $\mathcal{U}\coloneqq\mathcal{C}$;
$\Psi\coloneqq(\\{\rho\\},\emptyset,\emptyset,\rho)$;
$\mathbb{Q}\coloneqq[\rho]$; $\mathbb{P}\coloneqq\emptyset$;
$\mathbb{M}\coloneqq\\{\emptyset\\}$

5: while $\mathbb{Q}\neq[\,]$ do

6: $v\coloneqq\textsc{Head}(\mathbb{Q})$,
$\mathbb{Q}\coloneqq\textsc{RemoveFirstElement}(\mathbb{Q})$,
$\mathbb{P}\coloneqq\mathbb{P}\cup\\{v\\}$

7:
$\mathcal{M}_{\text{ex}}\coloneqq\textsc{Labels}(\textsc{Path}(\Psi,\rho,v))$

8: if $\textsc{Is-Path-
Redundant}(\Psi,\rho,\mathcal{M}_{\text{ex}},\mathbb{P})$ then

9: continue

10: if $\mathcal{M}\setminus\mathcal{M}_{\text{ex}}\not\models\alpha$ then

11: continue

12: if $\mathcal{M}\setminus\mathcal{M}_{\text{ex}}\subseteq\mathcal{U}$ then

13: continue

14: $\mathcal{M}\coloneqq\emptyset$

15: if there exists $\mathcal{M}^{\prime}\in\mathbb{M}$ such that
$\mathcal{M}_{\text{ex}}\cap\mathcal{M}^{\prime}=\emptyset$ then

16: $\mathcal{M}\coloneqq\mathcal{M}^{\prime}$

17: else

18: $\mathcal{M}\coloneqq\textsc{Single-
Justification}(\mathcal{M}\setminus\mathcal{M}_{\text{ex}},\alpha,\mathcal{C})$

19: if $\mathcal{M}=\mathcal{C}$ then

20: return $\\{\mathcal{C}\\}$

21: $\mathbb{M}\coloneqq\mathbb{M}\cup\\{\mathcal{M}\\}$

22: $\mathcal{U}\coloneqq\mathcal{U}\cup\mathcal{M}$

23: for every $\beta\in\mathcal{M}\setminus\mathcal{C}$ do

24: $v_{\beta}\coloneqq\textsc{AddChild}(\Psi,v,\beta)$

25: $\mathbb{Q}\coloneqq v_{\beta}::\mathbb{Q}$

26: return $\mathcal{U}$

To avoid computing all justifications, we prune the search space when all
remaining justifications are fully contained in the union computed so far
(Lines 11-12). In addition, we use the core to speed the search. As the axioms
in the core must appear in every justification, we can reduce the number of
calls made to the reasoner, and optimise the single justification computation
(Line 17). Finally, when we organise our search space, we do not need to
consider the axioms in the core (Line 22).

We now describe the Union-of-All-Justifications procedure in detail. Given an
ontology $\mathcal{O}$, a signature $\Sigma$, and the intersection of all
justifications $\mathcal{C}\subseteq\mathcal{O}$ of $\mathcal{O}$ w.r.t.
$\Sigma$ as input, a syntactic $\bot\\!\top^{\ast}$-locality module
$\mathcal{O}_{\Sigma}$ of $\mathcal{O}$ w.r.t. $\Sigma$ is extracted from
$\mathcal{O}$ (Lines 2). The justification search tree $\Psi$ is a four-tuple
$(\mathcal{V},\mathcal{E},\mathcal{L},\rho)$, where $\mathcal{V}$ is a finite
set of nodes, $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is a set of
edges, $\mathcal{L}$ is an edge labelling function, mapping every edge to an
axiom $\alpha\in\mathcal{M}$, and $\rho\in\mathcal{V}$ is the root node. We
initialise the variable $\Psi$ to represent a justification search tree for
$\mathcal{O}$ having only root node $\rho$. Besides, the variables
$\mathbb{M}\subseteq 2^{\mathcal{O}_{\Sigma}}$, containing the justifications
that have been computed so far, and $\mathbb{P}\subseteq\mathcal{V}$,
containing the already explored nodes of $\Psi$, are both initialised with the
empty set. The queue $\mathbb{Q}$ of nodes in $\Psi$ that still has to be
explored is also set to contain the node $\rho$ as its only element.

The algorithm then enters a loop (Lines 4–24) that runs while $\mathbb{Q}$ is
not empty. The loop extracts the first element $v$ from $\mathbb{Q}$ and adds
it to $\mathbb{P}$ (Line 5). The axioms that label the edges of the path
$\pi_{v}$ from $\rho$ to $v$ in $\Psi$ are collected in the set
$\mathcal{M}_{\text{ex}}$ (Line 7). After that, the algorithm checks whether
$\pi_{v}$ is redundant. The detailed method for checking redundancy is
described in Algorithm 4. The path $\pi_{v}$ is _redundant_ iff there exists
an explored node $w\in\mathbb{P}$ such that (a) the axioms in
$\mathcal{O}_{\text{ex}}$ are exactly the axioms labelling the edges of the
path $\pi_{w}$ from $\rho$ to $w$ in $\Psi$ (Lines 4–6), or (b) $w$ is a leaf
node of $\Psi$ and the edges of $\pi_{w}$ are only labelled with axioms from
$\mathcal{O}_{\text{ex}}$ (Lines 7–8). Case (a) corresponds to _early path
termination_ in [30, 17]: the existence of $\pi_{w}$ implies that all possible
extensions of $\pi_{v}$ have already been considered. Case (b) implies that
the axioms labelling the edges of $\pi_{w}$ lead to the fact that $\alpha$ can
not be entailed be the remaining TBox when removed from
$\mathcal{O}_{\Sigma}$. Therefore, by monotonicity of $\models$, we infer that
removing $\mathcal{O}_{\text{ex}}$ from $\mathcal{O}_{\Sigma}$ also has the
same consequence implying that we do not need to explore $\pi_{v}$ and all its
extensions.

Algorithm 4 Checking the Redundancy of a Path

1:justification search tree $\Psi$ for an $\mathcal{L}$-TBox $\mathcal{O}$
with root $\rho$, $\mathcal{O}^{w}_{\text{ex}}\subseteq\mathcal{O}$,
$\mathbb{P}\subseteq\textrm{Nodes}(\Psi)$

2:function Is-Path-Redundant($\Psi,\rho,\mathcal{O}_{\text{ex}},\mathbb{P}$)

3: for every  $w\in\mathbb{P}$ do

4:
$\mathcal{O}^{w}_{\text{ex}}\coloneqq\textsc{Labels}(\textsc{Path}(\Psi,\rho,w))$

5: if $\mathcal{O}^{w}_{\text{ex}}\subseteq\mathcal{O}_{\text{ex}}$ then

6: if $\mathcal{O}_{\text{ex}}\subseteq\mathcal{O}^{w}_{\text{ex}}$ then

7: return true

8: else if $\textsc{Is-Leaf}(\Psi,w)$ then

9: return true

10: return false

The current iteration can be terminated immediately if
$\mathcal{M}\setminus\mathcal{M}_{\text{ex}}\not\models\alpha$ (Lines 9–10) as
no subset of $\mathcal{M}_{\Sigma}\setminus\mathcal{M}_{\text{ex}}$ can be a
justification of $\mathcal{M}$ w.r.t. $\alpha$. In contrast to other black-box
algorithms for computing justifications, we additionally check whether
$\mathcal{M}\setminus\mathcal{M}_{\text{ex}}$ is a subset of $\mathcal{U}$. If
so, no new axioms belonging to the union of all justifications appear in this
sub-tree. Hence, the algorithm does not need to explore it any further.
Subsequently, the variable $\mathcal{M}$ that will hold a justification of
$\mathcal{M}\setminus\mathcal{M}_{\text{ex}}$ is initialised with $\emptyset$.
At this point we can check if a justification
$\mathcal{M}^{\prime}\in\mathbb{M}$ has already been computed for which
$\mathcal{O}_{\text{ex}}\cap\mathcal{M}^{\prime}=\emptyset$ (Lines 14–15)
holds, in which casewe set $\mathcal{M}$ to $\mathcal{M}^{\prime}$. This
optimisation step can also be found in [30, 17] and it allows us to avoid a
costly call to the Single-Justification procedure. Otherwise, in Line 17 we
call Single-Justification on $\mathcal{M}\setminus\mathcal{O}_{\text{ex}}$ to
obtain a justification of $\alpha$ w.r.t.
$\mathcal{M}\setminus\mathcal{O}_{\text{ex}}$. We then check whether
$\mathcal{M}$ is equal to $\mathcal{C}$ (Lines 18–19), in which case the
search for additional justifications can be terminated (recall Corollary 1).
Otherwise, the justification $\mathcal{M}$ is added to $\mathbb{M}$ in Line 20
and the union of all justifications is updated in Line 21. Finally, for every
$\beta\in\mathcal{M}\setminus\mathcal{C}$, the algorithm extends the tree
$\Psi$ in Lines 22–24 by adding a child $v_{\alpha}$ to $v$, connected by an
edge labelled with $\beta$. Note that it is sufficient to take
$\beta\not\in\mathcal{C}$ as a set $\mathcal{M}$ with
$\mathcal{C}\not\subseteq\mathcal{M}$ cannot be a justification of
$\mathcal{O}$ w.r.t. $\alpha$. The procedure finishes by returning the set
$\mathcal{U}$.

Note that this algorithm only adds justifications to $\mathbb{M}$. For
completeness, one can show that the locality-based module
$\mathcal{O}_{\Sigma}$ of $\mathcal{O}$ w.r.t. $\Sigma$ contains all the
minimal modules of $\mathcal{O}$ w.r.t. $\Sigma$. Moreover, it is easy to see
that the proposed optimisations do not lead to a minimal module not being
computed. Overall, we obtain the following result.

###### Theorem 4.1

Let $\mathcal{O}$ be an ontology, $\alpha$ a GCI, and
$\mathcal{C}\subseteq\mathcal{O}$ the core of $\alpha$ w.r.t. $\mathcal{O}$.
The procedure Union-of-All-Justifications computes the union of all
justifications of $\mathcal{O}$ w.r.t. $\alpha$.

Algorithm 3 terminates on any input as the paths in the module search tree
$\Psi$ for $\mathcal{O}$ that is constructed during the execution represent
all the permutations of the axioms in $\mathcal{O}$ that are relevant for
finding all minimal modules. It is easy to see that the procedure Union-of-
All-Justifications runs in exponential time in size of $\mathcal{O}$ (and
polynomially in $\Sigma$, $n$, and $\mathcal{C}$) in the worst case.

###  4.2 MUS Membership Problem

We now show how to compute the union of all justifications of a GCI $\alpha$
by a membership approach. The idea is to check the membership of each axiom,
i.e., whether it is a member of some justification. The main procedure is:
firstly, as a pre-processing step, we compute a CNF formula $\phi$ using the
consequence-based reasoner condor111We restrict to $\mathcal{ALC}$ in this
section as condor only accepts $\mathcal{ALC}$-TBoxes. proposed in [9]. Then,
we compute the union of all justifications of $\alpha\in\mathcal{O}$ by
checking the membership for each axiom using the SAT-tool cmMUS [16] and
$\phi$. In generally, the classification of an $\mathcal{ALC}$-TBox is of
exponential complexity. Since the MUS-membership problem is
$\Sigma_{2}^{P}$-complete [22], it follows that this method runs in
exponential time.

Specifically, the method is divided in two steps:

  1. 1.

Compute CNF formula $\phi$. Let $H,K$ denote (possibly empty) conjunctions of
concepts, and $M,N$ (possibly empty) disjunctions of concepts; condor
classifies the TBox through the inference rules in Table 1.

Table 1: Inference rules of condor
$\displaystyle\mathbf{R^{+}_{A}}~{}\frac{}{H\sqsubseteq A}:A\sqsubseteq
H~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\mathbf{R^{-}_{A}}~{}\frac{H\sqsubseteq
N\sqcup A}{H\sqsubseteq N}:\neg A\sqsubseteq H$
$\displaystyle\mathbf{R^{+}_{A}}~{}\frac{\\{H\sqsubseteq N_{i}\sqcup
A_{i}\\}_{i=1}^{n}}{H\sqsubseteq\sqcup_{i=1}^{n}N_{i}\sqcup
M}:\sqcap_{i=1}^{n}A_{i}\sqsubseteq M\in\mathcal{O}$
$\displaystyle\mathbf{R^{n}_{\sqcap}}~{}\frac{H\sqsubseteq N\sqcup
A}{H\sqsubseteq N\sqcup\exists R.B}:A\sqsubseteq\exists R.B\in\mathcal{O}$
$\displaystyle\mathbf{R^{+}_{\exists}}~{}\frac{H\sqsubseteq M\sqcup\exists
R.K,K\sqsubseteq N\sqcup A}{H\sqsubseteq M\sqcup B\sqcup\exists R(K\sqcap\neg
A)}:\exists R.A\sqsubseteq B\in\mathcal{O},\mathcal{O}\models R\sqsubseteq S$
$\displaystyle\mathbf{R^{\perp}_{\exists}}~{}\frac{H\sqsubseteq M\sqcup\exists
R.K,K\sqsubseteq\perp}{H\sqsubseteq M}$
$\displaystyle\mathbf{R_{\forall}}~{}\frac{H\sqsubseteq M\sqcup\exists
R.K,K\sqsubseteq N\sqcup A}{H\sqsubseteq M\sqcup B\sqcup\exists R(K\sqcap
B)}:A\sqsubseteq\forall S.B\in\mathcal{O},\mathcal{O}\models R\sqsubseteq S$

Each inference rule can be rewritten as a clause. For example, the
$R^{+}_{\exists}$ can be transferred to $\neg p_{1}\vee\neg p_{2}\vee p_{3}$
if we denote the $H{\sqsubseteq}N{\sqcup}A,\ A{\sqcup}\exists R.B,\
H{\sqsubseteq}N{\sqcup}\exists R.B$ as literals $p_{1},p_{2},p_{3}$. Then the
CNF formula $\phi$ is the conjunction of all the clauses corresponding to all
the applied inference rules during the classification process. For details see
[29, 32].

  2. 2.

Check membership of each axiom using cmMUS. Given an CNF formula $\phi$ and a
subformula $\phi^{\prime}\subseteq\phi$, the algorithm cmMUS is used to
determine whether there is a MUS $\phi^{\prime\prime}\subseteq\phi$ such that
$\phi^{\prime}\cap\phi^{\prime\prime}\neq\emptyset$. We say
$\textit{cmMUS}(\phi,\phi^{\prime})=1$ if there exists such MUS
$\phi^{\prime\prime}$ and $0$ otherwise. The membership is checked as follows:

    1. (a)

Define a CNF-formula
$\phi_{\mathcal{O}}=\wedge_{\beta\in\mathcal{O}}p_{\beta}$, where each literal
$p_{\beta}$ corresponds to an axiom $\beta\in\mathcal{O}$, and
$\phi_{\alpha}=\neg p_{\alpha}$, where $\alpha$ is the given conclusion.

    2. (b)

Define $\psi_{\alpha}=\phi\wedge\phi_{\mathcal{O}}\wedge\phi_{\alpha}$. Then
$\psi_{\alpha}$ is unsatisfiable; each MUS
$\psi^{\prime}\subseteq\psi_{\alpha}$ corresponds to a justification of
$\alpha$; and $\forall\beta\in\mathcal{O}$,
$\textit{cmMUS}(\psi_{\alpha},p_{\beta})=1$ iff $\beta$ belongs to some
justifications of $\alpha$.

Note that only a small number of clauses in $\phi$ are related to the
derivation of $\alpha$. In practice, (i) $\phi^{\prime}\subseteq\phi$ is the
subformula contributing to the derivation of $\alpha$ obtained by tracing back
from $\alpha$, (ii) $\phi_{\mathcal{O}}^{\prime}\subseteq\phi_{\mathcal{O}}$
is the subformula including only $\beta\in\mathcal{O}$ that appears in
$\phi^{\prime}$. Using
$\psi_{\alpha}^{\prime}=\phi^{\prime}\wedge\phi_{\mathcal{O}}^{\prime}\wedge\phi_{\alpha}$
instead of $\psi_{\alpha}$ as the input of algorithm cmMUS can significantly
accelerate the cmMUS algorithm.

##  5 Repairing Ontologies

In this section we propose a notion of optimal repair and provide a method for
computing all such optimal repairs.

######  Definition 2 (Optimal Repair)

Let $\mathcal{O}$ be an ontology, $\alpha$ a GCI, and
$\mathrm{Rep}(\mathcal{O},\alpha)$ the set of all repairs for
$\mathcal{O}\models\alpha$. We say
$\mathcal{R}\in\mathrm{Rep}(\mathcal{O},\alpha)$ is an _optimal repair_ for
$\mathcal{O}\models\alpha$, if $|\mathcal{R}|\geq|\mathcal{R}^{\prime}|$ holds
for every $\mathcal{R}^{\prime}\in\mathrm{Rep}(\mathcal{O},\alpha)$.

That is, an optimal repair is a repair such that removes the least amount of
axioms from the original ontology. It is also important to recall the notion
of a hitting set

######  Definition 3 (HS)

We say $\mathcal{S}$ is a minimal _hitting set_ for a sets $\mathbb{S}$ if
$\mathcal{S}\cap s\neq\emptyset$ for every $s\in\mathbb{S}$.

We say $\mathcal{S}$ is the smallest minimal hitting set if $|s|$ is the
smallest among all minimal hitting set. The following proposition shows how we
can compute the set of all optimal repairs through a hitting set computation
[31, 23, 6].

###### Proposition 1

Let $\mathrm{Just}(\mathcal{O},\alpha)$ be the set of all justifications for
the GCI $\alpha$ w.r.t. the ontology $\mathcal{O}$. If $\mathbb{S}$ is the set
of all smallest minimal hitting sets for $\mathrm{Just}(\mathcal{O},\alpha)$,
then $\\{\mathcal{O}\setminus\mathcal{S}\mid\mathcal{S}\in\mathbb{S}\\}$ is
the set of all optimal repairs for $\mathcal{O}\models\alpha$.

When the core is not empty, a set that consists of only one axiom from the
intersection of all justifications is a smallest hitting set for all
justifications. We get the following corollary, stating how to compute all
optimal repairs faster in this case, as a simple consequence of Proposition 1.

###### Corollary 2

Let $\mathcal{O}$ be an ontology, $\alpha$ a GCI and $\mathcal{C}$ the core
for $\mathcal{O}\models\alpha$. If $\mathcal{C}\neq\emptyset$, then
$\\{\mathcal{O}\backslash\\{\beta\\}\mid\beta\in\mathcal{C}\\}$ is the set of
all optimal repairs for $\mathcal{O}\models\alpha$.

The application of the union of all justifications can be used as a step
towards deducing IAR entailments [28].

##  6 Evaluation

To evaluate the performance of our algorithms in real-world ontologies, we
built a prototypical implementation. The black-box algorithm is implemented in
Java and uses the OWL API [15] to access ontologies and HermiT [14] as a
standard reasoner. The MUS-membership algorithm (MUS-MEM) is implemented in
Python and calls cmMUS [16] to detect whether a clause is a member of MUSes.
The ontologies used in the evaluation come from the classification task at the
ORE competition 2014 [25]. Among them, we selected the ontologies that have
less than 10,000 axioms, for a total of 95 ontologies. In the experiments, we
computed a single justification, the intersection and union of all
justifications for all atomic concept inclusions that are entailed by the
ontologies.222An atomic concept inclusion is the inclusion that in the form of
$A\sqsubseteq B$, where $A$ and $B$ are concept names. All experiments ran on
two processors Intel® Xeon® E5-2609v2 2.5GHz, 8 cores, 64Go, Ubuntu 18.04. All
the figures in this section plot the logarithmic computation time (in the
vertical axis) of each test instance (in the horizontal axis).

Figure 1: Computation time of $\mathcal{C}$ vs $\mathcal{J}$

|  $\mathcal{J}$ |  $\mathcal{C}$
---|---|---
min | 0.001s | 0.001s
max | 226.608s |  341.560s
mean | 0.400s | 0.456s
median | 0.009s | 0.002s

Figure 2: Statistics of Fig. 2

#### Computation time of the core vs. a single justification.

Fig. 2 compares the time to compute the core against computing a single
justification. The instances in the horizontal axis are ordered according to
the single-justification computation time, represented by the black line.
Orange dots represent the core computation time through Algorithm 1. Table 2
provides some basic statistics for comparison. Generally, computing the core
is almost as fast as computing one justification as expected. Note that, in
terms of computational complexity computing the core and one justification are
equally hard problems, the size of the remaining ontology reduces during the
latter process. Intuitively, if $\mathcal{O}^{\prime}\subseteq\mathcal{O}$,
checking whether a subsumption is satisfied by $\mathcal{O}^{\prime}$ would be
faster than checking it on $\mathcal{O}$.

#### Computation time of the union of all justifications.

As a benchmark, we use OWL API to compute all justifications and then get the
union. As our second algorithm could compute the union of all justifications
only for ${\cal ALC}$-ontologies, we separate our ontologies into two
categories: one is ${\cal ALC}$-ontologies and the other one is the ontologies
that are more expressive than ${\cal ALC}$. The computation time for the union
of all justifications for ${\cal ALC}$-ontologies is shown in Fig. 6 (the
cases with several justifications) and Fig. 6 (the cases with only one
justification). Figs. 6 and 6 show the computation time of the union of all
justifications for more expressive ontologies when there exists multiple
justifications and only one justification respectively. In Figs. 6–6, each
blue, green or red dot corresponds to computation time of the union by OWL
API, the black-box algorithm or the MUS-MEM algorithm for a conclusion
respectively. We order the conclusions along the X-axis by increasing order of
computation time of MUS-MEM algorithms in Figs. 6 and Fig. 6, and by the
black-box performance in the latter two figures. We observe from these plots
that the black-box algorithm outperforms other methods, and when available,
MUS-MEM tends to perform better than a direct use of the OWL API.

Figure 3: Computation time of the union for ${\cal ALC}$-ontologies when there
exist several justifications

Figure 4: Computation time of the union for ${\cal ALC}$-ontologies when there
exists one justification

Figure 5: Computation time of the union for more expressive ontologies when
there exist several justifications

Figure 6: Computation time of the union for more expressive ontologies when
there exists one justification

Figure 7: Ratio of $|\mathcal{C}|$ to a random $|\mathcal{J}|$ (left) and
ratio of $|\mathcal{C}|$ to $|\mathcal{U}|$ (right).

#### Size comparisons for justifications, cores, and unions of justifications.

Fig. 7 illustrates the ratio of the size of the core to the size of a random
justification and to the size of the union of all justifications. In our
experiments, the intersection of all justifications for only 2.35%
subsumptions is empty, which means that we could use Corollary 2 to compute
optimal repairs for 97.65% of the cases. Moreover, for more than 85% cases,
the size of a justification ($|\mathcal{J}|$) equals to the size of the core
($|\mathcal{C}|$), which indicates that there exists only one justification.
When several justifications exist (the second chart from the left of Fig. 7),
the ratio of $|\mathcal{C}|$ to a random $|\mathcal{J}|$ falls between 50% to
75% for almost half of the cases. The right-most chart displays the
distribution of the ratio of $|\mathcal{C}|$ to the union of all
justifications $\mathcal{U}$ when there exist multiple justifications. The
ratio distributes quite evenly between 0% (not including) to 75%.
Interestingly, the intersection of all justifications is empty for only 16%
subsumptions even when several justifications exist.

##  7 Conclusions

In this paper, we presented algorithms for computing the core (that is, the
intersection of all justifications) and the union of all justifications for a
given DL consequence. Most of the algorithms are based on repeated calls to a
(black-box) reasoner, and hence apply for ontologies and consequences of any
expressivity, as long as a reasoner exists. The only exception is a MUS-based
approach for computing the union of all justifications, which depends on the
properties of the ${\cal ALC}$ consequence-based method implemented by
_condor_. Still, the approach should be generalisable without major problems
to any language for which consequence-based reasoning methods exists like, for
instance, $\mathcal{SROIQ}$ [13, 12].

As an application of our work, we study how to find optimal repairs
effectively, through the information provided by the core and the union of all
justifications. Through an empirical analysis, run over more than 100,000
consequences from almost a hundred ontologies from the ORE 2014 competition we
observe that our methods behave better in practice than the usual approach
through the OWL API. A more detailed analysis of the experimental results is
left for future work.

Our experiments also confirm an observation that has already been made for
light-weight ontologies [33], and to a smaller degree in the ontologies from
the BioPortal corpus [8]; namely, that consequences tend to have one, or only
a few, overlapping justifications. In our case, we exploit this fact, and the
efficient core computation algorithm to find optimal repairs in more than 97%
of the test instances: those with exactly one justification, where removing
any axioms from it leads to an optimal repair.

## References

  * [1] M. F. Arif, C. Mencía, A. Ignatiev, N. Manthey, R. Peñaloza, and J. Marques-Silva.  Beacon: An efficient sat-based tool for debugging $\mathcal{EL}$${}^{\mbox{+}}$ ontologies.  In International Conference on Theory and Applications of Satisfiability Testing, pages 521–530. Springer, 2016.
  * [2] M. F. Arif, C. Mencía, and J. Marques-Silva.  Efficient axiom pinpointing with EL2MCS.  In Joint German/Austrian Conference on Artificial Intelligence (Künstliche Intelligenz), pages 225–233. Springer, 2015.
  * [3] M. F. Arif, C. Mencía, and J. Marques-Silva.  Efficient MUS enumeration of Horn formulae with applications to axiom pinpointing.  In International Conference on Theory and Applications of Satisfiability Testing, pages 324–342. Springer, 2015.
  * [4] F. Baader and B. Hollunder.  Embedding defaults into terminological knowledge representation formalisms.  Journal of Automated Reasoning, 14(1):149–180, 1995.
  * [5] F. Baader and R. Peñaloza.  Automata-based axiom pinpointing.  J. Autom. Reason., 45(2):91–129, 2010.
  * [6] F. Baader and R. Peñaloza.  Axiom pinpointing in general tableaux.  J. Log. Comput., 20(1):5–34, 2010.
  * [7] F. Baader, R. Peñaloza, and B. Suntisrivaraporn.  Pinpointing in the description logic EL+.  In J. Hertzberg, M. Beetz, and R. Englert, editors, Proceedings of the 30th Annual German Conference on AI, KI 2007, volume 4667 of Lecture Notes in Computer Science, pages 52–67. Springer, 2007.
  * [8] S. P. Bail.  The justificatory structure of OWL ontologies.  PhD thesis, University of Manchester, UK, 2013.
  * [9] A. Bate, B. Motik, B. C. Grau, D. T. Cucala, F. Simančík, and I. Horrocks.  Consequence-based reasoning for description logics with disjunctions and number restrictions.  J. Artif. Int. Res., 63(1):625–690, Sept. 2018.
  * [10] C.-L. Chang and R. C.-T. Lee.  Symbolic logic and mechanical theorem proving.  Academic press, 2014.
  * [11] J. Chen, M. Ludwig, Y. Ma, and D. Walther.  Zooming in on ontologies: Minimal modules and best excerpts.  In Proc. of ISWC’17, Part I, volume 10587 of Lecture Notes in Computer Science, pages 173–189. Springer, 2017.
  * [12] D. T. Cucala, B. C. Grau, and I. Horrocks.  Consequence-based reasoning for description logics with disjunction, inverse roles, number restrictions, and nominals.  In J. Lang, editor, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, pages 1970–1976. ijcai.org, 2018.
  * [13] D. T. Cucala, B. C. Grau, and I. Horrocks.  Sequoia: A consequence based reasoner for SROIQ.  In M. Simkus and G. E. Weddell, editors, Proceedings of the 32nd International Workshop on Description Logics, volume 2373 of CEUR Workshop Proceedings. CEUR-WS.org, 2019.
  * [14] B. Glimm, I. Horrocks, B. Motik, G. Stoilos, and Z. Wang.  HermiT: an OWL 2 reasoner.  Journal of Automated Reasoning, 53(3):245–269, 2014.
  * [15] M. Horridge and S. Bechhofer.  The OWL API: A Java API for OWL ontologies.  Semantic Web, 2(1):11–21, 2011.
  * [16] M. Janota and J. Marques-Silva.  cmMUS: A tool for circumscription-based mus membership testing.  In International Conference on Logic Programming and Nonmonotonic Reasoning, pages 266–271. Springer, 2011.
  * [17] A. Kalyanpur, B. Parsia, M. Horridge, and E. Sirin.  Finding all justifications of OWL DL entailments.  In Proceedings of ISWC 2007 & ASWC 2007, volume 4825 of LNCS, pages 267–280. Springer, 2007.
  * [18] A. Kalyanpur, B. Parsia, E. Sirin, and J. Hendler.  Debugging unsatisfiable classes in OWL ontologies.  Journal of Web Semantics, 3(4):268–293, 2005.
  * [19] A. A. Kalyanpur.  Debugging and repair of OWL ontologies.  PhD thesis, 2006.
  * [20] Y. Kazakov and P. Skočovskỳ.  Enumerating justifications using resolution.  In International Joint Conference on Automated Reasoning, pages 609–626. Springer, 2018.
  * [21] P. Koopmann and J. Chen.  Deductive module extraction for expressive description logics.  In C. Bessiere, editor, Proceedings of IJCAI’20, pages 1636–1643. ijcai.org, 2020.
  * [22] P. Liberatore.  Redundancy in logic i: Cnf propositional formulae.  Artificial Intelligence, 163(2):203–232, 2005.
  * [23] M. H. Liffiton and K. A. Sakallah.  On finding all minimally unsatisfiable subformulas.  In F. Bacchus and T. Walsh, editors, Proceedings of the 8th International Conference on Theory and Applications of Satisfiability Testing (SAT 2005), volume 3569 of Lecture Notes in Computer Science, pages 173–186. Springer, 2005.
  * [24] N. Manthey, R. Peñaloza, and S. Rudolph.  Efficient axiom pinpointing in EL using sat technology.  In Description Logics, 2016.
  * [25] B. Parsia, N. Matentzoglu, R. S. Gonçalves, B. Glimm, and A. Steigmiller.  The OWL reasoner evaluation (ORE) 2015 competition report.  Journal of Automated Reasoning, pages 1–28, 2015.
  * [26] B. Parsia, E. Sirin, and A. Kalyanpur.  Debugging owl ontologies.  In Proceedings of the 14th international conference on World Wide Web, pages 633–640, 2005.
  * [27] R. Peñaloza.  Axiom pinpointing.  In G. Cota, M. Daquino, and G. L. Pozzato, editors, Applications and Practices in Ontology Design, Extraction, and Reasoning, volume 49 of Studies on the Semantic Web, pages 162–177. IOS Press, 2020.
  * [28] R. Peñaloza.  Error-tolerance and error management in lightweight description logics.  Künstliche Intell., 34(4):491–500, 2020.
  * [29] R. Peñaloza, C. Mencía, A. Ignatiev, and J. Marques-Silva.  Lean kernels in description logics.  In E. Blomqvist, D. Maynard, A. Gangemi, R. Hoekstra, P. Hitzler, and O. Hartig, editors, Proceeding of ESWC’17, volume 10249 of Lecture Notes in Computer Science, pages 518–533, 2017.
  * [30] R. Reiter.  A theory of diagnosis from first principles.  Artificial Intelligence, 32(1):57–95, 1987.
  * [31] S. Schlobach and R. Cornet.  Non-standard reasoning services for the debugging of description logic terminologies.  In G. Gottlob and T. Walsh, editors, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, pages 355–362. Morgan Kaufmann, 2003.
  * [32] R. Sebastiani and M. Vescovi.  Axiom pinpointing in lightweight description logics via Horn-SAT encoding and conflict analysis.  In R. A. Schmidt, editor, Proceedings of the 22nd International Conference on Automated Deduction, volume 5663 of Lecture Notes in Computer Science, pages 84–99. Springer, 2009.
  * [33] B. Suntisrivaraporn.  Polynomial time reasoning support for design and maintenance of large-scale biomedical ontologies.  PhD thesis, Dresden University of Technology, Germany, 2009.
  * [34] B. Suntisrivaraporn, G. Qi, Q. Ji, and P. Haase.  A modularization-based approach to finding all justifications for OWL DL entailments.  In J. Domingue and C. Anutariya, editors, The Semantic Web, pages 1–15, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.


# The quantum query complexity of composition with a relation

Aleksandrs Belovs Faculty of Computing, University of Latvia. Email:
<EMAIL_ADDRESS>Troy Lee Centre for Quantum Software and Information,
University of Technology Sydney. Email<EMAIL_ADDRESS>
###### Abstract

The negative weight adversary method, $\mathrm{ADV}^{\pm}(g)$, is known to
characterize the bounded-error quantum query complexity of any Boolean
function $g$, and also obeys a perfect composition theorem
$\mathrm{ADV}^{\pm}(f\circ g^{n})=\mathrm{ADV}^{\pm}(f)\mathrm{ADV}^{\pm}(g)$.
Belovs [Bel15b] gave a modified version of the negative weight adversary
method, $\mathrm{ADV}_{rel}^{\pm}(f)$, that characterizes the bounded-error
quantum query complexity of a relation $f\subseteq\\{0,1\\}^{n}\times[K]$,
provided the relation is efficiently verifiable. A relation is efficiently
verifiable if $\mathrm{ADV}^{\pm}(f_{a})=o(\mathrm{ADV}_{rel}^{\pm}(f))$ for
every $a\in[K]$, where $f_{a}$ is the Boolean function defined as $f_{a}(x)=1$
if and only if $(x,a)\in f$. In this note we show a perfect composition
theorem for the composition of a relation $f$ with a Boolean function $g$

$\mathrm{ADV}_{rel}^{\pm}(f\circ
g^{n})=\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)\enspace.$

For an efficiently verifiable relation $f$ this means $Q(f\circ
g^{n})=\Theta(\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g))$.

##  1 Introduction

Quantum query complexity has been a very successful model for studying quantum
algorithms. The most famous quantum algorithms, like Grover’s search algorithm
[Gro96] and the period finding routine of Shor’s algorithm [Sho97], can be
formulated in this model, and the model has also been fruitful for developing
new algorithmic techniques like quantum walks [Amb07, Sze04, MSS07] and
learning graphs [Bel12b].

One of the greatest successes of quantum query complexity is the adversary
method. The (unweighted) adversary method began as a lower bound technique
developed by Ambainis [Amb02] to show a lower bound on the quantum query
complexity of the two-level AND-OR tree, among other problems. It was later
generalized to a weighted version in various forms by several authors [Amb06,
Zha05, BSS03, LM08]. Špalek and Szegedy [SS06] showed that all of these
generalizations were in fact equivalent.

A strictly stronger bound called the negative weights adversary method,
$\mathrm{ADV}^{\pm}(f)$, was developed by Høyer et al. [HLŠ07]. In a wonderful
turn of events, a series of works by Reichardt et al. [RS12, Rei14, Rei11]
showed that the bounded-error quantum query complexity, $Q(f)$, of a Boolean
function $f$ satisfies $Q(f)=O(\mathrm{ADV}^{\pm}(f))$, and therefore
$\mathrm{ADV}^{\pm}(f)$ characterizes bounded-error quantum query complexity
up to a constant multiplicative factor.

This characterization has several interesting consequences. For one, it means
that upper bounds on quantum query complexity on a function $f$ can now be
shown by upper bounding $\mathrm{ADV}^{\pm}(f)$, which can be expressed as a
relatively simple semidefinite program. This approach has led to improved
algorithms for many problems of interest [Bel12a, Bel15a, LMS17], especially
via the development of the learning graphs model of Belovs [Bel12b].

Another consequence is that quantum query complexity inherits the nice
properties of the adversary bound. One of these nice properties is that the
adversary bound behaves perfectly with respect to _function composition_. For
Boolean functions $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and
$g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$ define the composition $h=f\circ g^{n}$
to be the function $h:\\{0,1\\}^{nm}\rightarrow\\{0,1\\}$ where for an input
$x=(x_{1},\ldots,x_{n})\in\\{0,1\\}^{nm}$, with each $x_{i}\in\\{0,1\\}^{m}$,
we have $h(x)=f(g(x_{1}),\ldots,g(x_{n}))$. [HLŠ07] showed that
$\mathrm{ADV}^{\pm}(h)\geq\mathrm{ADV}^{\pm}(f)\mathrm{ADV}^{\pm}(g)$, and
[Rei14] showed a matching upper bound.

######  Theorem 1 ([HLŠ07, Rei14]).

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and
$g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$.

$\mathrm{ADV}^{\pm}(f\circ
g^{n})=\mathrm{ADV}^{\pm}(f)\mathrm{ADV}^{\pm}(g)\enspace.$

This perfect composition theorem was later extended by [LMR+11] to allow $g$
to be a partial Boolean function and allow the range of $f$ to be non-Boolean.
Kimmel [Kim13] showed a perfect composition theorem where both $f$ and $g$
were allowed to be partial Boolean functions. Thus here the domain of
$h=f\circ g^{n}$ is only those $x=(x_{1},\ldots,x_{n})$ where
$(g(x_{1}),\ldots,g(x_{n}))$ is in the domain of $f$.

Extensions of the negative weight adversary method have been given for the
more general query complexity problem of _state generation_ [Shi02, AMRR11,
LMR+11]. In this problem, on input $x$ the algorithm begins in the state
$|0\rangle|0\rangle$ as usual but now the goal is to transform this state into
the state $|\sigma_{x}\rangle|0\rangle$ for some target vector
$|\sigma_{x}\rangle$ by making queries to $x$. Lee et al. [LMR+11] have shown
that an extension of the negative weight adversary method called the filtered
$\gamma_{2}$ norm gives a _semi-tight_ characterization of the quantum query
complexity of the state conversion problem. It is semi-tight because a
slightly larger error is needed in the upper bound than in the lower bound.

Belovs [Bel15b] used this characterization to give a modified adversary bound,
$\mathrm{ADV}_{rel}^{\pm}(f)$, that characterizes the quantum query complexity
of a relation $f\subseteq\\{0,1\\}^{n}\times[K]$, provided the relation is
_efficiently verifiable_. Intuitively, a relation is efficiently verifiable if
given $a$ the complexity of checking if $(x,a)$ is in the relation is low-
order compared to $\mathrm{ADV}_{rel}^{\pm}(f)$; the formal definition is
given in Definition 15. For an efficiently verifiable relation the success
probability of an algorithm can be amplified without increasing the order of
the complexity, getting around the semi-tightness of the [LMR+11]
characterization.

In this work, we show a perfect composition theorem
$\mathrm{ADV}_{rel}^{\pm}(f\circ
g^{n})=\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)$ for the composition
of a relation $f\subseteq\\{0,1\\}^{n}\times[K]$ with Boolean function $g$. If
$f$ is efficiently verifiable this implies that $Q(f\circ
g^{n})=\Theta(\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g))$. The lower-
bound part of this theorem was required to show a lower bound on the runtime
of a quantum algorithm constructing a cut sparsifier of a graph [AdW19]. The
perfect adversary composition theorem for functions has been a very useful
tool, both for constructing algorithms and showing lower bounds, and we
believe our composition theorem for relations will find additional
applications as well.

##  2 Preliminaries

For a positive integer $m$ we let $[m]=\\{1,\ldots,m\\}$. For two matrices
$A,B$ of the same size, $A\circ B$ denotes the Hadamard or entrywise product:
$(A\circ B)(x,y)=A(x,y)B(x,y)$. We use $\|A\|$ to denote the spectral norm of
a matrix $A$ and $\|A\|_{tr}$ to denote the trace norm. For a symmetric matrix
$A$, we use $\lambda_{max}(A)$ and $\lambda_{min}(A)$ to denote the largest
and smallest eigenvalues of $A$, respectively. We use $I_{n}$ for the
$n$-by-$n$ identity matrix, and drop the subscript when the dimension is
implied from context. For a vector $v\in\mathbb{R}^{n}$ and natural numbers
$a\leq b$ we let $v(a:b)\in\mathbb{R}^{b-a+1}$ be the vector
$(v(a),v(a+1),\ldots,v(b))$.

We will need a few simple facts about positive semidefinite matrices. First,
if $A,B\succeq 0$, then $A\otimes B\succeq 0$. Also, a principal submatrix of
a positive semidefinite matrix is positive semidefinite. A matrix $\tilde{A}$
obtained from $A$ by duplicating rows and columns is again positive
semidefinite. The last two facts follow from the following more general
observations:

######  Fact 2.

Let $A\succeq 0$ be an $M$-by-$M$ matrix, and $h\colon[N]\to[M]$ a function.
Then the $N$-by-$N$ matrix $\tilde{A}$ defined by
$\tilde{A}(x,y)=A(h(x),h(y))$ is also positive semidefinite.

######  Fact 3.

If $A,B$ are the same size and $A\succeq 0,B\succeq 0$ then $A\circ B\succeq
0$. Similarly, if $A\succeq 0,B\preceq 0$ then $A\circ B\preceq 0$.

######  Fact 4.

Let $A$ be a symmetric matrix. Then $\lambda_{max}(A)\cdot I\succeq
A\succeq\lambda_{min}(A)\cdot I$. In particular, $\lambda_{max}(A)\geq
v^{T}Av\geq\lambda_{min}(A)$ for any unit vector $v$.

###  2.1 Quantum query complexity

The bounded-error quantum query complexity of the function
$g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, denoted $Q(g)$, is the minimum number
of queries needed by a quantum algorithm that outputs $g(x)$ with probability
at least $2/3$ for every input $x\in\\{0,1\\}^{n}$. Let $K$ be a positive
integer and $f\subseteq\\{0,1\\}^{n}\times[K]$ be a relation. We say that a
quantum algorithm computes $f$ if for every $x\in\\{0,1\\}^{n}$ the algorithm
outputs an $a\in[K]$ such that $(x,a)\in f$ with probability at least $2/3$.
We let $Q(f)$ denote the minimum cost of a quantum query algorithm that
computes $f$.

We will always assume that for every $x\in\\{0,1\\}^{n}$ there exists
$a\in[K]$ such that $(x,a)\in f$. This assumption is without loss of
generality as if $f$ defined on a strict subset $S$ of $\\{0,1\\}^{n}$ we can
consider instead $f^{\prime}$ which is defined as $f$ together with every pair
$(x,a)\in(\\{0,1\\}^{n}\setminus S)\times[K]$. In this way any algorithm that
computes $f$ on $S$ also computes $f^{\prime}$ on $\\{0,1\\}^{n}$, as any
output is accepted for inputs not in $S$.

###  2.2 Adversary bound

######  Definition 5 (Adversary matrix for a function).

Let $g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a Boolean function. Let
$\Gamma_{g}\in\mathbb{R}^{2^{n}\times 2^{n}}$, with rows and columns labeled
by elements of $\\{0,1\\}^{n}$. We say that $\Gamma_{g}$ is a functional
adversary matrix for $g$ iff $\Gamma_{g}$ is symmetric and $\Gamma_{g}(x,y)=0$
for all $x,y$ such that $g(x)=g(y)$.

Up to a permutation of rows and columns, we may always assume that the first
$|g^{-1}(0)|$ rows and columns of a functional adversary matrix $\Gamma_{g}$
are labeled by elements of $g^{-1}(0)$. Then there is a
$|g^{-1}(0)|$-by-$|g^{-1}(1)|$ matrix $Z$ such that

$\Gamma_{g}=\begin{bmatrix}0&Z\\\ Z^{T}&0\end{bmatrix}\enspace.$

In this paper we always assume that adversary matrices for functions are
presented in this form.

######  Definition 6 (Functional adversary bound [HLŠ07]).

Let $g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a Boolean function. For
$i\in[n]$, let $D_{i}$ be a $2^{n}$-by-$2^{n}$ Boolean matrix where
$D_{i}(x,y)=1$ iff $x_{i}\neq y_{i}$. The adversary bound
$\mathrm{ADV}^{\pm}(g)$ for $g$ is defined as

$\displaystyle\mathrm{ADV}^{\pm}(g)=$
$\displaystyle\underset{\Gamma}{\text{maximize}}$ $\displaystyle\|\Gamma\|$
subject to $\displaystyle\|\Gamma\circ D_{i}\|\leq 1\mbox{ for all
}i=1,\ldots,n$ $\displaystyle\Gamma(x,y)=0\mbox{ for all
}x,y\in\\{0,1\\}^{n}\mbox{ with }g(x)=g(y)\enspace.$

We will also need the dual formulation of the adversary bound.

######  Theorem 7 ([LMR+11] Theorem 3.4).

Let $g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a Boolean function. Let
$\\{u_{x,i}\\},\\{v_{x,i}\\}$ be two families of vectors of arbitrary finite
dimension indexed by $x\in\\{0,1\\}^{n}$ and $i\in[n]$.

$\displaystyle\mathrm{ADV}^{\pm}(g)=$
$\displaystyle\underset{\\{u_{x,i}\\},\\{v_{x,i}\\}}{\text{minimize}}$
$\displaystyle\max\left\\{\max_{x\in\\{0,1\\}^{n}}\sum_{i\in[n]}\|u_{x,i}\|^{2},\max_{x\in\\{0,1\\}^{n}}\sum_{i\in[n]}\|v_{x,i}\|^{2}\right\\}$
subject to $\displaystyle\sum_{i:x_{i}\neq y_{i}}\langle
u_{x,i},v_{y,i}\rangle=\begin{cases}1&\mbox{ if }g(x)\neq g(y)\\\ 0&\mbox{ if
}g(x)=g(y)\end{cases}\mbox{ for all }x,y\in\\{0,1\\}^{n}$

If one simply takes the dual of Definition 6 one gets the above optimization
problem without the constraint on $x,y$ pairs where $g(x)=g(y)$. These
additional constraints are needed to show the upper bound in the composition
theorem, and [LMR+11] show they can be added without increasing the objective
value of the program.

The functional adversary bound characterizes the bounded-error quantum query
complexity of any function $g$. The lower bound is due to Høyer et al. [HLŠ07]
and the upper bound due to Reichardt [Rei11].

######  Theorem 8 ([HLŠ07],[Rei11]).

Let $g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a Boolean function. Then
$Q(g)=\Theta(\mathrm{ADV}^{\pm}(g))$

##  3 Adversary bound for relations

Belovs [Bel15b] developed a modification, $\mathrm{ADV}_{rel}^{\pm}(f)$, of
the adversary bound that relates to the bounded-error quantum query complexity
of a relation $f\subseteq\\{0,1\\}^{n}\times[K]$. To motivate this bound, we
first review the _state generation_ problem [Shi02, AMRR11, LMR+11]. A state
generation problem is specified by a family of vectors
$|\sigma_{x}\rangle\in\mathbb{R}^{M}$ for each $x\in\\{0,1\\}^{n}$. On input
$x$ the algorithm begins in the state $|0\rangle|0\rangle$ and the goal is for
the algorithm to finish in the target state $|\sigma_{x}\rangle|0\rangle$
after making as few queries to $x$ as possible.

Lee et al. [LMR+11] give the following definition and theorem.

######  Definition 9 (Filtered $\gamma_{2}$ norm).

Let $A$ be a $2^{n}$-by-$2^{n}$ matrix and $D=\\{D_{1},\ldots,D_{n}\\}$ where
each $D_{i}$ is a $2^{n}$-by-$2^{n}$ Boolean matrix defined as $D_{i}(x,y)=1$
iff $x_{i}\neq y_{i}$. Define

$\displaystyle\gamma_{2}(A|D)=$
$\displaystyle\underset{\\{u_{x,i}\\},\\{v_{x,i}\\}}{\text{minimize}}$
$\displaystyle\max\left\\{\max_{x\in\\{0,1\\}^{n}}\sum_{i\in[n]}\|u_{x,i}\|^{2},\max_{x\in\\{0,1\\}^{n}}\sum_{i\in[n]}\|v_{x,i}\|^{2}\right\\}$
subject to $\displaystyle\sum_{i\in[n]}\langle u_{x,i},v_{y,i}\rangle\cdot
D_{i}(x,y)=A(x,y)\mbox{ for all }x,y\in\\{0,1\\}^{n}$

######  Theorem 10 ([LMR+11]).

Let $M,n$ be positive integers and
$\\{|\sigma_{x}\rangle\\}_{x\in\\{0,1\\}^{n}}$ be a family of vectors with
each $|\sigma_{x}\rangle\in\mathbb{R}^{M}$. Let $A$ be a $2^{n}$-by-$2^{n}$
matrix where $A(x,y)=1-\langle\sigma_{x}|\sigma_{y}\rangle$ for all
$x,y\in\\{0,1\\}^{n}$. Let $D=\\{D_{1},\ldots,D_{n}\\}$ where each $D_{i}$ is
a $2^{n}$-by-$2^{n}$ Boolean matrix defined as $D_{i}(x,y)=1$ iff $x_{i}\neq
y_{i}$. For any $0<\epsilon<\gamma_{2}(A|D)$ there is a quantum algorithm that
for every $x\in\\{0,1\\}^{n}$ terminates in a state
$|\sigma_{x}^{\prime}\rangle$ satisfying
$\langle\sigma_{x}^{\prime}|(|\sigma_{x}\rangle\otimes|0\rangle)\geq\sqrt{1-\epsilon}$
after making $O(\gamma_{2}(A|D)\frac{\log(1/\epsilon)}{\epsilon^{2}})$ many
queries to $x$.

In computing a relation $f\subseteq\\{0,1\\}^{n}\times[K]$, there is not a
fixed ideal target state; rather the algorithm has the freedom to optimize
over a set of target states which we call perfect target states for $f$.

######  Definition 11 (Perfect target states).

Let $f\subseteq\\{0,1\\}^{n}\times[K]$ and
$\\{|\psi_{x}\rangle\\}_{x\in\\{0,1\\}^{n}}$ a family of unit vectors. We say
that $\\{|\psi_{x}\rangle\\}_{x\in\\{0,1\\}^{n}}$ are _perfect target states_
for $f$ if there exists a complete family of orthogonal projectors
$\\{\Pi_{a}\\}_{a\in[K]}$ such that each $|\psi_{x}\rangle$ can be decomposed
as $|\psi_{x}\rangle=\sum_{a:(x,a)\in f}|\sigma_{x,a}\rangle$ for some (un-
normalized) vectors $|\sigma_{x,a}\rangle$ satisfying
$\Pi_{a}|\sigma_{x,a}\rangle=|\sigma_{x,a}\rangle$ for all $x,a$.

Let $\\{|\psi_{x}\rangle\\}_{x\in\\{0,1\\}^{n}}$ be a family of perfect target
states for $f$ and suppose there is a state generation algorithm that on input
$x$ terminates in the state $|\psi_{x}\rangle|0\rangle$ for every
$x\in\\{0,1\\}^{n}$. If the algorithm measures according to the projectors
$\\{\Pi_{a}\otimes I\\}_{a\in[K]}$, for the projectors
$\\{\Pi_{a}\\}_{a\in[K]}$ witnessing the perfection of
$\\{|\psi_{x}\rangle\\}_{x\in\\{0,1\\}^{n}}$, then for every $x$ it will
output an $a$ with $(x,a)\in f$ with certainty. This motivates studying the
optimization problem of minimizing the filtered $\gamma_{2}$ norm
$\gamma_{2}(1-[\langle\psi_{x}|\psi_{y}\rangle]_{x,y\in\\{0,1\\}^{n}}|D)$ over
all families of perfect target states
$\\{|\psi_{x}\rangle\\}_{x\in\\{0,1\\}^{n}}$ for $f$. This optimization
problem gives Belovs’ definition of the relational adversary bound.

######  Definition 12 ([Bel15b] Equation 20).

Let $f\subseteq\\{0,1\\}^{n}\times[K]$.

$\displaystyle\mathrm{ADV}_{rel}^{\pm}(f)=$
$\displaystyle\underset{\\{u_{x,i}\\},\\{v_{x,i}\\},\\{\sigma_{x,a}\\}}{\text{minimize}}$
$\displaystyle\max\left\\{\max_{x\in\\{0,1\\}^{n}}\sum_{i\in[n]}\|u_{x,i}\|^{2},\max_{x\in\\{0,1\\}^{n}}\sum_{i\in[n]}\|v_{x,i}\|^{2}\right\\}$
subject to $\displaystyle\sum_{i:x_{i}\neq y_{i}}\langle
u_{x,i},v_{y,i}\rangle=1-\sum_{a\in[K]}\langle\sigma_{x,a},\sigma_{y,a}\rangle\mbox{
for all }x,y\in\\{0,1\\}^{n}$ $\displaystyle\|\sigma_{x,a}\|^{2}=0\mbox{ for
all }x,a\mbox{ with }(x,a)\not\in f$

######  Theorem 13.

Let $f\subseteq\\{0,1\\}^{n}\times[K]$. Then
$Q(f)=O(\mathrm{ADV}_{rel}^{\pm}(f))$.

###### Proof.

Let $\\{|\sigma_{x,a}\rangle\\}_{x\in\\{0,1\\}^{n},a\in[K]}$ be part of an
optimal solution to the program for $\mathrm{ADV}_{rel}^{\pm}(f)$. Let $m_{a}$
be the dimension of $|\sigma_{x,a}\rangle$ and define
$|\psi_{x}\rangle=|\sigma_{x,1}\rangle\oplus\cdots\oplus|\sigma_{x,K}\rangle\in\mathbb{R}^{M}$
where $M=\sum_{a\in[K]}m_{a}$. For $a\in[K]$, let $s_{a}=\sum_{i<a}m_{i}$ and
define $\Pi_{a}=\sum_{i=s_{a}+1}^{s_{a}+m_{a}}|e_{i}\rangle\langle e_{i}|$,
where $|e_{i}\rangle$ is the $i^{th}$ standard basis vector. For
$A(x,y)=1-\langle\psi_{x}|\psi_{y}\rangle$ we have
$\gamma_{2}(A|D)=\mathrm{ADV}_{rel}^{\pm}(f)$. Therefore by applying Theorem
10 with $\epsilon=1/3$ there is a quantum algorithm that on input $x$
terminates in a state $|\psi_{x}^{\prime}\rangle$ satisfying
$\langle\psi_{x}^{\prime}|(|\psi_{x}\rangle\otimes|0\rangle)\geq\sqrt{1-\epsilon}$
after making $O(\mathrm{ADV}_{rel}^{\pm}(f))$ many queries. This implies
$\||\psi_{x}^{\prime}\rangle-|\psi_{x}\rangle|0\rangle\|^{2}\leq\epsilon$ and
so

$\displaystyle\epsilon$
$\displaystyle\geq\||\psi_{x}^{\prime}\rangle-|\psi_{x}\rangle|0\rangle\|^{2}$
$\displaystyle=\sum_{a\in[K]}\|(\Pi_{a}\otimes
I)|\psi_{x}^{\prime}\rangle-|\sigma_{x,a}\rangle\otimes|0\rangle\|^{2}$
$\displaystyle\geq\sum_{a:(x,a)\not\in f}\|(\Pi_{a}\otimes
I)|\psi_{x}^{\prime}\rangle\|^{2}$

Thus running the state generation algorithm for the states
$\\{|\psi_{x}\rangle\\}$ and measuring according to the projectors
$\\{\Pi_{a}\otimes I\\}_{a\in[K]}$ gives an algorithm with error probability
at most $\epsilon=1/3$ as desired. ∎

For the composition theorem we will also need the dual formulation of the
relational adversary bound from Definition 6.

######  Theorem 14 ([Bel15b] Equation 22).

Let $f\subseteq\\{0,1\\}^{n}\times[K]$ be a relation. For $i\in[n]$, let
$D_{i}$ be a $2^{n}$-by-$2^{n}$ Boolean matrix where $D_{i}(x,y)=1$ iff
$x_{i}\neq y_{i}$. For $a\in[K]$ let

$\chi_{a}(x)=\begin{cases}1&\mbox{ if }(x,a)\in f\\\ 0&\mbox{
otherwise.}\end{cases}$ (1)

Then

$\displaystyle\mathrm{ADV}_{rel}^{\pm}(f)=$
$\displaystyle\underset{\Gamma}{\text{maximize}}$
$\displaystyle\lambda_{max}(\Gamma)$ subject to $\displaystyle\|\Gamma\circ
D_{i}\|\leq 1\mbox{ for all }i=1,\ldots,n$
$\displaystyle\Gamma\circ\chi_{a}\chi_{a}^{T}\preceq 0\mbox{ for all
}a\in[K]\enspace.$

We will call a matrix $\Gamma$ satisfying
$\Gamma\circ\chi_{a}\chi_{a}^{T}\preceq 0$ for all $a\in[K]$ a relational
adversary matrix.

######  Definition 15 (Efficiently verifiable).

Let $K$ be a positive integer and $f\subseteq\\{0,1\\}^{n}\times[K]$ be a
relation. For each $a\in[K]$ define a Boolean function $f_{a}$ by $f_{a}(x)=1$
iff $(x,a)\in f$. We say that $f$ is _efficiently verifiable_ iff
$\mathrm{ADV}^{\pm}(f_{a})=o(\mathrm{ADV}_{rel}^{\pm}(f))$ for all $a\in[K]$.

Belovs [Bel15b] has shown that the relational adversary bound is also a lower
bound on the bounded-error quantum query complexity of a relation $f$ that is
efficiently verifiable.

######  Theorem 16 (Belovs [Bel15b] Theorem 40).

Let $f\subseteq\\{0,1\\}^{n}\times[K]$ be an efficiently verifiable relation.
Then $Q(f)=\Omega(\mathrm{ADV}_{rel}^{\pm}(f))$.

##  4 Composition Theorem

######  Definition 17.

Let $A$ be an $m$-by-$n$ matrix. Define

$\hat{A}=\begin{bmatrix}\|A\|I_{m}&A\\\
A^{T}&\|A\|I_{n}\end{bmatrix}\enspace.$ (2)

######  Lemma 18.

$\hat{A}$ is positive semidefinite for any $A$.

###### Proof.

The minimum eigenvalue of $A^{\prime}=\begin{bmatrix}0&A\\\
A^{T}&0\end{bmatrix}$ is $-\|A\|$ thus $\hat{A}=\|A\|I+A^{\prime}\succeq 0$ by
4. ∎

######  Definition 19 (Matrix Composition).

Let $N$ be a positive integer and let $B$ be a symmetric $2^{N}$-by-$2^{N}$
matrix. Let $A_{1},\ldots,A_{N}$ be matrices where $A_{i}$ is of size
$m_{i}$-by-$n_{i}$. Define the _matrix composition_ of $B$ with
$A_{1},\ldots,A_{N}$ to be a matrix $C$ of size $\prod_{i=1}^{N}(m_{i}+n_{i})$
with rows and columns labeled by elements of
$[m_{1}+n_{1}]\times\cdots\times[m_{N}+n_{N}]$. For
$a=(a_{1},\ldots,a_{N})\in[m_{1}+n_{1}]\times\cdots\times[m_{N}+n_{N}]$ define
$\tilde{a}\in\\{0,1\\}^{N}$ to be the string where $\tilde{a}_{i}=1$ if
$a_{i}>m_{i}$ and $\tilde{a}_{i}=0$ otherwise. Let $\tilde{B}$ be the matrix
of the same size as $C$ where $\tilde{B}(a,b)=B(\tilde{a},\tilde{b})$. Then

$C=\tilde{B}\circ(\otimes_{i=1}^{N}\hat{A}_{i})\enspace.$

######  Remark 20.

Each $A_{i}$ implicitly defines a function
$g_{i}:[m_{i}+n_{i}]\rightarrow\\{0,1\\}$ where $g_{i}(a)=1$ iff $a>m_{i}$.
Under this interpretation, the definition of $\tilde{a}$ arises naturally as
$\tilde{a}=(g_{1}(a_{1}),\ldots,g_{N}(a_{N}))$ for
$a=(a_{1},\ldots,a_{N})\in[m_{1}+n_{1}]\times\cdots\times[m_{N}+n_{N}]$.

Let $C$ be the matrix composition of $B$ with $A_{1},\ldots,A_{N}$. The key to
adversary composition theorems is the fact that
$\|C\|=\|B\|\cdot\prod_{i=1}^{N}\|A_{i}\|$, as originally shown in [HLŠ07]
Lemma 16. The statement we give here differs in two respects from the
statement given in [HLŠ07]. First, in [HLŠ07] the lemma was only stated for
$B$ restricted to be of the form

$B=\begin{bmatrix}0&Z\\\ Z^{T}&0\end{bmatrix}\enspace,$

for some matrix $Z$. To show the relational composition theorem we need to
allow an arbitrary symmetric matrix $B$. Second, as the objective function of
the relational adversary bound in Theorem 14 is in terms of $\lambda_{max}$ we
need a statement both about the spectral norm of $C$ and about
$\lambda_{max}(C)$. The proof given in [HLŠ07] can handle both of these
generalizations; the assumption about the structure of $B$ is not used and the
proof already determines the entire spectrum of $C$. Instead, however, we give
a new proof which is substantially shorter than the one from [HLŠ07].

######  Lemma 21.

Let $N$ be a positive integer. Let $B\in\mathbb{R}^{2^{N}\times 2^{N}}$ be a
symmetric matrix and $A_{1},\ldots,A_{N}$ be arbitrary matrices. If $C$ is the
matrix composition of $B$ with $A_{1},\ldots,A_{N}$ then

$\|C\|=\|B\|\cdot\prod_{i=1}^{N}\|A_{i}\|\qquad\mbox{ and
}\qquad\lambda_{max}(C)\geq\lambda_{max}(B)\cdot\prod_{i=1}^{N}\|A_{i}\|\enspace.$

###### Proof.

First we set up some notation which will be used for both the upper and lower
bounds of the proof. For $i=1,\ldots,N$ let $A_{i}$ be a $m_{i}$-by-$n_{i}$
matrix. Let
$\|A_{i}\|=\lambda^{(i)}_{1}\geq\cdots\geq\lambda^{(i)}_{m_{i}+n_{i}}$ be the
eigenvalues of the matrix $\begin{bmatrix}0&A_{i}\\\ A_{i}^{T}&0\end{bmatrix}$
and let $z^{(i)}_{1},\ldots,z^{(i)}_{m_{i}+n_{i}}$ be the corresponding
eigenvectors. Note that $z^{(i)}_{1},\ldots,z^{(i)}_{m_{i}+n_{i}}$ form an
orthonormal basis for $\mathbb{R}^{m_{i}+n_{i}}$. Finally, let
$z^{(i),0}_{j}=z^{(i)}_{j}(1:m_{i})$ and
$z^{(i),1}_{j}=z^{(i)}_{j}(m_{i}+1:m_{i}+n_{i})$, and for
$b_{1},b_{2}\in\\{0,1\\}$ define $\hat{A}_{i}^{(b_{1},b_{2})}$ by

$\begin{bmatrix}\hat{A}_{i}^{(0,0)}&\hat{A}_{i}^{(0,1)}\\\
\hat{A}_{i}^{(1,0)}&\hat{A}_{i}^{(1,1)}\end{bmatrix}=\begin{bmatrix}\|A_{i}\|I_{m_{i}}&A_{i}\\\
A_{i}^{T}&\|A_{i}\|I_{n_{i}}\end{bmatrix}\enspace.$

From the eigenvalue equation we see that
$A_{i}z^{(i),1}_{j}=\lambda^{(i)}_{j}z^{(i),0}_{j}$ and
$A_{i}^{T}z^{(i),0}_{j}=\lambda^{(i)}_{j}z^{(i),1}_{j}$. This means

$\lambda^{(i)}_{j}\|z^{(i),0}_{j}\|^{2}=(z^{(i),0}_{j})^{T}A_{i}z^{(i),1}_{j}=(z^{(i),1}_{j})^{T}A_{i}^{T}z^{(i),0}_{j}=\lambda^{(i)}_{j}\|z^{(i),1}_{j}\|^{2}$
(3)

and so $\|z^{(i),0}_{j}\|^{2}=\|z^{(i),1}_{j}\|^{2}=1/2$ whenever
$\lambda^{(i)}_{j}\neq 0$. Thus for $b_{1}\in\\{0,1\\}$ we can succinctly
write

$(z^{(i),b_{1}}_{j})^{T}\hat{A}_{i}^{(b_{1},1-b_{1})}z^{(i),1-b_{1}}_{j}=\lambda^{(i)}_{j}\|z^{(i),0}_{j}\|\|z^{(i),1}_{j}\|\enspace.$

These observations lead to the crucial fact we need, for
$b_{1},b_{2}\in\\{0,1\\}$

$z^{(i),b_{1}}_{j}\hat{A}_{i}^{(b_{1},b_{2})}z^{(i),b_{2}}_{k}=\begin{cases}0&\mbox{
if }j\neq k\\\ \|A_{i}\|\|z^{(i),b_{1}}_{j}\|^{2}&\mbox{ if
}j=k,b_{1}=b_{2}\\\ \lambda^{(i)}_{j}\|z^{(i),0}_{j}\|\|z^{(i),1}_{j}\|&\mbox{
if }j=k,b_{1}\neq b_{2}\end{cases}\enspace.$ (4)

We now turn to showing the most difficult part of the lemma, that
$\|C\|\leq\|B\|\cdot\prod_{i=1}^{N}\|A_{i}\|$. Let
$\psi_{j_{1},\ldots,j_{N}}=z^{(1)}_{j_{1}}\otimes\cdots\otimes
z^{(N)}_{j_{N}}$ where each $j_{i}\in[m_{i}+n_{i}]$. We compute

$\psi_{j_{1},\ldots,j_{N}}^{T}C\psi_{k_{1},\ldots,k_{N}}=\sum_{\alpha,\beta\in\\{0,1\\}^{N}}B(\alpha,\beta)\prod_{i\in[N]}z^{(i),\alpha_{i}}_{j_{i}}\hat{A}^{(\alpha_{i},\beta_{i})}z^{(i),\beta_{i}}_{k_{i}}\enspace.$
(5)

Suppose that $j_{i}\neq k_{i}$ for some $i$. Then by Eq. 4
$z^{(i),\alpha_{i}}_{j_{i}}\hat{A}^{(\alpha_{i},\beta_{i})}z^{(i),\beta_{i}}_{k_{i}}=0$
for all values of $\alpha_{i},\beta_{i}$. Thus
$\psi_{j_{1},\ldots,j_{N}}^{T}C\psi_{k_{1},\ldots,k_{N}}=0$ unless
$j_{i}=k_{i}$ for all $i=1,\ldots,N$.

Let us now consider the value in this case. For $i=1,\ldots,N$ let

$D_{i}=\begin{bmatrix}\|A_{i}\|&\lambda^{(i)}_{j_{i}}\\\
\lambda^{(i)}_{j_{i}}&\|A_{i}\|\end{bmatrix}\circ\left(\begin{bmatrix}\|z^{(i),0}_{j}\|\\\
\|z^{(i),1}_{j}\|\end{bmatrix}\begin{bmatrix}\|z^{(i),0}_{j}\|&\|z^{(i),1}_{j}\|\end{bmatrix}\right)\enspace.$

Each $D_{i}\succeq 0$ because it is the Hadamard product of two positive
semidefinite matrices (the first matrix is diagonally dominant as
$\|A_{i}\|\geq|\lambda^{(i)}_{j_{i}}|$ and so is psd). Thus
$\|D_{i}\|_{tr}=\mathrm{Tr}(D_{i})=\|A_{i}\|$. Let $D=\otimes_{i=1}^{N}D_{i}$
and note that $\|D\|_{tr}=\prod_{i=1}^{N}\|A_{i}\|$. Then from Eq. 4 and Eq. 5
we see that

$\psi_{j_{1},\ldots,j_{N}}^{T}C\psi_{j_{1},\ldots,j_{N}}=\mathrm{Tr}(BD)\leq\|B\|\|D\|_{tr}=\|B\|\prod_{i=1}^{N}\|A_{i}\|\enspace.$

Let $M=\prod_{i=1}^{N}(m_{i}+n_{i})$ and let
$\psi=\sum_{j_{1},\ldots,j_{N}}\alpha_{j_{1},\ldots,j_{N}}\psi_{j_{1},\ldots,j_{N}}\in\mathbb{R}^{M}$
be an arbitrary unit vector. Then

$\displaystyle\psi^{T}C\psi$
$\displaystyle=\sum_{j_{1},\ldots,j_{N},k_{1},\ldots,k_{N}}\alpha_{j_{1},\ldots,j_{N}}\alpha_{k_{1},\ldots,k_{N}}(\psi_{j_{1},\ldots,j_{N}}^{T}C\psi_{k_{1},\ldots,k_{N}})$
$\displaystyle=\sum_{j_{1},\ldots,j_{N}}\alpha_{j_{1},\ldots,j_{N}}^{2}(\psi_{j_{1},\ldots,j_{N}}^{T}C\psi_{j_{1},\ldots,j_{N}})$
$\displaystyle\leq\|B\|\prod_{i=1}^{N}\|A_{i}\|\enspace.$

This shows $\|C\|\leq\|B\|\cdot\prod_{i=1}^{N}\|A_{i}\|$.

We now turn to showing the lower bounds

$\displaystyle\|C\|$ $\displaystyle\geq\|B\|\cdot\prod_{i=1}^{N}\|A_{i}\|$ (6)
$\displaystyle\lambda_{max}(C)$
$\displaystyle\geq\lambda_{max}(B)\cdot\prod_{i=1}^{N}\|A_{i}\|\enspace.$ (7)

Recall that $z^{(i)}_{1}$ is an eigenvector of $\begin{bmatrix}0&A_{i}\\\
A_{i}^{T}&0\end{bmatrix}$ corresponding to eigenvalue $\|A_{i}\|$. Also
$\|z^{(i),0}_{1}\|^{2}=\|z^{(i),1}_{1}\|^{2}=1/2$ by Eq. 3. Let $v$ be a unit
norm eigenvector of $B$ corresponding to eigenvalue $\lambda$ (which later
will either be set to $\lambda_{max}(B)$ or $\lambda_{min}(B)$). For
$x=(x_{1},\ldots,x_{N})\in\\{0,1\\}^{Nm}$ let
$\tilde{x}=(g(x_{1}),\ldots,g(x_{N}))$. We now define our witness $\psi$ which
we will use to show Eqs. 6 and 7 via 4:

$\psi((x_{1},\ldots,x_{N}))=v(\tilde{x})\prod_{i=1}^{N}\sqrt{2}z^{(i),\tilde{x}_{i}}_{1}(x_{i})\enspace.$

We have

$\displaystyle\sum_{x_{1},\ldots,x_{N}}\psi((x_{1},\ldots,x_{N}))^{2}$
$\displaystyle=\sum_{\alpha\in\\{0,1\\}^{N}}v(\alpha)^{2}\prod_{i=1}^{N}\left(\sum_{x_{i}:\tilde{x}_{i}=\alpha_{i}}2z^{(i),\alpha_{i}}_{1}(x_{i})^{2}\right)$
$\displaystyle=\sum_{\alpha\in\\{0,1\\}^{N}}v(\alpha)^{2}\prod_{i=1}^{N}\left(2\|z^{(i),\alpha_{i}}_{1}\|^{2}\right)$
$\displaystyle=\sum_{\alpha\in\\{0,1\\}^{N}}v(\alpha)^{2}$
$\displaystyle=1\enspace.$

Thus $\psi$ is a unit vector. Now

$\displaystyle\psi^{T}C\psi$
$\displaystyle=\sum_{\alpha,\beta\in\\{0,1\\}^{N}}B(a,b)v(\alpha)v(\beta)\prod_{i=1}^{N}2\cdot\left(z^{(i),\alpha_{i}}_{1}\hat{A}^{(\alpha_{i},\beta_{i})}z^{(i),\beta_{i}}_{1}\right)$
$\displaystyle=\sum_{\alpha,\beta\in\\{0,1\\}^{N}}B(a,b)v(\alpha)v(\beta)\prod_{i=1}^{N}\|A_{i}\|$
$\displaystyle=\lambda\prod_{i=1}^{N}\|A_{i}\|\enspace.$

Taking $\lambda=\lambda_{max}(B)$ shows Eq. 7 by 4. If
$\lambda_{max}(B)=\|B\|$ this also shows Eq. 6. Otherwise, if
$\|B\|=-\lambda_{min}(B)$ then taking $\lambda=\lambda_{min}(B)$ we have
$\psi^{T}C\psi=-\|B\|\prod_{i=1}^{N}\|A_{i}\|$, implying Eq. 6 again by 4. ∎

We now turn to showing the main result of this note, that
$\mathrm{ADV}_{rel}^{\pm}(f\circ
g^{N})=\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)$ for a relation $f$
and Boolean function $g$. We start with the more difficult direction which is
showing the lower bound.

######  Theorem 22.

Let $f\subseteq\\{0,1\\}^{N}\times[K]$ be a relation and
$g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$ be a Boolean function. Then
$\mathrm{ADV}_{rel}^{\pm}(f\circ
g^{N})\geq\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)$.

###### Proof.

Let $\Gamma_{f}$ be a relational adversary matrix achieving the optimal bound
for the relation $f$. Let

$\Gamma_{g}=\begin{bmatrix}0&Z\\\ Z^{T}&0\end{bmatrix}$

be an optimal functional adversary matrix for $g$. Define $\Gamma_{h}$ as the
matrix composition of $\Gamma_{f}$ with $N$ copies of $Z$.

For $a\in[K]$ let $\chi_{a}\in\mathbb{R}^{2^{N}}$ be defined as in Eq. 1 and
define $\phi_{a}\in\mathbb{R}^{2^{mN}}$ similarly but for the composed
function:

$\phi_{a}((x_{1},\ldots,x_{N}))=\begin{cases}1,&\text{$((g(x_{1}),\ldots,g(x_{N})),a)\in
f$;}\\\ 0,&\text{otherwise.}\end{cases}$

We will show three things

  1. (1)

$\lambda_{max}(\Gamma_{h})=\lambda_{max}(\Gamma_{f})\cdot\|\Gamma_{g}\|^{N}$;

  2. (2)

$\Gamma_{h}\circ\phi_{a}\phi_{a}^{T}\preceq 0$ for all $a\in[K]$; and

  3. (3)

$\|\Gamma_{h}\circ D_{\ell}\|\leq\|\Gamma_{f}\circ
D_{p}\|\cdot\|\Gamma_{g}\circ D_{q}\|\cdot\|\Gamma_{g}\|^{N-1}$, for any
$p\in[N],q\in[m]$ where $\ell=(p-1)m+q$ is the $q^{th}$ bit in the $p^{th}$
block.

These three items give the theorem since item (2) implies $\Gamma_{h}$ is a
relational adversary matrix and

$\displaystyle\frac{\lambda_{max}(\Gamma_{h})}{\|\Gamma_{h}\circ D_{\ell}\|}$
$\displaystyle\geq\frac{\lambda_{max}(\Gamma_{f})\cdot\|\Gamma_{g}\|^{N}}{\|\Gamma_{f}\circ
D_{p}\|\cdot\|\Gamma_{g}\circ D_{q}\|\cdot\|\Gamma_{g}\|^{N-1}}$
$\displaystyle\geq\left(\frac{\lambda_{max}(\Gamma_{f})}{\|\Gamma_{f}\circ
D_{p}\|}\right)\left(\frac{\|\Gamma_{g}\|}{\|\Gamma_{g}\circ D_{q}\|}\right)$
$\displaystyle\geq\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)\enspace.$

We now show the three items. Item (1) follows immediately from the second
equation of Lemma 21 as $\Gamma_{h}$ is defined to be the matrix composition
of $\Gamma_{f}$ with $N$ copies of $Z$, and $\|\Gamma_{g}\|=\|Z\|$.

Item (2) is the main novelty in the relational case. From Definition 19 we see
that

$\Gamma_{h}\circ\phi_{a}\phi_{a}^{T}=(\tilde{\Gamma}_{f}\circ\phi_{a}\phi_{a}^{T})\circ(\otimes^{N}\hat{\Gamma}_{g})\enspace,$

where $\hat{\Gamma}_{g}$ is defined via Eq. 2 and $\tilde{\Gamma}_{f}$ is a
$2^{mN}$-by-$2^{mN}$ matrix defined as

$\tilde{\Gamma}_{f}((x_{1},\ldots,x_{N}),(y_{1},\ldots,y_{N}))=\Gamma_{f}((g(x_{1}),\ldots,g(x_{N})),(g(y_{1}),\ldots,g(y_{N}))\enspace.$

By Lemma 18, $\hat{\Gamma}_{g}\succeq 0$, which gives us
$\otimes^{N}\hat{\Gamma}_{g}\succeq 0$. Also,
$\Gamma_{f}\circ\chi_{a}\chi_{a}^{T}\preceq 0$ by the definition of the
relational adversary matrix, thus by Fact 2, we get that
$\tilde{\Gamma}_{f}\circ\phi_{a}\phi_{a}^{T}\preceq 0$. Combining the last two
observations with Fact 3, we get Item (2).

Item (3) follows as in [HLŠ07], but for completeness we give the details here.
Write $\ell\in[mN]$ as $\ell=(p-1)m+q$ with $p\in[N]$ and $q\in[m]$, i.e.
$\ell$ refers to $x_{p}(q)$, the $q^{th}$ bit in the $p^{th}$ block. It is
shown in [HLŠ07] that

$\Gamma_{h}\circ D_{\ell}=(\widetilde{\Gamma_{f}\circ
D_{p}})\circ\left((\otimes^{p-1}\;\hat{\Gamma}_{g})\otimes(\hat{\Gamma}_{g}\circ
D_{q})\otimes(\otimes^{N-p}\;\hat{\Gamma}_{g})\right)\enspace,$ (8)

where

$(\widetilde{\Gamma_{f}\circ
D_{p}})((x_{1},\ldots,x_{N}),(y_{1},\ldots,y_{N}))=(\Gamma_{f}\circ
D_{p})((g(x_{1}),\ldots,g(x_{N})),(g(y_{1}),\ldots,g(y_{N}))\enspace.$

The right hand side is not obviously in the proper form to apply Lemma 21
because Lemma 21 requires $\widehat{\Gamma_{g}\circ D_{q}}$ in place of the
term $\hat{\Gamma}_{g}\circ D_{q}$ in Eq. 8. We can show, however, that the
right hand side of Eq. 8 does not change if we replace $\hat{\Gamma}_{g}\circ
D_{q}$ with $\widehat{\Gamma_{g}\circ D_{q}}$.

######  Claim 23.

$(\widetilde{\Gamma_{f}\circ
D_{p}})\circ\left((\otimes^{p-1}\;\hat{\Gamma}_{g})\otimes(\hat{\Gamma}_{g}\circ
D_{q})\otimes(\otimes^{N-p}\;\hat{\Gamma}_{g})\right)=(\widetilde{\Gamma_{f}\circ
D_{p}})\circ\left((\otimes^{p-1}\;\hat{\Gamma}_{g})\otimes(\widehat{\Gamma_{g}\circ
D_{q}})\otimes(\otimes^{N-p}\;\hat{\Gamma}_{g})\right)$

###### Proof.

$\hat{\Gamma}_{g}\circ D_{q}$ and $\widehat{\Gamma_{g}\circ D_{q}}$ only
differ on the diagonal, therefore it suffices to show that for all entries
$(x_{1},\ldots,x_{N}),(y_{1},\ldots,y_{N})$ where $x_{p}=y_{p}$ the left and
right hand sides agree. When $x_{p}=y_{p}$ the left hand side will be $0$
because $\hat{\Gamma}_{g}\circ D_{q}$ is zero on the diagonal. When
$x_{p}=y_{p}$ the right hand side will also be zero because then
$\tilde{x}_{p}=\tilde{y}_{p}$ and so $(\widetilde{\Gamma_{f}\circ
D_{p}})(x,y)=0$. ∎

The right hand side of the expression in 23 is now in the right form to apply
the first equation of Lemma 21, and we can conclude $\|\Gamma_{h}\circ
D_{\ell}\|\leq\|\Gamma_{f}\circ D_{p}\|\|\Gamma_{g}\circ
D_{q}\|\|\Gamma_{g}\|^{N-1}$ as desired. ∎

Next we show the upper bound.

######  Theorem 24.

Let $f\subseteq\\{0,1\\}^{N}\times[K]$ be a relation and
$g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$ be a Boolean function. Then
$\mathrm{ADV}_{rel}^{\pm}(f\circ
g^{N})\leq\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)$.

###### Proof.

Let
$\\{u_{y,i}\\}_{y\in\\{0,1\\}^{m},i\in[m]},\\{u_{y,i}\\}_{y\in\\{0,1\\}^{m},i\in[m]}$
be an optimal solution to the $\mathrm{ADV}^{\pm}(g)$ program from Theorem 7,
and let
$\\{\psi_{z,i}\\}_{z\in\\{0,1\\}^{N},i\in[N]},\\{\phi_{z,i}\\}_{z\in\\{0,1\\}^{N},i\in[N]},\\{\sigma_{z,a}\\}_{z\in\\{0,1\\}^{N},a\in[K]}$
be an optimal solution to the $\mathrm{ADV}_{rel}^{\pm}(f)$ program from
Definition 12. We will construct a solution to the program from Definition 12
for $h=f\circ g^{N}$ of cost
$\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)$. For
$x=(x_{1},\ldots,x_{N})\in\\{0,1\\}^{Nm}$ let
$\tilde{x}=(g(x_{1}),\ldots,g(x_{N}))$.

Define

  * •

$\alpha_{x,\ell}=\psi_{\tilde{x},p}\otimes u_{x_{p},q}$ for $\ell=(m-1)p+q$
where $p\in[N],q\in[m]$.

  * •

$\beta_{x,\ell}=\phi_{\tilde{x},p}\otimes v_{x_{p},q}$ for $\ell=(m-1)p+q$
where $p\in[N],q\in[m]$.

  * •

$\rho_{x,a}=\sigma_{\tilde{x},a}$.

Then for any $x=(x_{1},\ldots,x_{N})\in\\{0,1\\}^{Nm}$

$\displaystyle\sum_{\ell}\|\alpha_{x,\ell}\|^{2}$
$\displaystyle=\sum_{p}\|\psi_{\tilde{x},p}\|^{2}\sum_{i\in[m]}\|u_{x_{p},i}\|^{2}$
$\displaystyle\leq\mathrm{ADV}^{\pm}(g)\sum_{p}\|\psi_{\tilde{x},p}\|^{2}$
$\displaystyle\leq\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)\enspace.$

A similar calculation shows
$\sum_{\ell}\|\beta_{x,\ell}\|^{2}\leq\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)$
for any $x\in\\{0,1\\}^{Nm}$.

Having established the objective value, we move on to the constraints.

$\displaystyle\sum_{\ell:x_{\ell}\neq
y_{\ell}}\langle\alpha_{x,\ell},\beta_{x,\ell}\rangle$
$\displaystyle=\sum_{p\in[N]}\langle\psi_{\tilde{x},p}|\phi_{\tilde{y},p}\rangle\sum_{i\in[m]\atop
x_{p}(i)\neq y_{p}(i)}\langle u_{x_{p},i}|v_{y_{p},i}\rangle$
$\displaystyle=\sum_{p\in[N]\atop\tilde{x}_{p}\neq\tilde{y}_{p}}\langle\psi_{\tilde{x},p}|\phi_{\tilde{y},p}\rangle$
$\displaystyle=1-\sum_{a:(\tilde{x},a)\in f,(\tilde{y},a)\in
f}\langle\sigma_{\tilde{x},a}|\sigma_{\tilde{y},a}\rangle$
$\displaystyle=1-\sum_{a:(x,a)\in h,(y,a)\in
h}\langle\rho_{x,a}|\rho_{y,a}\rangle\enspace,$

as desired.

Finally, $\|\rho_{x,a}\|^{2}=\|\sigma_{\tilde{x},a}\|^{2}=0$ if
$(\tilde{x},a)\not\in f$. As $(x,a)\in h$ iff $(\tilde{x},a)\in f$ this shows
$\|\rho_{x,a}\|^{2}=0$ for all $(x,a)\not\in h$. ∎

######  Corollary 25.

Let $f\subseteq\\{0,1\\}^{N}\times[K]$ be a relation and
$g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$ be a Boolean function. Then
$\mathrm{ADV}_{rel}^{\pm}(f\circ
g^{N})=\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)$.

###### Proof.

This follows from Theorem 22 and Theorem 24. ∎

######  Corollary 26.

Let $K$ be a positive integer, $f\subseteq\\{0,1\\}^{N}\times[K]$ be an
efficiently verifiable relation, and $g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$ be
a Boolean function. Then $Q(f\circ
g^{N})=\Theta(\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g))$.

###### Proof.

Let $h=f\circ g^{N}$. We start by showing
$Q(h)=\Omega(\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g))$. By Theorem 22
$\mathrm{ADV}_{rel}^{\pm}(h)\geq\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)$.
For $a\in[K]$ let $h_{a}:\\{0,1\\}^{mN}\rightarrow\\{0,1\\}$ be defined as
$h_{a}((x_{1},\ldots,x_{N}))=1$ iff $((g(x_{1}),\ldots,g(x_{N})),a)\in f$.
Letting $f_{a}:\\{0,1\\}^{N}\rightarrow\\{0,1\\}$ be defined as $f_{a}(x)=1$
iff $(x,a)\in f$, we see that $h_{a}=f_{a}\circ g^{N}$. By Theorem 1 we have
that
$\mathrm{ADV}^{\pm}(h_{a})=\mathrm{ADV}^{\pm}(f_{a})\mathrm{ADV}^{\pm}(g)$ and
therefore, as $f$ is efficiently verifiable,
$\mathrm{ADV}^{\pm}(h_{a})=o(\mathrm{ADV}_{rel}^{\pm}(h))$ for every
$a\in[K]$. Thus $h$ is also efficiently verifiable and the corollary follows
by Theorem 16.

For the other direction, we use Theorem 24 to obtain
$\mathrm{ADV}_{rel}^{\pm}(h)\leq\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g)$
and then apply Theorem 13. ∎

######  Corollary 27.

Let $K$ be a positive integer, $f\subseteq\\{0,1\\}^{N}\times[K]$ be an
efficiently verifiable relation, and $g:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$ be
a Boolean function. Then $Q(f\circ g^{N})=\Theta(Q(f)Q(g))$.

###### Proof.

By Corollary 26, $Q(f\circ
g^{N})=\Theta(\mathrm{ADV}_{rel}^{\pm}(f)\mathrm{ADV}^{\pm}(g))$. We have
$Q(g)=\Theta(\mathrm{ADV}^{\pm}(g))$ by Theorem 8. Also,
$Q(f)=O(\mathrm{ADV}_{rel}^{\pm}(f))$ by Theorem 13 and
$Q(f)=\Omega(\mathrm{ADV}_{rel}^{\pm}(f))$ by Theorem 16 as $f$ is efficiently
verifiable. The corollary follows. ∎

## Acknowledgements

We thank Ronald de Wolf for asking us if an adversary composition theorem
holds for relations, the question that began this note, and for helpful
comments on the manuscript. A.B. is supported by the ERDF project number
1.1.1.2/I/16/113. T.L. is supported by the Australian Research Council Grant
No: DP200100950.

## References

  * [AdW19] Simon Apers and Ronald de Wolf.  Quantum speedup for graph sparsification, cut approximation and Laplacian solving.  CoRR, abs/1911.07306, 2019.
  * [Amb02] Andris Ambainis.  Quantum lower bounds by quantum arguments.  J. Comput. Syst. Sci., 64(4):750–767, 2002.
  * [Amb06] Andris Ambainis.  Polynomial degree vs. quantum query complexity.  J. Comput. Syst. Sci., 72(2):220–238, 2006.
  * [Amb07] Andris Ambainis.  Quantum walk algorithm for element distinctness.  SIAM J. Comput., 37(1):210–239, 2007.
  * [AMRR11] Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jérémie Roland.  Symmetry-assisted adversaries for quantum state generation.  In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pages 167–177. IEEE Computer Society, 2011.
  * [Bel12a] Aleksandrs Belovs.  Learning-graph-based quantum algorithm for k-distinctness.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 207–216. IEEE Computer Society, 2012.
  * [Bel12b] Aleksandrs Belovs.  Span programs for functions with constant-sized 1-certificates: extended abstract.  In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 77–84. ACM, 2012.
  * [Bel15a] Aleksandrs Belovs.  Quantum algorithms for learning symmetric juntas via the adversary bound.  Comput. Complex., 24(2):255–293, 2015.
  * [Bel15b] Aleksandrs Belovs.  Variations on quantum adversary.  Technical Report arXiv:1504.06943, arXiv, 2015.
  * [BSS03] Howard Barnum, Michael E. Saks, and Mario Szegedy.  Quantum query complexity and semi-definite programming.  In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark, pages 179–193. IEEE Computer Society, 2003.
  * [Gro96] Lov K. Grover.  A fast quantum mechanical algorithm for database search.  In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 212–219. ACM, 1996.
  * [HLŠ07] Peter Høyer, Troy Lee, and Robert Špalek.  Negative weights make adversaries stronger.  In David S. Johnson and Uriel Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 526–535. ACM, 2007.
  * [Kim13] Shelby Kimmel.  Quantum adversary (upper) bound.  Chicago J. Theor. Comput. Sci., 2013, 2013.
  * [LM08] Sophie Laplante and Frédéric Magniez.  Lower bounds for randomized and quantum query complexity using Kolmogorov arguments.  SIAM J. Comput., 38(1):46–62, 2008.
  * [LMR+11] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, and Mario Szegedy.  Quantum query complexity of state conversion.  In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 344–353. IEEE Computer Society, 2011.
  * [LMS17] Troy Lee, Frédéric Magniez, and Miklos Santha.  Improved quantum query algorithms for triangle detection and associativity testing.  Algorithmica, 77(2):459–486, 2017.
  * [MSS07] Frédéric Magniez, Miklos Santha, and Mario Szegedy.  Quantum algorithms for the triangle problem.  SIAM J. Comput., 37(2):413–424, 2007.
  * [Rei11] Ben Reichardt.  Reflections for quantum query algorithms.  In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 560–569. SIAM, 2011.
  * [Rei14] Ben W. Reichardt.  Span programs are equivalent to quantum query algorithms.  SIAM J. Comput., 43(3):1206–1219, 2014.
  * [RS12] Ben Reichardt and Robert Spalek.  Span-program-based quantum algorithm for evaluating formulas.  Theory of Computing, 8(1):291–319, 2012.
  * [Shi02] Yaoyun Shi.  Quantum lower bounds for the collision and the element distinctness problems.  In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, pages 513–519. IEEE Computer Society, 2002.
  * [Sho97] Peter W. Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  SIAM J. Comput., 26(5):1484–1509, 1997.
  * [SS06] Robert Spalek and Mario Szegedy.  All quantum adversary methods are equivalent.  Theory of Computing, 2(1):1–18, 2006.
  * [Sze04] Mario Szegedy.  Quantum speed-up of Markov chain based algorithms.  In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 32–41. IEEE Computer Society, 2004.
  * [Zha05] Shengyu Zhang.  On the power of Ambainis lower bounds.  Theor. Comput. Sci., 339(2-3):241–256, 2005.