---
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 @Bel15 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) )$.'
author:
- 'Aleksandrs Belovs [^1]'
- 'Troy Lee [^2]'
title: The quantum query complexity of composition with a relation
---

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 @Bel12.

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<span>ø</span>yer et al. @HLS07. 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 @Bel12b [@Bel15b; @LMS17], especially via the development of the learning graphs model of Belovs @Bel12.

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))$. @HLS07 showed that ${\mathrm{ADV}}^\pm(h) \ge {\mathrm{ADV}}^\pm(f) {\mathrm{ADV}}^\pm(g)$, and @Rei14 showed a matching upper bound.

\[@HLS07 [@Rei14]\] \[thm:basic\] 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 @LMRSS11 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; @LMRSS11]. 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. @LMRSS11 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 @Bel15 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 \[def:verifiable\]. 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 @LMRSS11 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 @AW19. 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.

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 \le 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:duplication\] 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:simple\] 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:lmax\] 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) \ge v^T A v \ge \lambda_{min}(A)$ for any unit vector $v$.

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'$ 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'$ on $\{0,1\}^n$, as any output is accepted for inputs not in $S$.

Adversary bound
---------------

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

\[Functional adversary bound @HLS07\] \[def:adversary\] Let $g: \01^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 \ne y_i$. The adversary bound ${\mathrm{ADV}}^{\pm}(g)$ for $g$ is defined as $$\begin{aligned}
{\mathrm{ADV}}^\pm(g) = & \underset{\Gamma}{\text{maximize}}
& & \|\Gamma\| \\
& \text{subject to}
& & \|\Gamma \circ D_i \| \leq 1 \mbox{ for all } i = 1, \ldots, n \\
& & & \Gamma(x,y) = 0 \mbox{ for all } x,y \in \{0,1\}^n \mbox{ with } g(x) = g(y) \enspace .
\end{aligned}$$

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

\[@LMRSS11 Theorem 3.4\] \[thm:adv\_dual\] Let $g: \01^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]$. $$\begin{aligned}
{\mathrm{ADV}}^\pm(g) = & \underset{\{u_{x,i}\},  \{v_{x,i}\} }{\text{minimize}}
& & \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\} \\
& \text{subject to}
& & \sum_{i: x_i \ne y_i} \langle u_{x,i}, v_{y, i} \rangle = 
\begin{cases}
1 & \mbox{ if } g(x) \ne g(y) \\
0 & \mbox{ if } g(x) = g(y)
\end{cases}
\mbox{ for all } x,y \in \{0,1\}^n \\
\end{aligned}$$

If one simply takes the dual of \[def:adversary\] 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 @LMRSS11 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<span>ø</span>yer et al. @HLS07 and the upper bound due to Reichardt @Rei11.

\[@HLS07,@Rei11\] \[thm:adv\_char\] Let $g: \01^n \rightarrow \{0,1\}$ be a Boolean function. Then $Q(g) = \Theta({\mathrm{ADV}}^{\pm}(g))$

Adversary bound for relations
=============================

Belovs @Bel15 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; @LMRSS11]. 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. @LMRSS11 give the following definition and theorem.

\[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 \ne y_i$. Define $$\begin{aligned}
\gamma_2(A | D) = & \underset{\{u_{x,i}\},  \{v_{x,i}\} }{\text{minimize}}
& & \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\} \\
& \text{subject to}
& & \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 \\
\end{aligned}$$

\[@LMRSS11\] \[thm:lmrss\] 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 \ne 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'\rangle}$ satisfying $\langle  \sigma_x' | (|\sigma_x \rangle \otimes | 0 \rangle) \ge \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$.

\[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 \01^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 \01^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 \01^n}$ for $f$. This optimization problem gives Belovs' definition of the relational adversary bound.

