Editing Certified infinite randomness expansion

Jump to navigation Jump to search
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.

Latest revision Your text
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>i</math>
* <math>u_i</math>: randomness expanded string after iteration $i$
* <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 <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>.
* 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>.
* 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 <math>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>A_{bases}[0]</math>
**** <math>b_j\leftarrow</math> measurement results from device <math>D_2</math> in basis <math>B_{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>A_{bases}[x_i]</math>
*** set device <math>D_2</math> to <math>A_{bases}[0],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>A_{bases}[0]</math>
**** <math>b_j\leftarrow</math> measurement results from device <math>D_2</math> in set basis <math>B_{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</math> 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>, <math>s</math> of length <math>n</math>
* <math>w\leftarrow0</math>
* For <math>i\leftarrow1</math> 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</math> in basis <math>A_{bases}[x_i]</math>
** <math>b_i\leftarrow</math> measurement result from device <math>D_2</math> in basis <math>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 <math>\{0...n/N-1\}</math> (seed using <math>t^{(2)}</math>)
* <math>\gamma_2\leftarrow</math> random number in range <math>\{1...\sqrt{N}-1\}</math> (seed using <math>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>
==Further Information==
==References==
<div style='text-align: right;'>''contributed by Neil Mcblane''</div>
<div style='text-align: right;'>''contributed by Neil Mcblane''</div>
Please note that all contributions to Quantum Protocol Zoo may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Quantum Protocol Zoo:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel Editing help (opens in new window)
Retrieved from "https://wiki.veriqloud.fr/index.php?title=Certified_infinite_randomness_expansion"