Abstract:

    A central 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 standard two-way, interactive model. The answer is widely conjectured to be ``No''. In 2002, Razborov proved the conjecture for so far the most general class of functions F(x, y)=f(x1 * y1, x2 * y2, ..., xn * yn), where f is a symmetric Boolean function on n Boolean inputs, and xi, yi are the i'th bit of x and y, respectively.
     We prove the conjecture for a much broader class of functions. Each of those functions F(x, y) is obtained from what we call the ``block-composition'' of a ``building block'' g : {0, 1}^k by {0, 1}^k --> {0, 1}, with an f : {0, 1}^n -->{0, 1}, such that F(x, y) = f( g(x1, y1), g(x2, y2), ..., g(xn, yn) ), where xi and yi are the i'th k-bit block of x and y, respectively.
      We show that as long as g itself is ``hard'' enough, its block-composition with an _arbitrary_ f has polynomially related quantum and classical communication complexities. Our approach gives an alternative proof for Razborov's result (albeit with slightly weaker parameters), and establishes new quantum lower bounds. For example, when g is the Inner Product function and k=Omega(log n), for _any_ f, the classical _deterministic_ communication complexity of the block-composition is asymptotically at most the quantum complexity to the power of 7.
       A joint work with my student Yufan Zhu.
 

Short Bio:

Yaoyun Shi received his undergraduate degree from Beijing University in 1997, and his PhD from Princeton University in 2001, both in computer science. After a year of postdoctoral research at California Institute of Technology, he joined University of Michigan, Ann Arbor, as an assistant professor in 2002. In 2004, he received a Career Award from the National Science Foundation of the United States. His research interests are the theory of computation and quantum information processing.