Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity
arXiv:1308.2450
Abstract
There are three different types of nondeterminism in quantum communication: i) $\nqp$-communication, ii) $\qma$-communication, and iii) $\qcma$-communication. In this \redout{paper} we show that multiparty $\nqp$-communication can be exponentially stronger than $\qcma$-communication. This also implies an exponential separation with respect to classical multiparty nondeterministic communication complexity. We argue that there exists a total function that is hard for $\qcma$-communication and easy for $\nqp$-communication. The proof of it involves an application of the pattern tensor method and a new lower bound for polynomial threshold degree. Another important consequence of this result is that nondeterministic rank can be exponentially lower than the discrepancy bound.
arXiv commentThis paper has been withdrawn by the author due to a crucial mistake in the main proof
References in corpus (5)
- Multiplayer XOR games and quantum communication complexity with clique-wise entanglement
- Composition theorems in communication complexity
- Nondeterministic Quantum Query and Quantum Communication Complexities
- On Arthur Merlin Games in Communication Complexity
- Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication