Editing Certified infinite randomness expansion

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 to) private and uniformly random. The protocol of [https://dl.acm.org/citation.cfm?id=2591873 Courdon and Yuen] enables randomness expansion of such an input using eight identical untrusted (i.e. provided by an adversary) measurement devices. The protocol is able to extend the string to any desired length as the output of one iteration can be fed back into another iteration by ensuring that at each stage the intermediate output is private from the devices which produced it and independent of the input that seeded it. Privacy and uniformity of the final output is dependent on the length of the input string.

Such a protocol is useful in the case where one already has access to a private source for true randomness, but whose use is prohibitively expensive or whose access is limited. By applying randomness expansion, it is possible to make this resource go further using potentially much cheaper or more simple methods.

Tags: [[: Category: Building Blocks|Building Blocks]], [[: Category: Quantum Functionality|Quantum Functionality]], [[:Category: Specific Task|Specific Task]] [[Category: Building Blocks]] [[Category: Quantum Functionality]] [[Category: Specific Task]] [[Category:Entanglement Distribution Network stage]]

==Assumptions==
* Quantum theory is correct.
* The measurement devices do not interact during measurements.
* The measurement devices are not correlated with the input string.

==Outline==

In this protocol, Alice has her initial private random string (the seed) and has been provided with eight identical measurement devices by Eve. Each of the devices has four settings and can produce two outputs. Alice first groups these devices into two `clusters', each containing four devices. With her seed as the initial input, she then iterates through a repeated procedure of passing a string to one of the clusters, performing a set of subroutines (defined below), then passing the output of this to the other cluster, where the same subroutines are carried out. She is free to stop the process at on any cluster output (though the whole protocol may abort prematurely if privacy can no longer be guaranteed).

Each passage through one cluster corresponds to the application of two sub-protocols: one to expand the length of the input string, and the other to generate a new, private string. The second step reduces the length of the output from the first, but by a significantly smaller factor so overall the length is still increased. As the output is private, it can be used to seed a repeated application of the protocol.

The clusters themselves are also used in pairs. First, two of the devices are used to apply the protocol of [https://arxiv.org/abs/1111.6054 Vazirani and Vidick]. First, Alice splits her input string into two equal portions and stashes the second half for later use. Using the first half as a source of randomness for making probabilistic decisions, she performs an adaptation of the [https://wiki.veriqloud.fr/index.php?title=Glossary CHSH game]. In this version, both of her devices can make four measurements, in the original game corresponding to:

* The honest measurement that party A would make given an input of 0
* The honest measurement that party A would make given an input of 1
* The honest measurement that party B would make given an input of 0
* The honest measurement that party B would make given an input of 1

Alice must first set up a series of `blocks` with size and count related to the confidence with which she seeks protocol correctness - these are effectively tables for storing her measurement results. She then designates a subset of these to be `Bell blocks` with probability determined by the count she has chosen. This selection is done at random using some of her input seed to generate indices. 

To perform the game, Alice steps through each block in turn. If a given block has not been designated as a Bell block, for each position in the block she has her devices prepare an [https://wiki.veriqloud.fr/index.php?title=Glossary EPR pair] entangled across themselves and measures both qubits with the same setting applied to each device. If her results from each device do not perfectly match, she aborts the protocol as this implies the devices contain something other than an EPR pair. For any block that has been designated as a Bell block, she first takes two bits from her seed and uses these to determine measurement settings: if the first is zero she applies the setting corresponding to measurement (1.) from above, if if is one she applies setting (2.). For the second device, if the second bit is zero she also applies setting (1.), if it is one she applies setting (4.). For each position in the block she has her devices prepare and EPR pair as above and measures with in the prior settings applied. As the outcomes are now correlated but stochastic, she accepts if the agreement of her results are within some threshold.

Having completed the adapted CHSH game, Alice concatenates all of her measurement results into a single output string. To remove any correlations this may have with an eavesdropper, she passes this string to a quantum-strong [https://wiki.veriqloud.fr/index.php?title=Glossary randomness extractor], using the remaining half of the initial input as a seed. The resulting output is an exponentially expanded, still (close to) uniformly random and private string.

This string is then used as the input to another (thankfully much simpler) protocol: using the other two devices in the cluster, Alice plays a standard CHSH game. The string is split into a half and two quarters. Until her seeds have been exhausted, Alice has her devices prepare an EPR state then makes a measurement based on the next bit in each of the seed quarters - for example, if the next bits taken from each sections are 0 and 1, then the first device will be set to (1.) as described above and the second to (4.). Once the game has been completed, she compares the results obtained from each: if they are not close to the results that would have been obtained with the private quantum strategy then she aborts the protocol. If the protocol is not aborted, Alice divides up the measurement results from her first device into a series of equal sized chunks and, using the remaining half-string of seed to generate a random index, selects one of these chunks to be returned as the protocol output.

The above constitutes one full run through a single `cluster expansion` step. This can then be repeated by Alice indefinitely, with the output of each step being used as the input to the next, so long as she alternates between the clusters she uses.

==Notation==
* <math>t</math>: initial private random seed
* <math>k</math>: number of protocol iterations
* <math>u</math>: final randomness expanded string
* <math>D_i</math>: <math>i</math>-th measurement device
* <math>D</math>: set of all measurement devices
* <math>x_i</math>: measurement setting for device 1 on iteration <math>i</math>
* <math>y_i</math>: measurement setting for device 2 on iteration <math>i</math>
* <math>a_i</math>: measurement result for device 1 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>u_i</math>: randomness expanded string after iteration <math>i</math>
* <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>B_{bases}</math>: tuple of measurement bases for CHSH party B; <math>B_{bases}=\{1/\sqrt{2}(X+Z),1/\sqrt{2}(X-Z)\}</math>
* <math>\textrm{Ext}</math>: strong seeded (classical) randomness extractor
* <math>l</math>: parameter to control block size and count in <math>\textrm{RUVExpansion}</math>
* <math>C</math>: parameter to control block count in <math>\textrm{RUVExpansion}</math>
* <math>\kappa</math>: block size in <math>\textrm{RUVExpansion}</math>
* <math>m</math>: block count in <math>\textrm{RUVExpansion}</math>
* <math>R</math>: Boolean array marking blocks as ''Bell blocks'' in <math>\textrm{RUVExpansion}</math>
* <math>d</math>: Hadamard distance in <math>\textrm{RUVExpansion}</math>
* <math>n</math>: number of measurement iterations in <math>\textrm{RUVExpansion}</math>
* <math>N</math>: number of blocks in which to divide the output string in <math>\textrm{RUVExpansion}</math>
* <math>w</math>: CHSH game win count in <math>\textrm{RUVExpansion}</math>
* <math>\gamma_1</math>: output block start index in <math>\textrm{RUVExpansion}</math>
* <math>\gamma_1</math>: output block end index in <math>\textrm{RUVExpansion}</math>

==Requirements==
* '''Network stage''': [https://wiki.veriqloud.fr/index.php?title=Category:Entanglement_Distribution_Network_stage Entanglement Distribution]
* Random number generator
* Authenticated quantum channel
* Authenticated classical channel
* Hardware:
** Multi qubit non-separable state preparation
** Single qubit measurement
** Single qubit gates

==Properties==
* Requires eight measurement devices.
* 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>.
* Uniformity of final string dependent on input length - the distance of the output from uniform is <math>\exp(-\Omega(m^{1/3}))</math>.

==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</ma}th> 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>

==Further Information==

==References==
<div style='text-align: right;'>''contributed by Neil Mcblane''</div>