Strong direct product theorems for quantum communication and query complexity

Understand

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.