#  Round elimination in exact communication complexity

Jop Briët  Centrum Wiskunde & Informatica (CWI), Science Park 123, 1098 XG
Amsterdam, The Netherlands. Funded by a Rubicon grant from the Netherlands
Organization for Scientific Research (NWO). E-mail<EMAIL_ADDRESS> Harry
Buhrman  QuSoft, University of Amsterdam, and CWI, Science Park 123, 1098 XG
Amsterdam, The Netherlands. Supported by NWO Gravitation-grants NETWORKS and
QSC as well as EU grant QuantAlgo and CIFAR. E-mail<EMAIL_ADDRESS> Debbie
Leung  University of Waterloo, Waterloo, Canada. Funded in part by NSERC, CRC,
and CIFAR. E-mail<EMAIL_ADDRESS> Teresa Piovesan  Centrum
Wiskunde & Informatica (CWI), Science Park 123, 1098 XG Amsterdam, The
Netherlands. Funded in part by the EU project SIQS. E-mail:
<EMAIL_ADDRESS> Florian Speelman  Qusoft and Centrum Wiskunde &
Informatica (CWI), Science Park 123, 1098 XG Amsterdam, The Netherlands.
Funded in part by the EU project SIQS. E-mail<EMAIL_ADDRESS>
###### Abstract

We study two basic graph parameters, the chromatic number and the orthogonal
rank, in the context of classical and quantum exact communication complexity.
In particular, we consider two types of communication problems that we call
_promise equality_ and _list_ problems. For both of these, it was already
known that the one-round classical and one-round quantum complexities are
characterized by the chromatic number and orthogonal rank of a certain graph,
respectively.

In a promise equality problem, Alice and Bob must decide if their inputs are
equal or not. We prove that classical protocols for such problems can always
be reduced to one-round protocols with no extra communication. In contrast, we
give an explicit instance of a promise equality problem that exhibits an
exponential gap between the one- and two-round exact quantum communication
complexities. Whereas the chromatic number thus fully captures the complexity
of promise equality problems, the hierarchy of “quantum chromatic numbers”
(starting with the orthogonal rank) giving the quantum communication
complexity for every fixed number of communication rounds turns out to enjoy a
much richer structure.

In a list problem, Bob gets a subset of some finite universe, Alice gets an
element from Bob’s subset, and their goal is for Bob to learn which element
Alice was given. The best general lower bound (due to Orlitsky) and upper
bound (due to Naor, Orlitsky, and Shor) on the classical communication
complexity of such problems differ only by a constant factor. We exhibit an
example showing that, somewhat surprisingly, the four-round protocol used in
the bound of Naor et al. can in fact be optimal. Finally, we pose a conjecture
on the orthogonality rank of a certain graph whose truth would imply an
intriguing impossibility of _round elimination_ in quantum protocols for list
problems, something that works trivially in the classical case.

##  1 Introduction

The chromatic number $\chi(G)$ of a graph $G$ is the minimum number of colors
needed to color the vertices in such a way that adjacent vertices get
different colors. This important graph parameter appears frequently in
computer science and mathematics; it is well-known to be NP-hard to compute
and has recently found a number of meaningful generalizations in the context
of non-local games and entanglement-assisted zero-error information theory.
One of those generalizations is the _orthogonal rank_ of a graph, denoted
$\xi(G)$ and defined as follows. An orthonormal representation of a graph is
an assignment of complex unit vectors to the vertices such that adjacent
vertices receive orthogonal vectors. The orthogonal rank is the minimum
dimension of such a representation. Similar to the chromatic number, the
orthogonal rank is also NP-hard to compute (see Appendix A). In this paper, we
study both of these graph parameters in the context of communication
complexity.

Classical communication complexity. Since its introduction by Yao [Yao79]
communication complexity has become a standard model in computational
complexity that enjoys a wide variety of connections to other areas in
theoretical computer science [KN97]. Here two parties, Alice and Bob, receive
inputs $x,y$ from sets $\mathcal{X},\mathcal{Y}$ (resp.) and need to compute
the value $f(x,y)$ of a two-variable function $f$ known to them in advance.
Usually each party has insufficient information to solve the problem alone,
meaning that they have to exchange information about each others’ inputs. The
idea that communication is expensive motivates the study of the communication
complexity of $f$, which counts the minimal number of bits that the parties
must exchange on worst-case inputs. Throughout this paper, we consider only
exact (deterministic) communication protocols, meaning that no error is
allowed, and we will omit the word _exact_ from now on. Of particular
importance to this paper is the distinction between one-round protocols, where
all communication flows from Alice to Bob, and multi-round protocols, where
they take turns in sending messages from one party to the other.

Quantum communication complexity. In yet another celebrated paper, Yao [Yao93]
introduced quantum communication complexity, where to compute the value
$f(x,y)$ the parties are allowed to transmit qubits back and forth. The study
of this model has also become a well-established discipline in theoretical
computer science and quantum information theory. The most basic question that
arises when considering the classical and quantum models is whether they are
actually substantially different. An upper bound on the possible difference
between these models was proved by Kremer [Kre95, Theorem 4].111The result
stated here is actually a slight generalization of Kremer’s result (which
focuses on boolean functions) that can be proved in the same way; for
completeness we give a proof in Appendix B. Moreover, this statement (as well
as Kremer’s original formulation) holds in the bounded-error model of
communication complexity, not only in the exact one.

######  Theorem 1.1 (Kremer).

Any quantum protocol that uses $\ell$ qubits of communication can be turned
into a $2^{O(\ell)}$-bit one-round classical protocol for the same problem.

The first large gap between exact classical and quantum communication
complexity was demonstrated by Buhrman, Cleve, and Wigderson [BCW98], who gave
a problem admitting a one-round quantum protocol that is exponentially more
efficient than any (multi-round) classical protocol.

The chromatic number and orthogonal rank naturally show up in two types of
communication problems that we call _promise equality_ and _list_ problems,
discussed next.

###  1.1 Promise equality

In a _promise equality problem_ , Alice and Bob are either given equal inputs
or a pair of distinct inputs from a subset $\mathcal{D}$ of
$\binom{\mathcal{X}}{2}$ ($\mathcal{D}$ is known to them in advance). Their
goal is to decide whether their inputs are equal or different.

Classical communication complexity of promise equality problems. It was
observed by de Wolf [dW01, Theorem 8.5.1] that if
$G=(\mathcal{X},\mathcal{D})$ is the graph with vertex set $\mathcal{X}$ and
edge set $\mathcal{D}$, then the one-round classical communication of the
problem equals $\lceil{\log\chi(G)}\rceil$. Analogously, for each positive
integer $r$ one can define a “level-$r$” chromatic number of the graph
corresponding to the communication complexity of protocols that proceed in $r$
rounds or less. For general communication problems, using more rounds can
decrease the total communication, as is the case for the general Pointer
Jumping Problem, where for every positive integer $m$ there is an instance for
which any $m$-round protocol requires exponentially more communication than
the best $(m+1)$-round protocol [KN97, Section 4.2]. However, we show that
this is not true for promise equality problems (Lemma 3.1 below), meaning that
for such problems the chromatic number not only characterizes the one-round
complexity, but their overall communication complexity.

Quantum communication complexity of promise equality problems. The one-round
quantum communication complexity of promise equality problems is characterized
by the orthogonal rank of the associated graph $G=(\mathcal{X},\mathcal{D})$
[dW01, Theorem 8.5.2]. Indeed, it is not difficult to see that a one-round
quantum protocol of a promise equality problem is equivalent to an orthonormal
representation of $G$; the vectors correspond to the states that Alice would
send to Bob and orthogonality is required for Bob’s measurement to tell
whether they got equal inputs or not. Viewing the orthogonal rank as the “one-
round quantum chromatic number” naturally leads one to define a hierarchy of
such numbers where the level-$r$ quantum chromatic number corresponds to the
communication complexity of $r$-round quantum protocols. One might expect
that, as in the classical case, this hierarchy is redundant in that the levels
all carry the same number. However, one of our main results shows that in the
quantum setting, this is not the case.

######  Theorem 1.2.

There exist absolute constants $c,C\in(0,\infty)$, an infinite sequence of
natural numbers $n\in\mathbb{N}$ and a family of promise equality problems
$(\\{0,1\\}^{n},\mathcal{D}_{n})_{n\in\mathbb{N}}$ such that:

  * •

The one-round quantum communication complexity of
$(\\{0,1\\}^{n},\mathcal{D}_{n})$ is at least $cn$.

  * •

There is a two-round quantum protocol for $(\\{0,1\\}^{n},\mathcal{D}_{n})$
using at most $C\log n$ qubits.

During our analysis of the particular promise problem used for Theorem 1.2 we
answer an open question of Gruska, Qiu, and Zheng [GQZ14]. To explain this, we
briefly elaborate on what goes into our result. The problem we consider is
simple: Let $n$ be a positive integer multiple of $8$. Alice and Bob are given
$n$-bit strings $x$ and $y$, respectively, that are either equal or differ in
exactly $n/4$ coordinates and they must distinguish between the two cases. We
denote this problem by EQ-$\binom{n}{n/4}$. Similar promise equality problems
were studied before. In the above-mentioned result of Buhrman, Cleve, and
Wigderson [BCW98], which showed the first exponential gap between classical
and quantum communication, they used the problem EQ-$\binom{n}{n/2}$, where
Alice and Bob get $n$-bit strings that are either equal or differ in exactly
half of the entries (for $n$ a multiple of 4). They used a distributed version
of the Deutsch–Jozsa algorithm to give a one-round $O(\log n)$-qubit quantum
protocol, while a celebrated combinatorial result of Frankl and Rödl [FR87]
implies that the classical communication complexity is at least $\Omega(n)$.
Similar results were shown (based on similar techniques) in the above-
mentioned paper [GQZ14] for the analogous problem EQ-$\binom{n}{\alpha n}$
when $\alpha>1/2$, and the authors pose as an open problem to determine the
quantum communication complexity of EQ-$\binom{n}{\alpha n}$ when
$\alpha<1/2$. An easy observation is that the problem EQ-$\binom{n}{d}$ where
$n$ and $d$ have different parities is trivial: Alice has just to send the
parity bit of her string to Bob. For this reason, in this paper and in the
above-mentioned works both $n$ and $d$ are assumed to be even numbers.

To prove Theorem 1.2, we show that the one-round quantum communication
complexity of EQ-$\binom{n}{n/4}$ is at least $\Omega(n)$ and we give a two-
round protocol for it that uses at most $O(\log n)$ qubits. For the proof of
the first bound we use the famous Lovász theta number, which lower bounds the
orthogonal rank and therefore the one-round quantum communication complexity.
We prove a lower bound on the theta number using the theory of association
schemes and known properties of the roots of the Krawtchouk polynomials. Our
two-round protocol is based on a distributed version of Grover’s algorithm.
With a little extra technical work our results can be extended to any of the
problems EQ-$\binom{n}{\alpha n}$ with constant $\alpha<1/2$. In light of
Kremer’s Theorem and the obvious fact that the one-round classical
communication complexity is at least its quantum counterpart, we thus settle
the question of [GQZ14].

###  1.2 The list problem

In the _list problem_ , inputs are picked from a subset
$\mathcal{D}\subseteq\mathcal{X}\times\mathcal{Y}$ and the goal is for Bob to
learn Alice’s input. The reason for the name “list problem” is that Bob’s
input $y$ may just as well be given to him as the list (subset) of all of
Alice’s possible inputs $x$ satisfying $(x,y)\in\mathcal{D}$. A list problem
can thus equivalently be given by a family $\mathcal{L}\subseteq
2^{\mathcal{X}}$ of lists, where Bob gets a list $L\in\mathcal{L}$, Alice gets
an element $x\in L$, and Bob must learn $x$. We refer to this communication
problem as $\mathcal{L}$-list.

Classical communication complexity of list problems. Witsenhausen [Wit76]
observed that the one-round classical communication complexity of the list
problem is characterized by the chromatic number of the graph with vertex set
$\mathcal{X}$ and whose edge set consists of the pairs of distinct elements
appearing together in some list $L\in\mathcal{L}$. Denoting this graph by
$G_{\mathcal{L}}$, the one-round communication complexity equals
$\lceil{\log\chi(G_{\mathcal{L}})}\rceil$. The multi-round communication
complexity of the list problem has also been studied. Orlitsky [Orl90,
Corollary 3 and Lemma 3] proved the following lower bound in terms of the
chromatic number of $G_{\mathcal{L}}$, and the cardinality of the largest
list, denoted

$\omega(\mathcal{L})=\max\\{|L|:\,L\in\mathcal{L}\\}$

(not to be confused with the cardinality of the largest clique
$\omega(G_{\mathcal{L}})$, which can be larger).

######  Theorem 1.3 (Orlitsky).

For every family $\mathcal{L}\subseteq 2^{\mathcal{X}}$, the classical
communication complexity of $\mathcal{L}$-list is at least
$\max\\{\log\log\chi(G_{\mathcal{L}}),\log\omega(\mathcal{L})\\}$.

The basic idea behind the above result is that any multi-round protocol can be
simulated by a one-round protocol with at most an exponential difference in
communication, and that Alice must send sufficient information for Bob to be
able to distinguish among $\omega(\mathcal{L})$ elements. In the same work,
Orlitsky [Orl90, Theorem 4] gave a two-round classical protocol based on
perfect hashing functions that nearly achieves the above lower bound.

######  Theorem 1.4 (Orlitsky).

For every family $\mathcal{L}\subseteq 2^{\mathcal{X}}$, the two-round
classical communication complexity of $\mathcal{L}$-list is at most
${\log\log\chi(G_{\mathcal{L}})+3\log\omega(\mathcal{L})+4}$.

It thus follows from Witsenhausen’s observation and Theorem 1.4 that list
problems have exponentially more efficient two-round protocols than one-round
protocols, provided that $\omega(\mathcal{L})\leq
poly(\log\chi(G_{\mathcal{L}}))$. But Theorem 1.3 shows that—in stark contrast
with the Pointer Jumping Problem—using more than two rounds cannot decrease
the total amount of communication by more than a factor of 4, since obviously
${\log\log\chi(G_{\mathcal{L}})+3\log\omega(\mathcal{L})}\leq
4\max\\{\log\log\chi(G_{\mathcal{L}}),\log\omega(\mathcal{L})\\}$.
Furthermore, in a follow up work, Orlitsky [Orl91] showed that in general two-
round protocols are not sufficient to reach the communication complexity. The
natural question that thus arises is:

