39 lines
No EOL
3.2 KiB
Markdown
39 lines
No EOL
3.2 KiB
Markdown
# 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 |