Communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. It was introduced by Andrew Yao in 1979. (Wikipedia)
Questions tagged [communication-complexity]
3 questions
9
votes
2 answers
Resources for Quantum Communication Complexity
I recently came to know about this interesting topic of "communication complexity". In simple words, Wikipedia defines it as:
In theoretical computer science, communication complexity studies the
amount of communication required to solve a…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
7
votes
1 answer
Could quantum computers be useful for sending encrypted information over a classical channel?
A quantum computer running Shor's algorithm would be famously useful for decrypting information encrypted by many classical public-key cryptography algorithms. Is there any reason (either a specific proposed protocol or a general heuristic argument)…
tparker
- 2,939
- 13
- 26
3
votes
1 answer
Complexity of quantum circuits in a specific protocol
Consider the following simultaneous communication problem. Alice and Bob do not share any
entanglement or any common randomness, and cannot communicate directly with each other. As
inputs, $x$ is given to Alice, and $y$ is given to Bob, where $x, y…
Shlomo
- 31
- 2