[QIP-Sem] QIP seminar, Mon 10/15, 4pm, 36-428, Yaoyun Shi

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 10/15 at 4pm in 36-428
-------------------------------------------------

Yaoyun Shi (Michigan)

Quantum communication complexity of block-composed functions

Abstract:

A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical protocols on total Boolean functions in the standard two-party interactive model. The answer appears to be "No''. In 2002, Razborov proved this 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. His elegant proof critically depends on the symmetry of f.

 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(x, y) is obtained by 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(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 a slightly weaker parameter), and establishes new quantum lower bounds. For example, when g is the Inner Product function for k= Ω(log n), the deterministic communication complexity of its block-composition with any f is asymptotically at most the quantum complexity to the power of 7.
 This is a joint work with my student Yufan Zhu. 

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem