Abstract

This paper gives a nearly tight characterization of the quantum communication complexity of permutation-invariant Boolean functions. With such a characterization, we show that the quantum and randomized communication complexity of permutation-invariant Boolean functions are quadratically equivalent (up to a polylogarithmic factor of the input size). Our results extend a recent line of research regarding query complexity to communication complexity, showing symmetry prevents exponential quantum speedups. Furthermore, we show that the Log-rank Conjecture holds for any non-trivial total permutation-invariant Boolean function. Moreover, we establish a relationship between the quantum/classical communication complexity and the approximate rank of permutation-invariant Boolean functions. This implies the correctness of the Log-approximate-rank Conjecture for permutation-invariant Boolean functions in both randomized and quantum settings (up to a polylogarithmic factor of the input size).

1 Introduction↩︎

Exploring quantum advantages is a key issue in the realm of quantum computing. Numerous work focuses on analyzing and characterizing quantum advantages, such as [1]–[6]. It is known that quantum computers can demonstrate a potential exponential speedup compared with classical computers, such as Simon’s problem [7] and integer factoring [8], for which quantum algorithms exploit the internal structures of the problems (e.g. fast Fourier transform). However, for some highly unstructured problems, such as the unstructured search [9] and collision problems [10], quantum speedups are at most polynomial. In light of the aforementioned phenomenon, Aaronson and Ambainis [11] asked: How much structure is needed for huge quantum speedups?

Regarding the above question, there are two major directions to explore the structure needed for quantum speedups in the query model, a complexity model commonly used to describe quantum advantages. On the one hand, Aaronson and Ambainis [11] conjectured the acceptance probability of a quantum query algorithm to compute a Boolean function can be approximated by a classical deterministic algorithm with only a polynomial increase in the number of queries, which is one of most important conjecture in the field of Boolean analysis. On the other hand, Watrous conjectured that quantum and randomized query complexities are polynomially equivalent for any permutation-invariant function [11]. Along this direction, Aaronson and Ambainis [11] initiated the study on the quantum speedups of permutation-invariant functions for query complexity. They demonstrated that any (partial) function that is invariant under full symmetry does not exhibit exponential quantum speedups, thereby resolving the Watrous conjecture. Furthermore, Chailloux [12] expanded upon their work by providing a tighter bound and removing a technical constraint. Recently, Ben-David, Childs, Gilyén, Kretschmer, Podder, and Wang [13] further proved that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. All the above results demonstrated that symmetries break exponential quantum speedups in the query model.

The study of the roles of “structure” in quantum speedups has obtained considerable attention in the query model, which leads us to consider whether we can derive similar results in other computation models. In this paper, we study the communication complexity model introduced by Yao [14]. In the model of communication complexity, the inputs are distributed among two separated parties, each party is assumed to be computationally unbounded. The communication complexity studies the minimum number of bits the players need to exchange to achieve a task. In the model of quantum communication complexity [15], the players are allowed to exchange quantum messages. Quantum communication complexity comes to attention as it is also extensively used to demonstrate quantum advantages. Furthermore, while the exponential gap between quantum and classical communication models has been shown in many works [16]–[20], there are also some problems in communication models that demonstrate at most polynomial quantum speedups, such as the Set-Disjointness problem [21] and the (gap) Hamming-Distance-Problem [22]–[25]. Therefore, it is intriguing to consider how much structure is needed for significant quantum speedups in the communication complexity model. More specifically, would symmetry also break quantum exponential advantages in the communication complexity model? In this paper, we investigate a variant of the Watrous conjecture concerning the quantum and randomized communication complexities of permutation-invariant functions (2). Briefly, a permutation-invariant Boolean function is a function that is invariant under permutations of its inputs. We provide the formal definition below.

Definition 1 (Permutation-invariant (PI) functions [26]). A (total or partial) function \(f:\{0,1\}^n \times \{0,1\}^n \to \{-1,1,*\}\) is permutation-invariant if for all \(x,y \in \{0,1\}^n\), and every bijection \(\pi:\left \{ 0,...,n-1 \right \} \to \left \{ 0,...,n-1 \right \}\), \(f(x^{\pi}, y^{\pi}) = f(x,y)\), where \(x^\pi\) satisfies that \(x^{\pi}_{(i)} = x_{\pi(i)}\) for any \(i \in \left \{ 0,...,n-1 \right \}\).

Conjecture 2 (Communication complexity version of the Watrous Conjecture). Fix \(m \in \mathbb{Z^+}\). For any permutation-invariant function \(f:\left \{ 0,1,...,m \right \}^n \times \left \{ 0,1,...,m \right \}^n \rightarrow \left \{ -1,1,* \right \}\), \(R(f) \le Q(f)^{O(1)}\), where \(R(f)\) and \(Q(f)\) are the randomized and quantum communication complexities of \(f\), respectively.

Furthermore, we study the Log-rank Conjecture proposed by Lovasz and Saks [27], a long-standing open problem in communication complexity. Despite its difficulty on total functions [28]–[30], the conjecture has been shown for several subclasses of total permutation-invariant Boolean functions [31] and \(\mathrm{XOR}\)-symmetric functions [32]. Lee and Shraibman [33] further proposed the Log-approximate-rank Conjecture, stating that the randomized communication and the logarithm of the approximate rank of the input matrix are polynomially equivalent. However, this conjecture was later proven false [34], even for its quantum analogue [35], [36].

In this paper, we investigate both conjectures for permutation-invariant functions.

Conjecture 3 (Log-rank Conjecture for permutation-invariant functions). For any total permutation-invariant function \(f:\{0,1\}^n \times \{0,1\}^n \rightarrow \left \{ -1,1 \right \}\), \(D(f) \le \left ( \log\mathop{\mathrm{\mathrm{rank}}}(f) \right )^{O(1)}\), where \(\mathop{\mathrm{\mathrm{rank}}}(f)\) is the rank of the input matrix of \(f\).

Conjecture 4 (Log-Approximate-Rank Conjecture for permutation-invariant functions). For any (total or partial) permutation-invariant function \(f:\{0,1\}^n \times \{0,1\}^n \rightarrow \left \{ -1,1,* \right \}\), \(R(f) \le \left ( \log\mathop{\mathrm{\widetilde{rank}}}(f) \right )^{O(1)}\), where \(\mathop{\mathrm{\widetilde{rank}}}(f)\) is the approximate rank of the input matrix of \(f\) (see 2).

Conjecture 5 (Quantum Log-Approximate-Rank Conjecture for permutation-invariant functions). For any (total or partial) permutation-invariant function \(f:\{0,1\}^n \times \{0,1\}^n \rightarrow \left \{ -1,1,* \right \}\), \(Q(f) \le \left ( \log\mathop{\mathrm{\widetilde{rank}}}(f) \right )^{O(1)}\).

Definition 2 (Approximate rank). For matrix \(M \in \left \{ -1,1,* \right \}^{m \times n}\) (‘\(*\)’ means undefined entry) and \(0\leq \epsilon < 1\), we say a real matrix \(A\) approximates \(M\) with error \(\epsilon\) if:

\(|A_{i,j}-M_{i,j}|\leq \epsilon\) for any \(i \in [m], j\in [n]\) such that \(M_{i,j} \neq *\);
\(|A_{i,j}|\leq 1\) for all \(i\in [m], j\in [n]\).

Let \(\mathcal{M}_\epsilon\) be the set of all the real matrices that approximate \(M\) with error \(\epsilon\). The approximate rank of \(M\) with error \(\epsilon\), denoted by \(\mathop{\mathrm{\widetilde{rank}}}_{\epsilon}(M)\), is the smallest rank among all real matrices in \(\mathcal{M}_{\epsilon}\). If \(\epsilon = 2/3\), we abbreviate \(\mathop{\mathrm{\widetilde{rank}}}_{\epsilon}(M)\) as \(\mathop{\mathrm{\widetilde{rank}}}(M)\). For any (total or partial) Boolean function \(f:\{0,1\}^n\times\{0,1\}^n \rightarrow \{-1,1,*\}\), let \(\mathop{\mathrm{\widetilde{rank}}}(f)\mathrel{\vcenter{:}}= \mathop{\mathrm{\widetilde{rank}}}{\left ( M_f \right )}\), where \(M_f\) is the input matrix of \(f\).

1.1 Our Contribution↩︎

To study the communication complexity version of the Watrous conjecture, we start with permutation-invariant Boolean functions, which is an important step towards fully resolving 2. We show that for every permutation-invariant Boolean function, its classical communication complexity has at most a quasi-quadratic blowup compared to its quantum communication complexity ([th:main]). Thus, we cannot hope for significant quantum speedups of permutation-invariant Boolean functions. Additionally, [th:main] gives a nearly tight bound on the quantum communication complexity up to a polylogarithmic factor of the input size. Furthermore, we show that every non-trivial permutation-invariant Boolean function satisfies the Log-rank Conjecture in [th:logrank]. To resolve the (quantum) Log-Approximate-Rank Conjecture, we investigate the relationship between the quantum/classical communication complexities and the approximate rank of any permutation-invariant Boolean function in [th:PI95log95arank].

Consider a Boolean function \(f\). Let \(D(f),R(f),Q(f)\) be the deterministic communication complexity, randomized communication complexity, and quantum communication complexity of \(f\), respectively. Let \(\mathop{\mathrm{\mathrm{rank}}}\left ( f \right )\) and \(\mathop{\mathrm{\widetilde{rank}}}\left ( f \right )\) be the rank and approximate rank of \(f\). We summarize our results below.

theoremmaintheorem For any (total or partial) permutation-invariant function \(f:\{0,1\}^n \times \{0,1\}^n \to \{-1,1,*\}\) in Definition 1, the followings hold: \[\begin{align} &\Omega\left ( m\left ( f \right ) \right ) \le R(f) \le {O\left ( m\left ( f \right )^2\log^2 n \log\log n+\log n \right )},\\ &\Omega\left ( m\left ( f \right ) \right ) \le Q(f) \le {O\left ( m\left ( f \right )\log^2 n \log\log n+\log n \right )},\\ \end{align}\] where \(m(f)\) is a measure defined in Definition 9. Hence, \(R(f)\le {O(Q(f)^2\log^2 n \log\log n+\log n)}\) for any permutation-invariant function \(f\).

theoremlogrank For any non-trivial total permutation-invariant function \(f:\{0,1\}^n \times \{0,1\}^n \to \{-1,1\}\) in 1, we have \[D(f) = O\left ( \log^2\mathop{\mathrm{\mathrm{rank}}}\left ( f \right ) \right ).\] Here, we say \(f\) is non-trivial if \(f(x,y)\) does not only depend on \(|x|\) and \(|y|\).

theoremPIlogarank For any (total or partial) permutation-invariant function \(f:\{0,1\}^n \times \{0,1\}^n \to \{-1,1,*\}\) in 1, we have \[\begin{align} R(f) &= {O\left ( \log^2 \mathop{\mathrm{\widetilde{rank}}}\left ( f \right )\log^2n \log \log n+\log n \right )},\\ Q(f) &= {O\left ( \log \mathop{\mathrm{\widetilde{rank}}}\left ( f \right )\log^2 n \log\log n+\log n \right )}.\\ \end{align}\]

Remark 6. The relations between \(R(f),Q(f),\log\mathop{\mathrm{\widetilde{rank}}}(f)\) are tight in [th:main,th:PI_log_arank] (up to a polylogrithmic factor of the input size), since for the Set-Disjointness Problem, we have \(R(f) = \Omega(Q(f)^2)\) and \(Q(f) = \Omega\left ( \log\mathop{\mathrm{\widetilde{rank}}}(f) \right )\) [37].

The need for structure in quantum speedups has been studied in the query model extensively. Beals, Buhrman, Cleve, Mosca and de Wolf [38] demonstrated that there exists at most a polynomial quantum speedup for total Boolean functions in the query model. Moreover, Aaronson and Ambainis [11] established that partial symmetric functions also do not allow super-polynomial quantum speedups. Chailloux [12] further improved this result to a broader class of symmetric functions. Ben-David, Childs, Gilyén, Kretschmer, Podder and Wang [13] later analyzed the quantum advantage for functions that are symmetric under different group actions systematically. Ben-David [39] established a quantum and classical polynomial equivalence for a certain set of functions satisfying a specific symmetric promise. Aaronson and Ben-David [40] proved that if domain \(D\) satisfies \(D = \text{poly}(n)\), there are at most polynomial quantum speedups for computing an \(n\)-bit partial Boolean function.

In terms of communication complexity, there are a few results that imply the polynomial equivalence between quantum and classical communication complexity for several instances of permutation-invariant functions. Examples include \(\mathrm{AND}\)-symmetric functions [21], Hamming-Distance problem [22], [25], \(\mathrm{XOR}\)-symmetric functions [32]. While the above results characterized quantum advantage for a certain class of permutation-invariant Boolean functions, our work provides a systemic analysis of all permutation-invariant Boolean functions.

The study of the Log-rank Conjecture and the Log-Approximate-Rank Conjecture has a rich history. Here, we survey the results of the Log-rank Conjecture and the Log-Approximate-Rank Conjecture about permutation-invariant Boolean functions. Buhrman and de Wolf [31] verified the correctness of the Log-rank Conjecture for \(\mathrm{AND}\)-symmetric functions. Combining the results of Razborov [21], Sherstov [41] and Suruga [42], it is implied that the Log-Approximate-Rank Conjecture holds for \(\mathrm{AND}\)-symmetric functions both in the randomized and quantum settings. Moreover, Zhang and Shi [32] showed \(\mathrm{XOR}\)-symmetric functions satisfy the Log-Rank Conjecture. Chattopadhyayand and Mande [43] further proved that the Log-Approximate-Rank Conjecture holds for \(\mathrm{XOR}\)-symmetric functions for the first time.

1.3 Proof Techniques↩︎

In this section, we give a high-level technical overview of our main results.

First, we outline our approaches to obtain the lower bound on the quantum communication complexity, rank and approximate rank of permutation-invariant functions below:

Quantum communication complexity and approximate rank: In [th:main], we use the following two-step reduction (see Theorem 10 and 1): First, we reduce the lower bound of any permutation-invariant function to the lower bound of Exact Set-Inclusion Problem (\(\mathrm{ESetInc}\), a specific instance of permutation-invariant functions, 4). Second, we reduce the lower bound of the quantum communication complexity of \(\mathrm{ESetInc}\) to Paturis’s approximate degree of symmetric functions [44] by the pattern matrix method [41], a well-known method for lower bound analysis in quantum communication complexity. In [th:PI95log95arank], we use a similar method to prove the lower bound of approximate rank.
Rank: In [th:logrank], we reduce the lower bound of the rank of total permutation-invariant functions to the lower bound of the rank of some representative function instances, such as the Set-Disjointness Problem and the Equality Problem (see 4).

Moreover, we use the following methods to show the upper bounds on the communication complexity of permutation-invariant functions in the randomized, quantum, and deterministic models.

Randomized and quantum models: In [th:main], to prove the randomized upper bound for permutation-invariant functions, we first propose a randomized protocol to solve the Set-Inclusion problem (\(\mathrm{SetInc}\), 4) using a well-suited sampling method according to the parameters of \(\mathrm{SetInc}\) (see 3). Afterwards, we use this protocol as a subroutine to solve any permutation-invariant function based on binary search (see 11). Furthermore, to prove quantum upper bound, we use the quantum amplitude amplification technique [45], [46] to speed up the above randomized protocol to solve \(\mathrm{SetInc}\) (see [lemma:quantum95upper95bound95setinc]). It is also worth noting that in the quantum protocols, Alice and Bob do not need to share prior entanglement.
Deterministic model: In [th:logrank], to give an upper bound on the deterministic communication complexity of total permutation-invariant functions, we propose a deterministic protocol as follows (see [log95rank95upper95bound]): Alice and Bob first share the Hamming weight of their inputs, and decide who sends the input to the other party. The party that has all the information about inputs will output the answer.

1.4 Comparison with previous work↩︎

In previous work, Ghazi, Kamath and Sudan [26] considered the randomized communication complexity of permutation-invariant functions. For any permutation-invariant function \(f\), they introduced a complexity measure (denoted by \(M(f)\)) almost equivalent up to a fourth power of \(R(f)\), i.e., \[\begin{align} R(f) &= \Omega(M(f)),\\ R(f) &= O\left ( M(f)^4\log M(f)\log\log n \log\log\log n+\log n \right ). \end{align}\] In this paper, we propose a new complexity measure \(m(f)\), refining the argument in [26], which is almost quadratically equivalent to \(R(f)\) and tightly characterizes \(Q(f)\) up to a polylogarithmic factor of the input size (See [th:main]). This enables us to prove a quadratic equivalence between \(R(f)\) and \(Q(f)\) for all permutation-invariant functions \(f\).

Specifically, [26] first considered the Gap-Hamming-Distance Problem as 3, and then generalized the result to all permutation-invariant functions. In our work, we use a similar framework. The difference point is that, instead of the Gap-Hamming-Distance Problem, we consider the Set-Inclusion Problem as 4. It is worth noting that, while the two definition forms are different, the Set-Inclusion Problem is equivalent to the Gap-Hamming-Distance Problem, i.e., \(\mathsf{SetInc}_{a,b,c,g}^n\) is equivalent to \(\mathrm{GHD}_{a,b,a+b-2c,2g}^n\).

