Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds

Details Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds

2004-12-11

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

Physics

Quantum Physics

17 pages, appears at FSTTCS '04

Scientific paper

We derive lower bounds for tradeoffs between the communication C and space S for communicating circuits. The first such bound applies to quantum circuits. If for any function f with image Z the multicolor discrepancy of the communication matrix of f is 1/2^d, then any bounded error quantum protocol with space S, in which Alice receives some l inputs, Bob r inputs, and they compute f(x_i,y_j) for the lr pairs of inputs (x_i,y_j) needs communication C=\Omega(lrd \log |Z|/S). In particular, n\times n-matrix multiplication over a finite field F requires C=\Theta(n^3\log^2 |F|/S). We then turn to randomized bounded error protocols, and derive the bound C=\Omega(n^3/S^2) for Boolean matrix multiplication, utilizing a new direct product result for the one-sided rectangle lower bound on randomized communication complexity. This implies a separation between quantum and randomized protocols.

Affiliated with

Also associated with

No associations

Rating

Quantum and Classical Communication-Space Tradeoffs from Rectangle 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 and Classical Communication-Space Tradeoffs from Rectangle Bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-263952