\[@Bel15 Equation 20\] \[def:adv\_rel\] Let $f \subseteq \{0,1\}^n \times [K]$. $$\begin{aligned}
{\mathrm{ADV}}_{rel}^\pm(f) = & \underset{\{u_{x,i}\},  \{v_{x,i}\}, \{\sigma_{x,a}\} }{\text{minimize}}
& & \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\} \\
& \text{subject to}
& & \sum_{i: x_i \ne 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 \\
& & & \| \sigma_{x,a} \|^2 = 0 \mbox{ for all } x,a \mbox{ with } (x,a) \not \in f
\end{aligned}$$

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

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 \[thm:lmrss\] with $\epsilon = 1/3$ there is a quantum algorithm that on input $x$ terminates in a state ${|\psi_x'\rangle}$ satisfying $\langle  \psi_x' | (|\psi_x \rangle \otimes | 0 \rangle) \ge \sqrt{1-\epsilon}$ after making $O({\mathrm{ADV}}_{rel}^\pm(f))$ many queries. This implies $\| {|\psi_x'\rangle} - {|\psi_x\rangle}{|0\rangle} \|^2 \le \epsilon$ and so $$\begin{aligned}
\epsilon &\ge \| {|\psi_x'\rangle} - {|\psi_x\rangle}{|0\rangle} \|^2 \\
&= \sum_{a \in [K]} \| (\Pi_a \otimes I) {|\psi_x'\rangle} - {|\sigma_{x,a}\rangle} \otimes {|0\rangle} \|^2 \\
&\ge \sum_{a: (x,a) \not \in f} \| (\Pi_a \otimes I) {|\psi_x'\rangle} \|^2\end{aligned}$$ 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 \[def:adversary\].

\[@Bel15 Equation 22\] \[thm:rel\_adv\_dual\] Let $f \subseteq \01^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 \ne y_i$. For $a \in [K]$ let $$\label{eqn:chia}
\chi_a(x) = 
\begin{cases}
1 & \mbox{ if } (x,a) \in f \\
0 & \mbox{ otherwise.}
\end{cases}$$ Then $$\begin{aligned}
{\mathrm{ADV}}_{rel}^\pm(f) = & \underset{\Gamma}{\text{maximize}}
& & \lambda_{max}(\Gamma) \\
& \text{subject to}
& & \|\Gamma \circ D_i \| \leq 1 \mbox{ for all } i = 1, \ldots, n \\
& & & \Gamma \circ \chi_a \chi_a^T \preceq 0 \mbox{ for all } a \in [K] \enspace .
\end{aligned}$$

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.

\[Efficiently verifiable\] \[def: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 @Bel15 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.

\[Belovs @Bel15 Theorem 40\] \[thm:belovs\] Let $f \subseteq \01^n \times [K]$ be an efficiently verifiable relation. Then $Q(f) = \Omega({\mathrm{ADV}}_{rel}^\pm(f))$.

Composition Theorem
===================

Let $A$ be an $m$-by-$n$ matrix. Define $$\label{eqn:hatA}
\hat A = 
\begin{bmatrix}
\|A\| I_m & A \\
A^T & \|A\| I_n
\end{bmatrix}
\enspace .$$

\[lem:hat\_psd\] $\hat A$ is positive semidefinite for any $A$.

The minimum eigenvalue of $A' = \begin{bmatrix} 0 & A \\ A^T & 0 \end{bmatrix}$ is $-\|A\|$ thus $\hat A = \|A\| I + A' \succeq 0$ by \[fact:lmax\].

\[Matrix Composition\] \[def:comp\] 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 .$$

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 @HLS07 Lemma 16. The statement we give here differs in two respects from the statement given in @HLS07. First, in @HLS07 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 \[thm:rel\_adv\_dual\] 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 @HLS07 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 @HLS07.

\[lem:main\] 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) \ge \lambda_{max}(B) \cdot \prod_{i=1}^N \|A_i\| \enspace .$$

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 \ge \cdots \ge \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 $$\label{eq:half}
\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$$ and so $\|z^{(i),0}_j\|^2 = \|z^{(i),1}_j\|^2 =1/2$ whenever $\lambda^{(i)}_j \ne 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\}$ $$\label{eq:crucial}
z^{(i),b_1}_j \hat A_i^{(b_1,b_2)} z^{(i),b_2}_k= 
\begin{cases}
0 & \mbox{ if } j \ne 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 \ne b_2
\end{cases}
\enspace .$$

We now turn to showing the most difficult part of the lemma, that $\|C\| \le \|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 $$\label{eq:psi}
\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.$$ Suppose that $j_i \ne k_i$ for some $i$. Then by \[eq:crucial\] $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\| \ge | \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:crucial\] and \[eq:psi\] we see that $$\psi_{j_1, \ldots, j_N} ^T C \psi_{j_1, \ldots, j_N} = {\mathrm{Tr}}(BD) \le \|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 $$\begin{aligned}
\psi^T C \psi &= \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}) \\
&= \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}) \\
&\le \|B\| \prod_{i=1}^N \|A_i\| \enspace .\end{aligned}$$ This shows $\|C\| \le \|B\| \cdot \prod_{i=1}^N \|A_i\|$.

