A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical ones for computing a {\em total} Boolean function in the two-party interactive model. Razborov's result ({\em Izvestiya: Mathematics}, 67(1):145--159, 2002) implies the conjectured negative answer for functions
F of the following form:
F(x,y)=fn(x1⋅y1,x2⋅y2,...,xn⋅yn), where
fn is a {\em symmetric} Boolean function on
n Boolean inputs, and
xi,
yi are the
i'th bit of
x and
y, respectively. His proof critically depends on the symmetry of
fn. We develop a lower-bound method that does not require symmetry and prove the conjecture for a broader class of functions. Each of those functions
F is the ``block-composition'' of a ``building block''
gk:{0,1}k×{0,1}k→{0,1}, and an
fn:{0,1}n→{0,1}, such that
F(x,y)=fn(gk(x1,y1),gk(x2,y2),...,gk(xn,yn)), where
xi and
yi are the
i'th
k-bit block of
x,y∈{0,1}nk, respectively. We show that as long as g_k itself is "hard'' enough, its block-composition with an arbitrary f_n has polynomially related quantum and classical communication complexities. For example, when g_k is the Inner Product function with k=\Omega(\log n), the deterministic communication complexity of its block-composition with any f_n is asymptotically at most the quantum complexity to the power of 7.
An open problem in communication complexity proposed by several authors is to prove that for every Boolean function
f, the task of computing
f(x∧y) has polynomially related classical and quantum bounded-error complexities. We solve a variant of this question. For every
f, we prove that the task of computing, on input \mbox{
x and
y,} \emph{both} of the quantities
f(x∧y) and
f(x∨y) has polynomially related classical and quantum bounded-error complexities. We further show that the quantum bounded-error complexity is polynomially related to the classical deterministic complexity and the block sensitivity of
f. This result holds regardless of prior entanglement.
This dissertation is motivated by the following fundamental questions: (a) are there any exponential gaps between quantum and classical communication complexities? (b) what is the role of entanglement in assisting quantum communications? (c) how to characterize the nonlocality of quantum operations? We study four specific problems below. 1. The communication complexity of the Hamming Distance problem. The Hamming Distance problem is for two parties to determine whether or not the Hamming distance between two n-bit strings is more than a given threshold. We prove tighter quantum lower bounds in the general two-party, interactive communication model. We also construct an efficient classical protocol in the more restricted Simultaneous Message Passing model, improving previous results. 2. The Log-Equivalence Conjecture. A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical ones for computing a total Boolean function in the two-party, interactive model. The answer is believed to be No. Razborov proved this conjecture for the most general class of functions so far. We prove this conjecture for a broader class of functions that we called block-composed functions. Our proof appears to be the first demonstration of the dual approach of the polynomial method in proving new results. 3. Classical simulations of bipartite quantum measurement. We define a new ix concept that measures the nonlocality of bipartite quantum operations. From this measure, we derive an upper bound that shows the limitation of entanglement in reducing communication costs. 4. The maximum tensor norm of bipartite superoperators. We define a maximum tensor norm to quantify the nonlocality of bipartite superoperators. We show that a bipartite physically realizable superoperator is bi-local if and only if its maximum tensor norm is 1. Furthermore, the estimation of the maximum tensor norm can also be used to prove quantum lower bounds on communication complexities.
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).
It is known that the classical and quantum query complexities of a total Boolean function f are polynomially related to the degree of its representing polynomial, but the optimal exponents in these relations are unknown. We show that the non-deterministic quantum query complexity of f is linearly related to the degree of a "non-deterministic" polynomial for f. We also prove a quantum-classical gap of 1 vs. N for non-deterministic query complexity for a total f. In the case of quantum communication complexity there is a (partly undetermined) relation between the complexity of f and the logarithm of the rank of its communication matrix. We show that the non-deterministic quantum communication complexity of f is linearly related to the logarithm of the rank of a non-deterministic version of the communication matrix and that it can be exponentially smaller than its classical counterpart.
We show a new duality between the polynomial margin complexity of
f and the discrepancy of the function
f∘XOR, called an
XOR function. Using this duality, we develop polynomial based techniques for understanding the bounded error (
BPP) and the weakly-unbounded error (
PP) communication complexities of
XOR functions. We show the following. A weak form of an interesting conjecture of Zhang and Shi (Quantum Information and Computation, 2009) (The full conjecture has just been reported to be independently settled by Hatami and Qian (Arxiv, 2017). However, their techniques are quite different and are not known to yield many of the results we obtain here). Zhang and Shi assert that for symmetric functions
f:{0,1}n→{−1,1}, the weakly unbounded-error complexity of
f∘XOR is essentially characterized by the number of points
i in the set
{0,1,…,n−2} for which
Df(i)=Df(i+2), where
Df is the predicate corresponding to
f. The number of such points is called the odd-even degree of
f. We show that the
PP complexity of
f∘XOR is
Ω(k/log(n/k)). We resolve a conjecture of a different Zhang characterizing the Threshold of Parity circuit size of symmetric functions in terms of their odd-even degree. We obtain a new proof of the exponential separation between
PPcc and
UPPcc via an
XOR function. We provide a characterization of the approximate spectral norm of symmetric functions, affirming a conjecture of Ada et al. (APPROX-RANDOM, 2012) which has several consequences. Additionally, we prove strong
UPP lower bounds for
f∘XOR, when
f is symmetric and periodic with period
O(n1/2−ε), for any constant
ε>0.