= Communication complexity
{wiki}
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> $f(x,y)$, a one-way exact protocol has the receiver output $f$ 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.
Back to article page
