Randomness amplification (8 devices): Difference between revisions

Randomness amplification (8 devices) (edit)

Revision as of 00:14, 5 November 2019

116 bytes added , 5 November 2019

→‎Pseudocode

Rhea

Write

153

edits

@@ Line 63: / Line 63: @@
 ==Pseudocode==
-\hspace*{\algorithmicindent} \textbf{Input}: $t$, $\delta$, $N$, $\textrm{Ext}$\\
+'''Input''': <math>t</math>, <math>\delta</math>, <math>N</math>, <math>\textrm{Ext}</math>
-\hspace*{\algorithmicindent} \textbf{Output}: $u$
-\begin{algorithmic}[1]
-\State split $t$ into $t=(t^{(1)},t^{(2)},t^{(3)},t^{(4)})$ where $|t^{(3)}|=\log{N}$, $|t^{(2)}|=N|t^{(1)}|$ and $|t^{(1)}|,|t^{(4)}|$ are determined by $\textrm{Ext}$
-\State $n\leftarrow\big\lfloor\frac{|t^{(1)}|}{2}\big\rfloor$
-\State initialise arrays $r$, $s$ of length $n$
-\State initialise (2D) arrays $R$, $S$ of length $N$ (with elements of length $n$)
-\State \textrm{measurementBlock}($D^{(1)}$,$t^{(1)}$,$n$,$s$,$r$)
-\State $\hat{B}\leftarrow$\textrm{estimateBellViolation$(n,s,r)$}
-\If{$\hat{B}>\delta$}
-    \State \textbf{abort}
-\EndIf
-\For{$k\leftarrow1$ to $N$}
-    \State \textrm{measurementBlock}($D^{(2)},t^{(2)}_{nk:n(k+1)},n,S[k],R[k]$)
-\EndFor
-\State $t^{(3)}\leftarrow$ cast $t^{(3)}$ as an integer
-\State $\hat{B}\leftarrow$\textrm{estimateBellViolation$(n,S[t^{(3)}],R[t^{(3)}])$}
-\If{$\hat{B}>\delta$}
-    \State \textbf{abort}
-\EndIf
-\State $u\leftarrow$\textrm{Ext}($r,R[t^{(3)}],t^{(4)}$)
-\end{algorithmic}
-With the following subroutines defined:\\
+'''Output''': <math>u</math>
-\textrm{measurementBlock}\\
-\hspace*{\algorithmicindent} \textbf{Input}: $D$, $t$, $n$, $s$, $r$
-\begin{algorithmic}[1]
-\For{$i\leftarrow1$ to $n$}
-    \State prepare state $\ket{\Psi}=\frac{1}{\sqrt{2}}\big(\ket{\phi_-}\ket{\Tilde{\phi}_+} + \ket{\psi_+}\ket{\Tilde{\psi}_-}\big)$ and share across $D$
-    \For{$j\leftarrow1$ to 4}
-        \State $x_{i,j}\leftarrow t_{4i+j}$
-        \State $a_{i,j}\leftarrow$ measurement from device $j$ in basis \textrm{bases}[$x_{i,j}$]
-    \EndFor
-    \State $s[i]\leftarrow(x_{i,1},x_{i,2},x_{i,3},x_{i,4})$
-    \State $r[i]\leftarrow(a_{i,1},a_{i,2},a_{i,3},a_{i,4})$
-\EndFor
-\end{algorithmic}
-\textrm{estimateBellViolation}\\
+* split <math>t</math> into <math>t=(t^{(1)},t^{(2)},t^{(3)},t^{(4)})</math> where <math>|t^{(3)}|=\log{N}, |t^{(2)}|=N|t^{(1)}|</math> and <math>|t^{(1)}|,|t^{(4)}|</math> are determined by <math>\textrm{Ext}</math>
-\hspace*{\algorithmicindent} \textbf{Input}: $n$, $s$, $r$\\
+* <math>n\leftarrow\big\lfloor\frac{|t^{(1)}|}{2}\big\rfloor</math>
-\hspace*{\algorithmicindent} \textbf{Output}: $\hat{B}$
+* initialise arrays <math>r</math>, <math>s</math> of length <math>n</math>
-\begin{algorithmic}[1]
+* initialise (2D) arrays <math>R</math>, <math>S</math> of length <math>N</math> (with elements of length <math>n</math>)
-\State $\hat{B}\leftarrow0$
+* <math>\textrm{measurementBlock}</math>(<math>D^{(1)}, t^{(1)}, n, s, r</math>)
-\For{$i\leftarrow1$ to $n$}
+* <math>\hat{B}\leftarrow</math><math>\textrm{estimateBellViolation}</math><math>(n,s,r)</math>
-    \State $x_1,x_2,x_3,x_4\leftarrow s[i]$
+* If <math>\hat{B}>\delta</math>:
-    \State $a_1,a_2,a_3,a_4\leftarrow r[i]$
+** <math>\textbf{abort}</math>
-    \State $\hat{B}\leftarrow\hat{B}+\frac{1}{n}\big(\mathbb{I}_{\bigoplus_{j=1}^4x_j=0}\mathbb{I}_{\bigoplus_{a=1}^4u_j=1}+\mathbb{I}_{\bigoplus_{j=1}^4x_j=1}\mathbb{I}_{\bigoplus_{a=1}^4u_j=0}\big)$
+* For <math>k\leftarrow1</math> to <math>N</math>:
-\EndFor
+** <math>\textrm{measurementBlock}</math>(<math>D^{(2)},t^{(2)}_{nk:n(k+1)},n,S[k],R[k]</math>)
-\end{algorithmic}
+* <math>t^{(3)}\leftarrow</math> cast <math>t^{(3)}</math> as an integer
+* <math>\hat{B}\leftarrow\textrm{estimateBellViolation}(n,S[t^{(3)}],R[t^{(3)}])</math>
+* If <math>\hat{B}>\delta</math>:
+** <math>\textbf{abort}</math>
+* <math>u\leftarrow\textrm{Ext}(r,R[t^{(3)}],t^{(4)}</math>)
-\rule{\textwidth}{2pt}
+With the following subroutines defined:
-\section*{Further Information}
-\hyperlink{https://www.nature.com/articles/ncomms11345}{Brandão \emph{et al}} also provide a protocol which achieves randomness amplification using only four devices, however the randomness extractor required to produce multiple bits is only defined implicitly (i.e. we can prove that it exists but have not yet been able to construct it). A randomness extractor does exist that is able to produce a single private bit.
+'''<math>\textrm{measurementBlock}</math>'''
+'''Input''': <math>D, t, n, s, r</math>
+* For <math>i\leftarrow1</math> to <math>n</math>:
+** prepare state <math>|\Psi\rangle=\frac{1}{\sqrt{2}}\big(|\phi_-\rangle|\tilde{\phi}_+\rangle + |\psi_+\rangle|\tilde{\psi}_-\rangle\big)</math> and share across <math>D</math>
+** <math>j\leftarrow1</math> to 4:
+*** <math>x_{i,j}\leftarrow t_{4i+j}</math>
+*** <math>a_{i,j}\leftarrow</math> measurement from device <math>j</math> in basis \textrm{bases}[<math>x_{i,j}</math>]
+** <math>s[i]\leftarrow(x_{i,1},x_{i,2},x_{i,3},x_{i,4})</math>
+** <math>r[i]\leftarrow(a_{i,1},a_{i,2},a_{i,3},a_{i,4})</math>
+'''<math>\textrm{estimateBellViolation}</math>'''
+'''Input''': <math>n, s, r</math>
+'''Output''': <math>\hat{B}</math>
+* <math>\hat{B}\leftarrow0</math>
+* For <math>i\leftarrow1</math> to <math>n</math>:
+** <math>x_1,x_2,x_3,x_4\leftarrow s[i]</math>
+** <math>a_1,a_2,a_3,a_4\leftarrow r[i]</math>
+** <math>\hat{B}\leftarrow\hat{B}+\frac{1}{n}\big(\mathbb{I}_{\bigoplus_{j=1}^4x_j=0}\mathbb{I}_{\bigoplus_{a=1}^4u_j=1}+\mathbb{I}_{\bigoplus_{j=1}^4x_j=1}\mathbb{I}_{\bigoplus_{a=1}^4u_j=0}\big)</math>
+==Further Information==
+[https://www.nature.com/articles/ncomms11345 Brandão et. al.] also provide a protocol that achieves randomness amplification using only four devices, however, the randomness extractor required to produce multiple bits is only defined implicitly (i.e. we can prove that it exists but have not yet been able to construct it). A randomness extractor does exist that is able to produce a single private bit.