This work was supported in part by ACI Securite Informatique SI/03 511 and ANR AlgoQP grants of the French Research Ministry, and also partially supported by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate under Contract Number 015848.rnWe define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result, we show that if the quantum k-party communication complexity of a function f is Ω(n/2~k), its classical k-party communication is Ω(n/2~(k/2)). Finding such an f would allow us to prove strong classical lower bounds for k ≥ logn players and make progress towards solving a major open question about symmetric circuits.
展开▼
