Communication complexity studies how much information distributed parties must exchange to compute a function of their separately held inputs. Local computation is free; the resource being counted is communicated bits or qubits, with the allowed shared randomness, quantum entanglement or other correlations specified separately. For a Boolean function , a one-way exact protocol has the receiver output correctly for every input after a single message. One-bit computation using Popescu–Rohrlich boxes shows that this resource measure changes drastically if ideal superquantum boxes are available.
Articles by others on the same topic
Communication complexity is a branch of computational complexity theory that studies the amount of communication required to solve a problem when the input is distributed among multiple parties. It specifically investigates how much information needs to be exchanged between these parties to reach a solution, given that each party has access only to part of the input. Here are some key points about communication complexity: 1. **Setting**: In a typical model, there are two parties (often referred to as Alice and Bob), each having their own input.