We now turn to showing the lower bounds $$\begin{aligned}
\label{eq:sp_lower}
\|C\| &\ge \|B\| \cdot \prod_{i=1}^N \|A_i\| \\
\label{eq:lmax_lower}
\lambda_{max}(C) &\ge \lambda_{max}(B) \cdot \prod_{i=1}^N \|A_i\| \enspace .\end{aligned}$$ 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:half\]. 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 \[eq:sp\_lower,eq:lmax\_lower\] via \[fact:lmax\]: $$\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 $$\begin{aligned}
\sum_{x_1, \ldots, x_N} \psi((x_1, \ldots, x_N))^2 &= \sum_{\alpha \in \{0,1\}^N} v(\alpha)^2 \prod_{i=1}^N \left( \sum_{x_i : \tilde x_i = \alpha_i} 2 z^{(i),\alpha_i}_1(x_i)^2 \right) \\
&=  \sum_{\alpha \in \{0,1\}^N} v(\alpha)^2 \prod_{i=1}^N  \left( 2 \|z^{(i),\alpha_i}_1\|^2 \right) \\
&= \sum_{\alpha \in \{0,1\}^N} v(\alpha)^2 \\
&= 1 \enspace .\end{aligned}$$ Thus $\psi$ is a unit vector. Now $$\begin{aligned}
\psi^T C \psi &= \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) \\
& = \sum_{\alpha, \beta \in \{0,1\}^N} B(a,b) v(\alpha) v(\beta) \prod_{i=1}^N \|A_i\| \\
& = \lambda \prod_{i=1}^N \|A_i\| \enspace .\end{aligned}$$ Taking $\lambda = \lambda_{max}(B)$ shows \[eq:lmax\_lower\] by \[fact:lmax\]. If $\lambda_{max}(B) = \|B\|$ this also shows \[eq:sp\_lower\]. 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:sp\_lower\] again by \[fact:lmax\].

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.

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

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 \[eqn:chia\] 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) $\lambda_{max}(\Gamma_h ) =\lambda_{max}(\Gamma_f) \cdot \|\Gamma_g\|^N$;

(2) $\Gamma_h \circ \phi_a \phi_a^T \preceq 0$ for all $a \in [K]$; and

(3) $\|\Gamma_h \circ D_\ell \| \le \|\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 $$\begin{aligned}
\frac{\lambda_{max}(\Gamma_h)}{\| \Gamma_h \circ D_\ell \|} & \ge \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} } \\
&\ge \left( \frac{\lambda_{max}(\Gamma_f)}{\|\Gamma_f \circ D_p\|}\right) \left(\frac{\|\Gamma_g\|}{\|\Gamma_g \circ D_q\|} \right) \\
&\ge {\mathrm{ADV}}_{rel}^\pm(f) {\mathrm{ADV}}^{\pm}(g) \enspace .\end{aligned}$$

We now show the three items. Item (1) follows immediately from the second equation of \[lem:main\] 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 \[def:comp\] 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 \[eqn:hatA\] 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 \[lem:hat\_psd\], $\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 \[fact:duplication\], we get that $\tilde \Gamma_f \circ \phi_a \phi_a^T\preceq 0$. Combining the last two observations with Fact \[fact:simple\], we get Item (2).

Item (3) follows as in @HLS07, 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 @HLS07 that $$\label{eq:last_bit}
\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 ,$$ 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 \[lem:main\] because \[lem:main\] requires $\widehat{\Gamma_g \circ D_q}$ in place of the term $\hat{\Gamma}_g \circ D_q$ in \[eq:last\_bit\]. We can show, however, that the right hand side of \[eq:last\_bit\] does not change if we replace $\hat{\Gamma}_g \circ D_q$ with $\widehat{\Gamma_g \circ D_q}$.

\[clm:right\_form\] $$(\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)$$

$\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 \[clm:right\_form\] is now in the right form to apply the first equation of \[lem:main\], and we can conclude $\|\Gamma_h \circ D_\ell\| \le \|\Gamma_f \circ D_p\| \|\Gamma_g \circ D_q\| \|\Gamma_g\|^{N-1}$ as desired.

