Bounds on semi-device-independent quantum random number expansion capabilities

Randomness plays an important role in simulation algorithms [1, 2, 3], cryptography [4, 5, 6], fundamental sciences [7, 8, 9] and much research has been devoted to the generation of random numbers [10]. Deterministic algorithms can at best create ‘pseudo-random numbers’ that mimic the statistics of ‘true’ random numbers [11]. One needs access to unpredictable physical processes in order to generate truly random numbers [10, 12]. Quantum theory provides well-defined theoretical models which are inherently probabilistic and serve us with good entropy sources to extract randomness [13]. Generating randomness from quantum systems is a matured field [14]. There are now even commercially available quantum random number generators (QRNGs) [15, 16, 17]. These devices are based on methods that are only applicable to their specific experimental setup and corresponding entropy estimates of the output randomness depend on a number of assumptions. Ultimately, these devices require a level of trust in the manufacturer which is not ideal for a number of reasons [10].

For the above-mentioned reasons, it is highly advantageous to have a setup that provides certifiable entropy while making minimal assumptions about its working. Device-independent QRNGs (DI-QRNGs) [18, 19] provide a solution to this problem. By consuming input randomness and using non-locality of quantum theory it can, theoretically, certify the output randomness without characterizing the inner workings of the setup. There has also been numerous experimental demonstrations of this approach [20, 21, 22, 23]. However, protocols for DI-QRNG suffer from practical issues which make them hard to implement outside of a laboratory setup compared to one-way protocols commonly used in commercial devices.

A more practical approach to random number generation is provided by the so-called semi-device-independent QRNGs (SDI-QRNGs) [24, 25, 26, 27, 28, 29]. Unlike, DI-QRNG, complete knowledge of a part of the setup used for random number generation is allowed in SDI-QRNGs. Even though this incurs a weaker form of security compared to the DI counter part, it is much more practical. Realistically, there might be parts of the device that are more error-prone than others. The SDI approach lets you design protocols that can still generate certifiable randomness while leaving such parts uncharacterized [30, 31, 32, 33]. These protocols are also easier to implement since non-local sources are not required and is thus more consumer-friendly. Hence the entropy generation capabilities of the SDI protocols are of particular interest to cryptographers and others who use random numbers for various practical purposes.

In this work, we derive a general upper bound on the amount of entropy generated by a class of SDI protocols. Specifically, we consider prepare and measure protocols of two-dimensional systems and two-outcome measurements. Even though various protocols belonging to this class have been studied previously [24, 25], their analysis has been restricted to some particular dimension witnesses which are used to distinguish quantum processes from classical processes. Our results, however, are independent of dimensional witnesses. We prove that the maximum amount of entropy which could be generated by any protocol of this class is equal to $-\log_{2}\left[\frac{1}{2}\left(1+\frac{1}{\sqrt{3}}\right)\right]$. Moreover, the minimum number of preparation and measurement settings to certify this much entropy is also proven. We give an explicit example of a unique protocol that matches these bounds, proving them to be tight. Furthermore, we derive an analytical relationship between the witness values and the entropy generated with this protocol.

The rest of the paper is organized as follows. In Section II, we briefly describe the SDI model and state some definitions that we use in the subsequent sections. Section III contains results on the limits of output/input randomness. We report an explicit protocol matching these limits and its subsequent analysis in Section IV. In Section V, we present a brief discussion along with some relevant open questions for further research.

We first illustrate the general structure of the SDI-QRNG protocol that we have considered here. It involves two black boxes shielded from the outside world (see Figure 1). One of the devices (boxes) is used for state preparation while the other one is used for the measurement. The preparation black box, $A$ has $\mathcal{X}$ settings, and the measurement black box, $B$ has $\mathcal{Y}$ settings; $\mathcal{X},\mathcal{Y}\geq 2$ . Depending on the randomly chosen setting among $\mathcal{X}$, $A$ outputs a quantum system $\rho_{x}$, $x\in[\mathcal{X}]$ (we use $[N]$ to denote a set of cardinality $N$), which will then be sent to the second black box $B$ for measurement. We assume that the state $\rho_{x}\in\mathbb{C}^{2}$; is a two-dimensional system. The measurement device takes $\rho_{x}$ as input and measures it in one of the randomly chosen settings $\mathcal{Y}$ and outputs $b\in\{0,1\}$. This forms one round of the prepare and measure protocol. We can repeat this procedure multiple times to get a probability distribution given by

where $M^{b}_{y}$ is the measurement operator acting on $\rho_{x}$ with input parameter $y\in[\mathcal{Y}]$ and output $b$.
In order to identify whether the probability distributions truly have a quantum origin or not, dimension witnesses of the form

