Editing Certified finite 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://www.nature.com/articles/nature09008 Pironio et. al.] enables randomness expansion of such an input using only two identical untrusted (i.e. provided by an adversary) measurement devices. Privacy of the output string is guaranteed to a given confidence level and its length depends on the stochastic outcome of a  [https://wiki.veriqloud.fr/index.php?title=Glossary CHSH game], the confidence level desired and the [https://wiki.veriqloud.fr/index.php?title=Glossary randomness extractor] used in post-processing.

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.
* The adversary does not have access to a quantum memory.

==Outline==

In this protocol, Alice has an initial private random string (the seed) and has been provided with two identical measurement devices by Eve. Each of the devices has two settings and can produce two outputs. Prior to beginning the protocol, Alice has to decide with which confidence she would like her output string to be private from Eve, and which strong randomness extractor she would like to perform post-processing with. She then splits her seed into two portions - the sizes of which are determined by the chosen randomness extractor. 

Alice then takes two bits from the start of the first portion of her initial string and uses these to choose the settings of her measurement devices (i.e. if the pair is <math>(0,1)</math> then she sets the first device to setting $0$ and the second device to setting <math>1</math>). She prepares an [https://wiki.veriqloud.fr/index.php?title=Glossary EPR state] and shares it across the two measurement devices, then performs measurements using each device with the chosen settings and records the output. She repeats this process until this portion of her input string has been exhausted, resulting in a binary string of recorded outputs of equal length to the input.

Using the input and output strings, Alice estimates the violation of the CHSH inequality her experiment has produced. This allows her to place a bound on the [https://wiki.veriqloud.fr/index.php?title=Glossary conditional min-entropy] of the output string with respect to both the input string and any information Eve may have. 

Finally, Alice passes her output string, the second portion of her initial seed and the determined min-entropy bound to a strong randomness extractor to generate a processed string which is (close to) uniform and private from Eve with the confidence specified at the beginning of the protocol. As Alice has kept her seed private throughout and the randomness extractor used is a strong one, she can then simply append her entire seed to the output of the randomness extractor to produce a final expanded string, which is guaranteed to be longer than the seed so long as a super-classical CHSH game has occurred.

==Notation==
* <math>n</math>: number of measurement iterations
* <math>x_i</math>: measurement setting for device A on iteration <math>i</math>
* <math>y_i</math>: measurement setting for device B on iteration <math>i</math>
* <math>A_{bases}</math>: tuple of measurement bases for device A; <math>A_{bases}=\{X,Z\}</math>
* <math>B_{bases}</math>: tuple of measurement bases for device B; <math>B_{bases}=\{1/\sqrt{2}(X+Z),1/\sqrt{2}(X-Z)\}</math>
* <math>a_i</math>: measurement result for device A on iteration <math>i</math> (0 or 1)
* <math>b_i</math>: measurement result for device B on iteration <math>i</math> (0 or 1)
* <math>s</math>: string of measurement basis pairs; <math>s=(x_1,y_1;\ldots;x_n,y_n)</math>
* <math>r</math>: string of measurement result pairs; <math>r=(a_1,b_1;\ldots;a_n,b_n)</math>
* <math>\overline{r}</math>: output string from classical randomness extraction of <math>r</math>
* <math>t</math>: initial private random seed
* <math>u</math>: final randomness expanded string
* <math>\hat{I}</math>: experimental estimate of CHSH correlation
* <math>k</math>: lower bound on conditional min-entropy of measurement results <math>r</math> with respect to measurement settings <math>s</math> and any information held by an adversary
* <math>f</math>: function which takes as input a(n estimated) CHSH correlation and returns a per-use lower bound on the conditional min-entropy of the measurement results with respect to measurement settings and any information held by an adversary in the limit of a large number of uses (determined using semi-definite programming in [https://www.nature.com/articles/nature09008 Pironio et. al.])
* <math>\epsilon</math>: term to account for finite statistics effects
* <math>\alpha</math>: the chosen confidence with which the returned entropy lower bound is correct
* <math>\textrm{Ext}</math>: strong seeded (classical) randomness extractor

==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==
* Output string is of length <math>\theta(n^2)</math>
* Requires only two measurement devices.
* Devices can be untrusted.
* Imposes no constraints on input states or measurements (i.e. Bell inequality tested can be changed from what is specified here).
* Allows for devices to have an internal [https://wiki.veriqloud.fr/index.php?title=Glossary quantum memory].
* Length of expanded string dependent on magnitude of CHSH correlation (as this tells us how much min-entropy can be contained in the results string) and the choice of randomness extractor (as different constructions have varying degrees of performance).

==Pseudocode==

'''Input''': <math>t</math>, <math>\alpha</math>, <math>\textrm{Ext}v

'''Output''': <math>u</math>

* split <math>t</math> into <math>t=(t^{(1)},t^{(2)})</math> where <math>|t^{(1)}|</math> and <math>|t^{(2)}|</math> are determined by <math>\textrm{Ext}</math>
* <math>n\leftarrow\big\lfloor\frac{|t^{(1)}|}{2}\big\rfloor</math>
* initialize arrays <math>r</math>, <math>s</math> of length <math>n</math>
* For <math>i\leftarrow1</math> to <math>n</math>:
** prepare state <math>|\Psi^+\rangle</math> and share across devices A and B
** <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 A in basis <math>A_{bases}[x_i]</math>
** <math>b_i\leftarrow</math> measurement result from device B 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>
* <math>\hat{I}\leftarrow0</math>
* <math>i\leftarrow1</math> to <math>n</math>:
** <math>x_i,y_i\leftarrow s[i]</math>
** <math>a_i,b_i\leftarrow r[i]</math>
** <math>\hat{I}\leftarrow\hat{I}+\frac{4}{n}(-1)^{x_i\wedge y_i}(-1)^{a_i\oplus b_i}</math>
* <math>\epsilon\leftarrow4\sqrt{-\frac{2\sqrt{2}}{n}\ln{(1-\alpha)}}</math>
* <math>k\leftarrow nf\big(\hat{I}-\epsilon\big)</math>
* flatten <math>r</math> into an array of bits
* <math>\overline{r}\leftarrow\textrm{Ext}(r, t^{(2)},k)</math>
* <math>u\leftarrow(t,\overline{r})</math>

==Further Information==
* [https://www.nature.com/articles/nature09008 Pironio et. al.] implement the protocol using two ionic Yttrium qubits, separated by a distance of <math>1</math>, and a uniform probability distribution (i.e. <math>P(x,y)=\frac{1}{4}</math>).  Over the course of one month, they were able to produce <math>n=3016</math> entanglements and recorded a correlation of <math>\hat{I}=2.414</math>; implying at least 42 new random qubits had been produced with a confidence of 99%. The seed used in the experiment was generated from a combination of sources: radioactive decay, atmospheric noise and network activity on a remote computer.
* The protocol presented here implements the simplest design choices throughout. It is possible to use arbitrary Bell inequalities (rather than the CHSH inequality), to use the seed to generate <math>x_i</math> and <math>y_i</math> from some joint probability distribution <math>P(x,y)</math>, and to contsruct the protocol with more than two devices. 

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