Next we show the upper bound.

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

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 \[thm:adv\_dual\], 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 \[def:adv\_rel\]. We will construct a solution to the program from \[def:adv\_rel\] 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}$ $$\begin{aligned}
\sum_\ell \| \alpha_{x,\ell} \|^2 &= \sum_p \| \psi_{\tilde x, p} \|^2 \sum_{i \in [m]} \| u_{x_p,i} \|^2 \\
&\le {\mathrm{ADV}}^\pm(g) \sum_p \| \psi_{\tilde x, p} \|^2 \\
&\le {\mathrm{ADV}}_{rel}^\pm(f) {\mathrm{ADV}}^\pm(g) \enspace .\end{aligned}$$ A similar calculation shows $\sum_\ell \| \beta_{x,\ell} \|^2 \le {\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. $$\begin{aligned}
\sum_{\ell: x_\ell \ne y_\ell} \langle \alpha_{x,\ell}, \beta_{x, \ell} \rangle &= \sum_{p \in [N]} {\langle\psi_{\tilde x, p} | \phi_{\tilde y, p}\rangle} \sum_{i \in [m] \atop x_p(i) \ne y_p(i)} {\langleu_{x_p,i} | v_{y_p,i}\rangle} \\
&= \sum_{p \in [N] \atop \tilde x_p  \ne \tilde y_p} {\langle\psi_{\tilde x, p} | \phi_{\tilde y, p}\rangle} \\
&= 1 - \sum_{a: (\tilde x, a) \in f, (\tilde y, a) \in f} {\langle\sigma_{\tilde x,a} | \sigma_{\tilde y,a}\rangle} \\
&= 1 - \sum_{a: (x, a) \in h, (y, a) \in h} {\langle\rho_{x,a} | \rho_{y,a}\rangle} \enspace ,\end{aligned}$$ 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$.

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

This follows from \[thm:lower\] and \[thm:upper\].

\[cor:pcomp\] 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))$.