are usually used, where $w_{x,y}$ are real coefficients and

Under such dimension witnesses, an SDI protocol does not demand any restriction on pre-shared classical correlations between the preparation and measurement devices [34]. Although we do assume that they don’t share any quantum correlations. If we denote by $W_{c}$ and $W_{Q}$ the classical and quantum upper-bounds of the witness value using two-dimensional systems, whenever,

we can be certain that the protocol has no classical description [34, 24]. Hence the output $b$ of $B$ is truly probabilistic in nature and can be used to extract randomness [35, 36].

The entropy in the output $b$ can be quantified by the following min-entropy function [37]

This entropy is considered to be ‘certifiable’ if the corresponding probability distribution satisfies the constraint Equation 3.
Since our witnesses defined by Equation 2 are linear in probabilities, we just need to consider pure states for our analysis as any arbitrary mixed state can be written as a convex combination of pure states [34]. It has also been proven that POVMs can be depicted as a convex combinations of projective measurements in the case of two-measurement outcomes [38, 39]. Furthermore, its known that projective measurements on two dimensional systems can be represented as antipodal unit vectors on the Bloch sphere. In general, the basis elements can be expressed as

where $\overrightarrow{t}_{y}$ is a unit vector on the Bloch sphere and $\sigma=(\sigma_{x},\sigma_{y},\sigma_{z})$, the Pauli matrices. For preparations, it is enough to consider pure states represented using unit vectors $\overrightarrow{s}_{x}$ as

Under this representation, probability distribution $p(b|x,y)$ can be expressed as

We may now proceed to prove some general results related to the capabilities of SDI-QRNGs using the definitions and notations introduced in this section.

Note that our assumption that $0\leq\theta_{i,j}\leq\pi/2$ for $i,j\in[\mathcal{Y}]$ is valid enough since the minimum value for $p_{lb}$ is obtained when the measurement vectors are along the $3$D axes. This implies that by induction, using $\mathcal{Y}=2$ as the initial step and the freedom to relabel any measurement basis, we can take any $\mathcal{Y}$ measurement vectors to lie in the same octant.

An explicit protocol to achieve $H_{\infty}=-\log_{2}[\frac{1}{2}(1+\frac{1}{\sqrt{3}})]\approx 0.34249$ using $4$ preparation settings and $3$ measurement settings is given here. It corresponds to an QRAC-like protocol in which the preparation party $A$ encodes one of the strings $x\in\{000,011,101,110\}$ to a single qubit and the measurement party $B$ attempts to decode $x_{y}\in\{x_{1},x_{2},x_{3}\}$ by suitable measurements. Using arguments similar to those used for proving Theorem 2, this protocol can be proven to be unique up to some relabelling of the measurement bases. A suitable dimension witness is provided by

and whenever

the protocol has no classical description. Equation 16 was derived from the results provided in [40]. They have treated the protocol as a generalized version of the $2\rightarrow 1$ QRAC protocol where $B$ attempts to decode, in addition to the bits encoded by $A$, the parity of the bits as well. The average success probability of this particular protocol have previously found applications in the SDI security of QKD protocols [41]. The corresponding dimension witness has also been applied previously in self testing of POVMs [42, 43] and in reduction of symmetric dimension witnesses [44].
In order to achieve the maximal quantum value $2\sqrt{3}$, we may encode the bits using the states given by

and decode the bits using the measurement bases given by

with the corresponding Bloch vectors

Note that a general two-dimensional witness for $4$ preparation settings and $3$ measurement settings may not be able to produce the maximum amount of randomness. For example, consider the well known dimension witness $I_{4}$ [34, 45], defined as

Since the choice of the $4^{th}$ state solely depends on the $1^{st}$ measurement basis, one can always take $E_{4,1}$ to be $0$. This implies that $p(b=1|4,1)=1$; no entropy is generated in this case. The choice of dimension witness is special in that regard and warrants further analysis. We will now derive an analytical bound on the min-entropy based on the value of the dimension witness. The analysis and methods used is similar to what have been done in [46, 47].
Using Equation 5 and Equation 6, Equation 15 can be written as

where the first inequality follows from $|\overrightarrow{s}_{x}|<1$. Using Equation 9 we can write $p_{lb}$ for our example as

In order to obtain a bounded value of $R_{4,3}$ as a function of $p_{lb}$ we will use the extreme value problem of multi-variable function. Changing variables as

and applying it to LABEL:Wlong, we obtain

where $\left(q,r\right)$ is one of the real roots of equation set with variables $\left(a,b\right)$ given by,

