Editing Randomness amplification (8 devices) (section)

==Outline==

In this protocol, Alice has an initial string that has been produced by an SV source and therefore is not uniformly random. She has been provided with eight identical measurement devices by Eve, each of which has two settings and can produce two outputs. Classical [https://wiki.veriqloud.fr/index.php?title=Glossary randomness extractors] exist which are capable of combining three independent sources of weak randomness into a single (close to) uniform, private source. Alice's overarching goal is, therefore, to use her provided apparatus to simulate three independent sources using only her single initial string.

First, Alice divides up the measurement devices into two groups of four. Then, she divides her input string into four portions, the required sizes of which will depend on her choice of randomness extractor and the confidence with which she would like the protocol to succeed (i.e. produce a string which is uniformly random and private). She also decides on a threshold for noise which she deems acceptable.

Using the first portion of the string and the first group of four measurement devices, Alice performs a four-party analogue of a [https://wiki.veriqloud.fr/index.php?title=Glossary CHSH game]: taking four bits at a time from the string, she uses their values to choose measurement settings on the devices (i.e. if the bits taken are <math>0,1,0,1</math> then she sets device one to <math>0</math>, two to <math>1</math>, three to <math>0</math> and four to <math>1</math>). Then, she prepares a four-partite [https://wiki.veriqloud.fr/index.php?title=Glossary entangled state] across the devices and measures with each, storing the results she gets as a string of bits. Once the portion of string she started with has been exhausted, she looks at the correlation of her chosen inputs and results - if this value is within an accepted threshold (defined by her choice of noise) she continues, otherwise, the protocol is aborted.

Taking two more portions of the string and the remaining four devices, and dividing one of these portions into a number of equally sized blocks, Alice repeats the measurement process as described above, using each block in turn. She stops before the correlation check and records her results each time. Using the other selected portion of the string as an index to her list of stored results, Alice chooses one of the blocks of inputs and recorded results, and passes this to the same correlation check. 

If this check does not abort, Alice passes the first string of measurement results, the randomly selected string of results and the remaining portion of the original string to a classical randomness extractor. The output of this is then returned as (close to) uniformly random, private (i.e. randomness amplified) string.

* <math>n</math>: number of measurement iterations (per block)
* <math>N</math>: number of blocks to repeat second set of measurements for
* <math>x_{i,j}</math>: measurement setting for device <math>j</math> on iteration <math>i</math>
* <math>a_{i,j}</math>: measurement result for device <math>j</math> on iteration <math>i</math>
* <math>\textrm{bases}</math>: tuple of measurement bases for each device; \textrm{bases} = <math>\{X,Z\}</math>
* <math>s</math>: string of measurement basis groups; <math>s=(x_{1,1},x_{1,2},x_{1,3},x_{1,4};\ldots;x_{n,1},x_{n,2},x_{n,3},x_{n,4})</math>
* <math>r</math>: string of measurement result groups; <math>r=(a_{1,1},a_{1,2},a_{1,3},a_{1,4};\ldots;a_{n,1},a_{n,2},a_{n,3},a_{n,4})</math>
* <math>S</math>: list of strings of measurement basis groups for blocks 1 to <math>N</math>; <math>S=(s_1\ldots s_N)</math>
* <math>R</math>: list of strings of measurement result groups for blocks 1 to <math>N</math>; <math>R=(r_1\ldots r_N)</math>
* <math>t</math>: initial weak random seed
* <math>u</math>: final randomness amplified string
* <math>|\phi_-\rangle, |\psi_+\rangle</math>: [https://wiki.veriqloud.fr/index.php?title=Glossary maximally entangled] two qubit Bell states
* <math>|\tilde{\phi}_+\rangle</math>: two qubit entangled state; <math>|\tilde{\phi}_+\rangle=\frac{1}{\sqrt{2}}\big(|0\rangle|+\rangle+|1\rangle|-\rangle\big)</math>
* <math>|\tilde{\psi}_-\rangle</math>: two qubit entangled state; <math>|\tilde{\psi}_-\rangle=\frac{1}{\sqrt{2}}\big(|0\rangle|-\rangle-|1\rangle|+\rangle\big)</math>
* <math>|\Psi\rangle</math>: entangled state shared by measurement systems; <math>|\Psi\rangle=\frac{1}{\sqrt{2}}\big(|\phi^-\rangle|\tilde{\phi\rangle^+}+|\psi^+\rangle|\tilde{\psi}^-\rangle\big)</math>
* <math>\delta</math>: chosen tolerated noise
* <math>\hat{B}</math>: estimate of the bell inequality defined in [https://www.nature.com/articles/ncomms11345 Brandao et. al.]
* <math>\mathbb{I_\textrm{cond}}</math>: indicator function taking value 1 if \textrm{cond} evaluates true and 0 otherwise
* <math>D^{(1)}</math>: group of measurement devices containing devices 1 to 4
* <math>D^{(2)}</math>: group of measurement devices containing devices 5 to 8
* <math>\textrm{Ext}</math>: three-source randomness extractor