Communication complexity of entanglement assisted multi-party computation

Ruoyu Meng and Aditya Ramamoorthy Department of Electrical and Computer Engineering
Iowa State University, Ames, IA , USA
Email: {rmeng, adityar}@iastate.edu

Abstract

We consider a quantum and a classical version of a multi-party function computation problem with $n$ players, where players $2,\dots,n$ need to communicate appropriate information to player 1, so that a ”generalized” inner product function with an appropriate promise can be calculated. In the quantum version of the protocol, the players have access to entangled qudits but the communication is still classical. The communication complexity of a given protocol is the total number of classical bits that need to be communicated. When $n$ is prime and for our chosen function, we exhibit a quantum protocol (with complexity $(n-1)\log n)$ bits) and a classical protocol (with complexity $((n-1)^{2}(\log n^{2})$ bits). We present an integer linear programming formulation for determining a lower bound on the classical communication complexity. This demonstrates that our quantum protocol is strictly better than classical protocols.

I Introduction

We consider a multi-party function computation scenario in this work. There are a total of $n$ players in the system numbered $1,2,\dots,n$ . Each player observes her input and players $2,\dots,n$ (remote parties) communicate an appropriate number of bits that allows player 1 to finally compute the value of the function. Clearly, this can be accomplished if players $2,\dots,n$ send their inputs but in fact in many cases, the function value can be computed with much lesser information. Thus, a natural question is to understand the minimum number of bits the remote parties need to send to player 1.

Such problems are broadly studied under the umbrella of communication complexity [1, 2] in the literature. In this work we consider the zero-error version of this problem. Our main goal is to understand the advantage that the availability of quantum entanglement confers on this problem and comparing it with classical protocols. Such problems have a long history in the literature [3, 4].

Background: Within quantum communication complexity (QCC) problems, there are three kinds of quantum protocols. In the first kind (introduced by Yao [2]) each player communicates via a quantum channel and the metric is the number of qubits transmitted. We call it the quantum transmission model. The second variation assumes that each player can use entanglement as a free resource but the communication is classical; the metric is the number of classical bits transmitted. We call it the entanglement model. It was introduced by Cleve and Buhrman [5]. The third kind is a combination of the first two. We call it the combined model. It allows free usage of entanglement and works with quantum communication. The work of de Wolf [6] shows that, in the two party case, the entanglement model can be reduced to the quantum transmission model with a factor of two penalty using teleportation [7].

Buhrman, Cleve, Wigderson [8] and Cleve, van Dam, Nielsen and Tapp [9] considered the case of the two party function computation with quantum communication and used reduction techniques to connect problems in QCC to other known problems and derived upper/lower bounds for QCC in this manner. In particular, the first work [8] showed examples, such as set disjointness function, where quantum protocols are strictly better than classical ones in the bounded-error setting. Here, the set-disjointness problem is such that each player has a set and wants to decide if their intersection is empty. Buhrman and de Wolf [10] generalized the two-party "log rank" lower bound of classical communication complexity to QCC where quantum protocols use both shared entanglement and quantum communication. For other two-party upper/lower bound techniques, see [11, 12, 13, 14, 15].

Related Work: Now we discuss works in multiparty quantum communication complexity. There are mainly two kinds of models. The number-in-hand (NIH) model assumes each player observes only one variable. The number-on-forehead (NOF) model assumes each player observes all but one variable. François and Shogo[16] considered the NIH model with quantum communication and gave a quantum protocol for a three-party triangle-finding problem; the formulation considers bounded error. This has polynomial advantage with respect to any classical protocol. Here, the triangle-finding problem is such that the edge set of a graph is distributed over each user and the task is to find a triangle of the graph.

The results in next two works hold for both NIH and NOF models. Lee and Schechtman and Shraibman [17] proved a Grothendieck-type inequality and then derived a general lower bound of the multiparty QCC for Boolean function in Yao’s model. Following this work, Briet, Buhrman, Lee, Vidick [18] showed a similar inequality for the multiparty XOR game and proved that the discrepancy method lower bounds QCC when the combined is of the third kind discussed earlier.

Buhrman, van Dam, Høyer, Tapp [19] considered the NIH model with shared entanglement and proposed a three-party problem with a quantum protocol that is better than any classical protocol by a constant factor. Following this work, Xue, Li, Zhang, Guo [20] and Galvão [21] showed similar results under the same function with more restrictions. The work most closely related to our work is by Cleve and Buhrman [5]. This paper considered the case of three players denoted Alice, Bob and Carol who have $m$ -bit strings denoted $\vec{x},\vec{y}$ and $\vec{z}$ respectively. The strings are such that $\vec{x}+\vec{y}+\vec{z}=\mathds{1}$ , i.e., their binary sum (modulo-2) is the all-ones vector. The goal is for Alice to compute

\displaystyle g(x,y,z)

\displaystyle=\sum_{i=1}^{m}x_{i}y_{i}z_{i}

using binary arithmetic. We note that the communication from Bob and Carol to Alice is purely classical; however, they can use entanglement in a judicious manner. For this particular function [5] shows that a classical protocol (without entanglement) requires three bits of communication, whereas if the parties share $3m$ entangled qubits, then two bits of communication are sufficient.

Main Contributions: In this work, we consider a significant generalization of the original work of [5]. In particular, we consider a scenario with $n$ players (for prime $n$ ) that observe values that lie in a higher-order finite field, with a more general promise that is satisfied by the observed values. As we consider more players and higher-order finite fields, the techniques used in the original work are not directly applicable in our setting.

Our work makes the following contributions.

•

We demonstrate a quantum protocol that allows for the function to be computed with $(n-1)\log n$ bits. We use the quantum Fourier Transform as a key ingredient.
•

On the other hand, we demonstrate a classical protocol that requires the communication of $(n-1)^{2}(\log n^{2})$ bits.
•

To obtain a lower bound on the classical communication complexity, we define an appropriate integer linear programming problem that demonstrates that our quantum protocol is strictly better than any classical protocol.

This paper is organized as follows. Section II discusses the problem formulation and Section III discusses our quantum protocol. Sections IV and V discuss our classical protocol and the lower bound on any classical protocol respectively.

II Problem formulation

II-A Classical/Quantum Communication Scenarios

Let $\mathcal{X}_{i},i=1,\dots,n$ and $\mathcal{Y}$ denote sets in which the inputs and the output lie and $f(x_{1},\dots,x_{n}):\mathcal{X}_{1}\times\dots\times\mathcal{X}_{n}\mapsto\mathcal{Y}$ be a multivariate function. There are $n$ players such that $i$ -th player is given $x_{i}\in\mathcal{X}_{i}$ . The first player (henceforth, Alice) receives information from each of the players and this communication should allow her to compute $f(x_{1},\dots,x_{n})$ . The players are not allowed to communicate with each other.

In the classical protocol, players $2$ to $n$ communicate to Alice via classical channels. In the quantum protocol, we assume that the users have shared entanglement as a free resource; however, the communication is still classical. In both scenarios the classical/quantum communication complexity is the least possible number of classical bits transmitted such that Alice can compute the function among all classical/quantum protocols.

II-B Generalized Inner Product Function with a Promise

In this work we consider a specific multivariate function and the setting where $n\geq 3$ (number of players) is prime. Let $\mathbb{F}_{n}$ denote the finite field of order- $n$ and $[m]\triangleq\{1,\dots,m\}$ . The $i$ -th player is given a vector $\vec{x}^{i}=[x^{i}_{1}\dots x^{i}_{m}]^{T}\in\mathbb{F}_{n}^{m}$ , i.e., each $x^{i}_{j}\in\mathbb{F}_{n}$ . The vectors satisfy the following “promise”: $\forall j\in[m],$ the $j$ -th component of each player’s vector is s.t.

\displaystyle[x^{1}_{j},\dots,x^{n}_{j}]^{T}\in\{

\displaystyle a[1,\dots,1]^{T}+b[0,\dots,n-1]^{T}~{}|~{}a,b\in\mathbb{F}_{n}\},

i.e., $[x^{1}_{j},\dots,x^{n}_{j}]^{T}$ lies in a two-dimensional vector space spanned by the basis vectors $[1,\dots,1]^{T}$ and $[0,1,\dots,n-1]^{T}$ . In this case, it can be observed that $[x^{1}_{j},\dots,x^{n}_{j}]^{T}$ is either a multiple of the all-ones vector (if $b=0$ ) or a permutation of $[0,1,\dots,n-1]$ (if $b\neq 0$ ). The function to be computed is the generalized inner product function given by

\displaystyle GIP(\vec{x}^{1},\dots,\vec{x}^{n})=\sum_{i=1}^{m}\left(\prod_{j=1}^{n}x_{i}^{j}\right),

(1)

where the operations are over $\mathbb{F}_{n}$ .

III Proposed Quantum Protocol

We first discuss the entangled states and unitary transforms will be used in the proposed quantum protocol in Section III-A. In Section III-B, we discuss the quantum protocol with a proof of correctness in detail. A word about notation. In what follows for complex vectors $\vec{u},\vec{v}$ , $\braket{\vec{u},\vec{v}}=\sum_{i}u^{\dagger}_{i}v_{i}$ denotes the usual inner product. On the other hand if $\vec{u},\vec{v}\in\mathbb{F}_{n}^{m}$ , then $\braket{\vec{u},\vec{v}}=\sum_{i=1}^{m}u_{i}v_{i}$ denotes the inner product over $\mathbb{F}_{n}$ . Moreover, $\delta_{ij}$ denotes the Kronecker delta function which equals 1 if $i=j$ and 0 otherwise. All logarithms in this paper are to the base-2.

III-A Entanglement Resource and Unitary Transforms Used

Shared Entangled States.

Consider $n$ isomorphic $n$ -dimensional quantum systems, where each system has a computational basis denoted $\mathcal{B}=\{\ket{0},\ket{1},\dots,\ket{n-1}\}$ . There are $m$ entangled states shared among $n$ players. For $i\in[m]$ , prepare the entangled state

\displaystyle\ket{\Phi_{i}}:=\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\ket{k\dots k}.

(2)

The $j$ -th subsystem of this entangled state is given to $j$ -th player for $j=1,\dots,n$ .

Quantum Fourier Transform.

Let $\omega:=e^{\frac{2\pi\textrm{i}}{n}}$ denote the $n$ -th root of unity. The Quantum Fourier Transform (QFT) is the following unitary map that takes

\ket{j}\mapsto\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\omega^{jk}\ket{k},~{}\forall\ket{j}\in\mathcal{B}.

(3)

Let $QFT^{\otimes l}$ denote QFT performed over $l$ isomorphic systems.

Phase Shift Map.

For $j\in\mathbb{F}_{n}$ , we define

		$\displaystyle P_{0}\triangleq\begin{cases}\ket{0}\mapsto\omega^{-\frac{n-1}{2}}\ket{0}\\ \ket{i}\mapsto\ket{i},i\neq 0.\end{cases}$
	$\displaystyle\text{If }j\neq 0,~{}$	$\displaystyle P_{j}\triangleq\ket{i}\mapsto\omega^{-\frac{1}{n}(ij\text{ mod }n)}\ket{i}.$		(4)

For

i\in\{1,\dots,m\}

, prepare maximally entangled “shared state”

\ket{\Phi_{i}}

(cf. (2)) and distribute corresponding subsystems to all players.

for player

p\in\{1,\dots n\}

for each

i\in\{1,\dots,m\}

Assume

x_{i}^{p}=j

, then player

p

applies

P_{j}

(cf. (4)) on her part of

\ket{\Phi_{i}}

Player

p

performs

QFT

on her part of the shared state.

Player

p

measures her part of the shared state in the computational basis, yielding

s_{i}^{p}\in\mathbb{F}_{n}

end for

s^{p}\leftarrow\sum_{i=1}^{m}s_{i}^{p}

Player

p

sends

s^{p}

to Alice if

p\neq 1

end for

GIP(\vec{x}^{1},\dots,\vec{x}^{n})=\sum_{p}s^{p}.

Algorithm 1 Proposed Quantum protocol

III-B The Quantum Protocol

Next, we introduce the quantum protocol.

Theorem 1.

There exists a quantum protocol for computing $GIP(\vec{x}^{1},\dots,\vec{x}^{n})$ that uses $(n-1)\log n$ bits.

In our protocol (see Alg. 1), for each $i=1,\dots,m$ , each player $p$ examines $x_{i}^{p}$ and applies the corresponding phase shift map to her subsystem of $\ket{\Phi_{i}}$ . Following this, she applies the QFT on each of her symbols and then measures in the computational basis; this yields $s_{i}^{p}\in\mathbb{F}_{n}$ for $i=1,\dots,m$ . Player $p$ then transmits $\sum_{i=1}^{m}s_{i}^{p}$ . As players $2\leq p\leq n$ transmit a symbol from $\mathbb{F}_{n}$ , it is clear that the total communication in the protocol is $(n-1)(\log n)$ .

To show correctness of the protocol, we need the following auxiliary lemma. The proof appears in Appendix A.

Lemma 1.

Let $\vec{\alpha}=[1,\dots,1]^{T}\in\mathbb{F}_{n}^{n}$ . Then, for each $x\in\mathbb{F}_{n}$ , we have

\displaystyle QFT^{\otimes n}\left(\frac{1}{\sqrt{n}}\sum_{j=0}^{n-1}\omega^{-jx}\ket{j\cdot\vec{\alpha}}\right)=\frac{1}{n^{\frac{n}{2}}}\sum_{\vec{k}\in\{0,\dots,n-1\}^{n}}a_{\vec{k}}\ket{\vec{k}}.

(5)

Then the amplitude $a_{\vec{k}}\neq 0$ iff $\sum_{j=1}^{n}k_{j}=x$ where $\vec{k}=[k_{1},\dots,k_{n}]^{T}$ .

The proof of correctness of the protocol hinges on the following lemma.

Lemma 2.

\sum_{p=1}^{n}s_{i}^{p}=\prod_{p=1}^{n}x_{i}^{p},\text{for $i=1,\dots,m$}.

(6)

Proof.

The state jointly measured by each player is

QFT^{\otimes n}\left(\sum_{j=0}^{n-1}\left(\otimes_{p=1}^{n}P_{x_{i}^{p}}\right)\frac{1}{\sqrt{n}}\ket{j\cdot\vec{\alpha}}\right),

where $\vec{\alpha}=[1,\dots,1]^{T}$ . If $[x_{i}^{1},\dots,x_{i}^{n}]^{T}=[j,\dots,j]^{T}$ , then (see Appendix B for derivation)

\begin{split}P_{j}^{\otimes n}\left(\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}\right)\mapsto\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\omega^{-k{j}}\ket{k\cdot\vec{\alpha}}.\end{split}

