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)

Filter by
Sorted by
Tagged with
3
votes
1answer
81 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 ...
6
votes
1answer
73 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 ...
8
votes
2answers
258 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 ...