_Can the lower bound of Theorem 1.3 be attained by using more than two rounds
of communication?_

Towards answering this question, Naor, Orlitsky, and Shor [NOS93, Corollary 1]
slightly improved on Theorem 1.4 and showed that the four-round communication
complexity gets to within a factor of about 3 of the lower bound.

######  Theorem 1.5 (Naor–Orlitsky–Shor).

For every family $\mathcal{L}\subseteq 2^{\mathcal{X}}$, the four-round
classical communication complexity of $\mathcal{L}$-list is at most
$\log\log\chi(G_{\mathcal{L}})+2\log\omega(\mathcal{L})+3\log\log\omega(\mathcal{L})+7$.

As our contribution to this line of work we show that, perhaps surprisingly,
for some list problems the four-round protocol of Naor, Orlitsky, and Shor is
in fact asymptotically optimal, thus answering the above question in the
negative.

######  Theorem 1.6.

For any $\varepsilon>0$ there exists a set $\mathcal{X}$ and a family
$\mathcal{L}\subseteq 2^{\mathcal{X}}$ such that the classical communication
complexity of $\mathcal{L}$-list is at least
$\log\log\chi(G_{\mathcal{L}})+(2-\varepsilon)\log\omega(\mathcal{L})$.
Moreover, there exists such an $(\mathcal{X},\mathcal{L})$ pair for which
$\omega(\mathcal{L})=\log\chi(G_{\mathcal{L}})$.

In particular, our result gives a family of list problems with communication
complexity at least
$(3-\varepsilon)\max\\{\log\log\chi(G_{\mathcal{L}}),\log\omega(\mathcal{L})\\}$
for any $\varepsilon>0$.

Quantum communication complexity of list problems and quantum round
elimination. The one-round quantum communication complexity of list problems
is given by $\lceil{\log\xi(G_{\mathcal{L}})}\rceil$, which follows from the
same considerations as for the promise equality problems (see Lemma 4.4).
Based on a conjecture we make about the orthogonal rank of a certain family of
graphs, we believe that in the context of quantum communication complexity,
list problems may have the interesting property of resisting a quantum
analogue of _round elimination_.

In classical communication complexity, round elimination reduces the number of
rounds of a given protocol by having the parties send some extra information
instead. Consider the following basic example, where we start with a two-round
$(\log n+1)$-bit protocol in which Bob starts by sending Alice a single bit
and Alice replies with an $\log n$-bit string. This protocol can easily be
turned into a _one-round_ $2\log n$-bit protocol by having Alice directly send
Bob two $\log n$-bit strings, one corresponding to the case where Bob sends a
0 in the two-round protocol and another for if he sends a 1. Then Bob can just
pick the string corresponding to the bit he would have sent based on his input
and solve the problem.

A quantum analogue of the above example would turn a two-round $(\log
n+1)$-qubit protocol into a one-round $2\log n$-qubit protocol. We conjecture
that the following family of list problems is a counterexample to the
existence of such an analogue. For an even positive integer $n$ and $d\in[n]$,
let $\mathcal{L}_{d}\subseteq 2^{\\{0,1\\}^{n}}$ be the family of lists
$L\subseteq\\{0,1\\}^{n}$ of maximal cardinality such that all strings in $L$
have Hamming distance exactly $d$. Consider the family of lists given by
$\mathcal{K}=\mathcal{L}_{n/2}\cup\cdots\cup\mathcal{L}_{n}$. Similar to the
classical example above, we give a simple two-round protocol for
$\mathcal{K}$-list.

######  Theorem 1.7.

For $\mathcal{K}=\mathcal{L}_{n/2}\cup\cdots\cup\mathcal{L}_{n}$, there exists
a two-round protocol for $\mathcal{K}$-list where Bob sends Alice a single
qubit and Alice replies with a $((\log n)+1)$-qubit message.

It is easy to see that the graph $G_{\mathcal{K}}=(\\{0,1\\}^{n},E)$
associated with $\mathcal{K}$ has edge set $E$ given by all pairs of strings
with Hamming distance in $\\{n/2,\dots,n\\}$. In Appendix E we show that
$\Omega(n)\leq\xi(G_{\mathcal{K}})\leq O(2^{0.81n})$. We conjecture, however,
that the orthogonal rank of the graph $G_{\mathcal{K}}$ satisfies a much
stronger lower bound.222This conjecture has since been confirmed by Briët and
Zuiddam [BZ17].

######  Conjecture 1.8.

The graph $G_{\mathcal{K}}$ as above satisfies $\xi(G_{\mathcal{K}})\geq
n^{\omega(1)}$.

By the relation between the one-round quantum communication complexity of list
problems and the orthogonal rank of their associated graphs, it follows that
the validity of the above conjecture would imply that the exact one-round
quantum communication complexity of the above problem is super-logarithmic in
$n$, in marked contrast with the classical example of round elimination.

###  1.3 Connections to other work

Our work strengthens a link between communication complexity and graph theory
established by de Wolf [dW01]. Orthonormal representations appear in the
context of zero-error information theory. Indeed they were introduced by
Lovász [Lov79] to settle a famous problem of Shannon concerning the
(classical) capacity of the 5-cycle and they serve as proxies for
entanglement-assisted schemes [CMN+07, CLMW10, LMM+12, BBG12, BBL+15, CMR+14].
They also appear in the context of non-local games [CMN+07, GN08, SS12].
Nevertheless the orthogonal rank is poorly understood. To the best of our
knowledge, our result is the first time a lower bound on the dimension was
used. The use of the Lovász theta number in the context of communication
complexity problems also appears to be new and we hope that it may find
further applications there in the future. Finally, quantum variants of the
chromatic number that appeared in for example non-local games [CMN+07, SS12]
and zero-error information theory [BBL+15, CMR+14] can be interpreted as
quantum communication complexities of promise equality problems in various
different communication models, which puts those parameters in a more unified
framework.

##### Outline.

In Section 3 we study the promise equality problem and in particular we prove
Theorem 1.2. In Section 4 we discuss the list problem and prove Theorem 1.6
and Theorem 1.7.

##  2 Preliminaries

##### Graph theory.

Throughout the paper we consider only graphs that are simple - undirected, no
multiple edges and without loops. All the logarithms are in base two, unless
specified otherwise.

Given a graph $G=(V,E)$, $V$ and $E$ denote the vertex and edge set
respectively (equivalently denoted by $V(G)$ and $E(G)$). The complement of a
graph $G$, denoted by $\overline{G}$, has the same vertex set as the original
graph and a pair of vertices is adjacent if and only if it is non adjacent in
$G$. The _adjacency matrix_ of a graph $G$ is the $|V(G)|\times|V(G)|$
symmetric matrix where the $i,j$-th entry is equal to 1 if $ij\in E(G)$ and to
0 otherwise.

A clique of a graph is a set of pairwise adjacent vertices. The _clique
number_ $\omega(G)$ is the maximum cardinality of a clique. An independent set
is a set of pairwise non-adjacent vertices. The _independence number_
$\alpha(G)$ is the largest cardinality of an independent set. In other words,
for any graph $G$ we have $\omega(G)=\alpha(\overline{G})$. A $t$-coloring of
a graph $G$ is an assignment of $t$ colors such that adjacent vertices receive
different colors. The _chromatic number_ $\chi(G)$ is the minimum number $t$
such that a $t$-coloring exists. Equivalently, a coloring is a partition of
the vertex set into indepedent sets and therefore the inequality
$\chi(G)\alpha(G)\geq|V(G)|$ holds for every graph $G$. A (complex)
$d$-dimensional orthonormal representation of a graph $G$ is a map $\phi$ from
the vertex set to the $d$-dimensional complex unit sphere such that adjacent
vertices are mapped to orthogonal vectors. The _orthogonal rank_ $\xi(G)$ is
the minimum $d\in\mathbb{N}$ for which a $d$-dimensional orthonormal
representation exists. We stress that we consider the representations over the
complex sphere and not, as more usual in the combinatorial literature, over
the real one and that orthogonalities are required for adjacent vertices. A
simple observation gives that $\omega(G)\leq\xi(G)$.

With $H(n,d)$ we denote the graph that has $\\{0,1\\}^{n}$ as vertex set and
where two $n$-bit strings are adjacent if they differ exactly in $d$
positions. Equivalently, $H(n,d)$ is the graph with vertex set
$\\{-1,1\\}^{n}$ where two vertices are adjacent if their inner product is
equal to $n-2d$.

##### Orthogonality lemma.

We will make repeated use of the following standard lemma (see for example
[BBL+15]), which we will refer to here as the Orthogonality Lemma.

######  Lemma 2.1 (Orthogonality Lemma).

Let $\rho_{1},\dots,\rho_{\ell}\in\mathbb{C}^{d\times d}$ be a collection of
Hermitian positive semidefinite matrices. Then the following are equivalent:

  1. 1.

We have $\rho_{i}\rho_{j}=0$ for every $i\neq j\in[\ell]$.

  2. 2.

There exists a measurement consisting of positive semidefinite matrices
$P^{1},\dots,P^{\ell}$, $P^{\perp}\in\mathbb{C}^{d\times d}$ such that
$\operatorname{\mathsf{Tr}}(P^{i}\rho_{j})=\delta_{ij}\operatorname{\mathsf{Tr}}(\rho_{j})$
and $\operatorname{\mathsf{Tr}}(P^{\perp}\rho_{j})=0$ for every
$i,j\in[\ell]$.

In particular, a collection of pure states
$|\phi_{1}\rangle,\dots,|\phi_{\ell}\rangle\in\mathbb{C}^{d}$ can be perfectly
distinguished with a quantum measurement if and only if they are pairwise
orthogonal.

##  3 Promise Equality

In a promise equality problem, Alice and Bob each receive an input from a set
$\mathcal{X}$ with the promise that their inputs either are equal or come from
a subset $\mathcal{D}$ of $\binom{\mathcal{X}}{2}$ (known to the players
beforehand). The goal is to distinguish between the two cases. To any promise
equality problem, we associate the graph $G=(\mathcal{X},\mathcal{D})$.

###  3.1 General properties of promise equality

As we mentioned earlier, the one-round classical communication complexity of
the problem equals $\lceil{\log\chi(G)}\rceil$. We begin by proving that the
chromatic number of the associated graph actually gives the overall
communication complexity.

######  Lemma 3.1.

For any promise equality problem, the classical communication complexity is
attained with a single round of communication.

###### Proof.

We show how to transform a $k$-round communication protocol into a one-round
protocol that uses the same amount of bits. To summarize, the idea is that
Alice mimics all the rounds of communication assuming that her input is equal
to Bob’s one, and sends them in one-round. He then checks whether the message
received is consistent with his input. If this is not the case, then he knows
that the two strings are different, otherwise he completes the protocol.

More formally, fix a protocol $P$ that requires $k$ rounds, where $k\geq 2$.
Suppose that Alice has input $x$ and Bob has $y$. We assume that the first
round of communication is from Alice to Bob, but the same reasoning applies in
the other case. For $i$ odd, let $a_{i}$ be the message that Alice would send
to Bob on the $i$-th round of communication if she followed protocol $P$ and
used the knowledge of the messages exchanged in the previous rounds and of her
input $x$. Similarly, for $i$ even, let $\hat{b}_{i}$ be the message that Bob
would send to Alice on the $i$-th round of communication if he had $y=x$ as
input, followed the protocol $P$ and used the knowledge derived by the
previous rounds. Using the protocol $P$, Alice can mimic Bob’s rounds of
communication under the assumption that Bob’s input is equal to $x$. Alice
uses her input $x$ to produce the string $a_{1}\hat{b}_{2}a_{3}\dots
a_{i}\hat{b}_{i+1}\dots a_{k}$ and sends it to Bob in one round. From his
input $y$, Bob constructs the messages $b_{i}$ that he would have produced
during the protocol $P$, with the knowledge of Alice’s messages $a_{\ell}$ and
his messages $b_{\ell}$ for all $\ell<i$. If there exists an index $i$ such
that $b_{i}\neq\hat{b}_{i}$, then $x$ must be different from $y$. Otherwise,
Bob uses the transcript $a_{1}\hat{b}_{2}a_{3}\dots a_{i}\hat{b}_{i+1}\dots
a_{k}$ to finish the protocol and either outputs $x=y$ or $x\neq y$. We have
constructed a one-round communication protocol $\hat{P}$ that works as the
original protocol $P$ does and whose worst-case transcript length is at most
as long as the one of $P$. Therefore if $P$ is an optimal protocol, so is
$\hat{P}$. ∎

As mentioned in the introduction, de Wolf [dW01, Theorem 8.5.2] showed that
one-round quantum protocols are related to orthonormal representations. We
include a proof here for completeness.

######  Theorem 3.2 (de Wolf).

Consider a promise equality problem defined by the sets $\mathcal{X}$ and
$\mathcal{D}$, then its one-round quantum communication complexity is equal to
$\lceil{\log\xi(G)}\rceil$, where $G=(\mathcal{X},\mathcal{D})$.

###### Proof.

Let $P$ be an optimal one-round protocol for the considered promise equality
problem. Without loss of generality, Alice sends pure state
$|\phi_{x}\rangle\in\mathbb{C}^{d}$ on input $x\in\mathcal{X}$. For any pair
$(x,y)\in\mathcal{D}$, $|\phi_{x}\rangle$ and $|\phi_{y}\rangle$ have to be
perfectly distinguishable and therefore, in view of Lemma 2.1, they must be
orthogonal. Hence, the map $\phi:\mathcal{X}\to\mathbb{C}^{d}$ where
$\phi(x)=|\phi_{x}\rangle$ is a $d$-dimensional orthonormal representation of
$G=(\mathcal{X},\mathcal{D})$ and $\xi(G)\leq d$.

On the other hand, let $\phi$ be a $d$-dimensional orthonormal representation
of the graph $G=(\mathcal{X},\mathcal{D})$ and consider the one-round quantum
protocol that transmits $\phi(x)\in\mathbb{C}^{d}$ on input $x\in\mathcal{X}$.
This uses $\log d$-qubits of communication. From Lemma 2.1 we know that Bob
can use his input $y$ to perform a quantum measurement that allows him to
learn whether his input is equal or not to Alice’s one. Thus, the one-round
quantum communication complexity of this problem is at most
$\lceil{\log\xi(G)}\rceil$. ∎

###  3.2 Proof of Theorem 1.2

The rest of this section will be devoted to the proof of Theorem 1.2, which
shows that there is a family of promise equality problems where allowing two
rounds of quantum communication is exponentially more efficient than a single
round. The problem that exhibits this separation is EQ-$\binom{n}{n/4}$, where
Alice and Bob each receive an $n$-bit string that are either equal or differ
in exactly $n/4$ positions (with $n$ a multiple of $8$). We denote by
$H(n,n/4)$ the graph associated with this problem. We split the proof in two
parts: in Section 3.2.1 we bound the one-round quantum communication
complexity and in Section 3.2.2 we give the two-round protocol.

With a bit of extra work, we can also prove that for any of the problems
EQ-$\binom{n}{\alpha n}$ where $\alpha\in(0,1/2)$ and $n$, $\alpha n$ are
even, there is a quantum multi-round protocol that is exponentially more
efficient than a single round one. The lower bound on the one-round quantum
communication complexity is explain in Section 3.2.1, while the multi-round
protocol can be found in Appendix C.

####  3.2.1 One-round quantum communication complexity of EQ-$\binom{n}{n/4}$

The main result of this section is the following theorem, which gives the
first part of Theorem 1.2.

######  Theorem 3.3.

The one-round quantum communication complexity of EQ-$\binom{n}{n/4}$ is at
least $\Omega(n)$.

We remark that the statement of the above theorem holds for any problem
EQ-$\binom{n}{\alpha n}$ where $\alpha\in(0,1/2)$ and where $n$, $\alpha n$
are even. Indeed, in this section we prove a lower bound on the orthogonal
rank of any graph $H(n,\alpha n)$ (where $\alpha\in(0,1/2)$ and $n$, $\alpha
n$ are even) and then use Theorem 3.2 and focus on the case where $\alpha=1/4$
to derive Theorem 3.3.

We prove the desired bound in three steps: first, we show that the Lovász
theta number is a lower bound for the orthogonal rank; second, we use
structural properties of $H(n,d)$ together with known properties of the theta
number to reformulate this bound in terms of the eigenvalues of the adjacency
matrix of this graph; third, we bound the eigenvalues to get the desired
result.

Step 1: The Lovász theta number. This parameter was introduced by Lovász
[Lov79] to upper bound the Shannon capacity of a graph. Among its many
equivalent definitions, we will use the following primal and dual
formulations:

$\displaystyle\vartheta(G)=$ $\displaystyle\max\;\sum_{i,j\in
V(G)}X_{ij}\quad\text{s.t.}\quad X\in\mathcal{S}^{|V(G)|}_{+},\quad\sum_{i\in
V(G)}X_{ii}=1,\quad X_{ij}=0\quad\forall ij\in E(G),$ (1)
$\displaystyle\vartheta(G)=\min$ $\displaystyle t\quad\text{s.t.}\quad
X\in\mathcal{S}^{|V(G)|}_{+},\quad X_{ii}=t-1\quad\forall i\in V(G),\quad
X_{ij}=-1\quad\forall ij\in E(\overline{G}),$

where $\mathcal{S}^{n}_{+}$ is the set of $n\times n$ symmetric positive
semidefinite matrices.

Lovász [Lov79] proved that the theta number lower bounds the minimum dimension
of an orthonormal representation where the vectors are real valued. Note that
this is slightly different from our setting where we allow the vectors to have
complex entries. However, we show that the Lovász theta number is also a lower
bound for $\xi(G)$. The proof is an adaptation to the complex case of a known
proof [Lau14].

######  Lemma 3.4.

For any graph $G$, we have $\xi(G)\geq\vartheta(\overline{G})$.

###### Proof.

Let $n=|V(G)|$ and label the vertices of the graph $G$ by $\\{1,2,\dots,n\\}$.
Suppose that the orthogonal rank of $G$ is equal to $d$ and that
$u_{1},\dots,u_{n}\in\mathbb{C}^{d}$ are the unit vectors forming an
orthonormal representation of $G$. For every vertex of the graph $i\in[n]$,
define a matrix $U_{i}=u_{i}u_{i}^{\dagger}$ and $U_{0}=I_{d}$. Let $Z$ be a
$(n+1)\times(n+1)$ matrix where the $i,j$-th entry $Z_{ij}=\langle
U_{i},U_{j}\rangle=\operatorname{\mathsf{Tr}}(U_{j}^{\dagger}U_{i})$ for every
$i,j\in\\{0\\}\cup[n]$. Notice that $Z$ is positive semidefinite since it is
the Gram matrix of a set of complex vectors. Moreover, $Z$ is real valued and
we get that $Z_{00}=d$, $Z_{0i}=\langle I,u_{i}u_{i}^{\dagger}\rangle=1$ and
$Z_{ii}=\langle
u_{i}u_{i}^{\dagger},u_{i}u_{i}^{\dagger}\rangle=(u_{i}^{\dagger}u_{i})^{2}=1$
for all $i\in V(G)$ and that
$Z_{ij}=(u_{i}^{\dagger}u_{j})(u_{j}^{\dagger}u_{i})\geq 0$ for all $i,j\in
V(G)$ with equality if $ij\in E(G)$. By taking the Schur complement333 Let $X$
be a symmetric matrix of the form $X=\big{(}\begin{smallmatrix}\alpha&b^{T}\cr
b&A\end{smallmatrix}\big{)},$ where $b\in\mathbb{R}^{n-1}\text{ and
}\alpha>0$. $X$ is positive semidefinite if and only if $A-bb^{T}/\alpha$ is
positive semidefinite. The matrix $A-bb^{T}/\alpha$ is called the Schur
complement in $X$ with respect to the entry $\alpha$.  in ${Z}$ with respect
to the entry ${Z}_{00}$, we obtain a new symmetric positive semidefinite
matrix $X$ with $X_{ii}=1-1/d$ for all $i\in V(G)$ and $X_{ij}=-1/d$ for all
$ij\in E(G)$. Rescaling $X$ by $d$, we get a feasible solution for the
minimization program in (1) of $\vartheta(\overline{G})$ with value $d$. We
conclude that $d=\xi(G)\geq\vartheta(\overline{G})$. ∎

Step 2: Eigenvalue bound on the theta number. In the second step we show that
the theta number of the graph $H(n,d)$ can be expressed in terms of the
eigenvalues of its adjacency matrix. For the remainder of this step, by the
eigenvalues of a graph we mean the eigenvalues of its adjacency matrix.

######  Lemma 3.5.

For every positive integer $n$ and $d\in[n]$, we have
$\vartheta(\overline{H(n,d)})=1-\binom{n}{d}/{\lambda_{\text{\sc min}}}$,
where $\lambda_{\text{\sc min}}$ is the smallest eigenvalue of $H(n,d)$.

Let us recall the following standard definitions. Let $G=(V,E)$ be a graph. A
permutation $\pi:V\to V$ is _edge preserving_ if for every edge $\\{u,v\\}\in
E$, we have $\\{\pi(u),\pi(v)\\}\in E$. The graph $G$ is _vertex-transitive_
if for every pair of vertices $u,v\in V$ there is an edge-preserving
permutation $\pi:V\to V$ such that $\pi(u)=v$. Moreover, $G$ is _edge-
transitive_ if for every pair of edges $\\{u_{1},v_{1}\\},\\{u_{2},v_{2}\\}\in
E$, there is an edge-preserving permutation $\pi:V\to V$ such that
$\pi(u_{1})=u_{2}$ and $\pi(v_{1})=v_{2}$. Lovász [Lov79, Theorems 8 and 9]
showed that if a graph is both vertex- and edge-transitive, then the theta
number is given by a simple formula involving its eigenvalues.

######  Lemma 3.6 (Lovász).

For a positive integer $n$ let $G$ be an $n$-vertex graph with eigenvalues
$\lambda_{1}\geq\dots\geq\lambda_{n}$. If $G$ is both vertex- and edge-
transitive, then $\vartheta(\overline{G})=1-\lambda_{1}/\lambda_{n}$.

###### Proof of Lemma 3.5.

We start by showing that $H(n,d)$ is vertex-transitive. Given any pair of
vertices $u,v\in\\{0,1\\}^{n}$ of $H(n,d)$, consider the automorphism of the
graph $H(n,d)$ that maps $x\mapsto x\oplus u\oplus v$ where $\oplus$ is the
bit-wise addition. This map preserves the Hamming distance, and therefore the
adjacencies, between the vertices and sends $u\mapsto v$. Hence $H(n,d)$ is
vertex-transitive.

To show that $H(n,d)$ is edge-transitive, fix any two edges $uv$ and $st$ and
let $p=u\oplus v$, $q=s\oplus t$. Noting that the $n$-bit strings $p$ and $q$
have the same Hamming weight $d$, let $\pi$ be a permutation of the indices
such that $\pi(p)=q$. We define $\nu$ to be an automorphism that sends a
vertex $x$ to $\pi(x\oplus u)\oplus s$. The map $\nu$ preserves the edges of
$H(n,d)$ and, since the permutation $\pi$ maps the all-zero string to itself
and $p$ to $q$, we have that $\nu(u)=s$ and $\nu(v)=t$. Hence, $H(n,d)$ is
edge-transitive.

Finally, since the largest eigenvalue of a vertex-transitive graph is equal to
its degree, we clearly have $\lambda_{1}(H(n,d))=\binom{n}{d}$. The result now
follows from Lemma 3.6. ∎

Step 3: Bound on the smallest eigenvalue of $H(n,d)$. Finally, we prove an
upper bound on the magnitude of the smallest eigenvalue of $H(n,d)$.

######  Lemma 3.7.

Let $n$ and $d$ be even positive integers such that $d<n/2$. Then, the
smallest eigenvalue $\lambda_{\text{\sc min}}$ of the graph $H(n,d)$ is a
negative number such that

$|\lambda_{\text{\sc
min}}|\leq\sqrt{\frac{2^{n}\binom{n}{d}}{\binom{n}{n/2-\sqrt{d(n-d)}}}}.$

The proof of the lemma uses the following facts from coding theory that can be
found in the survey [DL98]. The eigenvalues of $H(n,d)$ play a fundamental
role in the theory of Hamming association schemes, where they are expressed in
terms of a set of orthogonal polynomials known as the (binary) _Krawtchouk
polynomials_. For a positive integer $n$ and $d=0,1,\dots,n$, the Krawtchouk
polynomial $K_{d}^{n}\in\mathbb{R}[x]$ is a degree-$d$ polynomial that is
uniquely defined by

$K_{d}^{n}(x)=\sum_{j=0}^{d}(-1)^{j}\binom{x}{j}\binom{n-x}{d-j},\quad\quad
x=0,1,\dots,n.$ (2)

When $n$ and $d$ are even, then $K_{d}^{n}$ is symmetric about the point
$x=n/2$. Moreover, these polynomials satisfy the important orthogonality
relation

$\sum_{x=0}^{n}\binom{n}{x}K_{d}^{n}(x)K_{d^{\prime}}^{n}(x)=\delta_{d,d^{\prime}}\binom{n}{d}2^{n}.$
(3)

The set of distinct eigenvalues of $H(n,d)$ turns out to be
$\\{K_{d}^{n}(0),K_{d}^{n}(1),\dots,K_{d}^{n}(n)\\}$. Crucial to our proof of
Lemma 3.7 then, is the following result of Levenshtein [Lev95, Theorem 6.1]
characterizing the smallest roots of the Krawtchouk polynomials.

######  Theorem 3.8 (Levenshtein).

Let $n$ be a positive integer and $d\in[n]$. Then, $K_{d}^{n}$ has exactly $d$
distinct roots and its smallest root is given by

$n/2-\max_{z}\Big{(}\sum_{i=0}^{d-2}z_{i}z_{i+1}\sqrt{(i+1)(n-i)}\Big{)},$ (4)

where the maximum is over all vectors $z=(z_{0},\dots,z_{d-1})$ on the real
Euclidean unit sphere.

This implies the following general bound on the location of the smallest root
of $K_{d}^{n}$. The bound is stated for instance in [KL01], but since we were
unable to find a published proof we include one here for completeness.

######  Corollary 3.9.

Let $n$ and $d$ be positive integers such that $d<n/2$. Then, the smallest
root of $K_{d}^{n}$ lies in the interval
$\big{[}n/2-\sqrt{(n-d)d},n/2\big{]}$.

###### Proof.

It is clear that (4) is trivially upper bounded by $n/2$. We focus on the
lower bound. To this end, let $z=(z_{0},\dots,z_{d-1})$ be a real unit vector
achieving the maximum in (4). For $i\in\\{0,1,\dots,d-1\\}$ define the numbers
$a_{i}=z_{i}\sqrt{n-i}$ and $b_{i}=z_{i+1}\sqrt{i+1}$. By the Cauchy-Schwarz
inequality,

$\displaystyle\Big{(}\sum_{i=0}^{d-2}z_{i}z_{i+1}\sqrt{(i+1)(n-i)}\Big{)}^{2}$
$\displaystyle=\Big{(}\sum_{i=0}^{d-2}a_{i}b_{i}\Big{)}^{2}$
$\displaystyle\leq\Big{(}\sum_{i=0}^{d-2}a_{i}^{2}\Big{)}\Big{(}\sum_{j=0}^{d-2}b_{j}^{2}\Big{)}$
$\displaystyle=\Big{(}\sum_{i=0}^{d-2}a_{i}^{2}\Big{)}\Big{(}\sum_{j=1}^{d-1}b_{j-1}^{2}\Big{)}$
$\displaystyle\leq\Big{(}\sum_{i=0}^{d-1}a_{i}^{2}\Big{)}\Big{(}\sum_{j=0}^{d-1}b_{j-1}^{2}\Big{)}$
$\displaystyle=\Big{(}\sum_{i=0}^{d-1}z_{i}^{2}(n-i)\Big{)}\Big{(}\sum_{j=0}^{d-1}z_{j}^{2}j\Big{)}$
$\displaystyle=\Big{(}n-\sum_{i=0}^{d-1}z_{i}^{2}i\Big{)}\Big{(}\sum_{j=0}^{d-1}z_{j}^{2}j\Big{)},$
(5)

