Certified infinite randomness expansion: Difference between revisions

Certified infinite randomness expansion (edit)

Revision as of 17:40, 4 November 2019

4,659 bytes added , 4 November 2019

no edit summary

Rhea

Write

153

edits

@@ Line 44: / Line 44: @@
 * <math>b_i</math>: measurement result for device 2 on iteration <math>i</math>
 * <math>r</math>: string (or array) of measurement results
-* <math>u_i</math>: randomness expanded string after iteration $i$
+* <math>u_i</math>: randomness expanded string after iteration <math>i</math>
 * <math>u</math>: final randomness expanded string
 * <math>A_{bases}</math>: tuple of measurement bases for CHSH party A; <math>A_{bases}=\{X,Z\}</math>
@@ Line 74: / Line 74: @@
 * Requires eight measurement devices.
 * Devices can be untrusted.
-* Length of expanded string unbounded: for $k$ iterations the output length is a <math>k</math>-height tower of exponential - i.e. two to the power of two to the power of two ... to the power of <math>\Omega(m^{1/3})</math>.
+* Length of expanded string unbounded: for <math>k</math> iterations the output length is a <math>k</math>-height tower of exponential - i.e. two to the power of two to the power of two ... to the power of <math>\Omega(m^{1/3})</math>.
 * Uniformity of final string dependent on input length - the distance of the output from uniform is <math>\exp(-\Omega(m^{1/3}))</math>.
 ==Pseudocode==
