Randomness amplification (8 devices): Difference between revisions

Jump to navigation Jump to search
(Created page with "Randomness amplification is a protocol for Quantum Random Number Generator which takes a string from a weak source of randomness - one which contains correlations and may...")
 
Line 63: Line 63:
==Pseudocode==
==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.
Write
153

edits

Navigation menu