Strong direct product theorems for quantum communication and query complexity

Details Strong direct product theorems for quantum communication and query complexity Strong direct product theorems for quantum communication and query complexity

2010-11-22

arxiv.org/abs/1011.4935v1

Computer Science

Computational Complexity

Scientific paper

A strong direct product theorem (SDPT) states that solving n instances of a problem requires Omega(n) times the resources for a single instance, even to achieve success probability exp(-Omega(n)). We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by the generalized discrepancy method, the strongest technique in that model. We prove that quantum query complexity obeys an SDPT whenever the query lower bound for a single instance is proved by the polynomial method, one of the two main techniques in that model. In both models, we prove the corresponding XOR lemmas and threshold direct product theorems.

Affiliated with

Also associated with

No associations

Rating

Strong direct product theorems for quantum communication and query complexity 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 Strong direct product theorems for quantum communication and query complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strong direct product theorems for quantum communication and query complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-586401