Randomness amplification (8 devices)

Randomness amplification is a protocol for Quantum Random Number Generator which takes a string from a weak source of randomness - one which contains correlations and may be at least somewhat predictable by an adversary - and converts it to a (potentially shorter) string which is (close to) uniformly random and private from any adversaries. The protocol of Brandao et al allows for eight untrusted devices to be used in a noise-tolerant setting to amplify an arbitrarily weak Santha-Vazirani (SV) source.

Classically, it is only possible to extract uniform, private randomness by combining multiple weak sources together. This protocol enables the extraction of such randomness from only a single weak source - useful in any situation where only some randomness has been provided but absolute security is required.

Tags: Building Blocks, Quantum Functionality, Specific Task

Assumptions

• No-signalling theorem 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 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 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 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 $0,1,0,1$ then she sets device one to $0$, two to $1$, three to $0$ and four to $1$). Then, she prepares a four-partite 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.

• $n$: number of measurement iterations (per block)
• $N$: number of blocks to repeat second set of measurements for
• $x_{i,j}$: measurement setting for device $j$ on iteration $i$
• $a_{i,j}$: measurement result for device $j$ on iteration $i$
• ${\textrm {bases}}$: tuple of measurement bases for each device; \textrm{bases} = $\{X,Z\}$
• $s$: string of measurement basis groups; $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})$
• $r$: string of measurement result groups; $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})$
• $S$: list of strings of measurement basis groups for blocks 1 to $N$; $S=(s_{1}\ldots s_{N})$
• $R$: list of strings of measurement result groups for blocks 1 to $N$; $R=(r_{1}\ldots r_{N})$
• $t$: initial weak random seed
• $u$: final randomness amplified string
• $|\phi _{-}\rangle ,|\psi _{+}\rangle$: maximally entangled two qubit Bell states
• $|{\tilde {\phi }}_{+}\rangle$: two qubit entangled state; $|{\tilde {\phi }}_{+}\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle |+\rangle +|1\rangle |-\rangle {\big )}$
• $|{\tilde {\psi }}_{-}\rangle$: two qubit entangled state; $|{\tilde {\psi }}_{-}\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle |-\rangle -|1\rangle |+\rangle {\big )}$
• $|\Psi \rangle$: entangled state shared by measurement systems; $|\Psi \rangle ={\frac {1}{\sqrt {2}}}{\big (}|\phi ^{-}\rangle |{\tilde {\phi \rangle ^{+}}}+|\psi ^{+}\rangle |{\tilde {\psi }}^{-}\rangle {\big )}$
• $\delta$: chosen tolerated noise
• ${\hat {B}}$: estimate of the bell inequality defined in Brandao et. al.
• $\mathbb {I_{\textrm {cond}}}$: indicator function taking value 1 if \textrm{cond} evaluates true and 0 otherwise
• $D^{(1)}$: group of measurement devices containing devices 1 to 4
• $D^{(2)}$: group of measurement devices containing devices 5 to 8
• ${\textrm {Ext}}$: three-source randomness extractor

Requirements

• Network stage: Entanglement Distribution
• Weak (SV) random number generator
• Authenticated quantum channel
• Authenticated classical channel
• Hardware:
  • Mutli qubit non-seperable state preparation
  • Single qubit measurement
  • Single qubit gate

Properties

• Requires eight measurement devices
• Devices can be untrusted
• Noise tolerance is dependent on weakness of the source
• Arbitrarily weak SV sources can be amplified in the absence of noise
• Length of the amplified string depends on the choice of a randomness extractor

Pseudocode

Input: $t$, $\delta$, $N$, ${\textrm {Ext}}$

Output: $u$

• split $t$ into $t=(t^{(1)},t^{(2)},t^{(3)},t^{(4)})$ where $|t^{(3)}|=\log {N},|t^{(2)}|=N|t^{(1)}|$ and $|t^{(1)}|,|t^{(4)}|$ are determined by ${\textrm {Ext}}$
• $n\leftarrow {\big \lfloor }{\frac {|t^{(1)}|}{2}}{\big \rfloor }$
• initialise arrays $r$, $s$ of length $n$
• initialise (2D) arrays $R$, $S$ of length $N$ (with elements of length $n$)
• ${\textrm {measurementBlock}}$($D^{(1)},t^{(1)},n,s,r$)
• ${\hat {B}}\leftarrow$${\textrm {estimateBellViolation}}$$(n,s,r)$
• If ${\hat {B}}>\delta$:
  • ${\textbf {abort}}$
• For $k\leftarrow 1$ to $N$:
  • ${\textrm {measurementBlock}}$($D^{(2)},t_{nk:n(k+1)}^{(2)},n,S[k],R[k]$)
• $t^{(3)}\leftarrow$ cast $t^{(3)}$ as an integer
• ${\hat {B}}\leftarrow {\textrm {estimateBellViolation}}(n,S[t^{(3)}],R[t^{(3)}])$
• If ${\hat {B}}>\delta$:
  • ${\textbf {abort}}$
• $u\leftarrow {\textrm {Ext}}(r,R[t^{(3)}],t^{(4)}$)

With the following subroutines defined:

${\textrm {measurementBlock}}$

Input: $D,t,n,s,r$

• For $i\leftarrow 1$ to $n$:
  • prepare state $|\Psi \rangle ={\frac {1}{\sqrt {2}}}{\big (}|\phi _{-}\rangle |{\tilde {\phi }}_{+}\rangle +|\psi _{+}\rangle |{\tilde {\psi }}_{-}\rangle {\big )}$ and share across $D$
  • $j\leftarrow 1$ to 4:
    • $x_{i,j}\leftarrow t_{4i+j}$
    • $a_{i,j}\leftarrow$ measurement from device $j$ in basis \textrm{bases}[$x_{i,j}$]
  • $s[i]\leftarrow (x_{i,1},x_{i,2},x_{i,3},x_{i,4})$
  • $r[i]\leftarrow (a_{i,1},a_{i,2},a_{i,3},a_{i,4})$

${\textrm {estimateBellViolation}}$

Input: $n,s,r$

Output: ${\hat {B}}$

• ${\hat {B}}\leftarrow 0$
• For $i\leftarrow 1$ to $n$:
  • $x_{1},x_{2},x_{3},x_{4}\leftarrow s[i]$
  • $a_{1},a_{2},a_{3},a_{4}\leftarrow r[i]$
  • ${\hat {B}}\leftarrow {\hat {B}}+{\frac {1}{n}}{\big (}\mathbb {I} _{\bigoplus _{j=1}^{4}x_{j}=0}\mathbb {I} _{\bigoplus _{a=1}^{4}u_{j}=1}+\mathbb {I} _{\bigoplus _{j=1}^{4}x_{j}=1}\mathbb {I} _{\bigoplus _{a=1}^{4}u_{j}=0}{\big )}$

Further Information

Brandão et. al. also provide a protocol that achieves randomness amplification using only four devices, however, the randomness extractor required to produce multiple bits is only defined implicitly (i.e. we can prove that it exists but have not yet been able to construct it). A randomness extractor does exist that is able to produce a single private bit.

References

contributed by Neil Mcblane