Questions tagged [communication-complexity]
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)
3
questions
8
votes
2
answers
463
views
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
...
- 17.7k
7
votes
1
answer
134
views
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 ...
- 2,871
3
votes
1
answer
194
views
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 ...
- 31