where in the last equality we used the fact that $z$ is a unit vector. Observe
that the sum $\sum_{i=0}^{d-1}z_{i}^{2}i$ lies in the interval $[0,d-1]$.
Hence, since $d<n/2$, (5) is at most
$\max\\{(n-t)t:\,t\in[0,d-1]\\}=(n-(d-1))(d-1)\leq(n-d)d$. ∎

###### Proof of Lemma 3.7.

Since the trace of a matrix equals the sum of its eigenvalues and the trace of
an adjacency matrix is zero, it follows that $\lambda_{\text{\sc min}}<0$.

Recall that the eigenvalues of $H(n,d)$ belong to the set
$\\{K_{d}^{n}(x):\,x=0,1,\dots,n\\}$. Moreover, since by our assumption $n$
and $d$ are even, the polynomial $K_{d}^{n}$ is symmetric about the point
$n/2$. Also observe that $K_{d}^{n}(0)>0$ and hence the first time this
polynomial assumes a negative value is somewhere beyond its smallest root,
i.e. the smallest $x$ for which $K_{d}^{n}(x)<0$ lies in between the smallest
root and $n/2$. It therefore follows from Corollary 3.9 and from the fact that
$K_{d}^{n}$ is symmetric about the point $n/2$ that $\lambda_{\text{\sc
min}}=K_{d}^{n}(x^{\star})$ for some integer
$x^{\star}\in[n/2-\sqrt{(n-d)d},n/2]$.

Clearly (3) implies that

$\sum_{x=0}^{n}\binom{n}{x}K_{d}^{n}(x)^{2}=\binom{n}{d}2^{n}.$

Hence,

$\binom{n}{x^{\star}}K_{d}^{n}(x^{\star})^{2}\leq\binom{n}{d}2^{n}$

and we can conclude that

$|\lambda_{\text{\sc
min}}|^{2}=|K_{d}^{n}(x^{\star})|^{2}\leq\frac{2^{n}\binom{n}{d}}{\binom{n}{x^{\star}}}\leq\frac{2^{n}\binom{n}{d}}{\binom{n}{n/2-\sqrt{(n-d)d}}}.$

∎

Putting everything together. To conclude this section, we combine the main
lemmas of the above three steps to prove Theorem 3.3.

###### Proof of Theorem 3.3.

Combining Lemmas 3.4, 3.5, and 3.7 gives

$\xi(H(n,d))\geq\vartheta\big{(}\overline{H(n,d)}\big{)}\geq
1-\binom{n}{d}/\lambda_{\text{\sc min}}\geq
1+\sqrt{\frac{\binom{n}{d}\binom{n}{n/2-\sqrt{(n-d)d}}}{2^{n}}}.$ (6)

We take the logarithm and use Stirling’s approximation:
$\log\binom{n}{k}=\big{(}H(k/n)+o(1)\big{)}n$, where $H(p)=-p\log
p-(1-p)\log(1-p)$ is the binary entropy function and the $o(1)$ term goes to
zero as $n\to\infty$ (see for example [SF14, p. 64]). Then, for $\alpha=d/n$,
the logarithm of (6) is at least

$\frac{1}{2}\log\left(\frac{\binom{n}{d}\binom{n}{n/2-\sqrt{(n-d)d}}}{2^{n}}\right)=\frac{n}{2}\left(H(\alpha)+H\left(1/2-\sqrt{(1-\alpha)\alpha}\right)-1+o(1)\right).$

Using properties of the binary entropy, it can be shown that
$H(\alpha)+H(1/2-\sqrt{(1-\alpha)\alpha})-1>0$ for any $\alpha\in(0,1/2)$ (for
the proof see Appendix D). In particular, $\log\xi(H(n,n/4))\geq\Omega(n)$. ∎

####  3.2.2 Two-round quantum communication

Using a distributed version of Grover’s search algorithm, we find a quantum
protocol that solves EQ-$\binom{n}{n/4}$ with a logarithmic number of qubits,
which gives the second part of Theorem 1.2.

######  Theorem 3.10.

The two-round quantum communication complexity of EQ-$\binom{n}{n/4}$ is at
most $2\lceil{\log n}\rceil+1$ qubits.

###### Proof.

Let $x$ and $y$ be the inputs of Alice and Bob, respectively, and $z=x\oplus
y$ be their bit-wise addition. The promise ensures that either $|z|=0$ if
$x=y$ or $|z|=n/4$ in the case where $x\neq y$.

If a bit string $z\in\\{0,1\\}^{n}$ is known to contain exactly $n/4$ entries
that are 1, Grover’s algorithm [Gro96] is able to find one of these entries
without error [BBHT98], needing only a single query to the string $z$. For any
string we define the query unitary
$U_{z}=\sum_{i=1}^{n}(-1)^{z_{i}}|i\rangle\\!\langle i|$ and we define
$|s\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}|i\rangle$ to be the uniform
superposition of all basis states. Then $G=2|s\rangle\\!\langle s|-I$ is a
unitary operation known as the Grover diffusion operator.

The quantum communication protocol can be viewed as combining Grover’s
algorithm with a special case of the simulation theorem given in [BCW98,
Theorem 2.1]. We want to perform the algorithm on the effective string
$z=x\oplus y$, using the fact that performing a single query $U_{z}$ is the
same as performing the operations $U_{x}$ and $U_{y}$ in sequence, i.e.,
$U_{z}=U_{x}U_{y}=U_{y}U_{x}$.

At the start of the protocol, Bob creates the state $U_{y}|s\rangle$ and sends
this state over to Alice using $\lceil{\log{n}}\rceil$ qubits. Alice first
applies $U_{x}$ to the incoming state and then applies the Grover operator
$G$. The final state of Grover’s algorithm is
$\frac{1}{\sqrt{n/4}}\sum_{i\text{ s.t.\ }z_{i}=1}|i\rangle$ if $|z|=n/4$.
That is, in the case that $x\neq y$, Grover’s algorithm has produced a
superposition over all indices $i$ such that $x_{i}\neq y_{i}$. Alice measures
the state, obtaining some index $i^{*}$ such that $x_{i^{*}}\neq y_{i^{*}}$ if
$x\neq y$. Then she sends $i^{*}$ and the value $x_{i^{*}}$ over to Bob using
$\lceil{\log n}\rceil+1$ qubits. He outputs ‘equal’ if and only if
$x_{i^{*}}=y_{i^{*}}$. The total communication cost of the protocol is then
$2\lceil{\log n}\rceil+1$ qubits. ∎

The above protocol can be extended to efficiently solve EQ-$\binom{n}{\alpha
n}$ for constants $\alpha<1/2$ (independent of $n$) in a constant number of
rounds, by using a more general exact version of the Grover search algorithm.
This construction is described in Appendix C.

###  3.3 Distances close to $n/2$

In [BCW98, GQZ14] it is shown that for any $\alpha\geq 1/2$, the problem
EQ-$\binom{n}{\alpha n}$ admits an $O(\log n)$-qubit one-round quantum
protocol, whereas the proof of our Theorem 3.3 shows that for
$\alpha\in(0,1/2)$ (independent of $n$), the one-round quantum communication
complexity of EQ-$\binom{n}{\alpha n}$ is at least $\Omega(n)$. Does the
threshold of this exponential jump sit exactly at $1/2$? In the following
simple lemma, we prove that this is not the case. When $\alpha$ is strictly
smaller than $1/2$ but very close to it, the one-round quantum communication
complexity of EQ-$\binom{n}{\alpha n}$ still requires only a logarithmic
number of qubits.

######  Lemma 3.11.

For $d=n/2-\ell$ with $\ell\leq O(\log n)$, $n$ and $d$ even, the one-round
quantum communication complexity of EQ-$\binom{n}{d}$ is at most $O(\log n)$.

###### Proof.

We first make the following easy observation. Suppose Alice sends to Bob the
first $2\ell$ bits of her input. If this $2\ell$-bit string differ from Bob’s
initial part of the input, he knows that the answer is ‘not equal’. Otherwise
Alice and Bob have to exchange information about the remaining part of their
inputs, which have length $n^{\prime}=n-2\ell$ and they are either equal or
differ in exactly $d^{\prime}=d=n/2-\ell=n^{\prime}/2$ positions.

Hence, the map $\phi:\\{0,1\\}^{n}\to\mathbb{C}^{2^{2\ell}n^{\prime}}$ that
sends $x\mapsto x_{1}\otimes x_{2}\otimes\dots\otimes
x_{2\ell}\otimes\frac{1}{\sqrt{n^{\prime}}}\sum_{i=1}^{n^{\prime}}(-1)^{x_{i+2\ell}}e_{i}$,
where $e_{i}$ is the $i$-th canonical basis vector, is an orthonormal
representation of the graph $H(n,d)$. The result now follows from Theorem 3.2.
∎

##  4 The list problem

In this section, we consider the $\mathcal{L}$-list problem: Bob gets a list
$L\in\mathcal{L}$ from a family $\mathcal{L}\subseteq 2^{\mathcal{X}}$ of
lists, Alice gets an element $x\in L$, and Bob must learn $x$.

###  4.1 Classical communication complexity of the list problem

Here we prove Theorem 1.6. The list problem that gives the result is simple:
For positive integers $k,N$ such that $2\leq k\leq N$, we consider the list
problem $\mathcal{L}=\binom{\mathcal{[}N]}{k}$, where the family of lists
consists of all $k$-element subsets of $[N]$. Note that for this
$\mathcal{L}$, we clearly have $\omega(\mathcal{L})=k$ (not to be confused
with $\omega(G_{\mathcal{L}})=N$) and that $G_{\mathcal{L}}$ is the complete
graph on $N$ vertices, giving $\chi(G_{\mathcal{L}})=N$. Hence, Theorem 1.5
gives a four-round protocol using at most $\log\log N+2\log k+O(\log\log k)$
bits of communication.

######  Theorem 4.1.

The classical communication complexity of $\binom{[N]}{k}$-list is at least

$\log\log N+2\log(k-1)-\log\log(k-1)-O(1).$

To see that this implies Theorem 1.6 note that the above bound can be written
as $\log\log\chi(G_{\mathcal{L}})+(2-o(1))\log\omega(\mathcal{L})$, where the
term $o(1)$ goes to zero as $k\to\infty$. Choosing $k=\log N$ then gives the
second part of the theorem.

To prove Theorem 4.1, we use a bound on the size of cover-free families due to
Dýachkov and Rykov [DR82]; see [Rus94, Für96] for simplified proofs (in
English).

######  Definition 4.2.

Let $r$ be a positive integer and $\mathcal{S}$ be a finite set. A family
$\mathcal{F}\subseteq 2^{\mathcal{S}}$ of at least $r+1$ subsets is _$r$
-cover-free_ if every subfamily of $r+1$ distinct sets
$F_{0},F_{1},\dots,F_{r}\in\mathcal{F}$ satisfies $F_{0}\nsubseteq
F_{1}\cup\dots\cup F_{r}$.

######  Theorem 4.3 (Dýachkov–Rykov).

There exists an absolute constant $c>0$ such that the following holds. Let $N$
and $r$ be positive integers such that $N\geq r+1$ and $r\geq 2$. Let
$\mathcal{S}$ be a finite set. Let $\mathcal{F}\subseteq 2^{\mathcal{S}}$ be
an $r$-cover free family consisting of $N$ sets. Then,

$|\mathcal{S}|\geq\frac{cr^{2}\log N}{\log r}.$

###### Proof of Theorem 4.1.

For a positive integer $C$, suppose that the communication complexity of
$\binom{[N]}{k}$-list is $C$. Fix such a protocol and for every input pair
$(x,L)$ in the $\binom{[N]}{k}$-list problem, define the _transcript_
$T_{x,L}\in\\{0,1\\}\cup\\{0,1\\}^{2}\cup\cdots\cup\\{0,1\\}^{C}$ as the
concatenation of the parties’ messages in the order they are sent during their
conversation on input $(x,L)$. Let $\mathcal{T}$ be the set of said
transcripts.

For each transcript $T\in\mathcal{T}$, denote by $T^{A}$ the sequence of
Alice’s messages in $T$, to be understood as a sequence of strings indexed by
her rounds in the conversation. Let
$\mathcal{F}=\\{F_{x}\\}_{x\in\mathcal{X}}\subseteq 2^{\mathcal{T}}$ be the
family where each $F_{x}$ is the collection of transcripts $T\in\mathcal{T}$
that is consistent with $x$ being Alice’s input and that agrees on $T^{A}$. We
claim that $\mathcal{F}$ is a $(k-1)$-cover free family. To see this, take any
$k$ sets of $\mathcal{F}$, say $F_{x_{0}},\dots,F_{x_{k-1}}$, and let $L$ be
the corresponding $k$-element list $\\{x_{0},\dots,x_{k-1}\\}$. Consider the
transcript $T_{x_{0},L}$ of the input pair $(x_{0},L)$. Clearly,
$T_{x_{0},L}\in F_{x_{0}}$. We show that $T_{x_{0},L}\not\in F_{x_{i}}$ for
each ${i\in\\{1,\dots,k-1\\}}$, which gives the claim as this implies that
$F_{x_{0}}\not\subseteq F_{x_{1}}\cup\cdots\cup F_{x_{k-1}}$. Suppose that
$T_{x_{0},L}\in F_{x_{i}}$ holds for some ${i\in\\{1,\dots,k-1\\}}$. This
means that Alice sends identical message sequences on inputs $x_{0}$ and
$x_{i}$ and therefore that Bob is not able to distinguish between these two
cases for the input pair $(x_{0},L)$, contradicting our assumption that we
started with a functional protocol.

We also claim that $\mathcal{F}$ consists of at least $N$ sets. Indeed, for
every pair ${x,y\in[N]}$, there is a list $L\in\binom{[N]}{k}$ containing both
$x$ and $y$. Since we must have $T_{x,L}^{A}\neq T_{y,L}^{A}$ for Bob to be
able to distinguish $x$ and $y$ on input $L$, the inputs $x$ and $y$ induce
distinct transcript sets.

It thus follows from Theorem 4.3 that the total number of distinct transcripts
is at least

$|\mathcal{T}|\geq\frac{c(k-1)^{2}\log N}{\log(k-1)}.$

Hence, since
$\mathcal{T}\subseteq\\{0,1\\}\cup\\{0,1\\}^{2}\cup\cdots\cup\\{0,1\\}^{C}$,
we have

