Randomness amplification (8 devices): Difference between revisions

Jump to navigation Jump to search

Randomness amplification (8 devices) (edit)

Revision as of 00:14, 5 November 2019

116 bytes added ,  5 November 2019
→‎Pseudocode
(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.
Rhea
Write
153

edits

Retrieved from "https://wiki.veriqloud.fr/index.php?title=Special:MobileDiff/4133"

Navigation menu