(7)

Thus, $QFT^{\otimes n}\left(\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\omega^{-kj}\ket{k\cdot\vec{\alpha}}\right)$ has non-zero coefficients only for states $\ket{\vec{k}}$ such that $\sum_{l=1}^{n}k_{l}=j$ by Lemma 1. Therefore, the measurement result $[s_{i}^{1},\dots,s_{i}^{n}]^{T}$ must be one of $\vec{k}=[k_{1},\dots,k_{n}]^{T}$ s.t.

\sum_{l=1}^{n}k_{l}=j\overset{(a)}{=}j^{n}=\prod_{p=1}^{n}x_{i}^{p}

where $(a)$ follows from the fact that $j\in\mathbb{F}_{n}$ .

Now assume $[x^{1}_{j},\dots,x^{n}_{j}]^{T}=a[1,\dots,1]^{T}+b[0,1,\dots,n-1]^{T}$ with $b\neq 0$ . This implies that $a+b\cdot i\in\mathbb{F}_{n}$ is distinct for each $i\in\{0,\dots,n\}$ . It can be observed that $a[1,\dots,1]+b[0,\dots,n-1]$ is a permutation of $[0,\dots,n-1]$ , so it suffices to discuss $[x_{i}^{1},\dots,x_{i}^{p}]^{T}=[0,\dots,n-1]^{T}$ by symmetry. We have that (see Appendix B for derivation)