$\frac{2^{C+1}-1}{2-1}=\sum_{l=0}^{C}2^{l}\geq\frac{c(k-1)^{2}\log
N}{\log(k-1)},$

for some absolute constant $c>0$. Taking logarithms now gives the claim. ∎

###  4.2 Quantum communication complexity of the list problem

Analogous to Witsenhausen’s result, the one-round quantum communication
complexity of a list problem is characterized in terms of the orthogonality
dimension of its associated graph.

######  Lemma 4.4.

For every family $\mathcal{L}\subseteq 2^{\mathcal{X}}$, the one-round quantum
communication complexity of $\mathcal{L}$-list equals
$\lceil{\log\xi(G_{\mathcal{L}})}\rceil$.

###### Proof.

Consider an optimal one-round protocol. Without loss of generality, we can
assume that Alice sends to Bob a pure state
$|\phi_{x}\rangle\in\mathbb{C}^{d}$ on input $x\in\mathcal{X}$. Then, given a
list $L\in\mathcal{L}$, Bob has a measurement that allows him to distinguish
the states $\\{|\phi_{x}\rangle:\,x\in L\\}$. It thus follows from Lemma 2.1
that these states must be orthogonal. In particular, since for every list
$L\in\mathcal{L}$, each pair of distinct elements $x,y\in L$ forms an edge in
$G_{\mathcal{L}}$, the vectors $|\phi_{x}\rangle$, $x\in\mathcal{X}$, form a
$d$-dimensional orthogonal representation. Hence, $\xi(G_{\mathcal{L}})\leq
d$.

Conversely, let $f:V(G_{\mathcal{L}})\to\mathbb{C}^{d}$ be an orthogonal
representation of $G_{\mathcal{L}}$. Then, for every list $L\in\mathcal{L}$,
the vectors $\\{f(x):\,x\in L\\}$ are pairwise orthogonal. If Bob gets a list
$L\in\mathcal{L}$ and Alice gets an element $x\in L$, it follows from Lemma
2.1 that there is a quantum measurement allowing Bob to uniquely identify $x$
when Alice sends $f(x)$ using $\log d$-qubits. Hence, the one-round quantum
communication complexity is at most $\lceil{\log\xi(G_{\mathcal{L}})}\rceil$.
∎

For multi-round protocols, a quantum analogue of Theorem 1.3 also holds.

######  Lemma 4.5.

For every family $\mathcal{L}\subseteq 2^{\mathcal{X}}$, the quantum
communication complexity of $\mathcal{L}$-list is at least
$\max\\{\Omega(\log\log\chi(G_{\mathcal{L}})),\log\omega(\mathcal{L})\\}$.

###### Proof.

Kremer’s Theorem (Theorem 1.1) shows that there is at most an exponential
difference between the (multi-round) quantum and one-round classical
communication complexity. Hence, by Witsenhausen’s result, the former is at
least $\Omega(\log\log\chi(G_{\mathcal{L}}))$. Moreover, on the worst input
Bob has to be able to distinguish among $\omega(\mathcal{L})$ different
elements. Hence, $\log\omega(\mathcal{L})$ bits of information must be
communicated and Holevo’s Theorem [Hol73] says that to retrieve
$\log\omega(\mathcal{L})$ bits of information $\log\omega(\mathcal{L})$ qubits
are necessary. ∎

###  4.3 Proof of Theorem 1.7

Recall that we are considering the following family of lists. For an even
positive integer $n$ and $d\in[n]$, let $\mathcal{L}_{d}\subseteq
2^{\\{0,1\\}^{n}}$ be the family of all lists $L\subseteq\\{0,1\\}^{n}$ of
maximal cardinality such that all strings in $L$ have Hamming distance exactly
$d$. We denote by $\mathcal{K}$ the union
$\mathcal{L}_{n/2}\cup\cdots\cup\mathcal{L}_{n}$. In other words, this is the
union of lists for which, individually, there is a one-round $O(\log n)$-qubit
protocol.

###### Proof of Theorem 1.7.

Let $\ell=\lceil{\log n}\rceil$ and $U$ be the $(\ell+1)$-qubit unitary matrix
which satisfies
$U|0\rangle|0\rangle^{\otimes\ell}=|0\rangle|0\rangle^{\otimes\ell}$ and
$U|1\rangle|0\rangle^{\otimes\ell}=\frac{1}{\sqrt{n}}|1\rangle\sum_{i=1}^{n}|i\rangle$.
Moreover, for any $2^{\ell}$-bit string $z$, we define the conditional query
unitary $U_{z}$ which acts on the computational basis states as
$U_{z}|0\rangle|i\rangle=|0\rangle|i\rangle$ and
$U_{z}|1\rangle|i\rangle=(-1)^{z_{i}}|1\rangle|i\rangle$ for any
$i\in[2^{\ell}]$. For a small technicality, if $n$ is not a power of $2$, i.e.
$\ell>\log n$, we will map any $n$-bit string to a $2^{\ell}$-bit string
obtained by padding zeros to the original string. We can now explain the
protocol.

Consider the input pair $(x,L)$ where $L\in\mathcal{L}_{d}$. Bob looking at
the list $L$ learns $d$ and sends to Alice the single qubit
$\gamma|0\rangle+\sqrt{1-\gamma^{2}}|1\rangle$ where
$\gamma^{2}=1-\frac{n}{2d}\geq 0$. Alice pads the state
$|0\rangle^{\otimes\ell}$ to the one she received and then applies in sequence
the unitaries $U$ and $U_{x}$, obtaining the state
$|\phi_{x}\rangle=U_{x}U\left((\gamma|0\rangle+\sqrt{1-\gamma^{2}}|1\rangle)|0\rangle^{\otimes\ell}\right)=\gamma|0\rangle|0\rangle^{\otimes\ell}+\sqrt{\frac{{1-\gamma^{2}}}{{n}}}\sum_{i=1}^{n}(-1)^{x_{i}}|1\rangle|i\rangle$.
She sends this to Bob using $\lceil{\log n}\rceil+1$ qubits. Notice that if
$x,y\in\\{0,1\\}^{n}$ differ in exactly $d$ positions, then the states
$|\phi_{x}\rangle$ and $|\phi_{y}\rangle$ are orthogonal to each other. Hence,
by Lemma 2.1, using the list $L$ Bob can perform a measurement that allows him
to learn Alice’s input $x$. ∎

###  4.4 Entanglement-assisted and non-signaling communication complexity of
the list problem

In this last section, we present two results regarding the list problem when
the players can only exchange classical bits but they are allow to share non-
classical correlations.

##### Quantum correlations.

If Alice and Bob can share an entangled state and communicate classical bits,
then they can use the teleportation protocol of Bennett et al. [BBC+93] to
simulate the quantum communication with a factor of 2 overhead. However, there
may be more efficient protocols. In particular, we show for the
$\mathcal{K}$-list problem, where $\mathcal{K}$ is the union
$\mathcal{L}_{n/2}\cup\cdots\cup\mathcal{L}_{n}$, a two-round entanglement-
assisted protocol that uses only $\lceil{\log n}\rceil+3$ classical bits.

######  Lemma 4.6.

For $\mathcal{K}=\mathcal{L}_{n/2}\cup\cdots\cup\mathcal{L}_{n}$, there exists
a two-round entanglement-assisted protocol for $\mathcal{K}$-list where Bob
sends Alice a single bit and Alice replies with $\lceil{\log n}\rceil+2$ bits
of communication.

###### Proof.

Let $(x,L)$ be Alice and Bob’s input pair where $L\in\mathcal{L}_{d}$.
Consider the conditional query unitary $U_{z}$, where $z$ is a $n$-bit string,
which acts on the computational basis states as
$U_{z}|0\rangle|i\rangle=|0\rangle|i\rangle$ and
$U_{z}|1\rangle|i\rangle=(-1)^{z_{i}}|1\rangle|i\rangle$ for any
$i\in\\{0,1\\}^{n}$. We show a two-round communication protocol that uses as
shared entanglement the state
$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}|i\rangle_{A}|i\rangle_{B}$ together with two
EPR pairs. We use the subscript $A$ (resp. $B$) to specify Alice’s part of the
state (resp. Bob’s).

From the list $L$, Bob learns the distance $d$ and uses one EPR pair and one
bit of communication to remote state prepare the qubit
$\gamma|0\rangle+\sqrt{1-\gamma^{2}}|1\rangle$, where
$\gamma^{2}=1-\frac{n}{2d}\geq 0$ [Pat00, Lo00]. Now Alice and Bob are sharing
the entangled state:
$\left(\gamma|0\rangle_{A}+\sqrt{1-\gamma^{2}}|1\rangle_{A}\right)\frac{1}{\sqrt{n}}\sum_{i=1}^{n}|i\rangle_{A}|i\rangle_{B}$.
Using her input $x$, Alice performs the unitary $U_{x}$ followed by the
unitary $U=|0\rangle\\!\langle 0|\otimes F_{n}+|1\rangle\\!\langle 1|\otimes
F_{n}$ where $F_{n}$ is the $n\times n$ discrete quantum Fourier transform.
The entangled state is now:

$\gamma|0\rangle_{A}\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}\omega^{ij}_{n}|j\rangle_{A}|i\rangle_{B}+(\sqrt{1-\gamma^{2}})|1\rangle_{A}\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}(-1)^{x_{i}}\omega^{ij}_{n}|j\rangle_{A}|i\rangle_{B},$

where $\omega_{n}$ is the $n$-th root of unity. Alice measures in the
computational basis her second $n$ qubits register and gets an outcome
$\hat{j}$. She sends $\hat{j}$ to Bob using $\lceil{\log n}\rceil$ classical
bits. Moreover, Alice teleports the qubit
$\gamma|0\rangle+\sqrt{1-\gamma^{2}}|1\rangle$ to Bob using the protocol of
Bennett et al. [BBC+93]. This requires two classical bits and an EPR pair.

He can then use $\hat{j}$ to perform a unitary
$(\sum_{i}\omega_{n}^{i*}|i\rangle\\!\langle i|)^{\hat{j}}$ that will put his
register in the state

$|\psi_{x}\rangle=\gamma|0\rangle\frac{1}{\sqrt{n}}\sum_{i=1}^{n}|i\rangle+(\sqrt{1-\gamma^{2}})|1\rangle\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(-1)^{x_{i}}|i\rangle.$

At last, we notice that if $x,y\in\\{0,1\\}^{n}$ differ in exactly $d$ bits
then $|\psi_{x}\rangle$ is orthogonal to $|\psi_{y}\rangle$. Using the
elements of the list $L$, by Lemma 2.1, Bob can construct a measurement that
allows his to learn Alice’s input. In total the protocol required $\lceil{\log
n}\rceil+2$ EPR pairs and $\lceil{\log n}\rceil+3$ bits of classical
communication. ∎

##### Non-signaling correlations.

If the two parties can share non-signaling correlations, every list problem
becomes trivial. Let $\mathcal{A,B,S}$, and $\mathcal{T}$ be some sets. Alice
and Bob are said to _share non-signalling correlations_ if there is a
(magically correlated) pair of devices taking inputs from $\mathcal{S}$ and
$\mathcal{T}$, respectively, such that if Alice gives $s\in\mathcal{S}$ to her
device and Bob gives $t\in\mathcal{T}$ to his, the devices return elements
$a\in\mathcal{A}$ and $b\in\mathcal{B}$ with probability $P(a,b|s,t)$, where
the joint distributions $P(\cdot,\cdot|s,t)$ on $\mathcal{A}\times\mathcal{B}$
have marginals satisfying

$\displaystyle\sum_{b\in\mathcal{B}}P(a,b|s,t)$
$\displaystyle=\sum_{b\in\mathcal{B}}P(a,b|s,t^{\prime}),\quad\forall
t,t^{\prime}\in\mathcal{T}$ $\displaystyle\sum_{a\in\mathcal{A}}P(a,b|s,t)$
$\displaystyle=\sum_{a\in\mathcal{A}}P(a,b|s^{\prime},t),\quad\forall
s,s^{\prime}\in\mathcal{S}.$

In words, the parties’ marginal distributions depend only on their own inputs
and not on the other’s.

######  Lemma 4.7.

For every family $\mathcal{L}\subseteq 2^{\mathcal{X}}$, there is a one-round
non-signaling protocol that uses only $\lceil{\log\omega(\mathcal{L})}\rceil$
bits of communication and this is optimal.

###### Proof.

Fix a list $L\in\mathcal{L}$ and an element $x\in L$. Uniquely label the
elements of $L$ with numbers in $\mathbb{Z}_{\omega(\mathcal{L})}$ and let $i$
be the label assigned to $x$. Let $P(\cdot,\cdot|x,L)$ be the probability
distribution over
$\mathbb{Z}_{\omega(\mathcal{L})}\times\mathbb{Z}_{\omega(\mathcal{L})}$ that
assigns probability $1/\omega(\mathcal{L})$ to each pair in
$\\{(a,a+i):\,a\in\mathbb{Z}_{\omega(\mathcal{L})}\\}$ and vanishes on all
other pairs. Clearly this distribution is non-signaling. Similarly define non-
signalling distributions for every other pairs $(x^{\prime},L^{\prime})$ in
the list problem.

Now consider the following protocol. Upon receiving $x\in\mathcal{X}$ and
$L\in\mathcal{L}$ such that $x\in L$, respectively, Alice and Bob sample from
the distribution $P(\cdot,\cdot|x,L)$ as explained above and get $a$ and
$a+i\in\mathbb{Z}_{\omega(\mathcal{L})}$, respectively. Next, Alice sends $a$
to Bob, using at most $\lceil{\log\omega(\mathcal{L})}\rceil$ bits of
communication. Finally, Bob subtracts Alice’s message from his input, getting
${(a+i)-a=i}$, which tells him Alice’s input.

At last, we notice that any functional protocol has to communicate at least
$\lceil{\log\omega(\mathcal{L})}\rceil$ bits and hence the above protocol is
an optimal one. Indeed, there is an instance of the problem where Bob has to
distinguish Alice’s input from a list of $\omega(\mathcal{L})$ different
elements. ∎

## Acknowledgements

Part of this work was conducted while H. B., D. L., T. P. and F. S. were at
the Newton Institute of Mathematical Sciences in Cambridge, UK. J. B. was
supported by a Rubicon grant from the Netherlands Organization for Scientific
Research (NWO). H. B., T. P. and F. S. were funded in part by the EU project
SIQS. D. L. is supported by NSERC, CRC, and CIFAR.

