Physics – Quantum Physics
Scientific paper
2007-09-29
Physics
Quantum Physics
Scientific paper
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 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(x_1 * y_1, x_2 * y_2, ..., x_n * y_n), where f is a_symmetric_ Boolean function on n Boolean inputs, and x_i, y_i 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(x_1, y_1), g(x_2, y_2), ..., g(x_n, y_n)), where x_i and y_i 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=\Omega(\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.
Shi Yaoyun
Zhu Yufan
No associations
LandOfFree
Quantum communication complexity of block-composed functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum communication complexity of block-composed functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum communication complexity of block-composed functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-721535