\begin{split}&P_{0}\otimes\dots\otimes P_{n-1}\left(\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}\right)\mapsto\frac{1}{\sqrt{n}}\omega^{-\frac{n-1}{2}}\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}\end{split}

(8)

It follows that

	$\displaystyle QFT^{\otimes n}\left(\frac{1}{\sqrt{n}}\omega^{-\frac{n-1}{2}}\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}\right)$
	$\displaystyle=\omega^{-\frac{n-1}{2}}QFT^{\otimes n}\left(\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}\right)=\frac{1}{n^{\frac{n}{2}}}\omega^{-\frac{n-1}{2}}\sum_{\vec{k}\in\mathbb{F}_{n}^{n}}a_{\vec{k}}\ket{\vec{k}}.$

By Lemma 1, $a_{\vec{k}}\neq 0$ iff $\sum_{l=1}^{n}k_{l}=0$ . The measurement result $[s_{i}^{1},\dots,s_{i}^{n}]^{T}$ must be $\vec{k}=[k_{1},\dots,k_{n}]^{T}$ such that

\sum_{l=1}^{n}k_{l}=0=\prod_{j=0}^{n-1}j=\prod_{p=1}^{n}x_{i}^{p}.

∎

Now, we show that our protocol computes $GIP(\vec{x}^{1},\dots,\vec{x}^{n})$ correctly. Since $s^{p}=\sum_{i}s_{i}^{p}$ , by applying (6), we have that

	$\displaystyle\sum_{p}s^{p}$	$\displaystyle=\sum_{p}\sum_{i}s_{i}^{p}=\sum_{i}\sum_{p}s_{i}^{p}$
		$\displaystyle=\sum_{i}\prod_{p=1}^{n}x_{i}^{p}=GIP(\vec{x}^{1},\dots,\vec{x}^{n}).$

IV Proposed Classical protocol

We now move on to considering purely classical protocols for our problem, i.e., ones that do not consider entanglement. At the top-level our classical scheme operates by communicating the “number” of different symbols that exist in within each player’s vector. We show that this suffices for Alice to recover the function value.

More precisely, let $\beta_{k}^{p}$ be the number of “ $k$ ” values in the vector of $p$ -th player; recall that player $p$ is assigned $\vec{x}_{p}=x_{1}^{p}\dots x_{m}^{p}$ . Note that $\sum_{k=0}^{n-1}\beta_{k}^{p}=m$ .

Theorem 2.

There exists a classical protocol for computing $GIP(\vec{x}^{1},\dots,\vec{x}^{n})$ that uses $(n-1)^{2}(\log n^{2})$ bits.

In our protocol (see Alg. 2), for each $i=1,\dots,n-1$ , each player $p$ transmits $\beta_{k}^{p}\text{ (mod}\ n^{2}\text{)}$ . Alice computes each $\beta_{0}^{p}\text{ (mod}\ n^{2}\text{)}$ by using the fact that $\sum_{k=0}^{n-1}\beta_{k}^{p}=m$ . Finally, Alice computes the value of the function by using $\{\beta_{k}^{p}\text{ (mod}\ n^{2}\text{)}|k\in\mathbb{F}_{n},p\in[n]\}$ For each player $p\in\{2,\dots,n\}$ , $p$ transmits $\{\beta_{1}^{p}\text{ (mod}\ n^{2}\text{)},\dots,\beta_{n-1}^{p}\text{ (mod}\ n^{2}\text{)}\}$ . The total number of bits transmitted is $(n-1)^{2}(\log n^{2})$ . The proof of the Theorem 2 appears in Appendix C.

for player

p\in\{1,\dots n\}

for each

k\in\mathbb{F}_{n}

\beta_{k}^{p}\leftarrow

number of “

k

” values in

x_{1}^{p}\dots x_{m}^{p}

p

is not Alice and

k\neq 0

then

p

sends

\beta_{k}^{p}\text{ (mod}\ n^{2}\text{)}

to Alice

end if

end for

for

p\in\{2,\dots n\}

Alice computes

\beta_{0}^{p}\text{ (mod}\ n^{2}\text{)}

by using

\sum_{k=0}^{n-1}\beta_{k}^{p}=m

end for

W\leftarrow\sum_{p=1}^{n}\sum_{k=1}^{n-1}k\cdot\beta_{k}^{p}+\frac{n^{2}-n}{2}(n-1)\sum_{p=1}^{n}\beta_{0}^{p}\text{ (mod}\ n^{2}\text{)}

GIP(\vec{x}^{1},\dots,\vec{x}^{n})=W/n

Algorithm 2 Proposed Classical protocol

V Classical communication complexity lower bound

We now discuss a lower bound on the classical communication complexity that demonstrates a strict separation between our proposed quantum protocol and any classical protocol. Analytically, this seems to be a rather hard problem, and we discuss it as an item for future work. We are able to show however, the strict separation numerically using ILPs (see Section V-A below). In addition, we present an analytical argument below that demonstrates that for $n=3$ , the communication cost of any classical protocol is at least $2\log_{2}3$ .

We assume that Alice, Bob, and Carol are given vectors $\vec{x}^{1}$ , $\vec{x}^{2}$ , and $\vec{x}^{3}$ , respectively, each of length $m$ . The promise (cf. Sec. II-B) is equivalent to

\displaystyle x^{1}_{j}+x^{2}_{j}+x^{3}_{j}=0,~{}\text{for~{}}j=1,\dots,m.

(9)

This implies that the GIP function in this case can be computed if we know any two out of $\vec{x}^{1},\vec{x}^{2}$ , and $\vec{x}^{3}$ . We assume that Carol labels her sequences ( $\vec{x}^{3}\in\{0,1,2\}^{m}$ ) with one of at most three possible labels.We denote this label by a mapping $\beta:\{0,1,2\}^{m}\to\{0,1,2\}$ . Recall that Alice knows $\vec{x}^{1}$ .

Definition 1.

We define Bob’s confusion graph $G_{B}=(V_{B},E_{B})$ as follows. The vertex set $V_{B}$ corresponds to the $3^{m}$ sequences $\vec{x}^{2}\in\{0,1,2\}^{m}$ . The $i$ -th such sequence is denoted $\vec{x}^{2}[i]$ for $i=0,\dots,3^{m}-1$ , with similar notation for Alice and Carol’s sequences.

There exists an edge $(\vec{x}^{2}[i],\vec{x}^{2}[j])\in E_{B}$ , for $i\neq j$ if there exists an Alice sequence $\vec{x}^{1}[*]$ and Carol sequences $\vec{x}^{3}[a]$ and $\vec{x}^{3}[b]$ such that (i) $\beta(\vec{x}^{3}[a])=\beta(\vec{x}^{3}[b])$ (note that we allow $a=b$ ), and (ii) $GIP(\vec{x}^{1}[*],\vec{x}^{2}[i],\vec{x}^{3}[a])\neq GIP(\vec{x}^{1}[*],\vec{x}^{2}[j],\vec{x}^{3}[b])$ .

Note that if $(\vec{x}^{2}[i],\vec{x}^{2}[j])\in E_{B}$ , the Bob has to assign different labels to $\vec{x}^{2}[i]$ and $\vec{x}^{2}[j]$ ; otherwise, Alice has no way to compute the function with zero error. The idea of the confusion graph goes back to the work of Shannon [22].

The main idea of the argument below is to show that there exists a triangle in $G_{B}$ . This implies that the Bob needs to use at least three labels for Alice to decode with zero-error.

Since Carol uses at most three labels, then using the pigeon-hole principle there exist at least $3^{m-1}$ sequences that have the same Carol label. Let us denote this set $\mathcal{C}$ .

Claim 1.

There is a subset of two coordinates where all nine patterns $\{0,1,2\}^{2}$ appear within the sequences in $\mathcal{C}$ .

Proof.

Suppose that $m$ is even. Then, we can partition the coordinates as $\{1,2\},\{3,4\},\dots,\{m-1,m\}$ . Let us arrange the sequences in $\mathcal{C}$ as rows; the number of rows is $|\mathcal{C}|\geq 3^{m-1}$ . Now suppose that the projection onto any pair of coordinates has at most 8 representatives. Then, the size of $\mathcal{C}$ can be at most $8^{m/2}$ . For large enough $m$ , we have

\displaystyle\frac{3^{m-1}}{8^{m/2}}

\displaystyle=\frac{1}{3}\times\left(\frac{9}{8}\right)^{m/2}>1.

∎

Without loss of generality, we assume that all nine patterns occur within the first two coordinates of $\mathcal{C}$ . We pick 9 such representatives from $\mathcal{C}$ and denote them $\mathbf{z}_{00},\mathbf{z}_{01},\mathbf{z}_{02},\mathbf{z}_{10},\dots,\mathbf{z}_{22}$ ; the subscript corresponds to the values on the first two coordinates.

Let us pick Alice’s sequence $\vec{x}^{1}[*]=[1~{}1~{}0~{}\dots~{}0]$ . Corresponding to this $\vec{x}^{1}[*]$ , for the Carol sequences $\mathbf{z}_{00},\dots,\mathbf{z}_{22}$ , using the promise we can obtain the corresponding Bob sequences $\mathbf{y}_{00},\dots,\mathbf{y}_{22}$ . We note here that

	$\displaystyle\mathbf{y}_{00}$	$\displaystyle=[2~{}2-z_{00}(3:m)],\text{~{}and}$
	$\displaystyle\mathbf{y}_{01}$	$\displaystyle=[2~{}1-z_{01}(3:m)],\text{~{}and}$
	$\displaystyle\mathbf{y}_{11}$	$\displaystyle=[1~{}1-z_{11}(3:m)].$

where, e.g., $z_{00}(3:m)$ denotes the components of vector $z_{00}$ from index 3 onwards (basically MATLAB notation).

Claim 2.

In Bob’s confusion graph, $G_{B}$ , the sequences $\mathbf{y}_{00},\mathbf{y}_{01},$ and $\mathbf{y}_{11}$ form a triangle.

Proof.

We need to examine $GIP(\vec{x}^{1}[*],\mathbf{y}_{i},\mathbf{z}_{i})$ for $i=00,01,11$ . Only the first two coordinates matter since $\vec{x}^{1}[*]=[1~{}1~{}0~{}\dots~{}0]$ . The corresponding evaluations are $0,1,2$ which are pairwise different. ∎

The above shows that Bob needs to use at least three labels for Alice to decode with zero-error. By symmetry, Carol needs to use three labels as well. To summarize, the communication complexity of any classical protocol is at least $2\log 3$ bits.

Remark 1.

It may be possible to use a variant of the above combinatorial argument to establish that the chromatic number of $G_{B}$ is strictly larger than three. However, this does not seem to follow in a straightforward manner.

TABLE I: Numerical results.

$m$	$l^{b}$	$l^{c}$	Feasibility
1	1	3	Feasible
3	1	17	Infeasible
2	2	4	Infeasible
3	3	3	Infeasible
2	3	4	Feasible
3	5	5	Feasible

V-A ILP Feasibility Problem for Classical Lower Bound

We now present a lower bound on the communication complexity of any classical protocol for our problem. Towards this end we pose this as an integer linear programming problem that can be solved numerically.

Suppose, for $p\in\{2,\dots,n\}$ , the $p$ -th player sends symbols (labels) in $[l^{p}]:=\{1,2,\dots,l^{p}\}$ for some large enough positive integer $l^{p}$ . Let $c\in[l^{p}]$ and define $I_{\vec{x}^{p},c}\in\{0,1\}$ to be the indicator that the $p$ -th player sends $c$ when it has the vector $\vec{x}^{p}\in\mathbb{F}_{n}^{m}$ . As this mapping is unique, we have $\sum_{c\in[l^{p}]}I_{\vec{x}^{p},c}=1$ . Furthermore, for a given set of vectors $\vec{x}^{p}$ for $p\in\{2,\dots,n\}$ if the $p$ -th player sends label $c^{p}$ , we have $\prod_{p=2}^{n}I_{\vec{x}^{p},c^{p}}=1$ .

Consider two sets of vectors $\{\vec{x}^{p}\in\mathbb{F}_{n}^{m}|p\in\{1,\dots,n\}\}$ , $\{\vec{z}^{p}\in\mathbb{F}_{n}^{m}|p\in\{1,\dots,n\}\}$ . We denote $(\vec{x}^{1},\dots,\vec{x}^{n})\sim_{GIP}(\vec{z}^{1},\dots,\vec{z}^{n})$ if the following conditions are satisfied.

1.

Both $(\vec{x}^{1},\dots,\vec{x}^{n})$ and $(\vec{z}^{1},\dots,\vec{z}^{n})$ satisfy the promise (cf. Sec. II-B).
2.

$\vec{x}^{1}=\vec{z}^{1}$ .
3.

$GIP(\vec{x}^{1},\dots,\vec{x}^{n})\neq GIP(\vec{z}^{1},\dots,\vec{z}^{n})$ .

This definition applies to distinct inputs with the "same" Alice vector, but different function evaluations. It can be seen that for two such distinct inputs, the symbols communicated by players 2 to $n$ have to be distinct, otherwise Alice has no way to decode in a zero-error fashion.

Our proposed ILP works with fixed $l^{p}$ ’s and a fixed value of $m$ . Owing to complexity reasons $m$ cannot be very large. However, we point out that if the ILP is infeasible for given $l^{p}$ ’s and a $\tilde{m}$ , then our lower bound holds for arbitrary values $m\geq\tilde{m}$ . To see this we note that our lower bound would continue to hold even if Alice was provided the values $x^{p}_{\tilde{m}+1},\dots,x^{p}_{m}$ for all players $p=2,\dots,n$ .

Consider a $0-1$ integer programming feasibility problem:

	$\displaystyle\min\quad 0$	(10)
s.t.	$\displaystyle p\in\{2,\dots,n\},c\in[l^{p}],\vec{x}^{p}\in\mathbb{F}_{n}^{m},$
	$\displaystyle I_{\vec{x}^{p},c}\in\{0,1\},$
	$\displaystyle\sum_{c\in[l^{p}]}I_{\vec{x}^{p},c}=1,~{}\forall~{}\vec{x}^{p},$
$\displaystyle\ \sum_{c^{2}\in[l^{2}],\dots,c^{n}\in[l^{n}]}$	$\displaystyle\|\prod_{p=2}^{n}I_{\vec{x}^{p},c^{p}}-\prod_{p=2}^{n}I_{\vec{z}^{p},c^{p}}\|=2$
for all	$\displaystyle(\vec{x}^{1},\dots,\vec{x}^{n})\sim_{GIP}(\vec{z}^{1},\dots,\vec{z}^{n}).$

The infeasibility of the above problem corresponds to a lower bound on the classical communication complexity. The proof of the following theorem appears in Appendix D.

Theorem 3.

There exists a deterministic classical protocol computing $GIP(\cdot)$ where each player sends at most $l^{p}$ different labels for $p\in\{2,\dots,n\}$ iff the above integer programming is feasible.

Remark 2.

The integer program contains constraints that involve the product of variables and equality constraints with sums of absolute values. We show how these constraints can be linearized in Appendix E. The entire code for our ILP is available at this online repository [23].

V-B Numerical experiments

In our numerical experiments, we considered an instance of the ILP involving $n=3$ players, namely Alice, Bob, and Carol. Let $m$ represent the length of each vector, while $[l^{b}],[l^{c}]$ denote the sets of labels used by Bob and Carol, with $l^{b},l^{c}$ as the sizes of these sets.

We assume that Alice, Bob, and Carol are given vectors $\vec{x}^{1}$ , $\vec{x}^{2}$ , and $\vec{x}^{3}$ , respectively, each of length $m$ . In this case, the promise is given by (9). It can be observed that swapping the vectors of Bob and Carol continues to satisfy the promise. Due to this inherent symmetry, a protocol with communication lengths $l^{b}=x$ and $l^{c}=y$ exhibits the same feasibility as one with $l^{b}=y$ and $l^{c}=x$ . Consequently, for the ILP we can assume that $l^{b}\leq l^{c}$ .

The experimental results under varying settings of $l^{b},l^{c},m$ are displayed in TABLE I. It shows for instance, that when $l^{b}=1$ and $l^{c}=17$ , the ILP is infeasible with $m=3$ . This implies that for a feasible classical protocol, with $l^{b}=1$ , we need at least $\log(18)$ bits to be transmitted from Carol. Similarly, the triplets $(m,l^{b},l^{c})=(2,2,4)$ and $(3,3,3)$ are infeasible. This implies that when $l^{b}$ equals 2 or 3 the sum rate is $\geq\min(\log 2+\log 5,\log 3+\log 4)$ .

Recalling that our proposed protocol employs $2\log(3)$ bits of communication, and by the fact that

\displaystyle 2\log 3<\min(\log 18,\log 3+\log 4,\log 2+\log 5)

we conclude that there is a strict separation between our quantum protocol and any classical protocol.

References

[1] A. C.-C. Yao, “Some complexity questions related to distributive computing(preliminary report),” in Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, ser. STOC ’79. New York, NY, USA: Association for Computing Machinery, 1979, p. 209–213. [Online]. Available: https://doi.org/10.1145/800135.804414
[2] A. Chi-Chih Yao, “Quantum circuit complexity,” in Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, 1993, pp. 352–361.
[3] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, “Quantum entanglement,” Rev. Mod. Phys., vol. 81, pp. 865–942, Jun 2009. [Online]. Available: https://link.aps.org/doi/10.1103/RevModPhys.81.865
[4] H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, “Nonlocality and communication complexity,” Rev. Mod. Phys., vol. 82, pp. 665–698, Mar 2010. [Online]. Available: https://link.aps.org/doi/10.1103/RevModPhys.82.665
[5] R. Cleve and H. Buhrman, “Substituting quantum entanglement for communication,” Phys. Rev. A, vol. 56, pp. 1201–1204, Aug 1997. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.56.1201
[6] R. de Wolf, “Quantum communication and complexity,” Theoretical Computer Science, vol. 287, no. 1, pp. 337–353, 2002, natural Computing. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0304397502003778
[7] 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., vol. 70, pp. 1895–1899, Mar 1993. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.70.1895
[8] H. Buhrman, R. Cleve, and A. Wigderson, “Quantum vs. classical communication and computation,” in Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, ser. STOC ’98. New York, NY, USA: Association for Computing Machinery, 1998, p. 63–68. [Online]. Available: https://doi.org/10.1145/276698.276713
[9] R. Cleve, W. van Dam, M. Nielsen, and A. Tapp, “Quantum entanglement and the communication complexity of the inner product function,” Theoretical Computer Science, vol. 486, pp. 11–19, 2013, theory of Quantum Communication Complexity and Non-locality. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S030439751201105X
[10] H. Buhrman and R. de Wolf, “Communication complexity lower bounds by polynomials,” in Proceedings of Computational Complexity. Sixteenth Annual IEEE Conference. Los Alamitos, CA, USA: IEEE Computer Society, jun 2001, p. 0120. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/CCC.2001.933879
[11] A. A. Razborov, “Quantum communication complexity of symmetric predicates,” Izvestiya: Mathematics, vol. 67, no. 1, p. 145, feb 2003. [Online]. Available: https://dx.doi.org/10.1070/IM2003v067n01ABEH000422
[12] H. Klauck, “Lower bounds for quantum communication complexity,” SIAM Journal on Computing, vol. 37, no. 1, pp. 20–46, 2007. [Online]. Available: https://doi.org/10.1137/S0097539702405620
[13] W. van Dam and P. Hayden, “Renyi-entropic bounds on quantum communication,” 2002.
[14] A. Marwah and D. Touchette, “Optical quantum communication complexity in the simultaneous-message-passing model,” Phys. Rev. A, vol. 102, p. 062608, Dec 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.102.062608
[15] F. Le Gall and D. Suruga, “Bounds on oblivious multiparty quantum communication complexity,” in LATIN 2022: Theoretical Informatics, A. Castañeda and F. Rodríguez-Henríquez, Eds. Cham: Springer International Publishing, 2022, pp. 641–657.
[16] F. L. Gall and S. Nakajima, “Multiparty Quantum Communication Complexity of Triangle Finding,” in 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), ser. Leibniz International Proceedings in Informatics (LIPIcs), M. M. Wilde, Ed., vol. 73. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, pp. 6:1–6:11. [Online]. Available: http://drops.dagstuhl.de/opus/volltexte/2018/8579
[17] T. Lee, G. Schechtman, and A. Shraibman, “Lower bounds on quantum multiparty communication complexity,” in 2009 24th Annual IEEE Conference on Computational Complexity, 2009, pp. 254–262.
[18] J. Briet, H. Buhrman, T. Lee, and T. Vidick, “Multiplayer xor games and quantum communication complexity with clique-wise entanglement,” 2009. [Online]. Available: https://arxiv.org/abs/0911.4007
[19] H. Buhrman, W. van Dam, P. Høyer, and A. Tapp, “Multiparty quantum communication complexity,” Phys. Rev. A, vol. 60, pp. 2737–2741, Oct 1999. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.60.2737
[20] P. Xue, C.-F. Li, Y.-S. Zhang, and G.-C. Guo, “Three-party quantum communication complexity via entangled tripartite pure states,” Journal of Optics B: Quantum and Semiclassical Optics, vol. 3, no. 4, p. 219, jul 2001. [Online]. Available: https://dx.doi.org/10.1088/1464-4266/3/4/304
[21] E. F. Galvão, “Feasible quantum communication complexity protocol,” Phys. Rev. A, vol. 65, p. 012318, Dec 2001. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.65.012318
[22] C. Shannon, “The zero error capacity of a noisy channel,” IRE Transactions on Information Theory, vol. 2, no. 3, pp. 8–19, 1956.
[23] “Python code for ILP in Sec. V.” [Online]. Available: https://github.com/mengruoyu/ILP