The authors thank Jeroen Zuiddam for useful discussions regarding Section 3.
T.P. thanks Monique Laurent for providing the proof of Lemma 3.4.

## References

  * [Alo14] Noga Alon, 2014.  Personal communication.
  * [Amb04] Andris Ambainis.  Quantum search algorithms.  SIGACT News, 35(2):22–35, June 2004.
  * [BBC+93] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters.  Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels.  Phys. Rev. Lett., 70:1895–1899, 1993.
  * [BBG12] J. Briët, H. Buhrman, and D. Gijswijt.  Violating the Shannon capacity of metric graphs with entanglement.  Proceedings of the National Academy of Sciences, 2012.
  * [BBHT98] M. Boyer, G. Brassard, P. Høyer, and A. Tapp.  Tight bounds on quantum searching.  Fortschritte der Physik, 46(4-5):493–505, 1998.
  * [BBL+15] J. Briët, H. Buhrman, M. Laurent, T. Piovesan, and G. Scarpa.  Entanglement-assisted zero-error source-channel coding.  Information Theory, IEEE Transactions on, 61(2):1124–1138, 2015\.  A previous version appeared in EuroComb 2014.
  * [BCW98] H. Buhrman, R. Cleve, and A. Wigderson.  Quantum vs. classical communication and computation.  In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pages 63–68, 1998.
  * [BHMT02] G. Brassard, P. Høyer, M. Mosca, and A. Tapp.  Quantum amplitude amplification and estimation.  In Quantum computation and information (Washington, DC, 2000), volume 305 of Contemp. Math., pages 53–74. Amer. Math. Soc., Providence, RI, 2002.
  * [BHT98] G. Brassard, P. Høyer, and A. Tapp.  Quantum counting.  In Proceedings of the 25th International Colloquium on Automata, Languages and Programming, ICALP ’98, pages 820–831, London, UK, 1998. Springer-Verlag.
  * [BZ17] Jop Briët and Jeroen Zuiddam.  On the orthogonal rank of cayley graphs and impossibility of quantum round elimination.  Quantum Info. Comput., 17(1-2):106–116, February 2017.
  * [CLMW10] T. S. Cubitt, D. Leung, W. Matthews, and A. Winter.  Improving zero-error classical communication with entanglement.  Physical Review Letters, 104(23):230503, 2010.
  * [CMN+07] P. J. Cameron, A. Montanaro, M. W. Newman, S. Severini, and A. Winter.  On the quantum chromatic number of a graph.  The electronic journal of combinatorics, 14(R81):1, 2007.
  * [CMR+14] T. S. Cubitt, L. Manc̆inska, D. E. Roberson, S. Severini, D. Stahlke, and A. Winter.  Bounds on entanglement assisted source-channel coding via the lovasz theta number and its variants.  IEEE Transactions of Information Theory, 60(11):7330–7344, 2014\.
  * [Del73] P. Delsarte.  An algebraic approach to the association schemes of coding theory.  PhD thesis, Université Catholique de Louvain, 1973.
  * [DL98] P. Delsarte and V. I. Levenshtein.  Association schemes and coding theory.  IEEE Transactions on Information Theory, 44(6):2477–2504, 1998\.
  * [DR82] A. G. Dýachkov and V. V. Rykov.  Bounds on the length of disjunctive codes.  Problemy Peredachi Informatsii, 18(3):7–13, 1982.  In Russian.
  * [DR08] I. Dukanovic and F. Rendl.  A semidefinite programming-based heuristic for graph coloring.  Discrete Applied Mathematics, 156(2):180–189, 2008.
  * [dW01] R. de Wolf.  Quantum Computing and Communication Complexity.  PhD thesis, Universiteit van Amsterdam, 2001.
  * [FR87] P. Frankl and V. Rödl.  Forbidden intersections.  Transactions of the American Mathematical Society, 300(1):259–286, 1987.
  * [Für96] Z. Füredi.  On r-cover-free families.  Journal of Combinatorial Theory, Series A, 73(1):172–173, 1996\.
  * [GN08] C. D. Godsil and M. W. Newman.  Coloring an orthogonality graph.  SIAM Journal on Discrete Mathematics, 22(2):683–692, March 2008\.
  * [GQZ14] J. Gruska, D. Qiu, and S. Zheng.  Generalizations of the distributed deutsch-jozsa promise problem.  Preprint available at arXiv:1402.7254, 2014.
  * [Gro96] L. Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of STOC’96, pages 212–219, 1996.
  * [Hol73] A. S. Holevo.  Bounds for the quantity of information transmitted by a quantum communication channel.  Problems of Information Transmission, 9:177–183, 1973.
  * [KL01] I. Krasikov and S. Litsyn.  Survey of binary Krawtchouk polynomials., pages 199–211.  Providence, RI: AMS, American Mathematical Society, 2001.
  * [Kle66] D. Kleitman.  On a combinatorial conjecture of Erdős.  Journal of Combinatorial Theory, 1(2):209–214, 1966.
  * [KN97] E. Kushilevitz and N. Nisan.  Communication Complexity.  Cambridge University Press, 1997.
  * [Kre95] I. Kremer.  Quantum communication.  Master’s thesis, Hebrew University, Computer Science Department, 1995\.
  * [Lau14] M. Laurent.  Private communications, 2014.
  * [Lev95] V. I. Levenshtein.  Krawtchouk polynomials and universal bounds for codes and designs in hamming spaces.  IEEE Trans. Inf. Theor., 41(5):1303–1321, 1995.
  * [LMM+12] D. Leung, L. Manc̆inska, W. Matthews, M. Ozols, and A. Roy.  Entanglement can increase asymptotic rates of zero-error classical communication over classical channels.  Communications in Mathematical Physics, 311:97–111, 2012.
  * [LNV13] M. Laurent, M. E. Nagy, and A. Varvitsiotis.  Complexity of the positive semidefinite matrix completion problem with a rank constraint.  Discrete Geomety and Optimization, 69:105–120, 2013.
  * [Lo00] Hoi-Kwong Lo.  Classical-communication cost in distributed quantum-information processing: A generalization of quantum-communication complexity.  Phys. Rev. A, 62:012313, Jun 2000.
  * [Lov79] L. Lovász.  On the Shannon capacity of a graph.  IEEE Transactions on Information Theory, 25(1):1–7, 1979.
  * [Meu05] P. Meurdesoif.  Strengthening of the lovász theta(g) for graph coloring.  Mathematical Programming, 102(3):577–588, 2005.
  * [MRR78] R.J. McEliece, E.R. Rodemich, and H.C. Rumsey.  The Lovász bound and some generalizations.  J. Combin. Inform. System Sci., 3:134–152, 1978.
  * [NOS93] M. Naor, A. Orlitsky, and P. Shor.  Three results on interactive communication.  IEEE Transactions on Information Theory, 39:1608–1615, 1993.
  * [Orl90] A. Orlitsky.  Worst-case interactive communication i: Two messages are almost optimal.  IEEE Transactions on Information Theory, 36:1111–1126, 1990.
  * [Orl91] A. Orlitsky.  Worst-case interactive communication - ii: Two messages are not optimal.  IEEE Transactions on Information Theory, 37(4):995–1005, 1991.
  * [Pat00] Arun K. Pati.  Minimum classical bit for remote preparation and measurement of a qubit.  Phys. Rev. A, 63:014302, Dec 2000.
  * [Pee96] M. J. P. Peeters.  Orthogonal representations over finite fields and the chromatic number of graphs.  Combinatorica, 16(3):417–431, 1996.
  * [Rus94] M. Ruszinkó.  On the upper bound of the size of the r-cover-free families.  Journal of Combinatorial Theory, Series A, 66(2):302–310, 1994\.
  * [Sch79] A. Schrijver.  A comparison of the Delsarte and Lovász bounds.  IEEE Transactions on Information Theory, 25(4):425–429, 1979.
  * [SF14] J. Spencer and L. Florescu.  Asymptopia.  Student Mathematical Library. American Mathematical Society, 2014.
  * [SS12] G. Scarpa and S. Severini.  Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number.  IEEE Transactions on Information Theory, 58(4):2524–2529, 2012\.
  * [Wit76] H. S. Witsenhausen.  The zero-error side information problem and chromatic numbers.  IEEE Transactions on Information Theory, 22(5):592–593, 1976\.
  * [Yao79] A. C.-C. Yao.  Some complexity questions related to distributive computing (preliminary report).  In Proceedings of the 11th annual ACM symposium on Theory of computing (STOC 1979), pages 209–213, 1979.
  * [Yao93] A. C.-C. Yao.  Quantum circuit complexity.  In Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS 1993), pages 352–361, 1993.

##  Appendix A Orthogonal rank is NP-hard

######  Theorem Athmcountersep1.

For any $k\geq 3$, it is NP-hard to decide whether or not $\xi(G)\leq k$.

Peeters [Pee96] proved this result in a more general context for the case of
$k=3$. We use the same ideas, sometimes simplifying them for our specific
case, and then use a trick from [LNV13] to extend the result to any $k\geq 3$.

######  Lemma Athmcountersep2.

[Pee96] It is NP-hard to decide whether or not $\xi(G)\leq 3$.

###### Proof.

The key idea is, given a graph $G$, to construct in polynomial time a new
graph $G^{\prime}$ with the property that $\chi(G)\leq 3$ if and only if
$\chi(G^{\prime})\leq 3$, and furthermore $\chi(G^{\prime})\leq 3$ if and only
if $\xi(G^{\prime})\leq 3$. Since deciding whether a graph is three colorable
is NP-complete, this implies that determining if $\xi(G)\leq 3$ is NP-hard.

Let $G$ be a graph with vertex set $V(G)=[n]$. The new graph $G^{\prime}$ is
obtained from $G$ by adding for each pair of distinct vertices $i,j\in[n]$ the
gadget graph $H_{ij}$, see Figure 1. Hence, $G^{\prime}$ has $|V(G)|+2n(n-1)$
vertices and $|E(G)|+\frac{9}{2}n(n-1)$ edges.

$i$$a_{ij}$$b_{ij}$$d_{ij}$$j$$c_{ij}$ Figure 1: The gadget graph $H_{ij}$.

Clearly, if $\chi(G^{\prime})=3$ then $\chi(G)\leq 3$. Moreover, if
$\chi(G)\leq 3$ we can three color the graph $G^{\prime}$ as following: if $i$
and $j$ have the same color then use the color classes
$\\{\\{i,j\\},\\{a_{ij},c_{ij}\\},\\{b_{ij},d_{ij}\\}\\}$, otherwise use
$\\{\\{i,c_{ij}\\},\\{a_{ij},d_{ij}\\},\\{b_{ij},j\\}\\}$. Thus $\chi(G)\leq
3$ if and only if $\chi(G^{\prime})=3$.

Now, since $3\leq\omega(G^{\prime})\leq\xi(G^{\prime})\leq\chi(G^{\prime})$ we
have that $\chi(G^{\prime})=3$ implies $\xi(G^{\prime})=3$. The only thing we
have to prove is that if $\xi(G^{\prime})=3$ then $\chi(G^{\prime})=3$. Let
$\phi:V(G^{\prime})\to\mathbb{C}^{3}$ be an orthonormal representation of
$G^{\prime}$. For every vertex $i$ in the subgraph $G$ of $G^{\prime}$, let
$V_{i}$ be the 1-dimensional subspace spanned by $\phi(i)$. We claim that for
every $i,j\in[n]$ either $V_{i}=V_{j}$ or $V_{i}$ is orthogonal to $V_{j}$.
Before proving this simple statement, we mention how we can use it to conclude
the proof. Every $V_{i}$ is a 1-dimensional subspace of $\mathbb{C}^{3}$ and
therefore there are only three different types of subspaces. We can now color
the nodes in $V(G)$ with three colors, associating each color class to a
different subspace.

Let’s now prove that either $V_{i}=V_{j}$ or $V_{i}\perp V_{j}$. Looking at
the adjacency relation between the vertices in the gadget graph $H_{ij}$, we
can see that the set $\\{\phi(i),\phi(a_{ij}),\phi(b_{ij})\\}$ and the set
$\\{\phi(j),\phi(c_{ij}),\phi(d_{ij})\\}$ form a basis for $\mathbb{C}^{3}$.
Moreover, we have $\phi(j)=\alpha\phi(i)+\beta\phi(b_{ij})$,
$\phi(c_{ij})=\hat{\alpha}\phi(i)+\hat{\gamma}\phi(a_{ij})$ and
$\phi(d_{ij})=\tilde{\gamma}\phi(a_{ij})+\tilde{\beta}\phi(b_{ij})$ where all
the constants are complex numbers. By contradiction, suppose that $V_{i}\neq
V_{j}$ but $V_{i}$ is not perpendicular to $V_{j}$. This means that both
$\alpha$ and $\beta$ are different from zero. Since $\phi(j)$ is orthogonal to
$\phi(c_{ij})$, then $\hat{\alpha}$ must be equal to zero and similarly, since
$\phi(j)$ is orthogonal to $\phi(d_{ij})$, also $\tilde{\beta}$ must be equal
to zero. But now the vector $\phi(c_{ij})=\hat{\gamma}\phi(a_{ij})$ is
orthogonal to $\phi(d_{ij})=\tilde{\gamma}\phi(a_{ij})$, which implies that
one of the two vectors is the zero one. This brings a contradiction as $\phi$
is an orthonormal representation of $G^{\prime}$. ∎

###### Proof of Theorem Athmcountersep1.

The hardness result of Lemma Athmcountersep2 can be extended to any $k$
greater than $3$ using the suspension operation on graphs as done in [LNV13].
Given a graph $G$, the suspension graph $\nabla^{t}G$ is obtained by adding
$t$ new vertices which are pairwise adjacent and are also adjacent to all the
vertices in $G$. Clearly $\xi(\nabla^{t}G)=\xi(G)+t$ holds. Hence, for any
fixed $k\geq 3$, it is NP-hard to decide whether $\xi(G)\leq k$. ∎

##  Appendix B Kremer’s Theorem

Here we prove Kremer’s Theorem (Theorem 1.1), which we restate for
convenience. The original proof by Kremer [Kre95] applied to boolean
functions; we give a slight generalization of the statement so that it applies
to functions with arbitrary range. It is important to notice that the
statements in this section hold for general communication protocols, not only
exact ones.

