# 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