# Quantum Communication Complexity

- [[quantum-computing]]
- $`\operatorname{CCC}\left(f\right)`$: number of bits sent to compute the bit $`f\left(x,y\right)`$ jointly
- $`\operatorname{QCC}\left(f\right)`$: number of bits sent to compute the qubit $`f\left(x,y\right)`$ jointly
- $`\operatorname{QCC}^*\left(f\right)`$: number of bits sent to compute the qubit $`f\left(x,y\right)`$ jointly, allowing prior entanglement
- example problem: disjointness (classically)
  - Alice and Bob both have $`n`$-bit bitmasks
  - $`f\left(x,y\right)`$ reports whether there exists some index where both Alice and Bob's bitmasks are unset
  - cannot do better than the trivial protocol $`\Omega\left(n\right)`$
- disjointness (quantum)
  - take a function $`z \in \left\{0,1\right\}^n`$
  - $`z_i = 1`$ iff $`x_i = y_i = 0`$
  - reduced problem to "is there a $`1`$ somewhere" ([[quantum-search]])
  - this results in $`O\left(\sqrt{n}\lg n\right)`$ communication: Alice runs quantum search on $`z`$
  - Alice wants to query the oracle $`\sum \alpha_i \ket{i} \mapsto \sum \alpha_i \left(-1\right)^{z_i} \ket{i}`$
  - one round proceeds as such:
    - Alice adds an ancilla qubit $`\sum \alpha_i \ket{i} \mapsto \sum \alpha_i \ket{i}\ket{x_i}`$
    - Alice sends this entire quantum state to Bob, which is $`\lg n + 1`$ qubits
    - Bob computes the phase $`\mapsto \sum \alpha_i \left(-1\right)^{x_i \wedge y_i} \ket{i}\ket{x_i}`$
    - Bob sends this entire quantum state back to Alice, which is $`\lg n + 1`$ qubits
    - Alice can XOR in the ancilla qubit to produce $`\sum \alpha_i \left(-1\right)^{z_i} \ket{i}`$
  - we need $`O\left(\sqrt{n}\right)`$ rounds of these oracle queries, producing our communication bound
    - getting rid of the logarithm is doable but hard, outside the scope of my course
- this shows that getting a communication speedup is "as easy as" getting an algorithmic speedup
- parity
  - same thing but we want to check $`\left|\vec{x} \wedge \vec{y}\right|`$
  - parity checking has the same algorithmic complexity in quantum
  - assume there exists a protocol $`\mathcal{P}`$ that behaves as a [[unitary-operator]] s.t. we can map a state $`\ket{\vec{x}}\ket{0} \mapsto \ket{\vec{x}}\ket{\left|\vec{x} \wedge \vec{y}\right|}`$
    - this is a protocol that computes parity
  - Alice can run $`\mathcal{P}`$ on $`\sum_{\vec{x}} \ket{\vec{x}}\ket{0}`$ to produce $`\sum_{\vec{x}} \ket{\vec{x}}\ket{\left|\vec{x} \wedge \vec{y}\right|}`$
  - Alice can then map the latter register to the phase and produce a state $`\sum_{\vec{x}} \left(-1\right)^{\left|\vec{x} \wedge \vec{y}\right|} \ket{\vec{x}}\ket{\left|\vec{x} \wedge \vec{y}\right|}`$
  - Alice can run $`\mathcal{P}^{-1}`$ to produce a state $`\sum_{\vec{x}} \left(-1\right)^{\left|\vec{x} \wedge \vec{y}\right|} \ket{\vec{x}}`$
  - taking the Hadamard transform on this state will give Alice $`\ket{\vec{y}}`$
  - [[bernstein-vazirani]]
  - this implies that if there is a quantum protocol for jointly computing parity, there's a quantum protocol for sending a classical bitstring
    - this gets no better than sending $`n`$ classical bits in $`\frac{n}{2}`$ qubits ([[superdense-coding]])
    - you cannot do better
  - this forces parity checking to not be asymptotically better than classical