######  Theorem Bthmcountersep1.

Let $\ell$ be a positive integer, $X,Y,\mathcal{R}$ be finite sets and
$\mathcal{D}\subseteq X\times Y$. Let $f:\mathcal{D}\to\mathcal{R}$ be a
function and suppose that $f$ admits an $\ell$-qubit quantum protocol. Then,
there exists a one-round $2^{O(\ell)}$-bit classical protocol for $f$.

The proof uses the following lemma of Yao [Yao93] and Kremer [Kre95]. To
reduce the amount of notation needed in the proof we assume that the parties
use the following general protocol. At any point during the protocol, both
Alice and Bob have a private quantum register. If it is Alice’s turn to
communicate, say $\ell$ qubits, she appends a fresh $\ell$-qubit register to
her existing register, applies a unitary to both registers and sends the
$\ell$-qubit register over to Bob, who then absorbs the $\ell$-qubit register
into his private register. If it’s his turn to communicate, Bob operates
similarly. This assumption will allow us to deal more easily with protocols in
which different numbers of qubits are sent in each round.

######  Lemma Bthmcountersep2 (Yao–Kremer).

Let $\ell$ be a positive integer, $X,Y,\mathcal{R}$ be finite sets and
$\mathcal{D}\subseteq X\times Y$. Suppose that there exists an $r$-round
quantum protocol for a function $f:\mathcal{D}\to\mathcal{R}$, where
$\ell_{i}$ qubits are communicated in round $i\in[r]$. Then, the final state
of the protocol on input $(x,y)\in\mathcal{D}$ can be written as

$\sum\alpha_{\bf u}(x)\beta_{\bf u}(y)|A_{\bf u}(x)\rangle|B_{\bf
u}(y)\rangle,$

where the sum is over all ${\bf
u}\in\\{0,1\\}^{\ell_{1}}\times\cdots\times\\{0,1\\}^{\ell_{r}}$, the
$\alpha_{\bf u}(x),\beta_{\bf u}(y)$ are complex numbers and the $|A_{\bf
u}(x)\rangle,|B_{\bf u}(y)\rangle$ are complex unit vectors.

###### Proof.

By induction on $r$. The base case $r=1$ is trivial, since then Alice sends
Bob an $\ell$-qubit state. For some $i\in\\{2,3,\dots,r\\}$, suppose that
after $i-1$ rounds the state is given by

$\sum\alpha_{\bf v}(x)\beta_{\bf v}(y)|A_{\bf v}(x)\rangle|B_{\bf
v}(y)\rangle,$

where the sum is over all ${\bf
v}\in\\{0,1\\}^{\ell_{1}}\times\cdots\times\\{0,1\\}^{\ell_{i-1}}$. Assume
that the $i$-th round is Alice’s turn (the case of Bob’s turn is handled
similarly). She appends a fresh $\ell_{i}$-qubit register to her current
register, causing the state to become

$\sum\alpha_{\bf v}(x)\beta_{\bf v}(y)|A_{\bf v}(x)\rangle|0_{1}\cdots
0_{\ell_{i}}\rangle|B_{\bf v}(y)\rangle.$

Next, she applies a unitary over both of her registers, turning the state into

$\sum\alpha_{\bf v}(x)\beta_{\bf v}(y)\left(\sum_{{\bf
w}\in\\{0,1\\}^{\ell_{i}}}\gamma_{{\bf w}}|A_{\bf v,w}(x)\rangle|{\bf
w}\rangle\right)|B_{\bf v}(y)\rangle,$

where $\gamma_{{\bf w}}$ is a complex number (which might depend on $x$) and
for some unit vectors $|A_{\bf v,w}(x)\rangle$. Now define

$\alpha_{\bf v,w}(x)=\alpha_{\bf v}(x)\gamma_{\bf w},\quad\quad\beta_{\bf
v,w}(y)=\beta_{\bf v}(y)\quad\quad\text{and}\quad\quad|B_{\bf
v,w}(y)\rangle=|{\bf w}\rangle|B_{\bf v}(y)\rangle,$

so that after the $i$-th round, after Alice has sent the $\ell_{i}$-qubit
register to Bob, the state equals

$\sum_{\bf v,w}\alpha_{\bf v,w}(x)\beta_{\bf v,w}(y)|A_{\bf
v,w}(x)\rangle|B_{\bf v,w}(y)\rangle.$

After $r$ rounds the state thus looks like as claimed in the lemma. ∎

###### Proof of Theorem 1.1.

Assume that the protocol proceeds in $r$ rounds and that $\ell_{i}$ qubits are
communicated during round $i\in[r]$. By Lemma Bthmcountersep2 the final state
of the protocol can be written as

$\sum\alpha_{\bf u}(x)\beta_{\bf u}(y)|A_{\bf u}(x)\rangle|B_{\bf
u}(y)\rangle,$

To produce his output, Bob performs a measurement $\\{M_{1},\dots,M_{k}\\}$ on
his register. For each pair ${\bf
u,v}\in\\{0,1\\}^{\ell_{1}}\times\cdots\times\\{0,1\\}^{\ell_{r}}$ and
$j\in[k]$ we define the complex numbers

$\displaystyle a_{\bf u,v}(x)$ $\displaystyle=$
$\displaystyle\overline{\alpha_{\bf u}(x)}\alpha_{\bf v}(x)\langle A_{\bf
u}(x)|A_{\bf v}(x)\rangle$ $\displaystyle b_{\bf u,v}^{j}(x)$ $\displaystyle=$
$\displaystyle\overline{\beta_{\bf u}(y)}\beta_{\bf v}(y)\langle B_{\bf
u}(y)|M_{j}|B_{\bf v}(y)\rangle.$

Then, the probability that Bob gets measurement outcome $j$ equals

$p_{j}(x,y)=\sum_{\bf u,v}a_{\bf u,v}(x)b_{\bf u,v}^{j}(y).$

The classical one-round protocol works in the following way. Let $\ell$ be the
total communication of the protocol and define $\tilde{a}_{\bf u,v}(x)$ as an
approximation of $a_{\bf u,v}(x)$ using $2\ell+4$ bits for the real part and
$2\ell+4$ bits for the imaginary part, so that $|\tilde{a}_{\bf u,v}(x)-a_{\bf
u,v}(x)|\leq 2^{-2\ell-3}$. Alice’s message consists of all $2^{2\ell}$
numbers $\tilde{a}_{\bf u,v}(x)$, making the total communication cost $O(\ell
2^{2\ell})$ bits. Bob calculates his approximation of the probability of
getting outcome $j$ as

$\tilde{p}_{j}(x,y)=\sum_{\bf u,v}\tilde{a}_{\bf u,v}(x)b_{\bf u,v}^{j}(y).$

We can bound the difference between this approximation and the acceptance
probability of the original quantum protocol by

$\displaystyle|\tilde{p}_{j}(x,y)-p_{j}(x,y)|$
$\displaystyle=\Bigl{|}\sum_{\bf u,v}\bigl{(}\tilde{a}_{\bf u,v}(x)-a_{\bf
u,v}(x)\bigr{)}b_{\bf u,v}^{j}(y)\Bigr{|}$ $\displaystyle\leq\sum_{\bf
u,v}\bigl{|}\tilde{a}_{\bf u,v}(x)-a_{\bf u,v}(x)\bigr{|}\,\bigl{|}b_{\bf
u,v}^{j}(y)\bigr{|}$ $\displaystyle\leq
2^{-2\ell-3}2^{2\ell}\leq\frac{1}{8}\,.$

Therefore, given a quantum protocol with sufficiently high success
probability, in this paper in particular probability 1, Bob can
(deterministically) choose the unique outcome $j$ for which
$\tilde{p}_{j}(x,y)$ is strictly greater than $\frac{1}{2}$, and this outcome
$j$ is equal to the function value $f(x,y)$, by correctness of the original
quantum protocol. ∎

##  Appendix C Multi-round quantum protocols for EQ-$\binom{n}{\alpha n}$ with
$\alpha<1/2$

Using distributed versions of Grover’s search algorithm, we find multi-round
quantum communication protocols that solve the EQ-$\binom{n}{\alpha n}$
problem for $\alpha<1/2$ with a logarithmic number of qubits. For
$\alpha=1/4$, this statement is proven in Theorem 3.10.

When $d=\alpha n$ where $\alpha\in(1/4,1/2)$, we can pad zeros to the inputs
such that the new strings are either equal or differ in exactly $1/4$-th of
the positions and run the above two-rounds protocol on the new strings. This
is the simple idea behind the following theorem.

######  Theorem Cthmcountersep1.

For $d=\alpha n$ with $\alpha\in(1/4,1/2)$, the two-round quantum
communication complexity of EQ-$\binom{n}{\alpha n}$ is at most $2\lceil{\log
n}\rceil+2\lceil{\log(4\alpha)}\rceil+1$ qubits.

###### Proof.

Let $x$ and $y$ be Alice’s and Bob’s inputs. Both of the players pad the input
received with $k=4d-n$ zeros. Hence, the new bit strings $\hat{x}$ and
$\hat{y}$ have length $n^{\prime}=n+k=4d$ and they are either equal or differ
in $n^{\prime}/4$ positions. Alice and Bob can now run communication protocol
described in the proof of Theorem 3.10 on the new inputs
$\hat{x},\hat{y}\in\\{0,1\\}^{n^{\prime}}$. The total communication cost is
$2\lceil{\log n^{\prime}}\rceil+1=2\lceil{\log(4\alpha n)}\rceil+1\leq
2\lceil{\log n}\rceil+2\lceil{\log(4\alpha)}\rceil+1$ qubits. ∎

For $d=\alpha n$ where $\alpha\in(0,1/4)$, we need to introduce some
technicalities to ensure an exact version of Grover’s search algorithm.

######  Theorem Cthmcountersep2.

For $d=\alpha n$ with $\alpha\in(0,1/4)$, the quantum communication complexity
of EQ-$\binom{n}{\alpha n}$ is at most $O(\log n)$ qubits. The quantum
communication protocol uses $O(\frac{1}{\sqrt{\alpha}})$ rounds.

###### Proof.

If a $n$-bit string $z$ is known to contain exactly $d$ entries that are 1,
Grover’s algorithm can be modified such that it finds an index for one of them
with certainty [BHMT02, Theorem 16] [BHT98, Amb04]. The number of queries
$\ell$ that the exact version of Grover’s algorithm needs in this case is
given by

$\ell=\left\lceil{\frac{\pi}{4\arcsin{\sqrt{\frac{d}{{n}}}}}-\frac{1}{2}}\right\rceil<\frac{\pi}{4}\sqrt{\frac{n}{d}}+1\,.$

The exact version of Grover’s algorithm is the same as the original algorithm,
except for an adapted final step, which uses a parametrized diffusion operator
$G(\phi)$ and partial query $V_{z}(\varphi)$, where $\phi$ and $\varphi$ are
angles that depend on the Hamming distance $d$. As these angles do not have a
nice closed formula, we refer the reader to [BHMT02, Equation (12)] for the
relation that $\phi$ and $\varphi$ must satisfy. Here

$V_{z}(\varphi)|j\rangle=\begin{cases}|j\rangle&\text{if }z_{j}=0\\\
e^{i\varphi}|j\rangle&\text{if }z_{j}=1\end{cases}$

and

$G(\phi)=F_{n}V_{0}(\phi)F_{n}^{\dagger}\,,$

where $F_{n}$ is the $n\times n$ discrete quantum Fourier transform.444Note
that if $n$ is a power of 2, it is also possible to use the $n\times n$
Hadamard transform.

Take $x,y\in\\{0,1\\}^{n}$ to be the input strings of Alice and Bob and let
$z=x\oplus y$. As in the proof of the $n/4$ case of Theorem 3.10, we turn this
search algorithm into a quantum communication protocol by writing a single
query $U_{z}=U_{x}U_{y}=U_{y}U_{x}$. We can use the commutativity of $U_{x}$
and $U_{y}$ to save rounds: The exact Grover’s algorithm is performed by
executing the operations

$G(\phi)V_{z}(\varphi)\underbrace{GU_{z}\ldots GU_{z}}_{\ell-1\text{ times}}$

on starting state $|s\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}|i\rangle$. Since
we can write two alternations as $GU_{z}GU_{z}=GU_{x}U_{y}GU_{y}U_{x}$,
alternating whether Alice or Bob executes the query first that round, only
$\ell-1$ rounds are needed for the $\ell-1$ ordinary Grover iterations. Alice
starts the protocol if $\ell$ is even, and Bob sends the first message if
$\ell$ is odd.

For the final step, the players need to simulate a query $V_{z}(\varphi)$ by
local operations that depend only on $x$ or $y$. At this point in the protocol
it is Alice’s turn to communicate. She currently holds the state

$|\psi\rangle=\underbrace{GU_{z}\ldots GU_{z}}_{\ell-1\text{
times}}|s\rangle\,.$

Now Alice adds an auxiliary qubit that starts in state $|0\rangle$. Define the
unitary operation $Q_{x}$ by its action on the computational basis states as

$Q_{x}|j\rangle|b\rangle=|j\rangle|b\oplus x_{j}\rangle$

and the (diagonal) unitary matrix $R_{y}(\varphi)$ as

$R_{y}(\varphi)|j\rangle|b\rangle=e^{i\varphi(b\oplus
y_{j})}|j\rangle|b\rangle\,.$

Now Alice first applies $Q_{x}$ on the state $|\psi\rangle|0\rangle$, sends
this state to Bob who performs $R_{y}(\varphi)$, sending the state back to
Alice who again performs $Q_{x}$. It is easy to check that
$Q_{x}R_{y}(\varphi)Q_{x}|\psi\rangle|0\rangle=(V_{z}(\varphi)\otimes
I)|\psi\rangle|0\rangle$, therefore Alice now discards the auxiliary qubit and
applies $G(\phi)$ to finish the simulation of the exact version of Grover’s
algorithm.

