Write
153
edits
Certified infinite randomness expansion: Difference between revisions
Certified infinite randomness expansion (edit)
Revision as of 18:40, 4 November 2019
, 4 November 2019no edit summary
(Created page with "Randomness expansion is a protocol for Quantum Random Number Generator which takes as input a private, uniformly random string and outputs a longer string which is (close...") |
No edit summary |
||
| Line 44: | Line 44: | ||
* <math>b_i</math>: measurement result for device 2 on iteration <math>i</math> | * <math>b_i</math>: measurement result for device 2 on iteration <math>i</math> | ||
* <math>r</math>: string (or array) of measurement results | * <math>r</math>: string (or array) of measurement results | ||
* <math>u_i</math>: randomness expanded string after iteration | * <math>u_i</math>: randomness expanded string after iteration <math>i</math> | ||
* <math>u</math>: final randomness expanded string | * <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> | * <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. | * Requires eight measurement devices. | ||
* Devices can be untrusted. | * Devices can be untrusted. | ||
* Length of expanded string unbounded: for | * 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>. | * Uniformity of final string dependent on input length - the distance of the output from uniform is <math>\exp(-\Omega(m^{1/3}))</math>. | ||
==Pseudocode== | ==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> | <div style='text-align: right;'>''contributed by Neil Mcblane''</div> | ||