garden/non-local-box.md

Non-Local Box

• quantum-computing
• `\begin{bmatrix} \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 \end{bmatrix}`
• the above matrix is an NLB s.t. `a \oplus b` = `x \wedge y`
• if Alice holds A and X and Bob holds B and Y, then for each user the probability of each output is `\frac{1}{2}`
  • from both players' PoV, their output (A and B respectively) is purely random, regardless of X and Y
• we assume that no communication was involved, i.e. Alice learns nothing about Y or B and Bob learns nothing about X or A
• cryptography
  • NLBs can be used to solve the socialist-millionaires-problem
  • `f : \left\{0,1\right\}^n \times \left\{0,1\right\}^n \to \left\{0,1\right\}`
  • we have the polynomials on bits
    • `\mathsf{And} = x \cdot y`
    • `\mathsf{Or} = x + y + x \cdot y`
    • `\mathsf{Not} = 1 + x`
  • any function on bits can be decomposed into a sum of monomials `f\left(x,y\right) = \sum_{i=1}^{2^n} P_i\left(x\right) \cdot Q_i\left(y\right)`
    • `2^n` because each possible combination of `x` has only one monomial in `y`
    • this is the fourier-tranform somehow? it's related to fourier-spectra?
  • notably, Alice can compute all `P_i` to get a bitstring `\alpha` and Bob can compute all `Q_i` to get a bitstring `\beta`
    • these bitstrings are exponentially long (`2^n` bits instead of `n` bits)
  • this makes `f = \sum\alpha_i \cdot \beta_i = \vec{\alpha} \cdot \vec{\beta}`
  • now we apply the NLB: we want to turn the dot product of our single bit into a parity
  • if we have `\left(a_1,b_1\right) = \operatorname{NLB}_{\mathsf{And}}\left(\alpha_1,\beta_1\right)` and `\left(a_2,b_2\right) = \operatorname{NLB}_{\mathsf{And}}\left(\alpha_2,\beta_2\right)`, then the dot product `\alpha \cdot \beta` can be rewritten
    • `\alpha_1 \beta_1 + \alpha_2 \beta_2`
    • `a_1 \oplus b_1 + a_2 \oplus b_2`
    • `a_1 + b_1 + a_2 + b+2`
    • `\left(a_1 \oplus a_2\right) + \left(b_1 \oplus b_2\right)`
  • we can do the NLB exponentially-many times to get `\vec{a}` and `\vec{b}`
    • this prevents either party from learning anything about the original `\vec{\alpha}` or `\vec{\beta}`
  • we then do local computation following the rewrite rule for dot products
    • `r = \bigoplus \vec{a}`
    • `s = \bigoplus \vec{b}`
  • and we just need Bob to send `s` to Alice, and she computes `r \oplus s`, and now she knows `f\left(x,y\right)` without learning `y`
• three party case (real implementation)
  • promise that `x + y + z \equiv 0 \mod 2`
  • for an input `000`, the output is `000` or `011` or `101` or `110`
  • for the other three inputs, the output is `001` or `010` or `100` or `111`
  • for each party,
    • if they start with a 0, apply hadamard-gate and measure
    • if they start with a 1, phase by `i` and measure
  • the parity of the output result reveals the And