Write
153
edits
Certified finite randomness expansion: Difference between revisions
Jump to navigation
Jump to search
Certified finite randomness expansion (edit)
Revision as of 15:52, 4 November 2019
, 4 November 2019no edit summary
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
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. | 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. | ||
[[: Category: Building Blocks|Building Blocks]], [[: Category: Quantum Functionality|Quantum Functionality]], [[:Category: Specific Task|Specific Task]] [[Category: Building Blocks]] [[Category: Quantum Functionality]] [[Category: Specific Task]] | 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== | ==Assumptions== | ||
| Line 52: | Line 52: | ||
** Single qubit gates | ** Single qubit gates | ||
<div style='text-align: right;'>''Neil Mcblane''</div> | ==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> | |||