The equation set provided above is obtained by taking the derivatives of LABEL:Wlong with respect to $a$ and $b$. It turns out that the solutions of Equation 20 should satisfy the condition

Since $p_{lb}$ is defined as $\max_{x}\frac{1}{\mathcal{Y}}\sum_{y}\max_{b}p(b|x,y)$, by Equation 21 all the terms in the summation are equal. This means that when $R_{4,3}$ is maximized, $p_{lb}$ is equivalent to $\max_{b,x,y}p(b|x,y)$. Hence the maximization will yield a tight upper bound on the randomness generated by this protocol. Also, Equation 21 reduces our problem to a single variable one.
Substituting Equation 21 in LABEL:Wlong and Equation 18, we get

Solving Equation 22 we obtain

This forms a min-entropy bound for the particular protocol as shown in Figure 4. Since the choice of angles is unique when $R_{4,3}=2\sqrt{3}$ i.e.,

it yields the maximum amount of certifiable randomness; $H_{\infty}\approx 0.34249$. Also note that since $p_{lb}$ forms an upper bound to the average success probability of the protocol, Equation 23 implies that certifiable randomness can be generated as soon as one violates the classical bound on witness. This is particularly relevant in practical setups, which might not be able to achieve the maximum possible quantum violation. The protocols is thus noise-robust, and has immediate applications in practical SDI-QRNG setups.
Since we assume that devices are shielded from the outside world, the randomness used to choose the input settings in each round can be used for other purposes. Hence the total output randomness from each round is more than what is being used to start the process. In order to increase randomness expansion even further, one can consider using a fixed subset of input setting for randomness generation for most rounds and a randomly chosen input setting for rest of the rounds [48, 46, 49]. If the number of rounds is large enough, one can use the subset of rounds wherein the input setting where randomly chosen in order to estimate the witness value [20].

A tight bound on the entropy generation rate is derived for SDI prepare and measure protocols for two-dimensional systems and two-outcome measurements solely from geometrical arguments. The maximum entropy generated from such a class of protocols is found to be equal to $-\log_{2}\left[\frac{1}{2}\left(1+\frac{1}{\sqrt{3}}\right)\right]$. Here it will be apt to note the results of a previous work [50] which suggests an upper bound on the certifiable randomness from a quantum black box as $-\log_{2}\left[\min\{l,k+1\}\right]$, where $l$ is the number of outputs for a measurement ($2$ in our case) and $k$ is the number of preparation settings. For the particular class of protocols that we are considering, this result forms a trivial bound of $1$ bit of certifiable entropy. Our results are much more strict in that regard. It was also conjectured in [25] that $3\rightarrow 1$ QRAC generates the maximum amount of randomness among $n\rightarrow 1$ QRAC protocols. We have proved that this is indeed the case. Our results are more general than QRAC protocols and also independent of any dimension witness. We have also provided an explicit protocol generating the maximum amount of entropy while having the least amount of input settings. The protocol generates as much entropy as $3\rightarrow 1$ QRAC protocol does, however it requires lesser input settings. Note that even though the protocol generates maximum entropy when $W=W_{Q}$, it still remains an open question if one can extract more randomness than what is given in Figure 4 when $W<W_{Q}$. Since Equation 23 is tied to a specific dimension witness i.e., $R_{4,3}$, it would be worthwhile to investigate whether the methods by Wang et. al. [51] would be able to extract more randomness when $3<R_{4,3}<2\sqrt{3}$. Inspired by the DI approach used in [49, 52], they used the full observed statistics to certify randomness rather than restricting to a particular inequality.
The results reported here are not only new and useful, it also opens up possibilities for a set of interesting investigations. An immediate generalisation of the presented work would be to consider the limits on entropy generation for $l$-outcome measurements on $d$-dimensional systems; $l,d>2$. It would also be interesting to investigate the randomness expansion capabilities of such protocols with partially free random sources as the input seed [53, 54]. Given the advantage of our protocol over the $3\rightarrow 1$ QRAC with perfect random sources, it would be interesting to see a comparison with partially free sources [55]. Another possible avenue for research would be to consider the randomness generation ability for multiple users as discussed in [56].

Authors acknowledge the support from the QUEST scheme of Interdisciplinary Cyber Physical Systems (ICPS) program of the Department of Science and Technology (DST), India (Grant No.: DST/ICPS/QuST/Theme-1/2019/14 (Q80)). They also thank Manik Banik, Ram Krishna Patra, Sandeep Mishra, R Srikanth, H. S. Karthik, H. Akshata Shenoy and Kishore Thapliyal for their interest and feedback on the work.