Title: Unbounded-Error Quantum Communication Complexity and Query Complexity
Speaker: Harumichi Nishimura
Date: Wednesday, March 26, 2008 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Communication complexity (CC) and query complexity (QC) are well-studied computation models in quantum and classical complexity theory. In this talk, I discuss quantum CC and QC of Boolean functions in the unbounded-error setting. They can be characterized in terms of two complexity measures that are studied so far. In particular, it can be shown that both of them are exactly the half of their classical correspondences albeit their characterizations are completely different.
The results on CC are joint work with K. Iwama, R. Raymond, S. Yamashita and those on QC are joint work with A. Montanaro and R. Raymond.