Appendix A Proof of Lemma 1

Recall that

\vec{\alpha}=[1,\dots,1]^{T}.

The action of $\text{QFT}^{\otimes n}$ on $\frac{1}{\sqrt{n}}\sum_{j=0}^{n-1}\omega^{-xj}\ket{j\cdot\vec{\alpha}}$ is

	$\displaystyle\frac{1}{n^{\frac{n}{2}}}\sum_{\vec{k}\in\mathbb{F}_{n}^{n}}$	$\displaystyle a_{\vec{k}}\ket{\vec{k}}=QFT^{\otimes n}\left(\frac{1}{\sqrt{n}}\sum_{j=0}^{n-1}\omega^{-xj}\ket{j\cdot\vec{\alpha}}\right)$
		$\displaystyle=\frac{1}{n^{\frac{n}{2}}}\sum_{\vec{k}\in\mathbb{F}_{n}^{n}}\left(\frac{1}{\sqrt{n}}\sum_{j=0}^{n-1}\omega^{-xj}\cdot\omega^{\langle\vec{k},j\cdot\vec{\alpha}\rangle}\right)\ket{\vec{k}}.$

Write $\vec{k}=[k_{1},\dots,k_{n}]^{T}$ . Therefore,

a_{\vec{k}}=\frac{1}{\sqrt{n}}\sum_{j=0}^{n-1}\omega^{-xj}\cdot\omega^{\langle\vec{k},j\cdot\vec{\alpha}\rangle}=\frac{1}{\sqrt{n}}\sum_{j=0}^{n-1}\omega^{-xj+j\sum_{l=1}^{n}k_{l}}.

When $\vec{k}$ satisfies $\sum_{l=1}^{n}k_{l}=x$ , we have that $a_{\vec{k}}=\sqrt{n}\neq 0$ . Otherwise, since $-x+\sum_{l=1}^{n}k_{l}\neq 0$ and $n$ being prime, $1-\omega^{n(-x+\sum_{l=1}^{n}k_{l})}=0$ and $1-\omega^{-x+\sum_{l=1}^{n}k_{l}}\neq 0$ . We have

	$\displaystyle\frac{1}{\sqrt{n}}\sum_{j=0}^{n-1}\omega^{-xj+j\sum_{l=1}^{n}k_{l}}=\frac{1}{\sqrt{n}}\sum_{j=0}^{n-1}\omega^{(-x+\sum_{l=1}^{n}k_{l})j}$
	$\displaystyle=\frac{1}{\sqrt{n}}\frac{1-\omega^{n(-x+\sum_{l=1}^{n}k_{l})}}{1-\omega^{-x+\sum_{l=1}^{n}k_{l}}}=0.$

Appendix B Derivation of equation (7) and equation (8)

We derive equation (7) by considering two cases. The first case is that $[x_{i}^{1},\dots,x_{i}^{n}]^{T}=[0,\dots,0]^{T}$ . Then, we have

\begin{split}&P_{0}^{\otimes n}\left(\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}\right)\mapsto\frac{1}{\sqrt{n}}\omega^{-\frac{n(n-1)}{2}}\ket{0\cdot\vec{\alpha}}\\ &+\frac{1}{\sqrt{n}}\sum_{k=1}^{n-1}\ket{k\cdot\vec{\alpha}}=\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}=\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\omega^{-k\cdot 0}\ket{k\cdot\vec{\alpha}}.\end{split}

(11)

The second case is that $[x_{i}^{1},\dots,x_{i}^{n}]^{T}=[j,\dots,j]^{T}$ with $j\neq 0$ . Then, we have

\begin{split}&P_{j}^{\otimes n}\left(\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}\right)\mapsto\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\omega^{-n(\frac{1}{n}(kj\text{ mod }n))}\ket{k\cdot\vec{\alpha}}\\ &=\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\omega^{-k{j}}\ket{k\cdot\vec{\alpha}}\end{split}

(12)

where the last equality holds since $\omega^{-kj}=\omega^{-(kj\text{~{}mod~{}}n)}$ . Thus, in this case collectively, we can express the joint state after phase-shifting as $\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\omega^{-kj}\ket{k\cdot\vec{\alpha}}$ .

Now we derive equation (8). We have

	$\displaystyle P_{0}\otimes\dots\otimes P_{n-1}\left(\frac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}\right)\mapsto$
	$\displaystyle\frac{1}{\sqrt{n}}\omega^{-\frac{n-1}{2}}\ket{0\cdot\vec{\alpha}}+\frac{1}{\sqrt{n}}\sum_{k=1}^{n-1}\omega^{-\sum_{j=0}^{n-1}\frac{1}{n}(kj\text{ mod }n)}\ket{k\cdot\vec{\alpha}}$
	$\displaystyle\overset{(a)}{=}\frac{1}{\sqrt{n}}\omega^{-\frac{n-1}{2}}\ket{0\cdot\vec{\alpha}}+\frac{1}{\sqrt{n}}\sum_{k=1}^{n-1}\omega^{-\frac{1}{n}(\sum_{j=0}^{n-1}j)}\ket{k\cdot\vec{\alpha}}$
	$\displaystyle=\frac{1}{\sqrt{n}}\omega^{-\frac{n-1}{2}}\ket{0\cdot\vec{\alpha}}+\frac{1}{\sqrt{n}}\sum_{k=1}^{n-1}\omega^{-\frac{1}{n}[\frac{n(n-1)}{2}]}\ket{k\cdot\vec{\alpha}}$
	$\displaystyle=\frac{1}{\sqrt{n}}\omega^{-\frac{n-1}{2}}\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}$

where $(a)$ follows from the fact that $\{kj\text{ mod }n|j\in\{0,\dots,n-1\}\}=\{0,\dots,n-1\}$ for $k\neq 0$ . It follows that

	$\displaystyle QFT^{\otimes n}\left(\frac{1}{\sqrt{n}}\omega^{-\frac{n-1}{2}}\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}\right)$
	$\displaystyle=\frac{1}{\sqrt{n}}\omega^{-\frac{n-1}{2}}QFT^{\otimes n}\left(\sum_{k=0}^{n-1}\ket{k\cdot\vec{\alpha}}\right)$
	$\displaystyle=\frac{1}{\sqrt{n}}\omega^{-\frac{n-1}{2}}\sum_{\vec{k}\in\mathbb{F}_{n}^{n}}a_{\vec{k}}\ket{\vec{k}}.$

Appendix C Proof of Theorem 2

