Quantum multiparty communication complexity and circuit lower bounds
- 1 February 2009
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 19 (1) , 119-132
Abstract
We 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/2k), its classical k-party communication is Ω(n/2k/2). Finding such an f would allow us to prove strong classical lower bounds for k ≥ log n players and make progress towards solving a major open question about symmetric circuits.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Quantum computing, postselection, and probabilistic polynomial-timeProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2005
- Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval2005
- Quantum FingerprintingPhysical Review Letters, 2001
- The BNS-Chung criterion for multi-party communication complexitycomputational complexity, 2000
- Communication Complexity1997
- On ACCcomputational complexity, 1994
- The Bns Lower-Bound for Multiparty Protocols Is Nearly OptimalInformation and Computation, 1994
- Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offsJournal of Computer and System Sciences, 1992
- On the power of small-depth threshold circuitscomputational complexity, 1991
- Quasi‐random classes of hypergraphsRandom Structures & Algorithms, 1990