Quantum multiparty communication complexity and circuit lower bounds

Details Quantum multiparty communication complexity and circuit lower bounds Quantum multiparty communication complexity and circuit lower bounds

2005-04-12

arxiv.org/abs/quant-ph/0504087v1

Physics

Quantum Physics

Scientific paper

We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result of our simulation, we show that if the quantum k-party communication complexity of a function f is $\Omega(n/2^k)$, then its classical k-party communication is $\Omega(n/2^{k/2})$. Finding such an f would allow us to prove strong classical lower bounds for (k>log n) players and hence resolve a main open question about symmetric circuits. Furthermore, we prove that for the Generalized Inner Product (GIP) function, the quantum model is exponentially more efficient than the classical one. This provides the first exponential separation for a total function between any quantum and public coin randomized communication model.

Affiliated with

Also associated with

No associations

Rating

Quantum multiparty communication complexity and circuit lower bounds 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 multiparty communication complexity and circuit lower bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum multiparty communication complexity and circuit lower bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-350538