For $a,b\in\mathbb{F}_{n}$ , we define $M_{a,b}=\{i\in[m]|[x^{1}_{i},\dots,x^{n}_{i}]^{T}=a[1,\dots,1]^{T}+b[0,1,\dots,n-1]^{T}\}$ and $m_{a,b}=|M_{a,b}|$ . Since the promise ensures that, for each $i\in\{1,\dots,m\}$ , there exists $a,b\in\mathbb{F}_{n}$ s.t. $[x^{1}_{i},\dots,x^{n}_{i}]^{T}=a[1,\dots,1]^{T}+b[0,1,\dots,n-1]^{T}\in\mathbb{F}_{n}^{n}$ , we have that $\{M_{a,b}|a,b\in\mathbb{F}_{n}\}$ forms a partition of the set $\{1,\dots,m\}.$

When $i\in M_{a,0}$ , i.e. $[x^{1}_{i},\dots,x^{n}_{i}]^{T}=a[1,\dots,1]^{T}$ , we have

\prod_{p=1}^{n}x_{i}^{p}=a^{n}=a.

(13)

Otherwise, we have $i\in M_{a,b}$ for some $b\neq 0$ , so $[x^{1}_{i},\dots,x^{n}_{i}]^{T}=a[1,\dots,1]^{T}+b[0,\dots,n-1]^{T}$ . Then,

\prod_{p=1}^{n}x_{i}^{p}=\prod_{i=0}^{n-1}(a+i\cdot b)=0.

(14)

By (13) and (14), if $i\in M_{a,b}$ , then $\prod_{p=1}^{n}x_{i}^{p}=\delta_{0b}\cdot a.$ Define

\mathds{1}((x^{1}_{i},\dots,x^{n}_{i}),M_{a,b})=\begin{cases}1,&i\in M_{a,b}\\ 0,&\text{otherwise},\end{cases}

i.e., it is the indicator of $i\in M_{a,b}$ . Since $i\in M_{a,b}$ for exactly one choice of $(a,b)$ , it follows that

\prod_{p=1}^{n}x_{i}^{p}=\delta_{0b}\cdot a=\sum_{a,b=0}^{n-1}\delta_{0b}\cdot a\cdot\mathds{1}((x^{1}_{i},\dots,x^{n}_{i}),M_{a,b}).

(15)

We have

\begin{split}&\sum_{i=1}^{m}\prod_{p=1}^{n}x_{i}^{p}\\ \overset{\text{(*)}}{=}&\sum_{i=1}^{m}\sum_{a,b=0}^{n-1}a\cdot\delta_{0b}\cdot\mathds{1}((x^{1}_{i},\dots,x^{n}_{i}),M_{a,b})\\ =&\sum_{a,b=0}^{n-1}\sum_{i=1}^{m}a\cdot\delta_{0b}\cdot\mathds{1}((x^{1}_{i},\dots,x^{n}_{i}),M_{a,b})\\ =&\sum_{a,b=0}^{n-1}a\cdot\delta_{0b}\cdot m_{a,b}=\sum_{a=0}^{n-1}a\cdot m_{a,0}\text{ (mod}\ n\text{)}.\end{split}

(16)

Here, (*) follows from (15). Our next step is to show $\sum_{a=0}^{n-1}am_{a,0}=W/n\text{ (mod}\ n\text{)}$ ; $W$ is defined in Alg. 2.