Let $h = f \circ g^N$. We start by showing $Q(h) = \Omega({\mathrm{ADV}}_{rel}^\pm(f) {\mathrm{ADV}}^\pm(g))$. By \[thm:lower\] ${\mathrm{ADV}}_{rel}^\pm(h) \ge {\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 \[thm:basic\] 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 \[thm:belovs\].

For the other direction, we use \[thm:upper\] to obtain ${\mathrm{ADV}}_{rel}^\pm(h) \le {\mathrm{ADV}}_{rel}^\pm(f) {\mathrm{ADV}}^\pm(g)$ and then apply \[thm:alg\].

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

By \[cor:pcomp\], $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 \[thm:adv\_char\]. Also, $Q(f) = O({\mathrm{ADV}}_{rel}^\pm(f))$ by \[thm:alg\] and $Q(f) = \Omega({\mathrm{ADV}}_{rel}^\pm(f))$ by \[thm:belovs\] as $f$ is efficiently verifiable. The corollary follows.

Acknowledgements {#acknowledgements .unnumbered}
================

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 (530)453-2566/I/16/113. T.L. is supported by the Australian Research Council Grant No: DP200100950.

<span>AMRR11</span>

Simon Apers and Ronald de Wolf. Quantum speedup for graph sparsification, cut approximation and <span>L</span>aplacian solving. , abs/1911.07306, 2019.

Andris Ambainis. Quantum lower bounds by quantum arguments. , 64(4):750–767, 2002.

Andris Ambainis. Polynomial degree vs. quantum query complexity. , 72(2):220–238, 2006.

Andris Ambainis. Quantum walk algorithm for element distinctness. , 37(1):210–239, 2007.

Andris Ambainis, Lo<span>ï</span>ck Magnin, Martin Roetteler, and J<span>é</span>r<span>é</span>mie Roland. Symmetry-assisted adversaries for quantum state generation. In <span>*Proceedings of the 26th Annual <span>IEEE</span> Conference on Computational Complexity, <span>CCC</span> 2011, San Jose, California, USA, June 8-10, 2011*</span>, pages 167–177. <span>IEEE</span> Computer Society, 2011.

Aleksandrs Belovs. Learning-graph-based quantum algorithm for k-distinctness. In <span>*53rd Annual <span>IEEE</span> Symposium on Foundations of Computer Science, <span>FOCS</span> 2012, New Brunswick, NJ, USA, October 20-23, 2012*</span>, pages 207–216. <span>IEEE</span> Computer Society, 2012.

Aleksandrs Belovs. Span programs for functions with constant-sized 1-certificates: extended abstract. In Howard J. Karloff and Toniann Pitassi, editors, <span>*Proceedings of the 44th Symposium on Theory of Computing Conference, <span>STOC</span> 2012, New York, NY, USA, May 19 - 22, 2012*</span>, pages 77–84. <span>ACM</span>, 2012.

Aleksandrs Belovs. Quantum algorithms for learning symmetric juntas via the adversary bound. , 24(2):255–293, 2015.

Aleksandrs Belovs. Variations on quantum adversary. Technical Report arXiv:1504.06943, arXiv, 2015.

Howard Barnum, Michael E. Saks, and Mario Szegedy. Quantum query complexity and semi-definite programming. In <span>*18th Annual <span>IEEE</span> Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark*</span>, pages 179–193. <span>IEEE</span> Computer Society, 2003.

Lov K. Grover. A fast quantum mechanical algorithm for database search. In Gary L. Miller, editor, <span>*Proceedings of the Twenty-Eighth Annual <span>ACM</span> Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996*</span>, pages 212–219. <span>ACM</span>, 1996.

Peter H<span>ø</span>yer, Troy Lee, and Robert <span>Š</span>palek. Negative weights make adversaries stronger. In David S. Johnson and Uriel Feige, editors, <span>*Proceedings of the 39th Annual <span>ACM</span> Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007*</span>, pages 526–535. <span>ACM</span>, 2007.

Shelby Kimmel. Quantum adversary (upper) bound. , 2013, 2013.

Sophie Laplante and Fr<span>é</span>d<span>é</span>ric Magniez. Lower bounds for randomized and quantum query complexity using <span>K</span>olmogorov arguments. , 38(1):46–62, 2008.

Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, and Mario Szegedy. Quantum query complexity of state conversion. In Rafail Ostrovsky, editor, <span>*<span>IEEE</span> 52nd Annual Symposium on Foundations of Computer Science, <span>FOCS</span> 2011, Palm Springs, CA, USA, October 22-25, 2011*</span>, pages 344–353. <span>IEEE</span> Computer Society, 2011.

Troy Lee, Fr<span>é</span>d<span>é</span>ric Magniez, and Miklos Santha. Improved quantum query algorithms for triangle detection and associativity testing. , 77(2):459–486, 2017.

Fr<span>é</span>d<span>é</span>ric Magniez, Miklos Santha, and Mario Szegedy. Quantum algorithms for the triangle problem. , 37(2):413–424, 2007.

Ben Reichardt. Reflections for quantum query algorithms. In Dana Randall, editor, <span>*Proceedings of the Twenty-Second Annual <span>ACM-SIAM</span> Symposium on Discrete Algorithms, <span>SODA</span> 2011, San Francisco, California, USA, January 23-25, 2011*</span>, pages 560–569. <span>SIAM</span>, 2011.

Ben W. Reichardt. Span programs are equivalent to quantum query algorithms. , 43(3):1206–1219, 2014.

Ben Reichardt and Robert Spalek. Span-program-based quantum algorithm for evaluating formulas. , 8(1):291–319, 2012.

Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. In <span>*43rd Symposium on Foundations of Computer Science <span>(FOCS</span> 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings*</span>, pages 513–519. <span>IEEE</span> Computer Society, 2002.

Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. , 26(5):1484–1509, 1997.

Robert Spalek and Mario Szegedy. All quantum adversary methods are equivalent. , 2(1):1–18, 2006.

Mario Szegedy. Quantum speed-up of <span>M</span>arkov chain based algorithms. In <span>*45th Symposium on Foundations of Computer Science <span>(FOCS</span> 2004), 17-19 October 2004, Rome, Italy, Proceedings*</span>, pages 32–41. <span>IEEE</span> Computer Society, 2004.

Shengyu Zhang. On the power of <span>A</span>mbainis lower bounds. , 339(2-3):241–256, 2005.

[^1]: Faculty of Computing, University of Latvia. Email: simpsonolivia@example.com

[^2]: Centre for Quantum Software and Information, University of Technology Sydney. Email: simpsonolivia@example.com

{'source': 'arXiv_out/2004'}