41 lines
3 KiB
Markdown
41 lines
3 KiB
Markdown
# 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
|