Suppose $i\in M_{a,b}$ , then $(x^{1}_{i},\dots,x^{n}_{i})=a(1,\dots,1)+b(0,\dots,n-1)$ . For the $p-$ th player, $a+(p-1)b$ is the value of the $i-$ th coordinate of her vector $\vec{x}^{p}$ . For a fixed $k\in\mathbb{F}_{n}$ , the set of $(a,b)$ s.t. $a+(p-1)b=k$ is $\{(k,0),(k+p-1,-1),(k+2p-2,-2),\dots,(k+(n-1)(p-1),-(n-1)\}$ . It follows that $\forall p\in\{1,\dots,n\},k\in\mathbb{F}_{n},$

\beta_{k}^{p}=\sum_{i=0}^{n-1}m_{k+i(p-1),-i}.

(17)

Consider $\sum_{i=0}^{n-1}\sum_{p=1}^{n}m_{k+i(p-1),-i}$ . When $i=0$ , $m_{k+i(p-1),-i}$ is counted $n$ times. Denote $S=\{(0,0),\dots,(n-1,0)\}.$ For arbitrary $[x,y]^{T}\in\mathbb{F}_{n}^{2}-S$ , the equation

\displaystyle\begin{bmatrix}k+i(p-1)\\ -i\end{bmatrix}

\displaystyle=\begin{bmatrix}x\\ y\end{bmatrix}

has a unique solution given by

	$\displaystyle i$	$\displaystyle=-y,\text{~{}and}$
	$\displaystyle p$	$\displaystyle=\frac{y-x+k}{y}.$

Thus, we have

\mathbb{F}_{n}^{2}-S=\{(k+i(p-1),-i~{}|~{}p\in\{1,\dots,n\},i\in\{1,\dots,n-1\}\}.

Therefore, when $i\neq 0$ , $m_{k+i(p-1),-i}$ is counted exactly once. It follows that

\begin{split}&\sum_{p=1}^{n}\sum_{i=0}^{n-1}m_{k+i(p-1),-i}\\ =&\sum_{p=1}^{n}\sum_{i=1}^{n-1}m_{k+i(p-1),-i}+\sum_{p=1}^{n}m_{k+0(p-1),0}\\ =&\sum_{a,b\in\mathbb{F}_{n}^{2}-S}m_{a,b}+n\cdot m_{k,0}.\end{split}

(18)

Now we have

	$\displaystyle\sum_{p=1}^{n}\sum_{k=1}^{n-1}k\cdot\beta_{k}^{p}\overset{\text{\eqref{relation4}}}{=}$	$\displaystyle\sum_{k=1}^{n-1}k\sum_{p=1}^{n}\sum_{i=0}^{n-1}m_{k+i\cdot(p-1),-i}$
	$\displaystyle\overset{\text{\eqref{relation2}}}{=}$	$\displaystyle\sum_{k=1}^{n-1}k\Big{[}\sum_{a,b\in\mathbb{F}_{n}^{2}-S}m_{a,b}+n\cdot m_{k,0}\Big{]}$
	$\displaystyle=$	$\displaystyle\frac{n^{2}-n}{2}\sum_{a,b\in\mathbb{F}_{n}^{2}-S}m_{a,b}+n\sum_{k=1}^{n-1}k\cdot m_{k,0}$
	$\displaystyle\text{and }\sum_{p=1}^{n}\beta_{0}^{p}\overset{\text{\eqref{relation4}}}{=}$	$\displaystyle\sum_{p=1}^{n}\sum_{i=0}^{n-1}m_{i\cdot(p-1),-i}\overset{\text{\eqref{relation2}}}{=}\sum_{a,b\in\mathbb{F}_{n}^{2}-S}m_{a,b}+n\cdot m_{0,0}.$

Note $n>2$ is prime, so $n-1$ is divisible by 2. It follows that

	$\displaystyle W=$	$\displaystyle\sum_{p=1}^{n}\sum_{k=1}^{n-1}k\cdot\beta_{k}^{p}+\frac{n^{2}-n}{2}\cdot(n-1)\sum_{p=1}^{n}\beta_{0}^{p}$
	$\displaystyle=$	$\displaystyle\frac{n^{2}-n}{2}\sum_{a,b\in\mathbb{F}_{n}^{2}-S}m_{a,b}+n\sum_{k=1}^{n-1}k\cdot m_{k,0}$
		$\displaystyle+\frac{n^{2}-n}{2}\cdot(n-1)\Big{[}\sum_{a,b\in\mathbb{F}_{n}^{2}-S}m_{a,b}+n\cdot m_{0,0}\Big{]}$
	$\displaystyle=$	$\displaystyle n\sum_{k=1}^{n-1}k\cdot m_{k,0}+n^{2}\cdot\frac{(n-1)}{2}\sum_{a,b\in\mathbb{F}_{n}^{2}-S}m_{a,b}$
		$\displaystyle+n^{2}\cdot\frac{(n-1)^{2}}{2}\cdot m_{0,0}$
	$\displaystyle=$	$\displaystyle n\sum_{k=0}^{n-1}k\cdot m_{k,0}\text{ (mod}\ n^{2}\text{)}.$

Divide both sides by $n$ and we get $W/n=\sum_{k=1}^{n-1}km_{k,0}\text{ (mod}\ n\text{)}$ . Now we are done because of (16).

Appendix D Proof of theorem 3

Suppose that we have a protocol that computes the function with zero-error. Our protocol is deterministic, so, for each $\vec{x}^{p}\in\mathbb{F}_{n}^{m}$ , it associates exactly one label $\hat{c}$ such that the $p$ -th player sends $\hat{c}$ if his vector is $\vec{x}^{p}$ . We set $I_{\vec{x}^{p},\hat{c}}=1$ and $I_{\vec{x}^{p},c}=0$ for all $c\neq\hat{c}.$ Therefore, $I_{\vec{x}^{p},c}\in\{0,1\}$ and $\sum_{c\in[l]}I_{\vec{x}^{p},c}=1$ are satisfied for all choice of $\vec{x}^{p},c$ .

Next, suppose we have that $(\vec{x}^{1},\dots,\vec{x}^{n})\sim_{GIP}(\vec{z}^{1},\dots,\vec{z}^{n})$ . Furthermore, assume that the $p$ -th player sends $s^{p}/t^{p}$ for $\vec{x}^{p}/\vec{z}^{p}$ for $p=2,\dots,n$ . This implies that $\prod_{p=2}^{n}I_{\vec{x}^{p},s^{p}}=1$ and that $\prod_{p=2}^{n}I_{\vec{z}^{p},t^{p}}=1$ . In addition, note that $\exists~{}p$ such that $s^{p}\neq t^{p}$ as for these sequences, the symbols transmitted from users $2,\dots,n$ have to be distinct.

Thus we have

\displaystyle 1=|\prod_{p=2}^{n}I_{\vec{x}^{p},s^{p}}-\prod_{p=2}^{n}I_{\vec{z}^{p},s^{p}}|=|\prod_{p=2}^{n}I_{\vec{x}^{p},t^{p}}-\prod_{p=2}^{n}I_{\vec{z}^{p},t^{p}}|

and consequently

	$\displaystyle\sum_{c_{2}\in[l^{2}],\dots,c_{n}\in[l^{n}]}\|\prod_{p=2}^{n}I_{\vec{x}^{p},c^{p}}-\prod_{p=2}^{n}I_{\vec{z}^{p},c^{p}}\|=$
	$\displaystyle\|\prod_{p=2}^{n}I_{\vec{x}^{p},\hat{s}^{p}}-\prod_{p=2}^{n}I_{\vec{z}^{p},\hat{s}^{p}}\|+\|\prod_{p=2}^{n}I_{\vec{x}^{p},\hat{t}^{p}}-\prod_{p=2}^{n}I_{\vec{z}^{p},\hat{t}^{p}}\|=2.$

Therefore, the third constraint is satisfied.

Conversely, if we have $\{I_{\vec{x}^{p},c}|\vec{x}^{p}\in\mathbb{F}_{n}^{m},c\in[l^{p}]\}$ that satisfy the constraints of the ILP, then we construct a classical protocol as follows. Suppose $p$ -th player has vector $\vec{x^{p}}$ for $p\in\{1,\dots,n\}$ . Since there exists exactly one $s^{p}\in[l^{p}]$ s.t. $I_{x^{p},s^{p}}=1$ , then $p$ sends $s^{p}$ to Alice for $p\in\{2,\dots,n\}$ . When Alice receives the symbols $s^{p},p=2,\dots,n$ from the other players she picks arbitrary $\{\vec{y}^{p}\in\mathbb{F}_{n}^{m}\}_{i=2}^{n}$ s.t. $(\vec{x}^{1},\vec{y}^{2},\dots,\vec{y}^{n})$ satisfies the promise and $\forall p\in\{2,\dots,n\},I_{\vec{y}^{p},s^{p}}=1$ .Then she outputs $f(\vec{x}^{1},\vec{y}^{2},\dots,\vec{y}^{n})$ . In what follows we show that

GIP(\vec{x}^{1},\vec{y}^{2},\dots,\vec{y}^{n})=GIP(\vec{x}^{1},\vec{x}^{2},\dots,\vec{x}^{n}).

To see this assume otherwise. Then, we have $GIP(\vec{x}^{1},\vec{y}^{2},\dots,\vec{y}^{n})\neq GIP(\vec{x}^{1},\vec{x}^{2},\dots,\vec{x}^{n}).$ It follows that

(\vec{x}^{1},\vec{x}^{2},\dots,\vec{x}^{n})\sim_{GIP}(\vec{x}^{1},\vec{y}^{2},\dots,\vec{y}^{n}).

Owing to the third constraint, we have that

\sum_{c^{2},\dots,c^{n}\in[l]}|\prod_{p=2}^{n}I_{\vec{x}^{p},c^{p}}-\prod_{p=2}^{n}I_{\vec{y}^{p},c^{p}}|=2.

However, we have that $I_{\vec{x}^{i},s^{i}}=I_{\vec{y}^{i},s^{i}}=1$ for all $i\in\{2,\dots,n\}$ . By the first and second constraint, we have that $I_{\vec{x}^{i},c^{i}}=I_{\vec{y}^{i},c^{i}}=0$ for all $i\in\{2,\dots,n\}$ and $c^{i}\neq s^{i}$ . Therefore,

\sum_{c^{2},\dots,c^{n}\in[l]}|\prod_{p=2}^{n}I_{\vec{x}^{p},c^{p}}-\prod_{p=2}^{n}I_{\vec{y}^{p},c^{p}}|=0.

This gives the desired contradiction.

Appendix E Linearizing constraints in the integer programming problem

One issue with the optimization problem in (10) is that the third constraint has multiple absolute value and products of variables. Here we transform the constraints and add extra variable in (10) to get the desired ILP.

Our first step is to introduce auxiliary 0-1 variables that correspond to the product of other 0-1 variables. For instance, it can be verified that we can handle $\prod_{i=1}^{k}x_{i}=x^{\prime}$ as follows.

	$\displaystyle x^{\prime}$	$\displaystyle\leq x_{i},\text{~{}for~{}}i=1,\dots,k$		(19)
	$\displaystyle x^{\prime}$	$\displaystyle\geq\sum_{i=1}^{k}x_{i}-(k-1).$		(20)

As a first step we introduce such auxiliary variable for all terms that involve products of our indicator function in (10).

Following this step, we are left with handling constraints that involve sums of absolute values of differences. For this step we show how to replace each absolute value difference by another auxiliary variable. In particular, we can replace $|x-y|$ by $z$ as follows.

\displaystyle|x-y|=|x-y|^{2}=x^{2}+y^{2}-2xy=x+y-2xy

where the last step follows from the fact that the variables are of type $0-1$ . The product term $2xy$ can be linearized as described previously. Following these steps, all constraints in the integer programming problem are linear.