Definition 3 (Gap-Hamming-Distance Problem [26]). Fix \(n \in \mathbb{Z}^+\). Consider \(a,b\in \left \{ 1,...,n-1 \right \}\) and \(c-g,c+g\) are achievable Hamming distances of \(\Delta(x,y)\) when \(|x| = a, |y| = b\). The Gap-Hamming-Distance Problem \(\mathrm{GHD}^n_{a,b,c,g}:\left \{ 0,1 \right \}^n\times\left \{ 0,1 \right \}^n\rightarrow\left \{ -1,1,* \right \}\) is defined as the following partial function: \[\begin{align} &\mathrm{GHD}_{a, b, c, g}^{n}(x, y)\\ &\mathrel{\vcenter{:}}=\begin{cases} -1 &\text{if |x|=a,|y|=b and \Delta(x, y)\ge c+g}, \\ 1 &\text{if |x|=a,|y|=b and \Delta(x, y)\le c-g}, \\ * &\text{otherwise,} \end{cases} \end{align}\] where \(\Delta(x,y) = |\left \{ i \in \{0,1,...,n-1\}|x_i \neq y_i \right \}|\) is the Hamming distance between \(x\) and \(y\). Additionally, the Exact Gap-Hamming-Distance Problem \(\overline{\mathrm{GHD}}_{a, b, c, g}^{n}\) as follows. \[\begin{align} &\overline{\mathrm{GHD}}_{a, b, c, g}^{n}(x, y)\\ &\mathrel{\vcenter{:}}=\begin{cases} -1 &\text{if |x|=a,|y|=b and \Delta(x, y) = c-g}, \\ 1 &\text{if |x|=a,|y|=b and \Delta(x, y) = c+g}, \\ * &\text{otherwise.} \end{cases} \end{align}\]

Definition 4 (Set-Inclusion Problem). Fix \(n \in \mathbb{Z}^+\). Consider \(a,b\in \left \{ 1,...,n-1 \right \}\) and \(c-g,c+g\) are achievable Hamming weights of \(|x \land y|\) when \(|x| = a, |y| = b\). The Set-Inclusion Problem \(\mathrm{SetInc}^n_{a,b,c,g}:\left \{ 0,1 \right \}^n\times\left \{ 0,1 \right \}^n \rightarrow \left \{ -1,1,* \right \}\) is defined as the following partial function: \[\begin{align} &\mathrm{SetInc}_{a, b, c, g}^{n}(x, y)\\ &\mathrel{\vcenter{:}}=\begin{cases} -1 &\text{if |x|=a,|y|=b and |x \land y|\le c-g}, \\ 1 &\text{if |x|=a,|y|=b and |x \land y|\ge c+g}, \\ * &\text{otherwise.} \end{cases} \end{align}\] Additionally, the Exact Set-Inclusion Problem \(\mathrm{ESetInc}_{a, b, c, g}^{n}\) is defined as follows. \[\begin{align} &\mathrm{ESetInc}_{a, b, c, g}^{n}(x, y)\\ &\mathrel{\vcenter{:}}=\begin{cases} -1 &\text{if |x|=a,|y|=b and |x \land y|=c+g}, \\ 1 &\text{if |x|=a,|y|=b and |x \land y|=c-g}, \\ * &\text{otherwise.} \end{cases} \end{align}\]

Next, we show the difference between [26] and our result about the Set-Inclusion Problem (or Gap-Hamming-Distance Problem equivalently) from upper and lower bounds respectively.

For the upper bound, we designed different protocols from [26]. The details of our protocols are shown in 3.2. Moreover, the comparison of required communication costs is shown in 1.

For the lower bound, noting that the information complexity of the Unique-Set-Disjointness problem (\(\mathrm{UDISJ}\)) has been known [17], by a series of reductions, [26] showed the information complexity of \(\text{\sc UDisj}\) is a lower bound on the randomized communication complexity of the Exact Gap-Hamming-Distance Problem (See Section 3.3 in [26]). As a comparison, we use a different reduction method as Figure 1. =[] = [->]

Figure 1: Our reduction path for the lower bound of \mathsf{ESetInc}. — Figure 1: Our reduction path for the lower bound of \(\mathsf{ESetInc}\).

We first reduce the lower bound of the Exact Set-Inclusion Problem to some smaller instances with specific parameters (See [le:qcc_lowbound1,le:qcc_lowbound2]). Then we resolve the lower bound on the quantum communication complexity of the instance \(\mathrm{ESetInc}_{2k,k,l,1/2}^{4k}\) (See [lemma:partial]). Compared to [26], our reduction is more concise and direct.

For the communication complexity of \(\mathsf{SetInc}_{a,b,c,g}^n\) and \(\mathsf{ESetInc}_{a,b,c,g}^n\) (or \(\mathrm{GHD}_{a,b,a+b-2c,2g}\) and \(\overline{\mathrm{GHD}}_{a,b,a+b-2c,2g}\) equivalently), the comparison between [26] and our results are shown as 1, where \(n_1,n_2\) are the smallest two numbers in \(a-c,b-c,c,n-a-b+c\) and \(n_1 \le n_2\). It is worth noting that the results in [26] mainly depend on \(n_2/g\), while our results mainly depend on \(\sqrt{n_1n_2}/g\), which is a key factor in characterizing the quantum communication complexity of the Set-Inclusion Problem.

Table 1: The communication complexity of Set-Inclusion Problem
	Communication complexity
Ref. [26]	Randomized: \(O\left ( \left ( \frac{n_2}{g} \right )^2\log \frac{b}{g} \right )\) (\(a \le b \le \frac{n}{2}\))
Ref. [26]	Randomized: \(\Omega\left ( \max\left \{ \frac{n_2}{g}, \log \left ( \frac{\min\left \{ a+b-2c,n-a-b+2c \right \}}{g} \right ) \right \} \right )\)

Our work	Randomized: \(O\left ( \frac{n_1n_2}{g^2}\log n \right )\)
	Quantum: \(O\left ( \frac{\sqrt{n_1n_2}}{g}\log n \right )\)
	Quantum: \(\Omega\left ( \frac{\sqrt{n_1n_2}}{g} \right )\)

Remark 7. It is worth noting that for both quantum and randomized communication complexities, the upper bound of \(\mathsf{SetInc}_{a,b,c,g}^n\) is also the upper bound of \(\mathsf{ESetInc}_{a,b,c,g}^n\). Similarly, the lower bound of \(\mathsf{ESetInc}_{a,b,c,g}^n\) is also the lower bound of \(\mathsf{SetInc}_{a,b,c,g}^n\).

1.5 Organization↩︎

The remaining part of the paper is organized as follows. In 2, we state some notations and definitions used in this paper. In 3, we study the quantum and classical communication complexities of permutation-invariant functions. In 4, we show the Log-rank Conjecture holds for non-trivial total permutation-invariant functions. In 5, we study the Log-approximate Conjecture of permutation-invariant functions both in quantum and classical setting. Finally, a conclusion is made in 6. The appendices contain a section on extended preliminaries and omitted proofs.

2 Preliminaries↩︎

We introduce the notations and definitions used in this paper.

A multiset is a set with possibly repeating elements. We use \(\{[\cdot]\}\) to denote multiset and \(\{\cdot\}\) to denote standard set. Let \(S\) be a multiset, \(S\setminus \left \{ a \right \}\) removes one occurrence of \(a\) from \(S\) if there is any.

2.1 Boolean Functions↩︎

A partial function is a function defined only on a subset of its domain \(\mathcal{X}\). Formally, given a partial Boolean function \(f\colon \mathcal{X}\rightarrow \left \{ -1,1,* \right \}\), \(f(x)\) is undefined for \(x\in \mathcal{X}\) if \(f(x)=*\). A total function is a function that is defined on the entire domain. We say \(f\colon \mathcal{X}\rightarrow \left \{ -1,1,* \right \}\) is a subfunction of \(g\colon \mathcal{X}\rightarrow \left \{ -1,1,* \right \}\) if \(f(x) = g(x)\) or \(f(x) = *\) for any \(x \in \mathcal{X}\). For function \(f\colon \mathcal{X}\rightarrow \left \{ -1,1,* \right \}\), we define \(\overline{f}\colon \mathcal{X}\rightarrow \left \{ -1,1,* \right \}\) as \[\begin{align} \overline{f}(x)\mathrel{\vcenter{:}}= \begin{cases} -f(x) &\text{if f(x) = 1 or -1}, \\ * &\text{otherwise.} \end{cases} \end{align}\]

A Boolean predicate is a partial function that has domain \(\mathcal{X}= \left \{ 0,1,...,n \right \}\) for any \(n\in\mathbb{Z}^+\).

An incomplete Boolean matrix is a matrix with entries in \(\left \{ -1,1,* \right \}\), where undefined entries are filled with \(*\).

A submatrix is a matrix that is obtained by extracting certain rows and/or columns from a given matrix.

A half-integer is a number of the form \(n+1/2\), where \(n \in \mathbb{Z}\).

We introduce some Boolean operators as follows. For every \(n\in\mathbb{N}\) and \(x,y\in\left \{ 0,1 \right \}^n\):

\(\overline{x} \mathrel{\vcenter{:}}= (\overline{x_0},...,\overline{x_{n-1}}) = (1-x_0,...,1-x_{n-1})\);
\(x \land y \mathrel{\vcenter{:}}= (x_0 \land y_0,..., x_{n-1} \land y_{n-1})\); and
\(x \oplus y \mathrel{\vcenter{:}}= (x_0 \oplus y_0,..., x_{n-1} \oplus y_{n-1})\).

2.2 Communication Complexity Model↩︎

In the two-party communication model, Alice is given input \(x \in \{0,1\}^n\), and Bob is given input \(y \in \{0,1\}^n\). Then they aim to compute \(f(x,y)\) for some function \(f: \{0,1\}^n \times \{0,1\}^n \to \{-1,1,*\}\) by communication protocols while minimizing the amount of communication between them. In this paper, we consider the communication protocols in the deterministic, randomized, and quantum settings, respectively. Furthermore, the formal definitions of communication complexities are shown as follows.

Definition 5 (Deterministic Communication Complexity). For any function \(f: \set{0,1}^n\times \set{0,1}^n\rightarrow \{-1,1,*\}\), the deterministic communication complexity \(D(f)\) is defined as the cost of the deterministic protocol with the smallest cost, which computes \(f\) correctly on any input. In particular, \[D(f)=\min_{\substack{\Pi: \text{ deterministic protocol}\\ \forall x,y\in\{0,1\}^n \text{ s.t. } \Pi(x,y)=f(x,y)}}\mathrm{CC}\left ( \Pi \right ),\] where \(\mathrm{CC}\left ( \Pi \right )\) is the number of bits exchanged between two parties in the protocol \(\Pi\).

Definition 6 (Randomized Communication Complexity). For any function \(f: \set{0,1}^n\times \set{0,1}^n\rightarrow \{-1,1,*\}\), the randomized communication complexity \(R_{\epsilon}(f)\) is defined as the cost of the randomized protocol with the smallest cost, which has access to public randomness and computes f correctly on any input with probability at least \(1-\epsilon\). In particular, \[R_{\epsilon}(f)=\min_{\substack{\Pi: \text{ randomized protocol}\\ \forall x,y\in\{0,1\}^n \text{ s.t. } f(x,y)\neq *: \Pr[\Pi(x,y)]=f(x,y)]\ge 1-\epsilon}}\mathrm{CC}\left ( \Pi \right ),\] where \(\mathrm{CC}\left ( \Pi \right )\) is the number of bits exchanged between two parties in the protocol \(\Pi\).

Definition 7 (Quantum Communication Complexity). For any function \(f: \set{0,1}^n\times \set{0,1}^n\rightarrow \{-1,1,*\}\), the quantum communication complexity \(Q_{\epsilon}(f)\) is defined as the cost of the quantum protocol with the smallest cost, which is allowed to share prior entanglement and computes \(f\) correctly on any input with probability at least \(1-\epsilon\). In particular, \[Q_{\epsilon}(f)=\min_{\substack{\Pi: \text{ quantum protocol}\\ \forall x,y\in\{0,1\}^n \text{ s.t. } f(x,y)\neq *: \Pr[\Pi(x,y)]=f(x,y)]\ge 1-\epsilon}}\mathrm{CC}\left ( \Pi \right ),\] where \(\mathrm{CC}\left ( \Pi \right )\) is the number of qubits exchanged between two parties in the protocol \(\Pi\).

If a protocol succeeds with probability at least \(1-\epsilon\) on any input for some constant \(\epsilon < 1/2\), we say the protocol is with bounded error. If \(\epsilon = 1/3\), we abbreviate \(R_{\epsilon}(f),Q_{\epsilon}(f)\) as \(R(f),Q(f)\). It is a folklore conclusion that \(Q(f) \le R(f) \le D(f)\).

2.3 Permutation-Invariant Functions↩︎

By 1, any permutation-invariant function \(f:\left \{ 0,1 \right \}^n\times \left \{ 0,1 \right \}^n \rightarrow \left \{ -1,1,* \right \}\) depends only on \(|x|,|y|\) and \(|x \land y|\). Thus, for any \(a,b \in \left \{ 0,1,...,n \right \}\), there exists a function \(f_{a,b}\colon\left \{ \max\left \{ 0,a+b-n \right \},...,\min\left \{ a,b \right \} \right \} \rightarrow \left \{ -1,1{,*} \right \}\) such that \[\label{eq:hab} f_{a,b}(|x\land y|) = f(x,y),\tag{1}\] for any \(x,y \in \left \{ 0,1 \right \}^n\) satisfying \(|x| = a, |y| = b\). If there exist \(a,b \in [n]\) such that \(f_{a,b}\) is not a constant function, we say \(f\) is non-trivial.

The following definition of jumps partitions the domain of \(f_{a,b}\) into different intervals according to the transition of function values.

Definition 8 (Jump in \(f_{a,b}\)). For \(f_{a,b}\) defined as (1 ), consider \(c\) and \(g\) such that \(c+g,c-g\) are in the domain of \(f_{a,b}\), we say \((c,g)\) is a jump in \(f_{a,b}\) if all the following three conditions are satisfied:

\(f_{a,b}(c-g) \neq f_{a,b}(c+g)\);
\(f_{a,b}(c-g),f_{a,b}(c+g) \in \{-1,1\}\);
\(f_{a,b}(r)\) is undefined for \(c-g < r < c+g\).

Moreover, we define \(\mathscr{J}(f_{a,b})\) to be the set of all jumps in \(f_{a,b}\): \[\mathscr{J}\left(f_{a, b}\right) \mathrel{\vcenter{:}}=\left\{(c, g): \begin{array}{c} f_{a, b}(c-g), f_{a, b}(c+g) \in\{0,1\} \\ f_{a, b}(c-g) \neq f_{a, b}(c+g) \\ \forall i \in(c-g, c+g), f_{a, b}(i)=* \end{array}\right\}.\]

Remark 8. If \((c,g)\) is a jump in \(f_{a,b}\), then one of \(\mathsf{ESetInc}_{a,b,c,g}^n\) and \(\overline{\mathsf{ESetInc}}_{a,b,c,g}^n\) is a subfunction of \(f\). Additionally, Definition 8 is adapted from [26], while [26] gives the definition of jumps in \(h_{a,b}\), where \(h_{a,b}(\Delta(x,y)) = f(x,y)\) for permutaion-invariant function \(f\) and \(\Delta(x,y)\) is the Hamming distance between \(x\) and \(y\).

The following measure \(m(\cdot)\) is used to capture the quantum communication complexity of permutation-invariant functions, which is inspired by the complexity measure introduced in [26].

Definition 9 (Measure \(m(f)\)). Fix \(n\in\mathbb{Z^+}\). Let \(f:\{0,1\}^n \times \{0,1\}^n \to \{-1,1,*\}\) be a permutation-invariant function. If \(f\) is non-trivial, we define the measure \(m(f)\) of \(f\) as follows: \[m(f) \mathrel{\vcenter{:}}= \max_{\substack{a, b \in \left \{ 1,2,...,n-1 \right \} \\(c, g) \in \mathscr{J}\left(f_{a, b}\right) \\ n_1\mathrel{\vcenter{:}}= \min\{[a-c,c,b-c,n-a-b+c]\}\\n_2\mathrel{\vcenter{:}}= \min\left(\{[a-c,c,b-c,n-a-b+c]\}\setminus \left \{ n_1 \right \}\right) }} \frac{\sqrt{n_{1} n_{2}}}{g}.\] If \(f(x,y)\) only depends on \(|x|\) and \(|y|\), let \(m(f)\mathrel{\vcenter{:}}= 0\).

Remark 9. 9 is motivated by the quantum lower bound of the Exact Set-Inclusion Problem (See 1). That is, \(m(f)\) is the maximum of the quantum lower bound of all subfunctions of \(f\) that are isomorphic to an Exact Set-Inclusion Problem. As a comparison, a similar measure in [26] is defined as the maximum of the randomized lower bound of all subfunctions of \(f\) that are isomorphic to an Exact Gap-Hamming-Distance Problem.

3 Polynomial Equivalence on Communication Complexity of Permutation-Invariant Functions↩︎

To show the polynomial equivalence between quantum and randomized communication complexity of permutation-invariant functions as stated in [th:main], we prove the following two theorems (proved in [subsec:qcc_lowerbound,subsec:upper-bound], respectively) for the quantum and randomized communication complexities of permutation-invariant functions using the measure in 9.

Theorem 10 (Lower Bound). Fix \(n\in{\mathbb{Z}^+}\). Let \(f:\{0,1\}^n \times \{0,1\}^n \to \{-1,1,*\}\) be a permutation-invariant function. We have \[Q(f) = \Omega(m(f)).\]