The final state of the exact Grover’s algorithm is
$\frac{1}{\sqrt{d}}\sum_{i\text{ s.t.~{}}z_{i}=1}|i\rangle$ if $|z|=d$. If
Alice has this state in her possession, she performs a measurement in the
computational basis, obtaining an index $i^{*}$ such that $x_{i^{*}}\neq
y_{i^{*}}$ if $x\neq y$. Then she sends $i^{*}$ and the value $x_{i^{*}}$ over
to Bob, who outputs ‘equal’ if and only if $x_{i^{*}}=y_{i^{*}}$. This final
message consists of $\lceil{\log{n}}\rceil+1$ qubits. By the correctness of
the exact Grover’s algorithm, this protocol correctly outputs ‘not equal’ if
the Hamming distance between $x$ and $y$ is the fixed value $d$. Therefore we
turned a $\ell$-query execution of the exact version of Grover’s algorithm
into a protocol that uses $(\ell+2)\lceil{\log{n}}\rceil+2$ qubits of
communication in $\ell+2$ rounds. ∎

##  Appendix D Bound on binary entropy function

Here we prove the following simple lemma, whose statement we have used in the
proof of Theorem 3.3. Recall that the binary entropy function $H$ is defined
as $H(p)=-p\log p-(1-p)\log(1-p)$ for $p\in[0,1]$.

######  Lemma Dthmcountersep1.

For any $p\in(0,1/2)$, we have $H(p)+H(1/2-\sqrt{(1-p)p})-1>0$.

The proof of the lemma uses the following lower bound for the binary entropy
function.

######  Lemma Dthmcountersep2.

For any $p\in[0,1]$, $H(p)\geq 1-(1-2p)^{2}$ holds. Moreover, equality holds
if and only if $p\in\\{0,1/2,1\\}$.

###### Proof.

The Taylor series of the binary entropy function around the point $1/2$ gives
that

$1-H(p)=\frac{1}{2\ln
2}\sum_{n=1}^{\infty}\frac{(1-2p)^{2n}}{n(2n-1)}\leq\frac{(1-2p)^{2}}{2\ln
2}\sum_{n=1}^{\infty}\frac{1}{n(2n-1)}=(1-2p)^{2},$

where the first inequality is due to the fact that $|1-2p|\leq 1$ and
therefore $(1-2p)^{2n}\leq(1-2p)^{2}$ and the last equation is due to fact
that $2\ln 2=\sum_{n\geq 1}\frac{1}{n(2n-1)}$. Indeed, the Taylor series for
$\ln 2$ around $0$ (also known as Mercator series) gives that $\ln
2=\sum_{n\geq 1}\frac{(-1)^{n+1}}{n}=\sum_{n\geq 1}\frac{1}{2n(2n-1)}$, and
multiplying both sides by 2 gives the wanted result.

Therefore, we deduce that $H(p)\geq 1-(1-2p)^{2}$. Moreover, equality holds
only at the points where $(1-2p)^{2n}=(1-2p)^{2}$, which are
$p\in\\{0,1/2,1\\}$. ∎

###### Proof of Lemma Dthmcountersep1.

Using Lemma Dthmcountersep2, we have that for any $p\in(0,1/2)$ the following
holds:

$H(p)+H(1/2-\sqrt{(1-p)p})-1>1-(1-2p)^{2}+1-(1-1+2\sqrt{(1-p)p})^{2}-1=0.$

∎

##  Appendix E Partial results on $\xi(G_{\mathcal{K}})$

We collect here some small results about the orthogonal rank of the graph
$G_{\mathcal{K}}$. In particular, we give an upper and lower bound on
$\xi(G_{\mathcal{K}})$ (Proposition Ethmcountersep1 and Proposition
Ethmcountersep3, respectively) and show that a variant of the Lovász theta
number does not provide an useful lower bound to $\xi(G_{\mathcal{K}})$
(Proposition Ethmcountersep4).

Recall that for $\mathcal{K}=\mathcal{L}_{n/2}\cup\cdots\cup\mathcal{L}_{n}$,
we defined $G_{\mathcal{K}}=(\\{0,1\\}^{n},E)$ to be the graph whose edge set
$E$ consists of all pairs of strings with Hamming distance
$\\{n/2,\dots,n\\}$. Also recall the definition the binary entropy function,
$H(p)=-p\log p-(1-p)\log(1-p)$.

######  Proposition Ethmcountersep1.

The graph $G_{\mathcal{K}}$ as above satisfies $\xi(G_{\mathcal{K}})\leq
2^{H(1/4)n+1}\approx 2^{0.81n+1}$.

###### Proof.

To start, we show that the existence of a certain polynomial implies the
existence of an orthonormal representation of the graph. Let
$P:\\{-1,1\\}^{n}\to\mathbb{R}$ be a polynomial with non-negative real
coefficients on $n$ variables $z_{1},\ldots,z_{n}$, each in $\\{-1,1\\}$. That
is,

$P(z)=\sum_{S\subseteq[n]}\alpha_{S}\prod_{k\in S}z_{k},\text{ with
}\alpha_{S}\geq 0,$

where for brevity we use $z$ as a shorthand for the vector
$z_{1},z_{2},\ldots,z_{n}$. Let
$\operatorname{\mathbf{mon}}P=\bigl{|}\\{S:\alpha_{S}\neq 0\\}\bigr{|}$ denote
the number of monomials of $P$ with a non-zero coefficient.

Note that if we have a polynomial $P$ such that $P(1,1,\ldots,1)\neq 0$ and
$P(z)=0$ for all $z\in\\{-1,1\\}^{n}$ such that $\sum_{k=1}^{n}z_{k}=2d-n$
then we can turn this into a $\operatorname{\mathbf{mon}}P$-dimensional
orthonormal representation of the graph $H(n,d)$ as following. Label the
canonical basis vectors by the sets $S$ for which $\alpha_{S}\neq 0$, and take
the map $\phi:\\{0,1\\}^{n}\to\mathbb{C}^{\operatorname{\mathbf{mon}}P}$
defined by

$\phi(x)=\sum_{S:\alpha_{S}\neq 0}\sqrt{\alpha_{S}}\prod_{k\in
S}(-1)^{x_{k}}e_{S}\,.$

For two strings $x,y$ the inner product of the associated vector is then given
by $\langle\phi(x),\phi(y)\rangle=\sum_{S:\alpha_{S}\neq
0}\alpha_{S}\prod_{k\in S}(-1)^{x_{k}+y_{k}}=P(z)$ for
$z_{k}=(-1)^{x_{k}+y_{k}}$. The orthogonality then follows by noting that if
$x$ and $y$ differ in $d$ positions, we have
$\sum_{k=1}^{n}z_{k}=\sum_{k=1}^{n}(-1)^{x_{k}+y_{k}}=\bigl{|}\\{k:x_{k}=y_{k}\\}\bigr{|}-\bigl{|}\\{k:x_{k}\neq
y_{k}\\}\bigr{|}=n-2d$.

We will find an orthonormal representation for $G_{\mathcal{K}}$ by
constructing a polynomial $P$ such that $P(z)=0$ for
$-n\leq\sum_{k=1}^{n}z_{k}\leq 0$. Now, for any even $d$ with $n/2\leq d\leq
n$ define the polynomial

$P_{d}(z)=(2d-n)+\sum_{k=1}^{n}z_{k}\,.$

The evaluation of $P_{d}$ is 0 whenever $\sum_{k=1}^{n}z_{k}=n-2d$ for the
given $d$. Also define the polynomial

$P_{odd}(z)=1+\prod_{k=1}^{n}z_{k}\,.$

This polynomial equals $0$ whenever an odd number of $z_{k}$ equal $-1$. To
simplify notation, define $c_{k}=4k$. Multiplying the $P_{d}$ together gives a
polynomial which is 0 on the correct inputs for all even $d\geq n/2$:

$\displaystyle P_{even}(z)$ $\displaystyle=\prod_{\begin{subarray}{c}d=n/2\\\
d\text{ even}\end{subarray}}^{n}P_{d}(z)=\prod_{\begin{subarray}{c}d=n/2\\\
d\text{
even}\end{subarray}}^{n}(2d-n+\sum_{j=1}^{n}z_{j})=\prod_{k=0}^{n/4}(c_{k}+\sum_{j=1}^{n}z_{j})$
$\displaystyle=\sum_{k=0}^{n/4}\biggl{[}\sum_{\begin{subarray}{c}S\subset[n/4]\\\
|S|=k\end{subarray}}\Bigl{(}\prod_{j\in
S}c_{j}\Bigr{)}\Bigl{(}\sum_{j=1}^{n}z_{j}\Bigr{)}^{n/4-k}\biggr{]}\,.$

Since this polynomial has only monomials with degree at most $n/4$, we can
upper bound the number of monomials by
${\operatorname{\mathbf{mon}}P_{even}\leq\sum_{k=0}^{n/4}\binom{n}{k}\leq
2^{H(1/4)n}}$. The product $P(z)=P_{even}(z)P_{odd}(z)$ gives an orthonormal
representation with the desired properties, and since
$\operatorname{\mathbf{mon}}P_{odd}=2$, we have that
$\operatorname{\mathbf{mon}}P\leq 2^{H(1/4)n+1}$. ∎

To the best of our knowledge, the current-best lower bound on
$\xi(G_{\mathcal{K}})$ is linear in $n$. The argument presented here is due to
Alon [Alo14]. We use the following result due to Kleitman [Kle66]. The
_diameter_ of a set $A\subseteq\\{0,1\\}^{n}$ is defined as the maximum
Hamming distance between any two elements in $A$.

######  Theorem Ethmcountersep2 (Kleitman).

Let $r$ and $n$ be positive integers such that $r\leq n/2$. Let
$A\subseteq\\{0,1\\}^{n}$ be a set of diameter $2r$. Then,

$|A|\leq\sum_{k=0}^{r}\binom{n}{k}\leq 2^{nH(r/n)}.$

######  Proposition Ethmcountersep3.

The graph $G_{\mathcal{K}}$ as above satisfies
$\xi(G_{\mathcal{K}})\geq\Omega(n)$.

###### Proof.

Suppose that there exists an orthogonal representation of $G_{\mathcal{K}}$
into $S^{d-1}$. Observe that any spherical cap of $S^{d-1}$ of angle strictly
less than $\pi/2$ contains only points of the representation that correspond
to an independent set in $G_{\mathcal{K}}$. For $\varepsilon>0$, consider a
covering of $S^{d-1}$ by spherical caps of radius $\pi/2-\varepsilon$ using
the minimum number of caps. A simple volume argument shows that for some
absolute constant $\alpha=\alpha(\varepsilon)\in(0,\infty)$, such a covering
uses at most $2^{\alpha d}$ caps. By the Pigeonhole Principle, there exists a
cap in the covering and a set $A\subseteq\\{0,1\\}^{n}$ of cardinality at
least $2^{n-\alpha d}$, such that the representation sends each string in $A$
to the cap. Since $A$ must be an independent set in $G_{\mathcal{K}}$, it has
diameter less than $n/2$. Hence, by Theorem Ethmcountersep2, we have $n-\alpha
d\leq nH(1/4)$, giving the result. ∎

At last, we show that a variant of the Lovász theta number cannot be used to
get at stronger lower bound on $\xi(G_{\mathcal{K}})$ than the one presented
in the above Proposition Ethmcountersep3. The variant we consider, called
$\vartheta^{\prime}(G)$, was introduced in [Sch79, MRR78] by adding
nonnegativity constraints to the maximization program that defined
$\vartheta(G)$ in (1):

$\vartheta^{\prime}(G)=\max\\{\sum_{i,j\in[n]}X_{ij}:\,X\in
S_{+},\;\sum_{i\in[n]}X_{ii}=1,\;X_{ij}\geq 0\;\forall\,ij\in[n]\text{ with
equality if $ij\in E(G)$}\\}.$

Clearly, for any graph $G$, the following chain of inequality holds:
$\vartheta^{\prime}(\overline{G})\leq\vartheta(\overline{G})\leq\xi(G)$. In
the following proposition, we show that
$\vartheta^{\prime}(\overline{G_{\mathcal{K}}})\leq 2n$, meaning that this
parameter does not provide a useful lower bound on
$\xi(\overline{G_{\mathcal{K}}})$. Although we don’t know whether
$\vartheta(\overline{G_{\mathcal{K}}})$ is also upper bounded by $cn$, for
some $c$ constant, computational results seems to indicate that these two
parameters are always close to each other [Meu05, DR08].

######  Proposition Ethmcountersep4.

The graph $G_{\mathcal{K}}$ as above satisfies
$\vartheta^{\prime}(\overline{G_{\mathcal{K}}})\leq 2n$.

###### Proof.

We consider the complement graph $\overline{G_{\mathcal{K}}}$, whose vertices
are all the strings in $\\{0,1\\}^{n}$ and two strings are adjacent if their
Hamming distance is at most $n/2-1$. This graph arises in the context of
Hamming schemes (see [DL98] for a background on association schemes) and
Schrijver [Sch79] (see also [MRR78]) proved that both
$\vartheta(\overline{G_{\mathcal{K}}})$ and
$\vartheta^{\prime}(\overline{G_{\mathcal{K}}})$ can be written as a linear
program. In particular,

$\vartheta^{\prime}(\overline{G_{\mathcal{K}}})=\max\bigg{\\{}1+\sum_{k=n/2}^{n}a_{k}:\,a_{k}\geq
0\;\forall\,k\in\\{n/2,\dots,n\\};\binom{n}{d}+\sum_{k=n/2}^{n}a_{k}K_{d}^{n}(k)\geq
0\;\forall\,d\in\\{0,\dots,n\\}\bigg{\\}}$

where $K_{d}^{n}(k)$ is the evaluation at $k$ of the degree-$d$ (binary)
Krawtchouk polynomial $K_{d}^{n}$ defined as (2). This program is equal to the
well-known Delsarte’s linear program [Del73].

Let us now consider a new linear program where, among the constraints using
the Krawtchouk polynomials, we only keep the ones of degree-1:

$\lambda(\overline{G_{\mathcal{K}}}):=\max\bigg{\\{}1+\sum_{k=n/2}^{n}a_{k}:\,a_{k}\geq
0\;\forall\,k\in\\{n/2,\dots,n\\};\;n+\sum_{k=n/2}^{n}a_{k}K_{1}^{n}(k)\geq
0\bigg{\\}}.$

Clearly,
$\vartheta^{\prime}(\overline{G_{\mathcal{K}}})\leq\lambda(\overline{G_{\mathcal{K}}})$
and it can be easily derived that the constraints of
$\lambda(\overline{G_{\mathcal{K}}})$ imply the Plotkin bound, i.e., that
$\lambda(\overline{G_{\mathcal{K}}})\leq 2n$ (see for example [Del73, Section
4.3]). ∎