+'''Input''': <math>t</math>, <math>l</math>, <math>C</math>, <math>k</math>, <math>N</math>
+'''Output''': <math>u</math>
+* <math>u_0\leftarrow t</math>
+* <math>i\leftarrow1</math> to <math>k</math>:
+** <math>u_i\leftarrow\textrm{clusterExpansion}(D_{i\mod2},u_{i-1},l,C,N)</math>
+* <math>u\leftarrow u_k</math>
+With the following subroutines defined:
+'''clusterExpansion'''
+'''Input''': <math>D</math>, <math>t</math>, <math>l</math>, <math>C</math>, <math>N</math>
+'''Output''': <math>u</math>
+* <math>u\leftarrow VVExpansion(\{D_1,D_2\},t,l,C)</math>
+* <math>u\leftarrow RUVExpansion(\{D_3,D_4\},u, N)</math>
+'''VVExpansion'''
+'''Input''': <math>D</math>, <math>t</math>, <math>l</math>, <math>C</math>
+'''Output''':  <math>u</math>
+* split <math>t</math> evenly into <math>(t^{(1)},t^{(2)})</math>
+* <math>\kappa\leftarrow\lceil10\log^2l\rceil</math>
+* <math>m\leftarrow\lceil Cl\log^2l\rceil</math>
+* initialise array <math>R,r</math> of length <math>m</math>
+* For <math>i\leftarrow1</math> to <math>m</math>:
+** set <math>R[i]=True</math> with probability <math>1/l</math> (seed with $t^{(1)}</math>)
+* For <math>i\leftarrow1</math> to <math>m</math> do initialise array <math>r_i</math> of length <math>\kappa</math>
+** If <math>R[i]</math>:
+*** For <math>j\leftarrow1</math> to <math>\kappa</math>:
+**** prepare state <math>|\Psi^+\rangle</math> and share across devices <math>D_1</math> and <math>D_2</math>
+**** <math>a_j\leftarrow</math> measurement results from device <math>D_1</math> in basis <math>\textrm{A\_bases}[0]</math>
+**** <math>b_j\leftarrow</math> measurement results from device <math>D_2</math> in basis <math>\textrm{A\_bases}[0]</math>
+**** If <math>a\neq b</math>:
+***** <math>\textbf{abort}</math>
+**** <math>r_i[j]\leftarrow(a_j,b_j)</math>
+** Else:
+*** <math>d\leftarrow0</math>
+*** <math>x_i\leftarrow</math> draw next random bit from <math>t^{(1)}</math>
+*** <math>y_i\leftarrow</math> draw next random bit from <math>t^{(1)}</math>
+*** set device <math>D_1</math> to <math>\textrm{A\_bases}[x_i]</math>
+*** set device <math>D_2</math> to <math>\{\textrm{A\_bases}[0],\textrm{B\_bases}[0]\}[y_i]</math>
+*** For <math>j\leftarrow1</math> to <math>\kappa</math>:
+**** prepare state <math>|\Psi^+\rangle</math> and share across devices <math>D_1</math> and <math>D_2</math>
+**** <math>a_j\leftarrow</math> measurement results from device <math>D_1</math> in set basis <math>\textrm{A\_bases}[0]</math>
+**** <math>b_j\leftarrow</math> measurement results from device <math>D_2</math> in set basis <math>\textrm{A\_bases}[0]</math>
+**** <math>r_i[j]\leftarrow(a_j,b_j)</math>
+**** <math>d\leftarrow d+(a_j\oplus b_j)/\kappa</math>
+*** If <math>x_j=0</math> and <math>y_j=0</math> and <math>d\neq0</math>:
+**** <math>\textbf{abort}</math>
+*** If <math>y_j=1</math> and <math>d>0.16</math>:
+**** <math>\textbf{abort}</math>
+*** If <math>x_j=0</math> and <math>y_j=0</math> and (<math>d<0.49</math> or <math>d>0.51</math>):
+**** <math>\textbf{abort}</math>
+** <math>r[i]\leftarrow r_i</math>
+* flatten <math>r</math> into array of bits
+* <math>u\leftarrow \textrm{Ext}\Big(r, t^{(2)}, \exp\big(2C|t^{(2)}|^{1/3}\big)\Big)</math>
+'''RUVExpansion'''
+'''Input''': <math>D</math>, <math>t</math>, <math>N</math>
+'''Output''': <math>u</math>
+* split <math>t$ evenly into <math>(t^{(1)},t^{(2)})</math>
+* <math>n\leftarrow\big\lfloor\frac{|t^{(1)}|}{2}\big\rfloor</math>
+* initialise arrays <math>r$, <math>s</math> of length <math>n</math>
+* <math>w\leftarrow0$
+* For <math>i\leftarrow1$ to <math>n</math>:
+** prepare state <math>|\Psi^+\rangle</math> and share across devices <math>D_1</math> and <math>D_2</math>
+** <math>x_i\leftarrow t^{(1)}_i</math>
+** <math>y_i\leftarrow t^{(1)}_{i+1}</math>
+** <math>a_i\leftarrow</math> measurement result from device <math>D_1$ in basis <math>\textrm{A\_bases}[x_i]</math>
+** <math>b_i\leftarrow</math> measurement result from device <math>D_2$ in basis <math>\textrm{B\_bases}[y_i]</math>
+** <math>s[i]\leftarrow(x_i,y_i)</math>
+** <math>r[i]\leftarrow(a_i,b_i)</math>
+** If <math>x_i\wedge y_i = a_i\otimes b_i</math>:
+*** <math>w\leftarrow w+1</math>
+* If <math>w < n\cos^2(\pi/8)-\frac{1}{2\sqrt{2}}\sqrt{n\log{n}}</math>:
+** \textbf{abort}
+* <math>\gamma_1\leftarrow</math> random number in range $\{0...n/N-1\}</math> (seed using $t^{(2)}</math>)
+* <math>\gamma_2\leftarrow</math> random number in range $\{1...\sqrt{N}-1\}</math> (seed using $t^{(2)}</math>)
+* initialise array <math>u</math> of length <math>\sqrt{N}</math>
+* For <math>i\leftarrow0</math> to <math>\sqrt{N}</math>:
+** <math>u[i]\leftarrow r[\gamma_1n/N+\gamma_2\sqrt{N}+i][0]</math>
 <div style='text-align: right;'>''contributed by Neil Mcblane''</div>