Theorem 11 (Upper Bound). Fix \(n\in{\mathbb{Z}^+}\). Given a permutation-invariant function \(f:\{0,1\}^n \times \{0,1\}^n \to \{-1,1,*\}\) and the corresponding measure \(m(f)\) defined in Definition 9, we have

\(R(f) = O\left ( m(f)^2 \log^2 n\log\log n+\log n \right )\), and
\(Q(f) = O\left ( m(f) \log^2 n\log\log n+\log n \right )\).

3.1 Quantum Communication Complexity Lower Bound↩︎

In this section, our goal is to obtain a lower bound on the quantum communication complexity for permutation-invariant functions (10). Towards this end, we show that every permutation-invariant function \(f\) can be reduced to \(\mathrm{ESetInc}\) (defined in 4) and exhibit a lower bound for \(\mathrm{ESetInc}\) (1). Additionally, 1 implies if \(|x|=a,|y|=b\), then the cost to distinguish \(|x\land y| =c-g\) from \(|x\land y| =c+g\) is related to the smallest two numbers in \(\{[a-c,c,b-c,n-a-b+c]\}\).

Lemma 1. Fix \(n\in{\mathbb{Z^+}}\). Consider \(a,b \in \left \{ 1,...,n-1 \right \}\) and \(c-g,c+g\) are achievable Hamming weights of \(|x \land y|\) when \(|x| = a, |y| = b\). Let \(n_1\mathrel{\vcenter{:}}= \min\{[a-c,c,b-c,n-a-b+c]\}\) and \(n_2\mathrel{\vcenter{:}}= \min\left(\{[a-c,c,b-c,n-a-b+c]\}\setminus \left \{ n_1 \right \}\right)\). We have \[Q\left ( \mathrm{ESetInc}_{a,b,c,g}^n \right ) = \Omega\left ( \frac{\sqrt{n_1 n_2}}{g} \right ).\]

Proof of 10. By the definitions of \(f_{a,b}\) and jump of \(f_{a,b}\), any quantum protocol computing \(f\) can also compute \(\mathrm{ESetInc}^{n}_{a,b,c,g}\) for any \(a,b\) and any jump \((c,g) \in \mathscr{J}(f_{a,b})\). Therefore, given a jump \((c,g)\) for \(f_{a,b}\), the cost of computing \(\mathrm{ESetInc}^{n}_{a,b,c,g}\) lower bounds the cost of computing \(f\). By 1, we have \(Q(f) \ge \Omega\left ( \frac{\sqrt{n_1n_2}}{g} \right )\) for any jump \((c,g)\) in \(f_{a,b}\), where \(n_1, n_2\) are the smallest two numbers in \(\{[a-c,c,b-c,n-a-b+c]\}\). We conclude that \(Q(f) = \Omega\left ( m(f) \right )\) as desired. ◻

Now we remain to show 1. We note that the following two lemmas imply 1 directly, where [le:qcc95lowbound1] reduces the instance such that the parameter only relies on \(n_1,n_2,g\) and 2 gives the final lower bound.

lemmaqcclowerboundone Fix \(n\in{\mathbb{Z^+}}\). Consider \(a,b \in \left \{ 1,...,n-1 \right \}\) and \(c-g,c+g\) are achievable Hamming weights of \(|x \land y|\) when \(|x| = a, |y| = b\). Let \(n_1\mathrel{\vcenter{:}}= \min\{[a-c,c,b-c,n-a-b+c]\}\) and \(n_2\mathrel{\vcenter{:}}= \min\left(\{[a-c,c,b-c,n-a-b+c]\}\setminus \left \{ n_1 \right \}\right)\). We have \[Q\left ( \mathrm{ESetInc}_{a,b,c,g}^n \right ) \ge Q\left ( \mathrm{ESetInc}_{n_1+n_2,n_1+n_2,n_1,g}^{n_1+3n_2} \right ).\]

Lemma 2. Consider \(n_1,n_2,g\) such that \(n_1\le n_2\) and \(n_1-g,n_1+g\) are achievable Hamming weights of \(|x \land y|\) when \(|x| = |y| = n_1+n_2\), we have \[Q\left ( \mathrm{ESetInc}_{n_1+n_2,n_1+n_2,n_1,g}^{n_1+3n_2} \right ) = \Omega\left ( \frac{\sqrt{n_1 n_2}}{g} \right ).\]

We use the following two results on \(\mathsf{ESetInc}\) to show [le:qcc_lowbound1,le:qcc_lowbound2]. Specifically, [le:SecInc] is a variant of Lemma 4.1 in [25] and shows some reduction methods to the instances of the Exact Set-Inclusion Problem. [lemma:partial] is a generalization of Theorem 5 in [47] proved by pattern matrix method and shows the lower bound of a special instance of the Exact Set-Inclusion Problem. The proofs of [le:SecInc,lemma:partial] are given in Appendix 8.1.

lemmaQSecInc Fix \(n\in{\mathbb{Z^+}}\). Consider \(a,b \in \left \{ 1,...,n-1 \right \}\) and \(c-g,c+g\) are achievable Hamming weights of \(|x \land y|\) when \(|x| = a, |y| = b\). The following relations hold.

\(Q\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right ) \le Q\left ( \mathrm{ESetInc}_{a+\ell_1 + \ell_3, b + \ell_2 + \ell_3, c+\ell_3, g}^{n+\ell} \right )\) for integers \(\ell_1, \ell_2, \ell_3 \ge 0\) such that \(\ell_1 + \ell_2 + \ell_3 \le \ell\);
\(Q\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right ) = Q\left ( \mathrm{ESetInc}_{a, n-b, a-c, g}^{n} \right ) = Q\left ( \mathrm{ESetInc}_{n-a, b, b-c, g}^{n} \right )\);
\(Q\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right ) \le Q\left ( \mathrm{ESetInc}_{ka, kb, kc, kg}^{kn} \right )\), where \(k \ge 1\) is an integer.

lemmalemmapartial For every \(k\in{\mathbb{Z}^+}\), if \(l\) is a half-integer and \(0 < l \le k/2\), then \(Q\left ( \mathrm{ESetInc}^{4k}_{2k,k,l,1/2} \right ) = \Omega\left ( \sqrt{kl} \right )\).

Proof of [le:qcc95lowbound1]. Using the second item of [le:SecInc], we assume \(n_1 = c\) without loss of generality. Furthermore, we assume \(n_2 = a-c\). Let \(n_3 \mathrel{\vcenter{:}}= b-c, n_4 \mathrel{\vcenter{:}}= n-a-b+c\). Then \(n_3,n_4 \ge n_2 \ge n_1\) and \(n = n_1+n_2+n_3+n_4\). By Lemma [le:SecInc], we have \[\begin{align} &Q\left ( \mathrm{ESetInc}^{n_1 + 3n_2}_{n_1 + n_2, n_1 + n_2, n_1, g} \right )\\ &= Q\left ( \mathrm{ESetInc}^{n_1+n_2+n_2+n_2}_{n_1+n_2,n_1+n_2, n_1, g} \right ) \\ &\le Q\left ( \mathrm{ESetInc}^{n_1+n_2+n_3+n_4}_{n_1+n_2, n_1+n_3, n_1, g} \right ) \\ &= Q\left ( \mathrm{ESetInc}^n_{a,b,c,g} \right ). \end{align}\] If \(n_2 = b-c\) or \(n-a-b+c\), the argument is similar. ◻

Proof of 2. Let \(m_1 = \left\lfloor\frac{n_1}{2g}+\frac{1}{2}\right\rfloor-\frac{1}{2}\), i.e., \(m_1\) is the largest half-integer no more than \(\frac{n_1}{2g}\). Similarly, let \(m_2 = \left\lfloor\frac{n_2}{2g}+\frac{1}{2}\right\rfloor-\frac{1}{2}\). By [le:SecInc], we have \[\begin{align} &Q\left ( \mathrm{ESetInc}^{n_1+3n_2}_{n_1+n_2, n_1+n_2, n_1, g} \right ) \\ &\ge Q\left ( \mathrm{ESetInc}^{m_1+3m_2}_{m_1+m_2, m_1+m_2, m_1, 1/2} \right ). \end{align}\] Then we discuss the following three cases:

