3.2 KiB
3.2 KiB
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)`
- Alice and Bob both have $
- 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}`
- Alice adds an ancilla qubit
- 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
- take a function
- 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 gets no better than sending
- this forces parity checking to not be asymptotically better than classical
- same thing but we want to check