Case 1: \(m_1 = m_2 = 1/2\). We have \[\begin{align} &Q\left ( \mathrm{ESetInc}^{m_1+3m_2}_{m_1+m_2, m_1+m_2, m_1, 1/2} \right ) \\ &= \Omega\left ( 1 \right ) \\ &= \Omega\left ( \sqrt{m_1m_2} \right ). \end{align}\]
Case 2: \(m_2 \ge 3/2\) and \(m_1 = 1/2\). Let \(m'_2 \mathrel{\vcenter{:}}= \left\lfloor \frac{m_1+m_2}{2}\right\rfloor, l_1 \mathrel{\vcenter{:}}= m_1+m_2-2m'_2, l_2 \mathrel{\vcenter{:}}= m_1+m_2-m'_2, l \mathrel{\vcenter{:}}= m_1+3m_2-4m'_2\). Then, \[\begin{align} l-(l_1+l_2) = m_2-m_1-m'_2 \ge \frac{m_2+m_1}{2}-m'_2 \ge 0. \end{align}\] By [{le:SecInc},lemma:partial], we have \[\begin{align} &Q\left ( \mathrm{ESetInc}^{m_1+3m_2}_{m_1+m_2, m_1+m_2, m_1, 1/2} \right )\\ &= Q\left ( \mathrm{ESetInc}^{4m'_2+l}_{2m'_2+l_1, m'_2+l_2, m_1, 1/2} \right )\\ &\ge Q\left ( \mathrm{ESetInc}^{4m'_2}_{2m'_2, m'_2, m_1, 1/2} \right )\\ &= \Omega\left ( \sqrt{m_1m'_2} \right )\\ &= \Omega\left ( \sqrt{m_1m_2} \right ). \end{align}\]
Case 3: \(m_1 \ge 3/2\). Let \(m \mathrel{\vcenter{:}}= \left\lfloor \frac{m_1}{6}+\frac{m_2}{2}\right\rfloor, k \mathrel{\vcenter{:}}= \left\lfloor\frac{m_1}{3}+\frac{1}{2}\right\rfloor-\frac{1}{2}, l_3 \mathrel{\vcenter{:}}= m_1-k, l_1 \mathrel{\vcenter{:}}= \left ( m_1+m_2-2m \right )-l_3, l_2 \mathrel{\vcenter{:}}= \left ( m_1+m_2-m \right )-l_3, l \mathrel{\vcenter{:}}= m_1+3m_2-4m\). Since \(k\) is the largest half-integer smaller than \(\frac{m_1}{3}\), we have \(k \le \frac{1}{2}\cdot \left\lfloor \frac{2m_1}{3}\right\rfloor\). Since \(m_1 \le m_2\), we have \[\label{eq:m1m} k \le \frac{1}{2}\cdot\left\lfloor \frac{2m_1}{3}\right\rfloor \le \frac{1}{2} \cdot\left\lfloor \frac{m_1}{6}+\frac{m_2}{2}\right\rfloor \le \frac{m}{2},\tag{2}\] and \[\label{eq:ll95com} \begin{align} l-\left ( l_1+l_2+l_3 \right ) &= m_2-k-m \\ &\ge m_2-\frac{m_1}{3}-\left ( \frac{m_1}{6}+\frac{m_2}{2} \right ) \\ &\ge 0. \end{align}\tag{3}\] Then we have \[\begin{align} &Q\left ( \mathrm{ESetInc}^{m_1+3m_2}_{m_1+m_2, m_1+m_2, m_1, 1/2} \right ) \\ &= Q\left ( \mathrm{ESetInc}^{4m+l}_{2m+l_1+l_3, m+l_2+l_3, k+l_3, 1/2} \right ) \\ &\ge Q\left ( \mathrm{ESetInc}^{4m}_{2m, m, k, 1/2} \right ) \\&= \Omega\left ( \sqrt{mk} \right ) \\ &= \Omega\left ( \sqrt{m_1m_2} \right ), \end{align}\] where the inequality follows from [le:SecInc] and (3 ) and the second equality follows from [lemma:partial] and (2 ).

We conclude that \[\begin{align} &Q\left ( \mathrm{ESetInc}^{n_1+3n_2}_{n_1+n_2, n_1+n_2, n_1, g} \right ) \\ &\ge Q\left ( \mathrm{ESetInc}^{m_1+3m_2}_{m_1+m_2, m_1+m_2, m_1, 1/2} \right )\\ &= \Omega\left ( \frac{\sqrt{n_1n_2}}{g} \right ). \end{align}\] ◻

3.2 Randomized and Quantum Communication Complexity Upper Bound↩︎

We show upper bounds on the randomized and quantum communication complexities for permutation invariant functions (11). Similar to 3.1, we do so by giving upper bounds for a specific problem, \(\mathsf{SetInc}\) (see 4), and reducing permutation-invariant functions to \(\mathsf{SetInc}\). The intuition of our randomized protocol to compute \(\mathsf{SetInc}\) is as follows: Let \(s_1,s_2\) \((s_1 \le s_2)\) be the smallest two numbers in \(\{[|\overline{x} \land y|, |x \land y|, |\overline{x} \land y|, |\overline{x} \land \overline{y}|]\}\), and \(n_1,n_2\) \((n_1 \le n_2)\) be the smallest two numbers in \(\{[a-c,c,b-c,n-a-b+c]\}\). It is worth noting that \(|n_1-s_1| = |n_2-s_2| = g\). Let \(p = \frac{s_1}{s_1+s_2}\). Then we show \(\mathsf{SetInc}\) is equivalent to distinguish \(p \le \beta-\epsilon\) from \(p \ge\beta+\epsilon\) for some \(\beta = O\left ( \frac{n_1}{n_2} \right ), \epsilon = \Omega\left ( \frac{n_2}{g} \right )\). Depending on the value of \(n_1,n_2\), we use different sampling methods to estimate \(p\) with error \(\epsilon\). In the bounded-error randomized case, the communication cost is \(O\left ( \frac{\beta}{\epsilon^2}\log n \right ) = O\left ( \frac{n_1n_2}{g^2}\log n \right )\). Then we repeat \(O(\log \log n)\) times of protocol such that the failed probability is at most \(O(1/\log n)\). Finally, we use quantum amplitude amplification to speed up the randomized protocol.

The following two lemmas capture the randomized and quantum communication complexity for \(\mathsf{SetInc}\), respectively.

Lemma 3 (Randomized Upper Bound). Fix \(n,a,b\in{\mathbb{Z}^+}\). Consider \(c,g\) such that \(c+g,c-g\in{\mathbb{N}}\). Let \(n_1\mathrel{\vcenter{:}}= \min\{[a-c,c,b-c,n-a-b+c]\}\) and \(n_2\mathrel{\vcenter{:}}= \min\left(\{[a-c,c,b-c,n-a-b+c]\}\setminus \left \{ n_1 \right \}\right)\). For any input \(x,y\in \{0,1\}^n\) of \(\mathrm{SetInc}_{a, b, c, g}^{n}\), there exists a randomized communication protocol that computes \(\mathrm{SetInc}_{a, b, c, g}^{n}(x,y)\) using \(O\left ( \frac{n_1n_2}{g^2} \log n \log \log n \right )\) bits of communication with success probability at least \(1- 1/(6\log n)\).

lemmaQuanUpperSetInc Fix \(n,a,b\in{\mathbb{Z}^+}\). Consider \(c,g\) such that \(c+g,c-g\in{\mathbb{N}}\). Let \(n_1\mathrel{\vcenter{:}}= \min\{[a-c,c,b-c,n-a-b+c]\}\) and \(n_2\mathrel{\vcenter{:}}= \min\left(\{[a-c,c,b-c,n-a-b+c]\}\setminus \left \{ n_1 \right \}\right)\). For any input \(x,y\in \{0,1\}^n\) of \(\mathrm{SetInc}_{a, b, c, g}^{n}\), there exists a quantum communication protocol without prior entanglement that computes \(\mathrm{SetInc}_{a, b, c, g}^{n}(x,y)\) using \(O\left ( \frac{\sqrt{n_1n_2}}{g} \log n \log \log n \right )\) qubits of communication with success probability at least \(1- 1/(6\log n)\).

The proof of 3 is given at the end of this section, and we postpone the proof of [lemma:quantum95upper95bound95setinc] to 8.2.

Now we explain how to derive 11 from the lemmas above.

Proof of 11. We first present a randomized protocol to compute \(f\) based on binary search:

Alice and Bob exchange \(a\mathrel{\vcenter{:}}= |x|, b\mathrel{\vcenter{:}}= |y|\).
Alice and Bob both derive \(f_{a,b}\) such that \(f_{a,b}(|x \land y|) = f(x,y)\).
Let \(\mathscr{J}\left(f_{a, b}\right)=\{(c_i,g_i)\}_{i\in[k]}\) for some \(k\leq n\) be the set of jumps of \(f_{a,b}\) as in 8.
Alice and Bob use binary search to determine \(i\in \{0,1,...,k\}\) such that \(\lvert x\land y \rvert\in I_i\), where \(I_i\) is defined in (4 ).

We first discuss the communication complexity of the above protocol. The first step takes \(O(\log n)\) bits of communication. The fourth step costs \(O\left ( m(f)^2 \log^2 n\log\log n \right )\) bits of communication: For each \(i\in[k]\), Alice and Bob can determine whether \(|x \land y| \le c_i-g_i\) or \(|x \land y| \ge c_i+g_i\) by \(O(m(f)^2 \log n\log\log n)\) communication cost with a success probability of at least \(1-1/ \left ( 6\log n \right )\) by 3. Since binary search takes at most \(\lceil \log \left ( k+1 \right ) \rceil = O\left ( \log n \right )\) rounds, the total communication cost is \(O\left ( m(f)^2 \log^2 n\log\log n+\log n \right )\).

Now we argue for the correctness of the protocol. Notice that the set of jumps \(\mathscr{J}\left(f_{a, b}\right)\) invokes \(k+1\) intervals: \[\label{eq:Ik} \begin{align} I_0&\mathrel{\vcenter{:}}= [0,c_1-g_1],\\ I_1 &\mathrel{\vcenter{:}}= [c_1+g_1,c_2-g_2],\\ &\dots\\ I_{k-1} &\mathrel{\vcenter{:}}= [c_{k-1}+g_{k-1},c_k-g_k],\\ I_k &\mathrel{\vcenter{:}}= [c_k+g_k,n]. \end{align}\tag{4}\] In particular, the followings hold:

For every \(j\in[0,k]\) and \(z_1,z_2\in I_j\) such that \(f_{a,b}(z_1)\neq *\) and \(f_{a,b}(z_2)\neq *\), we have \(f_{a,b}(z_1)=f_{a,b}(z_2)\).
If \(z\notin I_j\) for any \(j\in[0,k]\), then \(f_{a,b}(z)=*\).

Therefore, Alice and Bob start from \(i = \lfloor (k+1)/2 \rfloor\) to determine whether \(|x \land y| \le c_i-g_i\) or \(|x \land y| \ge c_i+g_i\) with success probability of at least \(1-1/ \left ( 6\log n \right )\). Depending on the result, they repeat the same process similar to binary search to find the interval that \(|x \land y|\) falls in. After at most \(\lceil \log \left ( k+1 \right ) \rceil = O\left ( \log n \right )\) repetitions, there is only one remaining interval and they can determine \(f_{a,b}(|x \land y|)\). For \(n \ge 2\), the failure probability of the above protocol is at most \[\begin{align} 1-\left ( 1-\frac{1}{6\log n} \right )^{\lceil \log \left ( k+1 \right ) \rceil} &\le \frac{\lceil \log \left ( k+1 \right ) \rceil}{6 \log n} \\ &\le \frac{\lceil \log \left ( n+1 \right ) \rceil}{3 \log n^2} \\ &\le \frac{1}{3}. \end{align}\]

For the quantum case, Alice and Bob use the same protocol above, but we invoke [lemma:quantum95upper95bound95setinc] to analyze the communication complexity. ◻

Proof of 3. We rely on the following two claims to prove the lemma.

Fact 12 ([11]). Fix \(0 < \epsilon < \beta < 1\) such that \(\beta+\epsilon \le 1\). For a set \(S\), suppose there is a subset \(S'\) of \(S\) such that \(\frac{|S'|}{|S|} \le \beta-\epsilon\) or \(\frac{|S'|}{|S|} \ge \beta+\epsilon\). Suppose we can sample from \(S\) uniformly and ask whether the sample is in \(S'\). Then we can decide whether \(\frac{|S'|}{|S|} \le \beta-\epsilon\) or \(\frac{|S'|}{|S|} \ge \beta+\epsilon\) by \(O(\beta/\epsilon^2)\) samples, with success probability at least \(2/3\).

factunisample Suppose \(x,y \in \{0,1\}^n\) are the inputs of Alice and Bob such that \(|x| \neq |y|\). Alice and Bob can sample an element from \(S \mathrel{\vcenter{:}}= \left \{ i:x_i \neq y_i \right \}\) uniformly using \(O(\log n)\) bits of communication.

We refer interesting readers to 7.4 for the proof of [fact:sample95oplus]. Now we prove the lemma by casing on the values of \(n_1\) and \(n_2\).

Case 1: \(n_1 = c\) and \(n_2 = a-c\). According to 4, we have either \(\frac{|x \land y|}{|x|}\le \frac{c-g}{a}\) or \(\frac{|x \land y|}{|x|} \ge \frac{c+g}{a}\). Alice and Bob estimate \(\frac{|x \land y|}{|x|}\) as follows: Alice chooses an index \(i\) such that \(x_i = 1\) uniformly at random. Then Alice sends \(i\) to Bob, and Bob checks whether \(y_i = 1\). By 12, setting \(\beta \mathrel{\vcenter{:}}= \frac{c}{a}\), \(\epsilon \mathrel{\vcenter{:}}= \frac{g}{a}\), Alice and Bob can decide whether \(\frac{|x \land y|}{|x|}\le \frac{c-g}{a}\) or \(\frac{|x \land y|}{|x|} \ge \frac{c+g}{a}\) with bounded error using \(O\left ( \frac{ac}{g^2} \right ) = O\left ( \frac{n_1n_2}{g^2} \right )\) samples. Since \(|x| = a\), using \(O\left ( \frac{n_1n_2}{g^2} \log \log n \right )\) samples, they can decide whether \(|x \land y | \le c-g\) or \(|x \land y | \ge c+g\) with success probability at least \(1- 1/(6\log n)\) by error reduction. Thus, the communication complexity is \(O\left ( \frac{n_1n_2}{g^2} \log n\log \log n \right )\).
Case 2: \(n_1= a-c\) and \(n_2 = c\), or \(n_1= a-c\) and \(n_2 = c\), or \(n_1= c\) and \(n_2 =b-c\). A similar argument as in Case 1 applies.
Case 3: \(n_1 = c\) and \(n_2 = n-a-b+c\). Since \(n_1 \le n_2\), we have \(a+b \le n\). Then we consider the following two cases:
1. Case 3.1: \(a+b < n\). Let \(m \mathrel{\vcenter{:}}= n_1+n_2\), \(p \mathrel{\vcenter{:}}= \frac{|x \land y|}{|\overline{x} \oplus y|}\). Since \[\begin{align} |\overline{x} \oplus y| &= |x \land y| + |\overline{x} \land \overline{y}| \\ &= |x \land y|+ \left ( n-\left ( a+b-|x \land y| \right ) \right ) \\ &= n-(a+b)+2|x \land y|, \end{align}\] we have \[p= \frac{|x \land y|}{n-(a+b)+2|x\land y|} = \frac{1}{\frac{n-(a+b)}{|x \land y|}+2}.\] Notice that \(p\) is an increasing function of \(|x\land y|\). As a result, if \(|x \land y| \le c-g\), then \(p\le \frac{c-g}{m-2g}\); if \(|x \land y| \ge c+g\), then \(p\ge \frac{c+g}{m+2g}\). Let \[\begin{align} \beta & \mathrel{\vcenter{:}}= \frac{1}{2}\left ( \frac{c+g}{m+2g}+ \frac{c-g}{m-2g} \right ) \\ &= \frac{cm-2g^2}{m^2-4g^2} \\ &= O\left ( \frac{c}{m} \right ),\\ \end{align}\] \[\begin{align} \epsilon & \mathrel{\vcenter{:}}= \frac{1}{2}\left ( \frac{c+g}{m+2g}- \frac{c-g}{m-2g} \right ) \\ &= \frac{gm}{m^2-4g^2}\\ &= \Omega\left ( \frac{g}{m} \right ). \end{align}\] For any \(x \in \{0,1\}^n\), we let \(S_x \mathrel{\vcenter{:}}= \left \{ i:x_i = 1 \right \}\). By [fact:sample95oplus], Alice and Bob can sample \(i\) from \(S_{\overline{x} \oplus y}\) uniformly using \(O(\log n)\) bits communication. Since \(i \in S_{\overline{x} \oplus y}\), if \(x_i = y_i = 1\), then \(i \in S_{x \land y}\); if \(x_i = y_i = 0\), then \(i \notin S_{x\land y}\). By 12, using \(O\left ( \frac{\beta}{\epsilon^2} \right ) = O\left ( \frac{mc}{g^2} \right ) = O\left ( \frac{n_1n_2}{g^2} \right )\) samples, Alice and Bob can decide whether \(p \le \beta-\epsilon\) or \(p \ge \beta + \epsilon\) with bounded error. Equivalently, Alice and Bob can distinguish \(|x \land y | \le c-g\) from \(|x \land y | \ge c+g\) with bounded error. By error reduction, using \(O\left ( \frac{n_1n_2}{g^2} \log \log n \right )\) samples, they can decide whether \(|x \land y | \ge c-g\) or \(|x \land y | \le c+g\) with success probability at least \(1- 1/(6\log n)\). Thus, the communication complexity is \(O\left ( \frac{n_1n_2}{g^2} \log n\log \log n \right )\).
2. Case 3.2: \(a+b = n\). Alice and Bob generate new inputs \(x' = x0\) and \(y' = y0\) (pad a zero after the original input). Then we have \[\mathrm{SetInc}_{a, b, c, g}^{n}(x,y) = \mathrm{SetInc}_{a, b, c, g}^{n+1}(x',y').\] Since \(a+b < n+1\), Alice and Bob perform the protocol in Case 3.1 in the new inputs, and the complexity analysis is similar to Case 3.1.
Case 4: \(n_1= n-a-b+c\) and \(n_2 = c\), or \(n_1= a-c\) and \(n_2 = b-c\), or \(n_1= b-c\) and \(n_2 =a-c\). A similar argument as in Case 3 works.

◻

4 Log-Rank Conjecture for Permutation-Invariant Functions↩︎

[th:logrank] states the Log-rank Conjecture for permutation-invariant functions. We argue for the lower bound (4) and the upper bound ([log95rank95upper95bound]) separately.

Lemma 4 (Lower Bound). Fix \(n\in{\mathbb{Z}^+}\). Let \(f:\{0,1\}^n \times \{0,1\}^n \rightarrow \left \{ -1,1 \right \}\) be a non-trivial total permutation-invariant function. For every \(a,b \in [n]\) such that \(f_{a,b}\) is not a constant function, we have \[\log\mathop{\mathrm{\mathrm{rank}}}(f) = \Omega\left ( \max\left \{ \log n, \min\left \{ a,b,n-a,n-b \right \} \right \} \right ),\] where \(f_{a,b}\) satisfies \(f_{a,b}(|x \land y|) = f(x,y)\) for \(x,y \in \{0,1\}^n\).

Proof. We rely on the following two claims to prove the lemma. Two claims show the lower bound on the rank of some special functions respectively.

Fact 13 ([31], merging Corollary 6 with Lemma 4). Fix \(n\in{\mathbb{Z}^+}\). Let \(f:\{0,1\}^n \times \{0,1\}^n \rightarrow \left \{ -1,1 \right \}\) be defined as \(f(x,y) \mathrel{\vcenter{:}}= D(|x\land y|)\) for some predicate \(D: \left \{ 0,1,...,n \right \}\rightarrow \left \{ -1,1 \right \}\). If \(t\) is the smallest integer such that \(D(t) \neq D(t-1)\), then \(\log\mathop{\mathrm{\mathrm{rank}}}(f) = \Omega\left ( \log \left ( \sum_{i=t}^n \binom{n}{i} \right ) \right )\).

factDISJEQ Fix \(n\in\mathbb{Z}^+\). Let \(\mathcal{X},\mathcal{Y} \mathrel{\vcenter{:}}= \left \{ x\in \{0,1\}^{n}: |x| = k \right \}\), where \(k \le n/2\). Let \(\mathop{\mathrm{\mathsf{DISJ}}}_n^k:\mathcal{X} \times \mathcal{Y} \rightarrow \left \{ -1,1 \right \}\) and \(\mathop{\mathrm{\mathsf{EQ}}}_n^k:\mathcal{X} \times \mathcal{Y} \rightarrow \left \{ -1,1 \right \}\) be defined as \[\begin{align} \mathop{\mathrm{\mathsf{DISJ}}}_n^k(x,y) &\mathrel{\vcenter{:}}= \begin{cases} -1& \text{ if }|x \land y| = 0,\\ 1& \text{ if } |x \land y| \neq 0, \end{cases}\\ \mathop{\mathrm{\mathsf{EQ}}}_n^k(x,y) &\mathrel{\vcenter{:}}= \begin{cases} -1& \text{ if }x = y,\\ 1& \text{ if } x \neq y. \end{cases} \end{align}\] Then \(\mathop{\mathrm{\mathrm{rank}}}\left ( \mathop{\mathrm{\mathsf{DISJ}}}_n^k \right ) \ge \binom{n}{k}-1\) and \(\mathop{\mathrm{\mathrm{rank}}}\left ( \mathop{\mathrm{\mathsf{EQ}}}_n^k \right ) \ge \binom{n}{k}-1\).

We refer interesting readers to 7.2 for the proof of [disj95eq]. Now we prove the lemma by casing on the values of \(a\) and \(b\).

We can assume \(a \le b \le n/2\) without loss of generality because the cases where \(a > n/2\) or \(b > n/2\) can be obtained by flipping each bit of Alice or Bob’s input. Thus, it suffices to prove \(\log \mathop{\mathrm{\mathrm{rank}}}(f) = \Omega\left ( \max\left \{ \log n, a \right \} \right )\).

We prove the following two claims that directly lead to our result:

If \(a \le b \le n/2\) and \(a = o\left ( \log n \right )\), then \(\log \mathop{\mathrm{\mathrm{rank}}}(f) = \Omega\left ( \log n \right )\).
If \(a \le b \le n/2\) and \(a = \Omega\left ( \log n \right )\), then \(\log \mathop{\mathrm{\mathrm{rank}}}(f) = \Omega\left ( a \right )\).

We first prove [item:logrank-lower-bound-item1]. Suppose \(a \le b \le n/2\) and \(a = o\left ( \log n \right )\). Since \(f_{a,b}\) is not a constant function, there exists \(c \in [0,a)\) such that \(f_{a,b}(c) \neq f_{a,b}(c+1)\). Without loss of generality, we assume \(f_{a,b}(c) = -1\). Let \(n' \mathrel{\vcenter{:}}= n-(a+b-c-2)\). Since \(b \le n/2\) and \(c \le a = o(\log n)\), \(n' = n-(a+b-c-2) = \Omega\left ( n \right )\). Let \(\mathcal{X}\) and \(\mathcal{Y}\) be the set \(\left \{ x \in \{0,1\}^{n'}: |x| = 1 \right \}\). For any \(x\in\mathcal{X},y\in\mathcal{Y}\), \[\mathop{\mathrm{\mathsf{DISJ}}}_{n'}^1(x,y) = f_{a,b}(|x\land y|+c) = f(x',y'),\] where \[x' \mathrel{\vcenter{:}}= x\underbrace{1\cdots 1}_{c}\underbrace{1\cdots 1}_{a-c-1}\underbrace{0\cdots 0}_{b-c-1} \text{ and } y' \mathrel{\vcenter{:}}= y\underbrace{1\cdots 1}_{c}\underbrace{0\cdots 0}_{a-c-1}\underbrace{1\cdots 1}_{b-c-1}.\] Thus, \(\mathop{\mathrm{\mathsf{DISJ}}}_{n'}^1\) is a submatrix of \(f\). By [disj95eq], we have \[\log\mathop{\mathrm{\mathrm{rank}}}(f) \ge \log\mathop{\mathrm{\mathrm{rank}}}(\mathop{\mathrm{\mathsf{DISJ}}}_{n'}^1) \ge \log \left ( n'-1 \right ) = \Omega\left ( \log n \right ).\]

Now we prove [item:logrank-lower-bound-item2]. Suppose \(a,b \le n/2\) and \(\min\left \{ a,b \right \} = \Omega\left ( \log n \right )\), we consider the following three cases:

Case 1: There exists \(c \in [4a/7,3a/5)\) such that \(f_{a,b}(c) \neq f_{a,b}(c+1)\). Let \(k = \lfloor a/2 \rfloor\) and \(k' = \lceil a/2 \rceil\). Let \(g:\{0,1\}^k\times \{0,1\}^k \rightarrow \left \{ -1,1 \right \}\) be such that \(g(x,y) = f_{a,b}(|x' \land y'|)\) for every \(x,y\in \{0,1\}^k\), where \[\begin{align} x' &\mathrel{\vcenter{:}}= x \overline{x} \underbrace{0\cdots 0}_k \underbrace{1\cdots 1}_{k'}\underbrace{0\cdots 0}_{b-a}\underbrace{0\cdots 0}_{n-b-2k} \\ y' &\mathrel{\vcenter{:}}= y \underbrace{0\cdots 0}_k \overline{y} \underbrace{1\cdots 1}_{k'}\underbrace{1\cdots 1}_{b-a}\underbrace{0\cdots 0}_{n-b-2k}. \end{align}\] Observe that \(x',y'\in\{0,1\}^n\) and \(|x'|= a,|y'| =b\). Moreover, \(g(x,y) = D(|x \land y|)\) for predicate \(D: \left \{ 0,1,...,k \right \}\rightarrow \left \{ -1,1 \right \}\) such that \(D(z) = f_{a,b}(z+k')\) for every \(z \in [0,k]\). Thus, we have \(D(c-k') \neq D(c-k'+1)\). By 13, we have \[\log \mathop{\mathrm{\mathrm{rank}}}(g) = \Omega\left ( \log \left ( \sum_{i = c-k'+1}^k \binom{k}{i} \right ) \right ).\] Since \(c-k'+1 < 3a/5-\lceil a/2 \rceil+1 \le a/10 \le k/2\), we conclude \(\log \mathop{\mathrm{\mathrm{rank}}}(g) = \Omega(k) = \Omega(a)\).
Case 2: There exists \(c \in [0,4a/7)\) such that \(f_{a,b}(c) \neq f_{a,b}(c+1)\) and \(f_{a,b}\) is a constant function in the range \([c,3a/5)\). Without loss of generality, we assume \(f_{a,b}(c) = -1\). Let \(l \mathrel{\vcenter{:}}= \lfloor 3a/5 \rfloor\), \(l' \mathrel{\vcenter{:}}= \lceil 2a/5 \rfloor\), \(m \mathrel{\vcenter{:}}= n-(c+b-a+2l')\). Since \(a \le b \le n/2\) and \(c < 4a/7\), we have \[m = n-(c+b-a+2l') \ge 2a - 2l'-c = 2l-c \ge 2(l-c).\] Let \(\mathcal{X}\) and \(\mathcal{Y}\) be the set \(\left \{ x\in \{0,1\}^{m}: |x| = l-c \right \}\). For every \(x \in \mathcal{X}, y \in \mathcal{Y}\), we have \[\mathop{\mathrm{\mathsf{DISJ}}}_m^{l-c}(x,y) = f_{a,b}(|x' \land y'|) = f(x',y'),\] where \[\begin{align} x' &\mathrel{\vcenter{:}}= x\underbrace{1\cdots 1}_c \underbrace{0\cdots 0}_{b-a} \underbrace{0\cdots 0}_{l'}\underbrace{1\cdots 1}_{l'},\\ y' &\mathrel{\vcenter{:}}= y\underbrace{1\cdots 1}_c \underbrace{1\cdots 1}_{b-a }\underbrace{1\cdots 1}_{l'}\underbrace{0\cdots 0}_{l'}. \end{align}\] Thus, \(\mathop{\mathrm{\mathsf{DISJ}}}_m^{l-c}\) is a submatrix of \(f\). By [disj95eq], we have \[\begin{align} \log\mathop{\mathrm{\mathrm{rank}}}\left ( f \right ) &\ge \log\mathop{\mathrm{\mathrm{rank}}}(\mathop{\mathrm{\mathsf{DISJ}}}_m^{l-c})\\ &= \Omega\left ( \log \binom{m}{l-c} \right ) \\ &= \Omega\left ( l-c \right ) \\ &= \Omega\left ( a \right ). \end{align}\]
Case 3: There exists \(c \in [3a/5,a)\) such that \(f_{a,b}(c) \neq f_{a,b}(c+1)\) and \(f_{a,b}\) is a constant function in the range \([0,c)\). Without loss of generality, we assume \(f_{a,b}(c) = -1\). Since \(a \le b \le \frac{n}{2}\), we have \(n-b+c \ge a+c \ge 2c\). Let \(\mathcal{X}\) and \(\mathcal{Y}\) be the set \(\left \{ x\in \{0,1\}^{n-b+c}: |x| = c \right \}\). For every \(x \in \mathcal{X}, y \in \mathcal{Y}\), we have \[\mathop{\mathrm{\mathsf{EQ}}}_{n-b+c}^c(x,y) = f_{a,b}(|x' \land y'|) = f(x',y'),\] where \[x' \mathrel{\vcenter{:}}= x\underbrace{0\cdots 0}_{b-a} \underbrace{0\cdots 0}_{a-c} \text{ and } y' \mathrel{\vcenter{:}}= y\underbrace{1\cdots 1}_{b-a} \underbrace{0\cdots 0}_{a-c }.\] Thus, \(\mathop{\mathrm{\mathsf{EQ}}}_{n-b+c}^c\) is a submatrix of \(f\). By [disj95eq], we have \[\begin{align} \log\mathop{\mathrm{\mathrm{rank}}}\left ( f \right ) &\ge \log\mathop{\mathrm{\mathrm{rank}}}(\mathop{\mathrm{\mathsf{EQ}}}_{n-b+c}^c)\\ &= \Omega\left ( \log \binom{n-b+c}{c} \right ) \\ &= \Omega\left ( c \right ) \\ &= \Omega\left ( a \right ). \end{align}\]

◻

lemmaLogRankUpperBound Fix \(n\in{\mathbb{Z}^+}\). Let \(f:\{0,1\}^n \times \{0,1\}^n \rightarrow \left \{ -1,1 \right \}\) be a non-trivial total permutation-invariant function. Then \(D(f)\) is \[O\left ( \max_{a,b \in [n]:f_{a,b}\text{ is not constant}}\min\left \{ a,b,n-a,n-b \right \}\cdot \log n \right ),\] where \(f_{a,b}\) satisfies \(f_{a,b}(|x \land y|) = f(x,y))\) for \(x,y\in\{0,1\}^n\).

Proof. We give the following deterministic protocol. First, Alice and Bob exchange the values of \(|x|,|y|\) by \(O(\log n)\) bits. Suppose \(|x| = a, |y| = b\). i) If \(f_{a,b} = c\) for some constant number \(c \in \left \{ -1,1 \right \}\), then they output \(c\) directly. ii) If \(f_{a,b}\) is not a constant function, then they perform the following operations: if \(\binom{n}{a} \le \binom{n}{b}\), Alice sends \(x\) to Bob using \(\log \binom{n}{a}\) bits, and then Bob outputs \(f_{a,b}(x,y)\); otherwise, Bob sends \(y\) to Alice using \(\log\binom{n}{b}\) bits, and then Alice outputs \(f_{a,b}(x,y)\). In total, the communication cost of the protocol is \[\label{eq:cost} \log n +\max_{a,b:f_{a,b}\text{ is not constant}}\min\left \{ \log\binom{n}{a}, \log \binom{n}{b} \right \}\tag{5}\] on the worst case. If \(f_{a,b}\) is not a constant function, then \(0 < a,b < n\), and thus \[\label{eq:log95ineq} \log n = \log \binom{n}{1} \le \min\left \{ \log\binom{n}{a}, \log \binom{n}{b} \right \}.\tag{6}\] If \(a \le n/2\), then \(\log \binom{n}{a} \le a \log n\); if \(a > n/2\), then \(\log \binom{n}{a} = \log \binom{n}{n-a} \le (n-a) \log n\). Thus, \[\label{eq:log95min} \log\binom{n}{a} \le \min\left \{ a,n-a \right \}\cdot\log n.\tag{7}\] Combining (5 ), (6 ), and (7 ), the communication cost of the protocol is \[O\left ( \max_{a,b:f_{a,b}\text{ is not constant}}\min\left \{ a,b,n-a,n-b \right \}\cdot \log n \right ).\] ◻

5 Log-Approximate-Rank Conjecture for Permutation-Invariant Functions↩︎

We discuss [th:PI95log95arank]. In particular, we use the following two lemmas (proved in 9) to prove [th:PI95log95arank]. Additionally, we note that [lemma:rank_SecInc,lemma:lower_rank2] are variants of [le:SecInc,lemma:partial].

lemmarankSecInc Let \(n,a,b,c,g\in\mathbb{Z}^+\). The following relations hold:

\(\mathop{\mathrm{\widetilde{rank}}}\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right ) \le \mathop{\mathrm{\widetilde{rank}}}\left ( \mathrm{ESetInc}_{a+\ell_1 + \ell_3, b + \ell_2 + \ell_3, c+\ell_3, g}^{n+\ell} \right )\) for \(\ell_1, \ell_2, \ell_3 \ge 0\) such that \(\ell_1 + \ell_2 + \ell_3 \le \ell\);
\(\mathop{\mathrm{\widetilde{rank}}}\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right ) = \mathop{\mathrm{\widetilde{rank}}}\left ( \mathrm{ESetInc}_{a, n-b, a-c, g}^{n} \right ) = \mathop{\mathrm{\widetilde{rank}}}\left ( \mathrm{ESetInc}_{n-a, b, b-c, g}^{n} \right )\); and
\(\mathop{\mathrm{\widetilde{rank}}}\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right ) \le \mathop{\mathrm{\widetilde{rank}}}\left ( \mathrm{ESetInc}_{ka, kb, kc, kg}^{kn} \right )\) for \(k \ge 1\).

lemmalowerrank Fix \(k\in\mathbb{Z}\). Let \(l\) be a half-integer such that \(0 < l\le k/2\). We have \[\log\left ( \mathop{\mathrm{\widetilde{rank}}}\left ( \mathrm{ESetInc}^{4k}_{2k,k,l,1/2} \right ) \right ) = \Omega\left ( \sqrt{kl} \right ).\]

Proof sketch of [th:PI95log95arank]. We use a similar argument as in the proof of 1. Namely, for every \(a,b \in [n]\) and jump \((c,g) \in \mathscr{J}(f_{a,b})\), let \(n_1\mathrel{\vcenter{:}}= \min\{[a-c,c,b-c,n-a-b+c]\}\) and \(n_2\mathrel{\vcenter{:}}= \min\left(\{[a-c,c,b-c,n-a-b+c]\}\setminus \left \{ n_1 \right \}\right)\). We have \[\log \mathop{\mathrm{\widetilde{rank}}}\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right ) = \Omega\left ( \frac{\sqrt{n_1n_2}}{g} \right ).\] Since \(\mathrm{ESetInc}_{a, b, c, g}^{n}\) is a subfunction of \(f\), we have \[\log \mathop{\mathrm{\widetilde{rank}}}\left ( f \right ) = \Omega\left ( \max _{\substack{a, b \in[n] \\(c, g) \in \mathscr{J}\left(f_{a, b}\right)}} \frac{\sqrt{n_{1} n_{2}}}{g} \right ) = \Omega\left ( m(f) \right ).\] Combining 11 and the above equation, we have [th:PI95log95arank] as desired. ◻

6 Conclusion↩︎

This paper proves that the randomized communication complexity of permutation-invariant Boolean functions is at most quadratic of the quantum communication complexity (up to a polylogarithmic factor of the input size). Our results suggest that symmetries prevent exponential quantum speedups in communication complexity, extending the analogous research on query complexity. Furthermore, we prove that the Log-rank Conjecture and Log-approximate-rank Conjecture hold for non-trivial permutation-invariant Boolean functions (up to a polylogarithmic factor of the input size). There are some interesting problems to explore in the future.

Permutation invariance over higher alphabets. In this paper, the permutation-invariant function is a binary function. The interesting question is to generalize our results to larger alphabets, i.e., to permutation-invariant functions of the form \(f:\left \{ 0,1,...,m \right \}^n \times \left \{ 0,1,...,m \right \}^n \to \left \{ -1,1,* \right \}\) where \(m \in \mathbb{N}\) and \(m > 1\).
Generalized permutation invariance. It is possible to generalize our results for a larger class of symmetric functions. One candidate might be a class of functions that have graph-symmetric properties. Suppose \(\mathcal{G}_A, \mathcal{G}_B\) are two sets of \(n\)-vertices graphs, and \(G_n\) is a group that acts on the edges of an \(n\)-vertices graph and permutes them in a way that corresponds to relabeling the vertices of the underlying graph. A function \(f:\mathcal{G}_A \times \mathcal{G}_B \to \{-1,1,*\}\) is graph-symmetric if \(f(x,y)=f(x\circ \pi, y\circ \pi)\), where \(x \in \mathcal{G}_A, y\in\mathcal{G}_B\), and \(\pi \in G_n\).

Appendices Organization↩︎

The appendices are organized as follows. In Section 7, we give extended preliminaries. Moreover, the relation between the sections of appendices and the omitted proofs are given in 2.

Table 2: The list of omitted proofs.
Section	Omitted Proofs
7	Facts [fact:sample95oplus] and [disj95eq] in Section 2
8	[le:SecInc,lemma:partial,lemma:quantum_upper_bound_setinc] in Section 3
9	[lemma:rank_SecInc,lemma:lower_rank2] in Section 5
10	Communication complexity of Gap-Hamming-Distance

7 Extended Preliminaries↩︎

7.1 Pattern Matrix Method and Approximate Degree↩︎

Pattern matrix method [41] is a well-known method for lower bound analysis in quantum communication complexity. Fix \(k,n \in \mathbb{Z}\) and \(k\) divides \(n\). The set \([n]\) is partitioned into \(k\) blocks, each consisting of \(n/k\) elements. For the universal set \([n]\), let \(\mathcal{V}(n,k)\) be a family of subsets that have exactly one element in each block. Clearly, \(|\mathcal{V}(n,k)|=(n/k)^k\). Fix \(x\in\{0,1\}^n\) and \(V\in\mathcal{V}(n,k)\), let the projection of \(x\) onto \(V\) be defined as \(x|_V \mathrel{\vcenter{:}}= (x_{i_1},x_{i_2},\dots,x_{i_k}) \in \{0,1\}^k\), where \(i_1<i_2<\cdots< i_k\) are the elements of \(V\).

Definition 10 (Pattern matrix [41]). The \((n,k,f)\)-pattern matrix \(A\) for a function \(f \colon \{0,1\}^k\to \{-1,1,*\}\) is defined as \[A \mathrel{\vcenter{:}}= \Big[f(x|_V\oplus w)\Big]_{x\in\{0,1\}^n,\,(V,w)\in\mathcal{V}(n,k)\times\{0,1\}^k} \;.\]

Here, \(A\) is a matrix of size \(2^n\) by \((n/k)^k2^k\), where each row is indexed by strings \(x\in\{0,1\}^n\) and each column is indexed by pairs \((V,w)\in\mathcal{V}(n,k)\times\{0,1\}^k\). The entries of \(A\) are given by \(A_{x,(V,w)}= f(x|_V\oplus w)\).

Definition 11 (Approximate degree). For \(f:\{0,1\}^n \rightarrow \left \{ -1,1,* \right \}\) and \(0\leq \epsilon < 1\), we say a real multilinear polynomial \(p\) approximates \(f\) with error \(\epsilon\) if:

\(|p(x)-f(x)|\leq \epsilon\) for any \(x\in \{0,1\}^n\) such that \(f(x) \neq *\);
\(|p(x)|\leq 1\) for all \(x\in\{0,1\}^n\).

The approximate degree of \(f\) with error \(\epsilon\), denoted by \(\widetilde{ \deg}_{\epsilon}(f)\), is the minimum degree among all real multilinear polynomials that approximate \(f\) with error \(\epsilon\). If \(\epsilon = 2/3\), we abbreviate \(\widetilde{ \deg}_{\epsilon}(f)\) as \(\widetilde{\deg}(f)\).

Fact 14 ([44], Theorem 4). For symmetric Boolean functions \(f:\{0,1\}^n\rightarrow\left \{ -1,1,* \right \}\), let \(D\) be a Boolean predicate such that \(D(|x|) = f(x)\) for any \(x \in \{0,1\}^n\). Then \(\mathop{\mathrm{\mathsf{\widetilde{deg}}}}\left ( f \right ) = \Omega\left ( \sqrt{n(n-\Gamma(D))} \right )\), where \[\begin{align} \Gamma(D) &= \min\{|2k-n+1|:D(k),D(k+1)\neq *, \\ &D(k)\neq D(k+1)\text{ and }0 \le k \le n-1\}. \end{align}\]

Each two-party communication problem \(F: \mathcal{X} \times \mathcal{Y} \rightarrow \left \{ -1,1,* \right \}\) can be viewed as a matrix naturally according to the definition of \(F\). Then the following fact gives a lower bound on the quantum communication complexity by the approximate degree.

Fact 15 ([47], Theorem 6). Let \(F\) be the \((n,t,f)\)-pattern matrix, where \(f\colon \{0,1\}^t\to\{-1,+1,*\}\) is given. Then for every \(\epsilon\in[0,1)\) and every \(\delta<\epsilon/2,\) \[\begin{align} Q_{\delta}(F) &\geq \frac{1}{4} \mathop{\mathrm{\mathsf{\widetilde{deg}}}}_{\epsilon}(f)\log \left(\frac{n}{t}\right) - \frac{1}{2} \log\left(\frac{3}{\epsilon-2\delta}\right). \end{align}\]

7.2 Rank↩︎

We first restate and prove Fact [disj95eq] as follows:

Proof. Let \({\mathop{\mathrm{\mathsf{DISJ}}}'}_n^k:\mathcal{X} \times \mathcal{Y} \rightarrow \left \{ 0,1 \right \}\) and \({\mathop{\mathrm{\mathsf{EQ}}}'}_n^k:\mathcal{X} \times \mathcal{Y} \rightarrow \left \{ 0,1 \right \}\) be defined as \[{\mathop{\mathrm{\mathsf{DISJ}}}'}_n^k(x,y) \mathrel{\vcenter{:}}= \begin{cases} 1,& \text{ if }|x \land y| = 0,\\ 0,& \text{ if } |x \land y| \neq 0. \end{cases}\] and \[{\mathop{\mathrm{\mathsf{EQ}}}'}_n^k(x,y) \mathrel{\vcenter{:}}= \begin{cases} 1,& \text{ if }x = y,\\ 0,& \text{ if } x \neq y. \end{cases}\] By Example 2.12 in [48], \(\mathop{\mathrm{\mathrm{rank}}}\left ( {\mathop{\mathrm{\mathsf{DISJ}}}'}_n^k \right ) = \binom{n}{k}\). Since \(2{\mathop{\mathrm{\mathsf{DISJ}}}'}_n^k = J-\mathop{\mathrm{\mathsf{DISJ}}}\), where \(J\) is the all-ones matrix, we have \(\mathop{\mathrm{\mathrm{rank}}}\left ( {\mathop{\mathrm{\mathsf{DISJ}}}'}_n^k \right ) \le \mathop{\mathrm{\mathrm{rank}}}\left ( J \right )+\mathop{\mathrm{\mathrm{rank}}}\left ( \mathop{\mathrm{\mathsf{DISJ}}} \right )\). Thus, \(\mathop{\mathrm{\mathrm{rank}}}\left ( \mathop{\mathrm{\mathsf{DISJ}}} \right )\ge \mathop{\mathrm{\mathrm{rank}}}\left ( {\mathop{\mathrm{\mathsf{DISJ}}}'}_n^k \right )-\mathop{\mathrm{\mathrm{rank}}}\left ( J \right ) = \binom{n}{k}-1\). Since \(\mathop{\mathrm{\mathsf{EQ}}}'\) is an identity matrix, we have \(\mathop{\mathrm{\mathrm{rank}}}\left ( {\mathop{\mathrm{\mathsf{EQ}}}'}_n^k \right ) = \binom{n}{k}\). Similar to \(\mathop{\mathrm{\mathsf{DISJ}}}\), we have \(\mathop{\mathrm{\mathrm{rank}}}\left ( \mathop{\mathrm{\mathsf{EQ}}} \right ) \ge \mathop{\mathrm{\mathrm{rank}}}\left ( {\mathop{\mathrm{\mathsf{EQ}}}'}_n^k \right )-1 = \binom{n}{k}-1\). ◻

7.3 Approximate Rank↩︎

While some properties of approximate rank have been known for real matrices [41], [49], we generalize them to partial matrices. The proofs are adapted from the original proofs.

First, utilizing Facts 16 and 17, we prove [reduction] to show the error reduction of approximate rank.

Fact 16 ([49], Fact 1). Let \(0 < E < 1\) be given. Then for each interger \(c \ge 1\), there exists a degree-\(c\) real univariate polynomial \(p(t)\) such that for any \(1-E \le |t| \le 1+E\), \[|p(t)-\mathrm{sign}(t)| \le 8\sqrt{c}\left ( 1-\frac{(1-E)^2}{16} \right )^c,\] where \[\mathrm{sign}(t) \mathrel{\vcenter{:}}= \begin{cases} 1,&\text{ if }t > 0,\\ -1,&\text{ if }t < 0. \end{cases}\]

Fact 17 ([33], Lemma 11). Let \(A\) be a real matrix, \(p\) be a degree-\(d\) polynomial and \(B \mathrel{\vcenter{:}}= [p(A_{i,j})]_{i,j}\). Then \(\mathop{\mathrm{\mathrm{rank}}}\left ( B \right ) \le \left ( d+1 \right )\mathop{\mathrm{\mathrm{rank}}}\left ( A \right )^d\).

factreduction Let \(F\) be a matrix with \(\left \{ -1,1,* \right \}\) entries. Let \(\epsilon, E\) be constants with \(0 < \epsilon < E < 1\). Then \(\log\mathop{\mathrm{\widetilde{rank}}}_{\epsilon}(F) = O\left ( \log\mathop{\mathrm{\widetilde{rank}}}_E(F) \right )\).

Proof. Let \(c\) be any constant positive integer such that \[8\sqrt{c}\left ( 1-\frac{(1-E)^2}{16} \right )^c \le \epsilon/2.\] By 16, there is a degree-\(d\) polynomial \(p(t)\) such that for any \(1-E \le |t| \le 1\), \[|p(t)-\mathrm{sign}(t)|\le \epsilon/2.\] Let \(q(t) = p(t)-\epsilon/2\). Then for any \(1-E \le |t| \le 1\), we have \[|q(t) - \mathrm{sign}(t)| \le \epsilon, |q(t)| \le 1.\] Let \(A\) be a real matrix such that \(A \in \mathcal{F}_{E}\) and \(\mathop{\mathrm{\mathrm{rank}}}\left ( A \right ) = \mathop{\mathrm{\widetilde{rank}}}_E\left ( F \right )\), where \(\mathcal{F}_{E}\) be the set of real matrices that approximates \(F\) with error \(E\) as 2. Then the matrix \(B = [q\left ( A_{i,j} \right )]_{i,j}\) satisfies that \(B \in \mathcal{F}_{\epsilon}.\) By 17, we have \(\mathop{\mathrm{\mathrm{rank}}}(B) \le (c+1)\mathop{\mathrm{\mathrm{rank}}}(A)^c\). Thus, \[\begin{align} \mathop{\mathrm{\widetilde{rank}}}_{\epsilon}(F) &\le \mathop{\mathrm{\mathrm{rank}}}(B) \\ &\le (c+1)\mathop{\mathrm{\mathrm{rank}}}(A)^c \\ &= (c+1)\mathop{\mathrm{\widetilde{rank}}}_{E}(F)^c. \end{align}\] Thus, we have \(\log\mathop{\mathrm{\widetilde{rank}}}_{\epsilon}(F) = O\left ( \log\mathop{\mathrm{\widetilde{rank}}}_{E}(F) \right )\). ◻

Next, we first give some useful definitions, facts, and lemmas about the pattern matrix method [41].

Definition 12 (Norm of matrices). For a matrix \(A \in \mathbb{R}^{m \times n}\), let the singular values of \(A\) be \(\sigma_1(A) \ge \sigma_2(A) \ge \cdots \ge \sigma_{\min\left ( m,n \right )}(A) \ge 0\). The spectral norm and trace norm are given by \[\begin{align} ||A|| &\mathrel{\vcenter{:}}= \sigma_1(A),\\ ||A||_{\Sigma} &\mathrel{\vcenter{:}}= \sum_i \sigma_i(A). \end{align}\]

Definition 13 (Approximate trace norm). For any matrix \(F \in \left \{ -1,1,* \right \}^{m\times n}\) and \(0\leq \epsilon < 1\), the \(\epsilon\)-approximate trace norm of \(F\) is \[||F||_{\Sigma,\epsilon} \mathrel{\vcenter{:}}= \min_{A\in\mathcal{F}_{\epsilon}}||A||_{\Sigma},\] where \(\mathcal{F}_{\epsilon}\) is defined in 2.

Definition 14. For any incomplete matrix \(F \in \left \{ -1,1,* \right \}^{m\times n}\) and \(0\leq \epsilon < 1\), we say a real matrix \(A\) is a real representation of \(F\) if:

\(A_{i,j} = F_{i,j}\) for any \(i \in [m], j\in [n]\) such that \(F_{i,j} \neq *\);
\(|A_{i,j}|\leq 1\) for all \(i\in [m], j\in [n]\).

Let \(\mathcal{F}\) be the set of all real representations of \(F\).

By [def:real_rep,app_trace_norm], we have \(||F||_{\Sigma,\epsilon} = \min_{A\in\mathcal{F}}||A||_{\Sigma,\epsilon}\).

Fact 18 ([41], Proposition 2.2). Let \(F \in \mathbb{R}^{m \times n}\) and \(\epsilon \ge 0\). Then \[||F||_{\Sigma,\epsilon} \ge \sup_{\Psi\in\mathbb{R}^{m \times n}, ||\Psi|| \neq 0}\frac{\langle F,\Psi\rangle -\epsilon||\Psi||_1}{||\Psi||}.\]

As a corollary of 18, we have the following lemma:

Lemma 5. Let \(F \in \left \{ -1,1,* \right \}^{m\times n}\) and \(0 \le \epsilon < 1\). Then for any \(\Psi\in\mathbb{R}^{m \times n}\) such that \(||\Psi||\neq 0\), we have \[\frac{\sum_{(x,y)\in \mathrm{dom}} \Psi_{x,y}F_{x,y}-\sum_{(x,y)\notin \mathrm{dom}}|\Psi_{x,y}|-\epsilon||\Psi||_1}{||\Psi||}\] is a lower bound of \(||F||_{\Sigma,\epsilon}\), where \(\mathrm{dom} := \{(x,y): F_{x,y} \in \{-1,1\}\}\).

Proof. By 18, we have \[\begin{align} ||F||_{\Sigma,\epsilon} &= \min_{A\in\mathcal{F}}||A||_{\Sigma,\epsilon} \\ &\ge \min_{A\in\mathcal{F}}\sup_{\Psi\in\mathbb{R}^{m \times n}, ||\Psi|| \neq 0}\frac{\langle A,\Psi\rangle -\epsilon||\Psi||_1}{||\Psi||}\\ &= \sup_{\Psi\in\mathbb{R}^{m \times n}, ||\Psi|| \neq 0}\frac{1}{||\Psi||}\\ &\left ( \sum_{(x,y)\in \mathrm{dom}}\Psi_{x,y}F_{x,y}-\sum_{(x,y)\notin \mathrm{dom}} |\Psi_{x,y}|-\epsilon||\Psi||_1 \right ). \end{align}\] ◻

Lemma 6. Let \(F \in \left \{ -1,1,* \right \}^{m\times n}\) and \(0 \le \epsilon < 1\). Then \[\mathop{\mathrm{\widetilde{rank}}}_{\epsilon}(F) \ge \frac{||F||_{\Sigma,\epsilon}^2}{\left ( 1+\epsilon \right )^2mn}.\]

Proof. Same as Proposition 2.3 in [41], for any real matrix \(A\) that approximates \(F\) with \(\epsilon\), we have \[\begin{align} ||F||_{\Sigma,\epsilon} &=\min_{A \in \mathcal{F}_{\epsilon}}||A||_{\Sigma}\\ &\le ||A||_{F}\sqrt{\mathop{\mathrm{\mathrm{rank}}}{A}}\\ &\le \sqrt{\sum_{i,j}A_{i,j}^2} \sqrt{\mathop{\mathrm{\mathrm{rank}}}{A}} \\ &\le \sqrt{\left ( 1+\epsilon \right )^2mn}\sqrt{\mathop{\mathrm{\mathrm{rank}}}{A}}. \end{align}\] Thus, \[\mathop{\mathrm{\widetilde{rank}}}_{\epsilon}(F)\ge \mathop{\mathrm{\mathrm{rank}}}{A} \ge \frac{||F||_{\Sigma,\epsilon}^2}{\left ( 1+\epsilon \right )^2mn}.\] ◻

Fact 19 ([47], Theorem 10). Let \(F\) be the \((n,t,f)\)-pattern matrix, where \(f:\{0,1\}^t \rightarrow \left \{ -1,1,* \right \}\) is given. Suppose \(d = \mathop{\mathrm{\mathsf{\widetilde{deg}}}}_{\epsilon}(f)\). Then there exists \(\Psi\) be a \((n,t,2^{-n}(n/t)^{-t}\psi)\)-pattern matrix for some function \(\psi:\{0,1\}^t \rightarrow \mathbb{R}\) such that \[\label{eq:Psi} \begin{align} ||\Psi||_1 &= 1,\\ \epsilon &<\sum_{(x,y)\in \mathrm{dom}}F_{x,y}\Psi_{x,y}-\sum_{(x,y)\notin \mathrm{dom}}|\Psi_{x,y}|,\\ ||\Psi|| &\le \left ( \frac{t}{n} \right )^{d/2}\left ( 2^{n+t}\left ( \frac{n}{t} \right )^t \right )^{-1/2}, \end{align}\qquad{(1)}\] where \(\mathrm{dom} := \{(x,y): F_{x,y} \in \{-1,1\}\}\).

Finally, we give the following lower bound of approximate rank via the pattern matrix method by [arank95lowerbound].

lemmaaranklowerbound Let \(F\) be the \((n,t,f)\)-pattern matrix, where \(f:\{0,1\}^t \rightarrow \left \{ -1,1,* \right \}\) is given. Then for every \(\epsilon \in [0,1)\) and every \(\delta \in [0,\epsilon]\), \[\mathop{\mathrm{\widetilde{rank}}}_{\delta}(F) \ge \left ( \frac{\epsilon-\delta}{1+\delta} \right )^2\left ( \frac{n}{t} \right )^{\mathop{\mathrm{\mathsf{\widetilde{deg}}}}_{\epsilon}(f)}.\]

Proof. By 5 and (?? ), we have \[\label{eq:fro95lowerbound} ||F||_{\Sigma,\delta} \ge (\epsilon-\delta)\left ( \frac{n}{t} \right )^{\mathop{\mathrm{\mathsf{\widetilde{deg}}}}_{\epsilon}(f)/2}\sqrt{2^{n+t}(n/t)^t}.\tag{8}\] Since \(F\) is a \(2^n \times (n/t)^t2^t\) matrix, by 6 and (8 ), we have \[\begin{align} \mathop{\mathrm{\widetilde{rank}}}_{\delta}(F) &\ge \frac{||F||_{\Sigma,\delta}^2}{\left ( 1+\delta \right )^2 2^{n+t}(n/t)^t}\\ &\ge \left ( \frac{\epsilon-\delta}{1+\delta} \right )^2\left ( \frac{n}{t} \right )^{\mathop{\mathrm{\mathsf{\widetilde{deg}}}}_{\epsilon}(f)}.\\ \end{align}\] ◻

7.4 Sampling in Communication Model↩︎

First, we give Fact 20. Then we restate and prove its randomized version, Fact [fact:sample95oplus].

Fact 20 ([50], Proposition 2). Suppose \(x,y \in \{0,1\}^n\) are inputs of Alice and Bob such that \(|x| \neq |y|\). Alice and Bob can find an index \(i\) such that \(x_i \neq y_i\) using \(O(\log n)\) bits of communication.

Proof. The protocol of 20 is a deterministic protocol based on binary search. Initially, the search space is \(\left \{ 0,1,...,n-1 \right \}\). In each round, Alice and Bob shrink the search space to one-half of the original search space. Finally, Alice and Bob find one index \(i \in \left \{ 0,1,...,n-1 \right \}\) such \(x_i \neq y_i\) by \(O(\log n)\) rounds. The deterministic protocol can be adjusted to a randomized protocol easily. By making the same random permutation to the bits of the inputs using public coins, Alice and Bob can find an index \(i\) such that \(x_i \neq y_i\) uniformly. ◻

7.5 Quantum Amplitude Amplification↩︎

Fact 21 ([46], Merging Theorem 3 and item (4) in Corollary 4). Given a unitary \(U\) such that \(U\ket{0} = \ket{\psi}\) and an orthogonal projector \(\Pi\), there exists a quantum algorithm outputting an estimation \(\tilde{p}\) of \(p = \langle \psi | \Pi | \psi \rangle\) such that \[|\tilde{p}-p| \le \frac{1}{3}\epsilon\] by \(O\left ( \sqrt{p}/\epsilon \right )\) calls to (the controlled versions of) \(U,U^{\dagger}\) and \(I-2\Pi\) with bounded error.

As a direct corollary of 21, we give the quantum version of 12 as follows.

Fact 22. Given a set \(S\), suppose there is a subset \(S'\) of \(S\) such that \(\frac{|S'|}{|S|} \le \beta-\epsilon\) or \(\frac{|S'|}{|S|} \ge \beta+\epsilon\). Suppose we have a quantum sampler such that \(\mathcal{S}\ket{0} = \frac{1}{\sqrt{|S|}}\sum_{i \in S}\ket{i}\). Let orthogonal projector \(\Pi\) be defined as \(\Pi = \sum_{i \in S'}\ket{i}\bra{i}\). Since \(\frac{|S'|}{|S|} = \bra{0}\mathcal{S}^{\dagger} \Pi \mathcal{S}\ket{0}\), we can decide whether \(\frac{|S'|}{|S|} \le \beta-\epsilon\) or \(\frac{|S'|}{|S|} \ge \beta+\epsilon\) by \(O\left ( \sqrt{\beta}/\epsilon \right )\) calls of (the controlled versions of) \(\mathcal{S},\mathcal{S}^{\dagger}\) and \(I-2\Pi\) with bounded error.

Remark 23. Fact 22 is also correct if \(\mathcal{S}\ket{0}\ket{0} = \frac{1}{\sqrt{|S|}}\sum_{i \in S}\ket{\psi_i}\ket{i}\) and \(\Pi = I \otimes \sum_{i \in S'}\ket{i}\bra{i}\), where \(\left \{ \ket{\psi_i} \right \}\) is an orthonormal basis.

8 Quantum and Randomized Communication Complexity of Permutation-Invariant Functions↩︎

8.1 The Lower Bound on Quantum Communication Complexity↩︎

In this section, we restate and prove the following lemmas:

Proof.

Suppose there exists a quantum protocol \(\mathcal{P}\) that solves \(\mathrm{ESetInc}_{a+\ell_1 + \ell_3, b + \ell_2 + \ell_3, c+\ell_3, g}^{n+\ell}\). To solve \(\mathrm{ESetInc}_{a, b, c, g}^{n}\), Alice and Bob can append some bit strings to their input, respectively. First, Alice appends \(\ell_1\) 1’s to her input string, and Bob appends \(\ell_1\) 0’s in the same positions. Second, Bob appends \(\ell_2\) 1’s to his input, and Alice appends \(\ell_2\) 0’s in the same positions. Third, Alice and Bob append \(\ell_3\) 1’s at the same time. Finally, Alice and Bob run the protocol for \(\mathrm{ESetInc}_{a+\ell_1 + \ell_3, b + \ell_2 + \ell_3, c+\ell_3, g}^{n+\ell}\).
Suppose there exists a quantum protocol solving \(\mathrm{ESetInc}_{a, b, c, g}^{n}\). To solve \(\mathrm{ESetInc}_{a, n-b, a-c, g}^{n}\), Bob can first flip each bit of his input, and then Alice and Bob run the protocol for \(\mathrm{ESetInc}_{a, b, c, g}^{n}\). Thus \(Q\left ( \mathrm{ESetInc}_{a, n-b, a-c, g}^{n} \right ) \le Q\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right )\). By a similar argument, we have \[\begin{align} Q\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right ) &\le Q\left ( \mathrm{ESetInc}_{a, n-b, a-c, g}^{n} \right ), \\ Q\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right ) &\le Q\left ( \mathrm{ESetInc}_{n-a, b, b-c, g}^{n} \right ), \\ Q\left ( \mathrm{ESetInc}_{n-a, b, b-c, g}^{n} \right ) &\le Q\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right ). \end{align}\] Thus, \(Q\left ( \mathrm{ESetInc}_{a, b, c, g}^{n} \right ) = Q\left ( \mathrm{ESetInc}_{a, n-b, a-c, g}^{n} \right ) = Q\left ( \mathrm{ESetInc}_{n-a, b, b-c, g}^{n} \right )\).
Suppose there exists a quantum protocol solving \(\mathrm{ESetInc}_{ka, kb, kc, kg}^{kn}\). To solve \(\mathrm{ESetInc}_{a, b, c, g}^{n}\), Alice and Bob can repeat their input strings \(k\) times and run the protocol for \(\mathrm{ESetInc}_{ka, kb, kc, kg}^{kn}\).

◻

Proof. We consider the function \(f_{k,l}:\{0,1\}^k \rightarrow \left \{ -1,1,* \right \}\) given by \[\begin{align} \label{def:fkl} f_{k,l}(x)\mathrel{\vcenter{:}}= \begin{cases} -1, &\text{if |x|=l-1/2,}\\ 1, &\text{if |x|=l+1/2,}\\ *, &\text{otherwise.} \end{cases} \end{align}\tag{9}\] Let \(D\) be a Boolean predicate such that \(D(|x|) = f(x)\) for any \(x \in \{0,1\}^k\). By 14, we have \[\Gamma(D) = |2(l-1/2)-k+1| = |2l-k| = k-2l,\] and thus \[\label{eq:adeg} \mathop{\mathrm{\mathsf{\widetilde{deg}}}}_{1/3}\left ( f_{k,l} \right ) = \Omega\left ( \sqrt{k(k-\Gamma(D))} \right ) = \Omega\left ( \sqrt{kl} \right ).\tag{10}\] Let \(P\) be the \(\left ( 2k,k,f_{k,l} \right )\)-pattern matrix defined as 10. 15 implies that \(Q_{1/3}\left ( P \right ) = \Omega\left ( \sqrt{kl} \right )\), where \[\begin{align} P &= \Big[f_{k,l}(x|_V\oplus w)\Big]_{x\in\{0,1\}^{2k},\,(V,w)\in\mathcal{V}(2k,k)\times\{0,1\}^k} \\ &= \Big[f_{k,l}(x_1\overline{x}_1 x_2\overline{x}_2\ldots x_{2k}\overline{x_{2k}}|_V)\Big]_{x\in\{0,1\}^{2k},\,V\in\mathcal{V}(4k,k)}. \end{align}\] For any \(x \in \{0,1\}^{2k}\), we have \(x_1\overline{x}_1 x_2\overline{x}_2\ldots x_{2k}\overline{x_{2k}} \in \{0,1\}^{4k}\) and \(|x_1\overline{x}_1 x_2\overline{x}_2\ldots x_{2k}\overline{x_{2k}}| = 2k\); for any \(V\in\mathcal{V}(4k,k)\), we have \(V \in \{0,1\}^{4k}\) and \(|V|= k\). Thus, \(P\) is a submatrix of \(\mathrm{ESetInc}^{4k}_{2k,k,l,1/2}\), which is defined as \[\begin{align} &\mathrm{ESetInc}^{4k}_{2k,k,l,1/2}(x, y)\\ &\mathrel{\vcenter{:}}=\begin{cases} -1, &\text{if |x|=2k,|y|=k and |x \land y|=l-1/2}, \\ 1, &\text{if |x|=2k,|y|=k and |x \land y|=l+1/2}, \\ *, &\text{otherwise.} \end{cases} \end{align}\] As a result, we have \(Q_{1/3}\left ( \mathrm{ESetInc}^{4k}_{2k,k,l,1/2} \right ) \ge Q_{1/3}\left ( P \right ) = \Omega\left ( \sqrt{kl} \right )\). ◻

8.2 Quantum Upper Bound of Set-Inclusion Problem↩︎

We restate and prove [lemma:quantum95upper95bound95setinc] as follows:

Proof. The proof of Lemma [lemma:quantum95upper95bound95setinc] is similar to the proof of Lemma 3. The only essential difference is that 12 is replaced by its quantum speedup version, 22. For simplicity, we discuss the following two cases as the proof of 3. For other cases, we can obtain the same result similarly. In the following proof, for \(x \in \{0,1\}^n\), let \(S_x \mathrel{\vcenter{:}}= \left \{ i:x_i = 1 \right \}\). Let \(\Pi \mathrel{\vcenter{:}}= \sum_{i \in S_{x \land y}}\ket{i}\bra{i}\).

\(n_1 = c, n_2 = a-c\). In this case, the problem to compute \(\mathrm{SetInc}_{a, b, c, g}^{n}(x,y)\) can be reduced equivalently to estimate \(\frac{|x \land y|}{|x|}\). We first prove some special unitary operations can be constructed with \(O(\log n)\) qubits communication.
1. Since Alice knows all information about \(x\), she can implement \(S_x\) such that \(\mathcal{S}_{x}\ket{0} = \frac{1}{\sqrt{a}}\sum_{i \in S_x}\ket{i}\) by herself without communication. Let \(\ket{\phi_1} \mathrel{\vcenter{:}}= \mathcal{S}_{x}\ket{0}\). Then we have \[\bra{\phi_1}\Pi\ket{\phi_1} = \frac{|x\land y|}{|x|}.\]
2. For inputs \(x,y \in \{0,1\}^n\) and any \(i \in [n]\), let unitary operator \(O_x,O_y,O_{x \land y}\) be defined as \[\begin{align} O_x \ket{i} &\mathrel{\vcenter{:}}= (-1)^{x_i}\ket{i},\\ O_y \ket{i} &\mathrel{\vcenter{:}}= (-1)^{y_i}\ket{i},\\ O_{x \land y}\ket{i} &\mathrel{\vcenter{:}}= (-1)^{x_i y_i}\ket{i}.\\ \end{align}\] Then \(I-2\Pi = O_{x \land y}\). For any \(\ket{\phi} \mathrel{\vcenter{:}}= \sum_{i \in [n]}\alpha_i \ket{i}\), Alice and Bob can perform \(I-2\Pi\) to any state \(\ket{\phi}\) using \(O(\log n)\) qubits of quantum communication as follows: i) Alice performs \(O_x\) to \(\ket{\phi}\) and sends \(\ket{\phi'} = O_x \ket{\phi} = \sum_{i \in [n]}\alpha_i (-1)^{x_i} \ket{i}\) to Bob; ii) Bob performs \(O_y\) to \(\ket{\phi'}\) and obtains \(\sum_{i \in [n]}\alpha_i (-1)^{x_iy_i} \ket{i} = O_{x \land y}\ket{\phi}\).
By 22, a quantum speedup version of 12, and using an argument similar to Lemma 3, we can obtain the following conclusion: using \(O\left ( \frac{\sqrt{n_1n_2}}{g} \right )\) unitary operations \(\mathcal{S}_x\) and \(I-2\Pi\), Alice and Bob can estimate \(\frac{|x \land y|}{|x|}\) with errors at most \(O\left ( \frac{g}{a} \right )\). Furthermore, they can decide whether \(|x\land y| \ge c+g\) or \(|x \land y| \le c-g\) with success probability at least \(1- 1/(6\log n)\) using \(O\left ( \frac{\sqrt{n_1n_2}}{g} \log n \log\log n \right )\) qubits communication.
\(n_1 =c\), \(n_2 = n-a-b+c\) and \(a+b < n\). In this case, the problem to compute \(\mathrm{SetInc}_{a, b, c, g}^{n}(x,y)\) can be reduced equivalently to estimate \(\frac{|x \land y|}{|\overline{x} \oplus y|}\). Similar to Case [item:case195quantum95upper95bound95setinc], we first prove Alice and Bob can construct a quantum sampler \(\mathcal{S}_{\overline{x} \oplus y}\) such that \[\mathcal{S}_{\overline{x}\oplus y}\ket{0}\ket{0} = \frac{1}{\sqrt{|N|}}\sum_{f \in [N]}\ket{ff}\ket{f(x,y)} = \ket{\phi_2},\] using \(O\left ( \log n \right )\) qubits communication, where \(N = C \cdot \frac{n_1n_2}{g^2}\) for some enough large constant \(C\) and each \(f\) encodes a random function such that \(f(x,y)\) is a uniform distribution of the elements in \(S_{\overline{x} \oplus y}\). Specifically, the construction procedure is as follows: First, Alice and Bob use \(O\left ( \log\frac{n_1n_2}{g^2} \right )\) qubits communication to transform \(\ket{0}\) into a maximum entanglement bipartite state \(\frac{1}{\sqrt{N}}\sum_{f \in [N]}\ket{ff}\). Moreover, both Alice and Bob hold one part of the state. Second, by Fact [fact:sample95oplus], Alice and Bob can sample an element from \(S_{\overline{x} \oplus y}\) uniformly using \(O(\log n)\) bits of communication. Equivalently, Alice and Bob can generate a random function \(f\) using public coins, and output \(f(x,y)\) using \(O(\log n)\) bits of communication such that the distribution of the output is a uniform distribution of the elements in \(S_{\overline{x} \oplus y}\). Since quantum circuits can simulate classical circuits efficiently, Alice and Bob can perform a uniform operation that transforms \(\ket{ff}\ket{b}\) into \(\ket{ff}\ket{f(x,y)+b}\) for any \(f \in N\) using \(O\left ( \log n \right )\) qubits communication, where both Alice and Bob hold one part of \(\ket{ff}\), \(b \in \left \{ 0,1,...,n-1 \right \}\) and the addition is with modulo \(n\). As a whole, Alice and Bob can construct the above quantum sampler \(\mathcal{S}_{\overline{x}\oplus y}\) using \(O\left ( \log \frac{n_1n_2}{g^2} + \log n \right ) = O\left ( \log n \right )\) qubits communication. Furthermore, since \(f(x,y)\) is a uniform distribution of the elements in \(S_{\overline{x} \oplus y}\) for any \(f \in \left \{ 0,1,...,N-1 \right \}\), \(N = C \cdot \frac{n_1n_2}{g^2}\) for some enough large constant \(C\), and \[\bra{\phi_2}\left ( I \otimes \Pi \right )\ket{\phi_2} = \frac{|\left \{ f:f(x,y) \in S_{x \land y} \right \}|}{N},\] we have \[\label{eq:innerproduct95phi95two} \left|\bra{\phi_2}\left ( I \otimes \Pi \right )\ket{\phi_2}-\frac{|x\land y|}{|\overline{x} \oplus y|}\right| = O\left ( \frac{g}{m} \right ),\tag{11}\] similar to the analysis of Case [a95b95less95n] of Lemma 3, where \(m = n_1+n_2\).

By 22, a quantum speedup version of 12, and using an argument similar to Lemma 3, we can obtain the following conclusion, using \(O\left ( \frac{\sqrt{n_1n_2}}{g} \right )\) unitary operations \(\mathcal{S}_{|\overline{x} \oplus y|}\) and \(I-2\Pi\), Alice and Bob can estimate \(\bra{\phi_2}\left ( I \otimes \Pi \right )\ket{\phi_2}\) with errors at most \(O\left ( \frac{g}{m} \right )\). By (11 ), Alice and Bob also can estimate \(\frac{|x \land y|}{|\overline{x} \oplus y|}\) with errors at most \(O\left ( \frac{g}{m} \right )\). Next, using the same argument as 3, we can prove that Alice and Bob can decide whether \(|x\land y| \ge c+g\) or \(|x \land y| \le c-g\) with success probability at least \(1- 1/(6\log n)\) using \(O\left ( \frac{\sqrt{n_1n_2}}{g} \log n \log\log n \right )\) qubits communication. ◻

9 Log-Approximate-Rank Conjecture of Permutation-Invariant Functions↩︎

In this section, we restate and prove [lemma:rank_SecInc,lemma:lower_rank2].

Proof. By the definition of approximate rank (2), to prove \(\mathop{\mathrm{\widetilde{rank}}}(A) \le \mathop{\mathrm{\widetilde{rank}}}(B)\), it suffices to prove \(A\) is a submatrix of \(B\). Then we discuss three cases:

For \(x,y \in \{0,1\}^n\), let \[\begin{align} x' &\mathrel{\vcenter{:}}= x\underbrace{1\cdots 1}_{l_1}\underbrace{0\cdots 0}_{l_2}\underbrace{1\cdots 1}_{l_3}\underbrace{0\cdots 0}_{l-\left ( l_1+l_2+l_3 \right )},\\ y' &\mathrel{\vcenter{:}}= y\underbrace{0\cdots 0}_{l_1}\underbrace{1\cdots 1}_{l_2}\underbrace{1\cdots 1}_{l_3}\underbrace{0\cdots 0}_{l-\left ( l_1+l_2+l_3 \right )}.\\ \end{align}\] Then \(\mathrm{ESetInc}_{a, b, c, g}^{n}\left ( x,y \right ) = \mathrm{ESetInc}_{a+\ell_1 + \ell_3, b + \ell_2 + \ell_3, c+\ell_3, g}^{n+\ell}\left ( x',y' \right )\). Thus, \(\mathrm{ESetInc}_{a, b, c, g}^{n}\) is a submatrix of \(\mathrm{ESetInc}_{a+\ell_1 + \ell_3, b + \ell_2 + \ell_3, c+\ell_3, g}^{n+\ell}\).
For \(x,y\in \{0,1\}^n\), we have \[\begin{align} \mathrm{ESetInc}_{a, b, c, g}^{n}(x,y) &= \mathrm{ESetInc}_{a, n-b, a-c, g}^{n}(x,\overline{y})\\ &= \mathrm{ESetInc}_{n-a, b, b-c, g}^{n}(\overline{x},y). \end{align}\]
Since \(\mathrm{ESetInc}_{a, b, c, g}^{n}(x,y) = \mathrm{ESetInc}_{ka, kb, kc, kg}^{kn}(\underbrace{x\cdots x}_{k},\underbrace{y\cdots y}_k)\), we have \(\mathrm{ESetInc}_{a, b, c, g}^{n}\) is a submatrix of \(\mathrm{ESetInc}_{ka, kb, kc, kg}^{kn}\).

◻

Proof. Let \(P\) be the \(\left ( 2k,k,f_{k,l} \right )\)-pattern matrix, where \(f_{k,l}\) is defined in (9 ). By [lemma:partial], \(P\) is a submatrix of \(\mathrm{ESetInc}^{4k}_{2k,k,l,1/2}\). Thus, we have \[\log\left ( \mathop{\mathrm{\widetilde{rank}}}\left ( \mathrm{ESetInc}^{4k}_{2k,k,l,1/2} \right ) \right ) \ge \log\left ( \mathop{\mathrm{\widetilde{rank}}}\left ( P \right ) \right ).\] By Facts [reduction] and [arank95lowerbound] and (10 ), we have \[\log\left ( \mathop{\mathrm{\widetilde{rank}}}\left ( P \right ) \right ) = \Omega\left ( \mathop{\mathrm{\mathsf{\widetilde{deg}}}}\left ( f_{k,l} \right ) \right ).\] Thus, \[\begin{align} \log\left ( \mathop{\mathrm{\widetilde{rank}}}\left ( \mathrm{ESetInc}^{4k}_{2k,k,l,1/2} \right ) \right ) &= \Omega\left ( \mathop{\mathrm{\mathsf{\widetilde{deg}}}}\left ( f_{k,l} \right ) \right ) \\ &= \Omega\left ( \sqrt{kl} \right ), \end{align}\] where the second equality comes from (10 ). ◻

10 Communciation Complexity of Gap-Hamming-Distance Problem↩︎

Ref. [26] gave the lower and upper bounds on the randomized communication complexity of Gap-Hamming-Distance as [lemma_gks_lower,lemma_gks_upper]. We show [lemma_gks_lower,lemma_gks_upper] can be expressed as [lemma_gks_lower_2,lemma_gks_upper_2] equivalently.

Lemma 7 (Lemma 3.3 in [26]). Fix \(n\in{\mathbb{Z^+}}\). Consider \(a,b \in \left \{ 1,...,n-1 \right \}\) and \(c-g,c+g\) are achievable Hamming distances of \(\Delta(x,y)\) when \(|x| = a, |y| = b\). Then \[\label{gks95upper} \begin{align} R(\mathrm{GHD}_{a,b,c,g}^n) &= \Omega\left ( \frac{\min\left \{ a,b,c,n-a,n-b,n-c \right \}}{g} \right ),\\ R(\mathrm{GHD}_{a,b,c,g}^n) &= \Omega\left ( \log\left ( \frac{\min\left \{ c,n-c \right \}}{g} \right ) \right ). \end{align}\qquad{(2)}\]

Lemma 8. Fix \(n\in{\mathbb{Z^+}}\). Consider \(a,b \in \left \{ 1,...,n-1 \right \}\) and \(c-g,c+g\) are achievable Hamming weights of \(|x \land y|\) when \(|x| = a, |y| = b\). Let \(n_1\mathrel{\vcenter{:}}= \min\{[a-c,c,b-c,n-a-b+c]\}\) and \(n_2\mathrel{\vcenter{:}}= \min\left(\{[a-c,c,b-c,n-a-b+c]\}\setminus \left \{ n_1 \right \}\right)\). Then \(R(\mathsf{SetInc}_{a,b,c,g}^n)\) has two lower bounds: \(\Omega\left ( \frac{n_2}{g} \right )\) and \[\Omega\left ( \log\frac{\min\left \{ a+b-2c,n-a-b+2c \right \}}{g} \right ).\]

Proof. By [def:GHD,def:setinc], \(\mathsf{SetInc}_{a,b,c,d}^n\) and \(\mathrm{GHD}_{a,b,a+b-2c,2g}^n\) are the same problems. Thus, we have \[R(\mathsf{SetInc}_{a,b,c,d}^n) = R(\mathrm{GHD}_{a,b,a+b-2c,2g}^n).\] By 7, \(R(\mathrm{GHD}_{a,b,a+b-2c,2g}^n)\) has two lower bounds: \[\Omega\left ( \frac{\min\left \{ a,b,a+b-2c,n-a,n-b,n-(a+b-2c) \right \}}{g} \right ),\\None\] and \[\Omega\left ( \log\frac{\min\left \{ a+b-2c,n-a-b+2c \right \}}{g} \right ).\] Since \[\begin{align} a &= (a-c)+c, \\ b &= (b-c)+c,\\ a+b-2c &= (a-c)+(b-c),\\ n-a &= (n-a-b+c)+(b-c), \\ n-b &= (n-a-b+c)+(a-c),\\ n-(a+b-2c) &= (n-a-b+c)+c, \\ \end{align}\] and \(n_1,n_2\) are smallest two numbers in \(a-c,c,b-c,n-a-b+c\), we have \[\begin{align} &\min\left \{ a,b,a+b-2c,n-a,n-b,n-(a+b-2c) \right \} \\ &= n_1+n_2\\ &\ge n_2. \end{align}\] ◻

Lemma 9 (Lemma 3.4 in [26]). Fix \(n\in{\mathbb{Z^+}}\). Consider \(a,b \in \left \{ 1,...,n-1 \right \}\) and \(c-g,c+g\) are achievable Hamming distances of \(\Delta(x,y)\) when \(|x| = a, |y| = b\). If \(a \le b \le n/2\), then \(R(\mathrm{GHD}_{a,b,c,g}^n)\) is \[\label{gks95lower} O\left ( \min\left \{ \left ( \frac{a}{g} \right )^2\log \left ( \frac{b}{g} \right ),\left ( \frac{c}{g} \right )^2,\left ( \frac{n-c}{g} \right )^2 \right \} \right ).\qquad{(3)}\]

Lemma 10. Fix \(n\in{\mathbb{Z^+}}\). Consider \(a,b \in \left \{ 1,...,n-1 \right \}\) and \(c-g,c+g\) are achievable Hamming weights of \(|x \land y|\) when \(|x| = a, |y| = b\). If \(a \le b \le n/2\), then \[R(\mathsf{SetInc}_{a,b,c,g}^n) = O\left ( \left ( \frac{n_2}{g} \right )^2\log \frac{b}{g} \right ).\]

Proof. Since \(a \le b \le n/2\), similar to the proof of 8, we have \[\begin{align} &\min\left \{ a,a+b-2c,n-(a+b-2c) \right \}\\ &= \min\left \{ a,b,a+b-2c,n-a,n-b,n-(a+b-2c) \right \} \\ &=n_1+n_2 \\ &\le 2n_2. \end{align}\] By 9, we have \[\begin{align} &R(\mathsf{SetInc}_{a,b,c,d}^n) \\ &= R(\mathrm{GHD}_{a,b,a+b-2c,2g}^n) \\ &= O\left ( \frac{\min\left \{ a,a+b-2c,n-(a+b-2c) \right \}^2}{(2g)^2}\log \left ( \frac{b}{2g} \right ) \right )\\ &= O\left ( \left ( \frac{n_2}{g} \right )^2\log \left ( \frac{b}{g} \right ) \right ).\\ \end{align}\] ◻

Acknowledgement↩︎

The authors would like to thank the editor and anonymous reviewers for their helpful comments and suggestions. We also would like to express our gratitute to Arkadey Chattopadhyay for drawing our attention to the proper attribution of the resolution of the Log-Approximate-Rank Conjecture for \(\mathrm{XOR}\)-symmetric functions. Accordingly, we have revised the manuscript to correctly acknowledge the work of Chattopadhyay and Mande [43], who first established this result.

References↩︎

[1]

Anurag Anshu, Dave Touchette, Penghui Yao, and Nengkun Yu. Exponential separation of quantum communication and classical information. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 277–288. ACM, 2017. https://doi.org/10.1145/3055399.3055401.

[2]

Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel. Quantum advantage with noisy shallow circuits in 3D. In Proccedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, pages 995–999, 2019. https://doi.org/10.1109/FOCS.2019.00064.

[3]

Daniel Grier and Luke Schaeffer. Interactive shallow clifford circuits: quantum advantage against NC\({^1}\) and beyond. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 875–888, 2020. https://doi.org/10.1145/3357713.3384332.

[4]

Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In Proccedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, pages 574–585, 2021. https://doi.org/10.1109/FOCS52979.2021.00063.

[5]

John Kallaugher. A quantum advantage for a natural streaming problem. In Proccedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, pages 897–908, 2021. https://doi.org/10.1109/FOCS52979.2021.00091.

[6]

Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. In Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, pages 69–74, 2022. https://doi.org/10.1109/FOCS54457.2022.00014.

[7]

Daniel R. Simon. On the power of quantum computation. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 116–123, November 1994. https://doi.org/10.1109/SFCS.1994.365701.

[8]

Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 124–134, November 1994. https://doi.org/10.1109/SFCS.1994.365700.

[9]

L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th IEEE Annual Symposium on Theory of Computing, pages 212–219, 1996. https://doi.org/10.1145/237814.237866.

[10]

Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. Journal of ACM, 51(4):595–605, 2004. https://doi.org/10.1145/1008731.1008735.

[11]

Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. Theory of Computing, 10:133–166, 2014. https://doi.org/10.4086/toc.2014.v010a006.

[12]

André Chailloux. A note on the quantum query complexity of permutation symmetric functions. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference, volume 124, pages 19:1–19:7, 2019. https://doi.org/10.4230/LIPIcs.ITCS.2019.19.

[13]

Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, and Daochen Wang. Symmetries, graph properties, and quantum speedups. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, pages 649–660, 2020. https://doi.org/10.1109/FOCS46700.2020.00066.

[14]

Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard, and Alfred V. Aho, editors, Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 209–213. ACM, 1979. https://doi.org/10.1145/800135.804414.

[15]

Andrew Chi-Chih Yao. Quantum circuit complexity. In Proceeding of the 34th Annual Symposium on Foundations of Computer Science, pages 352–361, 1993. https://doi.org/10.1109/SFCS.1993.366852.

[16]

Ran Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pages 358–367. ACM, 1999. https://doi.org/10.1145/301250.301343.

[17]

Ziv Bar-Yossef, T. S. Jayram, and Iordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity. SIAM J. Comput., 38(1):366–384, 2008. https://doi.org/10.1137/060651835.

[18]

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 516–525. ACM, 2007. https://doi.org/10.1145/1250790.1250866.

[19]

Dmitry Gavinsky and Pavel Pudlák. Exponential separation of quantum and classical non-interactive multi-party communication complexity. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, pages 332–339. IEEE Computer Society, 2008. https://doi.org/10.1109/CCC.2008.27.

[20]

Ashley Montanaro. A new exponential separation between quantum and classical one-way communication complexity. Quantum Information and Computation, 11(7&8):574–591, 2011. https://doi.org/10.26421/QIC11.7-8-3.

[21]

Alexander A Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145, 2003. https://doi.org/10.1070/IM2003v067n01ABEH000422.

[22]

Wei Huang, Yaoyun Shi, Shengyu Zhang, and Yufan Zhu. The communication complexity of the Hamming distance problem. Information Processing Letter, 99(4):149–153, 2006. https://doi.org/10.1016/j.ipl.2006.01.014.

[23]

Alexander A. Sherstov. The communication complexity of gap Hamming distance. Theory of Computing, 8(1):197–208, 2012. https://doi.org/10.4086/toc.2012.v008a008.

[24]

Thomas Vidick. A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the Gap-Hamming-Distance problem. Chicago Journal of Theoretical Computer Science, 2012, 2012. URL: http://cjtcs.cs.uchicago.edu/articles/2012/1/contents.html.

[25]

Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of Gap-Hamming-Distance. SIAM Journal on Computing, 41(5):1299–1317, 2012. https://doi.org/10.1137/120861072.

[26]

Badih Ghazi, Pritish Kamath, and Madhu Sudan. Communication complexity of permutation-invariant functions. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1902–1921, 2016. https://doi.org/10.1137/1.9781611974331.ch134.

[27]

L. Lovasz and M. Saks. Lattices, mobius functions and communications complexity. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 81–90, 1988. https://doi.org/10.1109/SFCS.1988.21924.

[28]

Eli Ben-Sasson, Shachar Lovett, and Noga Ron-Zewi. An additive combinatorics approach relating rank to communication complexity. Journal of the ACM, 61(4), 2014. https://doi.org/10.1145/2629598.

[29]

Shachar Lovett. Communication is bounded by root of rank. Journal of the ACM, 63(1), 2016. https://doi.org/10.1145/2724704.

[30]

Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan. Log-rank and lifting for AND-functions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, page 197–208, 2021. https://doi.org/10.1145/3406325.3450999.

[31]

Harry Buhrman and Ronald de Wolf. Communication complexity lower bounds by polynomials. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, pages 120–130, 2001. https://doi.org/10.1109/CCC.2001.933879.

[32]

Zhiqiang Zhang and Yaoyun Shi. Communication complexities of symmetric XOR functions. Quantum Information and Computation, 9(3&4):255–263, 2009. https://doi.org/10.26421/QIC9.3-4-5.

[33]

Troy Lee and Adi Shraibman. An approximation algorithm for approximation rank. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, pages 351–357. IEEE Computer Society, 2009. https://doi.org/10.1109/CCC.2009.25.

[34]

Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif. The log-approximate-rank conjecture is false. J. ACM, 67(4), jun 2020. https://doi.org/10.1145/3396695.

[35]

Anurag Anshu, Naresh Goud Boddu, and Dave Touchette. Quantum log-approximate-rank conjecture is also false. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 982–994, 2019. https://doi.org/10.1109/FOCS.2019.00063.

[36]

Makrand Sinha and Ronald de Wolf. Exponential separation between quantum communication and logarithm of approximate rank. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 966–981, 2019. https://doi.org/10.1109/FOCS.2019.00062.

[37]

Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263–398, 2009. https://doi.org/10.1561/0400000040.

[38]

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. https://doi.org/10.1145/502090.502097.

[39]

Shalev Ben-David. The structure of promises in quantum speedups. In Proceedings of the 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, volume 61, pages 7:1–7:14, 2016. https://doi.org/10.4230/LIPIcs.TQC.2016.7.

[40]

Scott Aaronson and Shalev Ben-David. Sculpting quantum speedups. In Proceedings of the 31st Conference on Computational Complexity, volume 50, pages 26:1–26:28, 2016. https://doi.org/10.4230/LIPIcs.CCC.2016.26.

[41]

Alexander A. Sherstov. The pattern matrix method. SIAM Journal of Computing, 40(6):1969–2000, 2011. https://doi.org/10.1137/080733644.

[42]

Daiki Suruga. Matching upper bounds on symmetric predicates in quantum communication complexity. arXiv preprint, 2023. https://arxiv.org/abs/2301.00370.

[43]

Arkadev Chattopadhyay and Nikhil S. Mande. A lifting theorem with applications to symmetric functions. In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, volume 93, pages 23:1–23:14, 2017. https://doi.org/10.4230/LIPICS.FSTTCS.2017.23.

[44]

Ramamohan Paturi. On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 468–474. ACM, 1992. https://doi.org/10.1145/129712.129758.

[45]

Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53–74, 2002.

[46]

Yassine Hamoudi and Frédéric Magniez. Quantum chebyshev’s inequality and applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132, pages 69:1–69:16, 2019. https://doi.org/10.4230/LIPIcs.ICALP.2019.69.

[47]

Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, and Alexander A. Sherstov. Quantum communication complexity of distribution testing. Quantum Information and Computation, 21(15&16):1261–1273, 2021. https://doi.org/10.26421/QIC21.15-16-1.

[48]

Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997.

[49]

Adam R. Klivans and Alexander A. Sherstov. A lower bound for agnostically learning disjunctions. In Proceeding of the 20th Annual Conference on Learning Theory, volume 4539, pages 409–423. Springer, 2007. https://doi.org/10.1007/978-3-540-72927-3_30.

[50]

Gerth Stølting Brodal and Thore Husfeldt. A communication complexity proof that symmetric functions have logarithmic depth. BRICS, 1995.

Partially supported by the Ethereum Foundation.↩︎
Supported by the National Natural Science Foundation of China under Grant 62332009 and Grant 12347104, the Innovation Program for Quantum Science and Technology under Grant 2021ZD0302901, the National Natural Science Foundation of China (NSFC)/Research Grants Council of Hong Kong (RGC) Joint Research Scheme under Grant 12461160276, the Natural Science Foundation of Jiangsu Province under BK20243060, and the New Cornerstone Science Foundation.↩︎
Supported by the National Natural Science Foundation of China under Grant 62332009 and Grant 12347104, the Innovation Program for Quantum Science and Technology under Grant 2021ZD0302901, the National Natural Science Foundation of China (NSFC)/Research Grants Council of Hong Kong (RGC) Joint Research Scheme under Grant 12461160276, the Natural Science Foundation of Jiangsu Province under BK20243060, and the New Cornerstone Science Foundation.↩︎
Partially supported by the Ethereum Foundation.↩︎
Supported by the National Natural Science Foundation of China under Grant 62332009 and Grant 12347104, the Innovation Program for Quantum Science and Technology under Grant 2021ZD0302901, the National Natural Science Foundation of China (NSFC)/Research Grants Council of Hong Kong (RGC) Joint Research Scheme under Grant 12461160276, the Natural Science Foundation of Jiangsu Province under BK20243060, and the New Cornerstone Science Foundation.↩︎
Supported by the National Natural Science Foundation of China under Grant 62332009 and Grant 12347104, the Innovation Program for Quantum Science and Technology under Grant 2021ZD0302901, the National Natural Science Foundation of China (NSFC)/Research Grants Council of Hong Kong (RGC) Joint Research Scheme under Grant 12461160276, the Natural Science Foundation of Jiangsu Province under BK20243060, and the New Cornerstone Science Foundation.↩︎

Quantum and Classical Communication Complexity of Permutation-Invariant FunctionsQuantum and Classical Communication Complexity of Permutation-Invariant Functions

Abstract

1 Introduction↩︎

1.1 Our Contribution↩︎

1.3 Proof Techniques↩︎

1.4 Comparison with previous work↩︎

1.5 Organization↩︎

2 Preliminaries↩︎

2.1 Boolean Functions↩︎

2.2 Communication Complexity Model↩︎

2.3 Permutation-Invariant Functions↩︎

3 Polynomial Equivalence on Communication Complexity of Permutation-Invariant Functions↩︎

3.1 Quantum Communication Complexity Lower Bound↩︎

3.2 Randomized and Quantum Communication Complexity Upper Bound↩︎

4 Log-Rank Conjecture for Permutation-Invariant Functions↩︎

5 Log-Approximate-Rank Conjecture for Permutation-Invariant Functions↩︎

6 Conclusion↩︎

Appendices Organization↩︎

7 Extended Preliminaries↩︎

7.1 Pattern Matrix Method and Approximate Degree↩︎

7.2 Rank↩︎

7.3 Approximate Rank↩︎

7.4 Sampling in Communication Model↩︎

7.5 Quantum Amplitude Amplification↩︎

8 Quantum and Randomized Communication Complexity of Permutation-Invariant Functions↩︎

8.1 The Lower Bound on Quantum Communication Complexity↩︎

8.2 Quantum Upper Bound of Set-Inclusion Problem↩︎

9 Log-Approximate-Rank Conjecture of Permutation-Invariant Functions↩︎

10 Communciation Complexity of Gap-Hamming-Distance Problem↩︎

Acknowledgement↩︎

References↩︎

Subjects

Updated on Academus

Quantum and Classical Communication Complexity of Permutation-Invariant FunctionsQuantum and Classical Communication Complexity of Permutation-Invariant Functions

Abstract

1 Introduction↩︎

1.1 Our Contribution↩︎

1.2 Related Work↩︎

1.3 Proof Techniques↩︎

1.4 Comparison with previous work↩︎

1.5 Organization↩︎

2 Preliminaries↩︎

2.1 Boolean Functions↩︎

2.2 Communication Complexity Model↩︎

2.3 Permutation-Invariant Functions↩︎

3 Polynomial Equivalence on Communication Complexity of Permutation-Invariant Functions↩︎

3.1 Quantum Communication Complexity Lower Bound↩︎

3.2 Randomized and Quantum Communication Complexity Upper Bound↩︎

4 Log-Rank Conjecture for Permutation-Invariant Functions↩︎

5 Log-Approximate-Rank Conjecture for Permutation-Invariant Functions↩︎

6 Conclusion↩︎

Appendices Organization↩︎

7 Extended Preliminaries↩︎

7.1 Pattern Matrix Method and Approximate Degree↩︎

7.2 Rank↩︎

7.3 Approximate Rank↩︎

7.4 Sampling in Communication Model↩︎

7.5 Quantum Amplitude Amplification↩︎

8 Quantum and Randomized Communication Complexity of Permutation-Invariant Functions↩︎

8.1 The Lower Bound on Quantum Communication Complexity↩︎

8.2 Quantum Upper Bound of Set-Inclusion Problem↩︎

9 Log-Approximate-Rank Conjecture of Permutation-Invariant Functions↩︎

10 Communciation Complexity of Gap-Hamming-Distance Problem↩︎

Acknowledgement↩︎

References↩︎

Subjects

Updated on Academus