\documentclass[aps,pra,twocolumn,superscriptaddress]{revtex4}
\setlength{\paperheight}{11in}

\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{epstopdf}
\usepackage{lmodern}
\usepackage{xfrac}
\usepackage{natbib}
\usepackage{xcite}
\externalcitedocument{main}
\usepackage[breaklinks]{hyperref}
\usepackage{verbatim}

\usepackage{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}

\newcommand{\ket}[1]{|{#1}\rangle}
\newcommand{\bra}[1]{\langle{#1}|}
\newcommand{\OD}[0]{\mathrm{OD}}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}

\newcommand\inner[2]{\langle #1, #2 \rangle}
\newcommand\innerHS[2]{\langle #1, #2 \rangle_{\mathrm{HS}}}
\newcommand{\BH}{\mathcal{B}(\mathcal{H})}
\newcommand{\tr}{\mathrm{tr}}
\newcommand{\ketbrad}[2]{| \hspace{1pt} #1 \rangle \langle #2 \hspace{1pt} |}
\newcommand{\ketbra}[1]{\ketbrad{#1}{#1}}
\newcommand{\braket}[2]{\langle #1 \hspace{1pt} | \hspace{1pt} #2 \rangle}
\newcommand{\abs}[1]{| #1 |}

\newcommand{\diff}{\mathrm{d}}
\newcommand{\binwidth}{\tau}

\newcommand{\epsc}{\epsilon_\textrm{c}} % completeness
\newcommand{\epss}{\epsilon_\textrm{s}} % soundness
\newcommand{\epsp}{\epsilon'} % smoothing parameter
\newcommand{\epsEX}{\epsilon_\textrm{EX}} % extractor
\newcommand{\epsEA}{\epsilon_\textrm{EA}} % entropy accumulation
\newcommand{\epsSA}{\epsilon_\textrm{SA}}
\newcommand{\epsest}{\epsilon_\textrm{est}}
\newcommand{\abort}{\textrm{abort}}
\newcommand{\pass}{\textrm{pass}}
\newcommand{\omegaexp}{\omega_{\textrm{exp}}}
\newcommand{\deltaest}{\delta_{\textrm{est}}}
\newcommand{\Ext}{\textrm{Ext}}
\newcommand{\Hmin}{H_{\textrm{min}}}
\newcommand{\etaopt}{\eta_\textrm{opt}}
\newcommand{\unittime}{\textrm{sec}^{-1}}

%\usepackage{seqsplit}
%\usepackage{xcolor}
%\newcommand{\jd}[1]{{\color{cyan}#1}}
%\newcommand{\ac}[1]{{\color{orange}#1}}


\begin{document}
\title{Randomness Extraction from Bell Violation  with Continuous Parametric
  Down-Conversion - Supplemental Material}

\author{Lijiong~Shen}
\affiliation{Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543}
\affiliation{Department of Physics, National University of Singapore, 2 Science Drive 3, Singapore 117551}

\author{Jianwei~Lee}
\affiliation{Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543}

\author{Le~Phuc~Thinh}
\affiliation{Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543}

\author{Jean-Daniel~Bancal}
\affiliation{Department of Physics, University of Basel, Klingelbergstrasse 82, 4056 Basel, Switzerland}

\author{Alessandro~Cer\`{e}}
\affiliation{Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543}

\author{Antia~Lamas-Linares}
\affiliation{Texas Advanced Computing Center, The University of Texas at Austin, Austin, Texas}
\affiliation{Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543}


\author{Adriana~Lita}
\affiliation{National Institute of Standards and Technology, Boulder 80305, CO, USA}

\author{Thomas~Gerrits}
\affiliation{National Institute of Standards and Technology, Boulder 80305, CO, USA}

\author{Sae~Woo~Nam}
\affiliation{National Institute of Standards and Technology, Boulder 80305, CO, USA}

\author{Valerio~Scarani}
\affiliation{Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543}
\affiliation{Department of Physics, National University of Singapore, 2 Science Drive 3, Singapore 117551}

\author{Christian~Kurtsiefer}
\affiliation{Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543}
\affiliation{Department of Physics, National University of Singapore, 2 Science Drive 3, Singapore 117551}


\email[]{christian.kurtsiefer@gmail.com}
\date{\today}


% insert suggested PACS numbers in braces on next line
\pacs{03.65.Ud, 42.50.Xa, 42.65.Lm}

\maketitle





\section{Modelling the violation of CHSH by a Poissonian source of qubit pairs}
\label{appmodel}

The output of a CW-pumped SPDC process can be accurately described as the emission of independent pairs distributed according to Poissonian statistics of average $\mu$, if the time under consideration (in our case, the length of a round) is much longer than the single-photon coherence time. The goal of this Section is to provide an estimate of the observed CHSH parameter $S$ for such a source.

The pairs being independent, it helps to think in two steps. First, each pair is converted into classical information $(\alpha,\beta)\in\{+,-\}$ with probability
\begin{align}
    P_Q(\alpha,\beta|x,y)=\textrm{Tr}(\rho \Pi_\alpha^x\otimes \Pi_\beta^y)\,,
\end{align}
where the $\Pi$'s are measurement operators. If some of the events have $\alpha=-$ ($\beta=-$), Alice's (Bob's) detector may be triggered, leading to the observed outcome $a=-1$ ($b=-1$).

For the purpose of studying CHSH, it is sufficient to consider $P(-1,+1|x,y)$ and $P(+1,-1|x,y)$, since
\begin{align}
    E_{xy}=1-P(-1,+1|x,y)-P(+1,-1|x,y)\,.
\end{align}
With our convention of outcomes, $P(-1,+1|x,y)$ is the
probability associated with the
case when Alice's
detector clicks and Bob's does not.
Thus, Bob's detector should not be triggered by any pair: each pair will contribute to $P(-1,+1|x,y)$ with
\begin{align}
    D(\alpha)\equiv P_Q(\alpha,+|x,y)+(1-\eta_B)P_Q(\alpha,-|x,y)\,.
\end{align}
Now, let us look at the contribution by $v$ pairs to $P(-1,+1|x,y)$. At least one of the $\alpha$'s must be $-$ for the detector to be triggered; and multiple detections will also be treated as $a=-1$. Thus, a configuration in which exactly $k$ $\alpha$'s are $-$ leads to $a=-1$ with probability $1-(1-\eta_A)^k$ (i.e. at least one $\alpha=-$ must trigger a detection). Obviously there can be $\binom{v}{k}$ such configurations, so the contribution of the $v$ pair events to $P(-1,+1|x,y)$ is
\begin{equation}\label{eq:Dn}
    D_v=\sum_{k=1}^v \binom{v}{k} [1-(1-\eta_A)^k] D(-)^kD(+)^{v-k}\,.
\end{equation}
Finally,
\begin{equation}
    P(-1,+1|x,y)=\sum_{v=0}^{\infty} P_{\mu}(v)D_v\,.
\end{equation} The calculation of $P(+1,-1|x,y)$ is identical, with $D(\beta)\equiv P_Q(+,\beta|x,y)+(1-\eta_A)P_Q(-,\beta|x,y)$ and $\eta_B$ instead of $\eta_A$ in \eqref{eq:Dn}.

Because the quantum probabilities appear in such a convoluted way, the optimal parameters for both the state and the measurements are not the same as for the single-pair case. Upon inspection, however, the values are close, as expected from the fact that the violation is mostly contributed by the single-pair events.

The curves presented in Fig.~2 %\ref{fig:vio_bin}
have been obtained with a slightly modified model that
includes the effect of the background events. The quantum probabilities
$P_Q(\alpha,\beta|x,y)$ have been computed with $\rho=\ket{\psi}\bra{\psi}$
given in Equation (4) of the main article %\eqref{eq:eb_state}
 and with projective measurements, with the values of the parameters given in the main text.


\section{\label{sec:proofs}Protocol and security proof}

For completeness, we will present the protocol studied in~\cite{Rotem:diproofs} and give explicit constants in its security proof. We also refer to this paper for basic definitions of (smooth) min-entropy and related quantities. It will be more convenient for us to switch to to the notation $a,b\in\{0,1\}$ for the outcome labels (instead of $a,b\in\{+1,-1\}$ of the main text) and use the language of nonlocal games with winning condition
\begin{align}
     w_\textrm{CHSH}(a,b,x,y) = \begin{cases} 1 &\textrm{if } a\oplus b=x\cdot y\,,\\
     0 &\textrm{otherwise}\,.
     \end{cases}
\end{align}
The game winning probability is then $w=1/2+S/8$ in terms of the CHSH value. The optimal classical winning strategy achieve a winning probability of 0.75, while the optimal quantum strategy achieves a winning probability of $(2+\sqrt{2})/4\approx0.85$.

A randomness expansion protocol is a procedure that consumes $r$-bits of randomness and generates $m$-bits of almost uniform randomness. Formally, a $(\epsc,\epss)$-secure $r\to m$ randomness expansion protocol if given $r$ uniformly random bits,
\begin{itemize}
    \item (Soundness) For any implementation of the device it either aborts or returns an $m$-bit string $Z\in\{0,1\}^m$ with
    \begin{align*}
        (1-\Pr[\abort])\norm{\rho_{ZRE}-\rho_{U_m}\otimes\rho_{U_r}\otimes\rho_E}_1  \leq \epss\,,
    \end{align*}
    where $R$ is the input randomness register, $E$ is the adversary system, and $\rho_{U_m}, \rho_{U_r}$ are the completely mixed states on appropriate registers.
    \item (Completeness) There exists an honest implementation with $\Pr[\abort]\leq\epsc$.
\end{itemize}
We remark that this security definition is a composable definition assuming quantum adversary, but not composable assuming a no-signalling adversary~\cite{Rotem:diproofs}. Composability allows the randomness generated to be safely used inside a larger protocol, such as quantum key distribution, without compromising the latter's security.

For a concrete randomness expansion protocol, we present the protocol studied in~\cite{Rotem:diproofs}. The protocol takes parameters $\gamma$ expected fraction (marginal probability) of test rounds, $\omegaexp$ expected winning probability for an honest (perhaps noisy) implementation, and $\deltaest$ width of the statistical confidence interval for the estimation test. In an execution, for every round $i\in\{1,\dots,n\}$:
\begin{itemize}
    \item Bob chooses a random bit $T_i\in\{0,1\}$ such that $\Pr(T_i=1)=\gamma$ using the interval algorithm~\cite{interval_algorithm}.
    \item If $T_i=0$ (randomness generation), Alice and Bob choose deterministically $(X_i,Y_i)=(0,0)$, otherwise $T_i=1$ (test round) they choose uniformly random inputs $(X_i,Y_i)$.
    \item Alice and Bob use the physical devices with the said inputs $(X_i,Y_i)$ and record their outputs $(A_i,B_i)$.
    \item If $T_i=1$, they compute 
    \begin{align}
        C_i=w_\textrm{CHSH}(A_i,B_i,X_i,Y_i)\,.
    \end{align}
\end{itemize}
They abort the protocol if $\sum_jC_j<(\omegaexp\gamma-\deltaest)n$ where $j$ is the index of test rounds, otherwise they return $\Ext({\bf AB},{\bf Z})$ where $\textrm{Ext}$ is a randomness extractor, ${\bf AB}=A_1B_1...A_nB_n$ and  ${\bf Z}$ is a uniformly random seed.

More precisely, we use a Trevisan extractor in~\cite{Mauerer:extractors} based on polynomial hashing with block weak design, because of its efficiency in terms of seed length. This is a function $\Ext:\{0,1\}^{2n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ such that if $\Hmin({\bf AB}|E)\geq 4\log\frac{1}{\epsilon_1}+6+m$ then
\begin{align}
    \frac{1}{2}\norm{\rho_{\Ext({\bf AB},{\bf Z}){\bf Z}E}-\rho_{U_m}\otimes\rho_{U_d}\otimes\rho_E}_1 \leq m\epsilon_1
\end{align}
The seed length of this extractor is $d = a(2\ell)^2$ where
\begin{align}
    a &= \ceil*{\frac{\log(m-2e)-\log(2\ell-2e)}{\log(2e)-\log(2e-1)}}\\
    \ell &= \ceil*{\log 2n+2\log\frac{2}{\epsilon_1}}
\end{align}

Now it can be shown that the entropy accumulation protocol gives the completeness and soundness of our randomness expansion protocol. However, let us mention how the input randomness affects the soundness and completeness of the final protocol.

In the protocol we assume access to a certain uniform randomness source, from which the random bits required in the protocol are generated: the $T_i$, $X_i$ and $Y_i$. In certain rounds, $X_i$ and $Y_i$ are either deterministic or fully random bits and can be directly obtained from the source. On the other hand, $T_i$ must be simulated from the uniform source (except when $\gamma=1/2$ which is not usually the case in practice). This can be done efficiently by the interval algorithm~\cite{interval_algorithm}: the expected number of random bits needed to generate one Bernoulli$(\gamma)$ is at most $h(\gamma)+2$ and the maximum number of random bits needed is at most $L_{\max}:=\max\{\log\gamma^{-1},\log(1-\gamma)^{-1}\}$. Then Lemma 16 of~\cite{Rotem:diproofs} gives us: let $\gamma>0$, for any $n$ there is an efficient procedure that given (at most) $6h(\gamma)n$ uniformly random bits either it aborts with probability at most $\epsSA = \exp(-18h(\gamma)^3n/L_{\max})$ or outputs $n$ bits $T_1,\dots,T_n$ whose distribution is within statistical distance at most $\epsSA$ of $n$ i.i.d. Bernoulli$(\gamma)$ random variables. This raises both the completeness and soundness parameter of the final protocol by $\epsSA$.

In an honest implementation of the protocol, Alice and Bob execute the protocol with a device that performs i.i.d. measurements on a tensor product state resulting in an expected winning probability $\omegaexp$. Here Lemma 8 of~\cite{Rotem:diproofs} bounds the probability of aborting using Hoeffding's inequality. That is, the probability that our randomness expansion protocol aborts for an honest implementation is
\begin{align}
    \Pr[\abort] \leq \exp(-2n\delta_{\textrm{est}}^2)=:\epsest\,.
\end{align}
Therefore, the total completeness is bounded by $\epsSA+\epsest$. (Note that $\epsest$ is actually the completeness parameter of the entropy accumulation protocol in~\cite{Rotem:diproofs}.)

For the soundness, Corollary 11 of~\cite{Rotem:diproofs} ensures that for any $\epsEA,\epsilon'\in(0,1)$ either the protocol aborts with probability greater than $1-\epsEA$ or
\begin{align}
    \Hmin^{\epsilon'}({\bf AB}|{\bf XYT}E)_{\rho_{|\pass}} > n\cdot\eta_\textrm{opt}(\epsilon',\epsEA)\,.
\end{align}
Together with our extractor, for all $\epsilon_1\in(0,1)$, if the length $m$ of the final string satisfies
\begin{align}
    n\cdot\eta_\textrm{opt}(\epsilon',\epsEA) = 4\log\frac{1}{\epsilon_1}+6+m
    \label{eq:rand_length_relation}
\end{align}
then we are guaranteed that
\begin{align}
    \frac{1}{2}\norm{\rho_{SRE}-\rho_{U_m}\otimes\rho_{U_R}\otimes\rho_E}_1 \leq \epsilon'/2 + m\epsilon_1\,.
\end{align}
Here $\eta_\textrm{opt}(\epsilon',\epsEA)$ is given by the following equations: for $h$ the binary entropy and $\gamma,p(1)\in(0,1]$
\begin{widetext}
\begin{align}
    \eta_\textrm{opt}(\epsilon',\epsEA) &= \max_{\frac{3}{4}<\frac{p_t(1)}{\gamma}<\frac{2+\sqrt{2}}{4}} \eta(\omega_{\textrm{exp}}\gamma-\delta_{\textrm{est}},p_t,\epsilon',\epsEA)\,,\\
    \eta(p,p_t,\epsilon',\epsEA) &= f_{\min}(p,p_t)-\frac{1}{\sqrt{n}}2\left(\log13+\frac{\diff}{\diff p(1)}g(p)|_{p_t}\right)\sqrt{1-2\log(\epsilon'\epsEA)}\,,\\
    f_{\min}(p,p_t) &= \begin{cases}
    g(p) &\textrm{ if } p(1)\leq p_t(1)\,,\\
    \frac{\diff}{\diff p(1)}g(p)|_{p_t}\cdot p(1) + \left(g(p_t)-\frac{\diff}{\diff p(1)}g(p)|_{p_t}\cdot p_t(1)\right) &\textrm{ if } p(1)>p_t(1)
    \end{cases}\\
    g(p) &= \begin{cases}
    1-h\left(\frac{1}{2}+\frac{1}{2}\sqrt{16\frac{p(1)}{\gamma}\left(\frac{p(1)}{\gamma}-1\right)+3}\right) &\textrm{ if } \frac{p(1)}{\gamma} \in \left[0,\frac{2+\sqrt{2}}{4}\right] \\
    1  &\textrm{ if } \frac{p(1)}{\gamma} \in \left[\frac{2+\sqrt{2}}{4},1\right]
    \end{cases}
\end{align}
\end{widetext}
Combined with the input sampling soundness, the total soundness is bounded by $\epsSA+\epsEA+\epsilon'/2 + m\epsilon_1$.

\begin{table}[h]
    \centering
    \begin{tabular}{|c|l|}
        \hline
        Parameter & \multicolumn{1}{c|}{Definition}\\
        \hline
        $\epsc$ & completeness, bounding honest abort probability\\
        $\epss$ & soundness, bounding randomness security\\
        $\epsSA$ & input sampling error tolerance\\
        $\epsilon'$ & smoothing parameter\\
        $\epsilon_1$ & 1-bit extractor error tolerance\\
        $\epsEX$ & randomness extractor error tolerance\\
        $\epsest$ & Bell estimation error tolerance\\
        $\epsEA$ & soundness of entropy accumulation protocol\\ 
        \hline
    \end{tabular}
    \caption{Definition of security parameters.}
    \label{tab:security_params}
\end{table}

Finally, let us count the number of random bits consumed in the protocol. It consists of the randomness used to decide if a round is a test or generation round, the randomness used to pick the inputs in a test round, and the randomness used for the Trevisan extractor. Taking into account the finite statistical fluctuations, we need at most $6h(\gamma)n$ bits to choose between test and generation except with probability $\epsSA$. This results in at most $2\gamma n$ testing rounds except with probability $\epsSA$, which equates to $2\times 2\gamma n$ random bits being consumed for generating the inputs for test rounds. The randomness for Trevisan extractor is $d$ bits. (Practically, after the first run of the protocol, we can omit this amount because the extractor is a strong extractor: we can reuse the seed for next run of the protocol). Summing these up, we have consumed at most $6h(\gamma)n+4\gamma n+d$ uniformly random bits with probability at least $1-2\epsSA$.

In summary, for a device with $\omegaexp$, any choice of $\gamma,\epsilon_1,\epsilon',\epsEA\in(0,1)$, and $n$ large enough, our protocol is an $(\epsSA+\epsest,\epsSA+\epsEA+\epsilon'/2 + m\epsilon_1)$-secure $[6h(\gamma)n+4\gamma n+d]\to m$ randomness expansion protocol. That is either our protocol abort with probability greater than $1-\epsEA$, or it produces a string of length $m$ such that $\frac{1}{2}\norm{\rho_{SRE}-\rho_{U_m}\otimes\rho_{U_R}\otimes\rho_E}\leq\epsSA+\epsilon'/2 + m\epsilon_1$\,. The protocol consume at most $6h(\gamma)n+4\gamma n+d$ uniformly random bits with probability at least $1-2\epsSA$.\\

\section{\label{sec:randomness_formula}Input-Output randomness analysis}
The previous Section gives a complete picture of the (one-shot) behavior of
our randomness expansion protocol. For the purpose of this paper, it suffices
to obtain rough estimates on the randomness output, but further optimization
can be done.

For simplicity, we introduce some bounds on the resources. Since $m\leq2n$ we can let $m\epsilon_1\leq2n\epsilon_1=:\epsEX$ which gives $\epsilon_1=\epsEX/(2n)$. Plugging this back in~\eqref{eq:rand_length_relation} gives us the number of random bits one can extract,
\begin{align}
    m = n\cdot\eta_\textrm{opt}(\epsilon',\epsEA) -4\log n + 4\log\epsEX -10\,,
    \label{eq:rand_length}
\end{align}
for a given level of soundness $\epsSA+\epsEA+\epsilon'/2+\epsEX$. Moreover, the protocol consumes $6h(\gamma)n+4\gamma n + d$  bits of randomness with probability at least $1-\epsSA$, where
\begin{align}
    d = a(2\ell)^2 &\textrm{ with } a \leq \frac{\log(2n-2e)-\log(2\ell-2e)}{\log(2e)-\log(2e-1)} + 1 \nonumber \\
    &\textrm{ and } \, \, \, \ell \leq 3\log n +6 - 2\log\epsEX\,.
    \label{eq:rand_usage}
\end{align}
This leads to an expansion of $m-6h(\gamma)n-4\gamma n - d$. Hence, the output randomness rate per unit time is
\begin{align}
    r_n = \frac{1}{\binwidth}\left(\eta_\textrm{opt}(\epsilon',\epsEA) -4\frac{\log n}{n} + 4\frac{\log\epsEX}{n} -\frac{10}{n}\right)\,,
\end{align}
and the net randomness rate per unit time is
\begin{widetext}
\begin{align}
    r^\textrm{net}_n = \frac{1}{\binwidth}\left(\eta_\textrm{opt}(\epsilon',\epsEA) -4\frac{\log n}{n} + 4\frac{\log\epsEX}{n} -\frac{10}{n} - 6h(\gamma) - 4\gamma - \frac{d}{n}\right)  \,.
\end{align}
\end{widetext}
These formulas are of course given for a protocol with completeness $\epsSA+\epsest$ and soundness $\epsSA+\epsEA+\epsilon'/2+\epsEX$, where
\begin{align}
    \epsSA &= \exp(-18h(\gamma)^3n/L_{\max})\label{eq:epsSA}\\
    L_{\max}&=\max\{\log\gamma^{-1},\log(1-\gamma)^{-1}\}\\
    \epsest &= \exp(-2n\delta_{\textrm{est}}^2)\label{eq:deltaest}\,.
\end{align}

The asymptotic rate for the block size $n\to\infty$ is given by taking the limit of block size $n$
\begin{equation}
    r_\infty = \frac{1}{\binwidth} \;\left[1-h\left(\frac{1}{2}+\frac{1}{2}\sqrt{\frac{S^2}{4}-1}\right)\right]\,.
\end{equation}
For the net asymptotic rate we could also take the same limit, however we could obtain a better bound by the expected behavior of the interval algorithm. Since the expected number of random bits needed to generate $T_1,...,T_n$ is $nh(\gamma)+2$ by~\cite{interval_algorithm}, and $\gamma n$ of which is expected to be test rounds each consuming 2 random bits, we have the asymptotic net rate
\begin{equation}
    r_\infty^\textrm{net} = \frac{1}{\binwidth} \;\left[1-h\left(\frac{1}{2}+\frac{1}{2}\sqrt{\frac{S^2}{4}-1}\right)-h(\gamma) - 2\gamma\right]\,.
\end{equation}


From an end-user perspective, one may argue that the only parameters of
interest are the completeness and soundness security parameters which will
constrain the rest of protocol parameters---$\gamma,\deltaest,n,\epsilon$'s---for a given objective such as maximizing randomness rate or net randomness rate. For the illustrative plots we set the
constraints 
\begin{align}\label{eq:epsilons}
    \epsSA+\epsEA+\epsilon'/2+\epsEX &= \epss\,,\\
    \epsSA+\epsest &= \epsc\,,
\end{align}
and fix $\epsc=10^{-10},\epss=10^{-10}$.
One then maximizes randomness output or net randomness output given these constraints. This gives us the best (as measured by our objective function) protocol parameters within the relaxations made to obtain~\eqref{eq:rand_length} and~\eqref{eq:rand_usage}.

However, in the main text we take a simpler approach without optimizing over the variables $\gamma,\deltaest,\epsilon$'s. For each block size $n$, we compute $\epsSA$ as given by~\eqref{eq:epsSA} which then fixes $\deltaest$ via $\epsest=10^{-10}-\epsSA$ and~\eqref{eq:deltaest}. The remaining $\epsilon$'s which have weight $10^{-10}-\epsSA$ are chosen in a $1:2:1$ ratio of $\epsEA:\epsilon':\epsEX$, which is guaranteed to add up to the specified level of completeness and soundness. This approach is not far from optimal in the regime of large block size $n$. This results in the
experimental points reported in Figure 3 in the main text. %~\ref{fig:rnd_bin}.

\section{Random bits extraction procedure}
\label{appextraction}

As mentioned in the main text, the data observed during the experiment contains certified randomness. Here we describe the procedure we use to extract this randomness in a finite run of the experiment. We consider two blocks of data, corresponding to an acquisition time of $\approx42.8$ min (\texttt{dataset1}) and $\approx17.33$ hours (\texttt{dataset2}).

The randomness protocol we use (described in Section II) relies on two elements:
\begin{itemize}
\item an honest implementation, and
\item security parameters.
\end{itemize}
These elements must be chosen adequately before proceeding to the extraction. Indeed, if a too optimistic honest implementation is chosen, for instance, the data observed will fail to pass the test, and the whole protocol will abort: no randomness can then be extracted.

Moreover, our setup allows us to choose freely the
%\begin{itemize}
%\item
bin width
%\end{itemize}
which can significantly affect the amount of certified randomness.

We dedicate a fraction $\gamma_\text{calib}$ of our data to the estimation of these parameters
so as to maximize the amount of randomness certified.
The randomness protocol is then run with these parameters on the remaining fraction $(1-\gamma_\text{calib})$ of the data only.
We determine
the fraction of data~$\gamma_\text{calib}$ to use for the calibration of the randomness extraction procedure
from a simulation of the experiment.
We estimate the number of random bits that can be certified from an experiment of the envisioned length if a fraction $\gamma_\text{calib}$ of the data is dedicated to calibration purpose (all other parameters being set as expected). We choose the value of $\gamma_\text{calib}$ that maximizes this quantity. We find that $\gamma_\text{calib}=22\%$ is adequate for
\texttt{dataset1}, and $\gamma_\text{calib}=8\%$ for \texttt{dataset2}.

We then proceed to define the parameters of the randomness protocol.
The security parameters $\epss, \epsc$ are set a priori, with all the other
parameters derived as described in Sections~\ref{sec:proofs} and~\ref{sec:randomness_formula}, with~$\gamma=1$.
We define \textit{honest implementation}
an implementation which reproduces the CHSH violation observed during the calibration stage with probability
\begin{equation}
P(S_\text{exp}\geq S_\text{calib})\geq \epsilon_\text{calib}\,.
\end{equation}
For concreteness, we set $\epsilon_\text{calib}=10^{-10}$. This step guarantees that we will not overestimate the amount of Bell violation which we can expect from a honest experiment. This is crucial for the whole certification procedure to succeed with a large probability. We then have
\begin{equation}
w_\text{exp} = w_\text{calib} - \delta_\text{calib}\,,
\end{equation}
with $\delta_\text{calib} = B(\omega_\text{exp},(1-\gamma_\text{calib})n,\omega_\text{calib})$, where
\begin{equation}
B(p,n,q) = \sum_{i=0}^{nq}\binom{n}{i}p^i(1-p)^{n-i}
\end{equation}
is the cumulative distribution of $n$ Bernoulli variable with parameter $p$. For simplicity, we use the upper bound
\begin{equation}
\delta_\text{calib}\leq \sqrt{\frac{\log(1/\epsilon_\text{calib})}{2n}}
\end{equation}
valid for all winning probability~$\omega_\text{calib}$, which leads to a conservative estimate of the honest implementation Bell violation~$S_\text{est}$.



Having fixed all security parameters and defined our honest implementation, we are now left with the choice of the bin width. For this, following the procedure discussed in the main text, we compute the number of certified random bits that we can hope to certify in the remaining $(1-\gamma_\text{calib})$ fraction of the data as a function of the bin width. We then choose the bin width which yields the maximum rate of random bits.
We find that optimal bin widths 8.9~$\mu$s for \texttt{dataset1} and 5.35~$\mu$s for \texttt{dataset2}.
This allows us to define how the remaining data is to be treated: first, we extract the outcomes corresponding to the chosen bin width, then we use the exact number of bins so extracted to compute precisely the threshold Bell violation $w_\text{exp}-\delta_\text{est}$ and the number of certified bits $m$ corresponding to this dataset, finally we check whether the data indeed yields a Bell violation larger than $w_\text{exp}-\delta_\text{est}$.
If this is not the case, we abort. Otherwise, we apply a randomness extractor on the string of outcomes.
Both datasets pass this test.

Finally, we use the Trevisan extractor implemented by Mauerer et al.~\cite{Mauerer:extractors}, and further improved by Bierhorst et al.~\cite{Bierhorst:2018uk} to extract the certified bits. Our modified source code is available online at \url{https://github.com/jdbancal/libtrevisan}.
%~\cite{github}.
The advantage of Trevisan extractors over other kinds of randomness extractors is that they require little initial seeds, and that they are composable, strong extractors, and secure against quantum side information. Following the suggestion of~\cite{Mauerer:extractors}, we use the block weak design construction with a RSH extractor to maximize the number of extracted bits. The extractor also require a supply of seed randomness. For this, we use the bits generated with the random number generator described in~\cite{Shi:2016kw}.

In the end, we extract 617\,920 and 35\,799\,872 uniformly random bits from \texttt{dataset1} and \texttt{dataset2} respectively, using seeds of length 1\,808\,802 and 2\,923\,224.
The corresponding rates,
calculated including the acquisition time of the calibration data, source phase lock and basis switching, are~$\approx240$~bits/s and~$\approx~573$~bits/s.
If we consider only the time necessary for the data acquisition, we obtain net randomness rates of~$\approx 396$~bit/s and~$\approx 943$~bit/s.

These rates do not include the processing time of the Trevisan extractor.
This classical computation took 9 hours for \texttt{dataset1} on a machine
processing 24 threads in parallel. The bits extracted can be found in the
Supplementary Material as well (see file \texttt{extracted\_randomness-dataset1.bin}).
For \texttt{dataset2} we estimated an unreasonable extraction time of $\approx18$\,years if run on the same hardware.
In order to reduced this time to few days it would be necessary to employ thousands of cores. We decided not to pursue this effort as we do not think this would add any more interest to the presented results.
% and 22
% days for \texttt{dataset2} on a machine processing 24 threads in parallel.
% This task could be heavily parallelized. The bits extracted can be found in the ancillary files.

We used the NIST Statistical Test Suite~\cite{Rukhin:2010dn} to ensure the quality of generated strings is at least on par with acceptable pseudo-randomness. This suit of test can only verify the uniformity of the generated random string, it does not certify its privacy.
The string generated from \texttt{dataset1} passed all
the tests that are meaningful for this relatively short data sample, assuming an acceptable significance level~$\alpha=0.01$. The result of the individual tests are summarized in table~\ref{tab:NISTtest}.
\begin{table}[h]
    \centering
    \begin{tabular}{|l|c|c| }
        \hline
        \multicolumn{1}{|c|}{Test} & $P$--value & Proportion\\
        \hline
        Frequency & 0.590949 & 96/97\\
        Block Frequency & 0.275709 & 95/97\\
        Cumulative Sums Forward & 0.964295 & 96/97\\
        Cumulative Sums Backward & 0.637119 & 96/97\\
        Runs & 0.162606 & 97/97\\
        Longest Run of Ones & 0.590949 & 96/97\\
        Discrete Fourier Transform & 0.183769 & 96/97\\
        \hline
    \end{tabular}
    \caption{Result of the NIST Statistical Test Suite for the bits extracted from \texttt{dataset1}. We split the random bits into 97 sequences of 6300 bits each.}
    \label{tab:NISTtest}
\end{table}

% \pagebreak

% \onecolumngrid
% \pagebreak

% \section{One page with the first 5712 generated random bits}

% \noindent\seqsplit{0100001111111001101000111001111110011010110011001110111100000010
% 1010111001011111111101010011100010011000100011011100001000110000
% 0001110001101101010111100000111011100111110000001110111000000000
% 0111111111001001011001101010001011101100001001111100010011010100
% 0000111000011111101011010000010110010110111010100010001000111000
% 1100001001010010101001001010100110001111001101001111100100011100
% 1111000010000010111011001000000010011100000000000111000111100011
% 0110111010110001001000001000000001010110001001011110110100000110
% 0011000010011010110111001001010101100000100000110101100001000001
% 1100111100110010000110000110110101011100110100101111111011000100
% 0010101011101100110011001100001000010101011100010001100010110100
% 1010010011110100101000110111000011010000101011010010110100011001
% 1000100001101000001001110100001010110010110110110011001010010011
% 0001101111001101100010000100010000100111101000101000001010111010
% 1101011001000010111101010001101110000100011010001011110000100111
% 0101110100001011110111110101001100010000110111011011010001010111
% 1000011100110000001011100111101101010101110001100001111011010001
% 0010010000110011110010010100000100001110111000100000110011101011
% 0110011101111110001010101110010010110101011011101100100100011000
% 1010011001001101100000010100111001100010110011110110101001001000
% 1100011000001111010000000010111101101000101101011101111001111101
% 0110010011111001110000101000010101100100100000111001000010101010
% 1100011000111001101101010110110101111101110011010100101111000100
% 0010110001101001100110011100111111000000010110110100011010001100
% 1110101011011001110011010101100101001111111001110011101001000100
% 0001000101100110011111001110110100001010010110001011110100010101
% 0011000010000110110000001011111011101111111101000110110001001100
% 1100101101101000010010100001000011010100101111100101101011110011
% 0111001001001111100011000000000100110101111010010011110010110100
% 1101111001000111000010111101101001010100110001101000011100010100
% 1111001100110001100100000100011100110000111011000010100011000010
% 0010100010111001010101100110011011100111000111011000000000100110
% 1100001100110011001011001011110110101010110110011000010111101100
% 1001001100101000110010110111101010101111011011011000011110011011
% 0010111110011110110001011101000100100010010101001110101011010000
% 1100101110111111111011010011100101110010001111011011101100100111
% 1100101110101111101111111100110100001010111010110110001101011010
% 1110000000111101100010100000010010011100101101000000101010100110
% 1001111010101001101010110011111110101010101110010111110010010101
% 1010101101000110101100101100110101100101011101011101011111011001
% 0000111111010011110110011010111011011011010111010010101111001011
% 1101010110100100110101000111001010001010111111100010110001000000
% 1100101111001000001101110010000110011000010111000000101011001100
% 0000010011000001110010101110010101001111100011010111011100010101
% 0100101010010101100010000010000100111000111101110100011001101010
% 1010111001011011001011011101001010101100111011011011001100011011
% 0100011000001111111101000101111100001001000110001010000110010010
% 0111100100010100010101010110011010010011111101010101101011011100
% 1101000000100001011010000010101100110010111001001011101101111010
% 0100101010000111110110010000110011001001100000111011101101110100
% 1010100011001011100111110001101101111111101101000101110100101110
% 0100100000001010001010000001001111001100100010001110000001000010
% 1010011001011110100011100011011100001011001000101111011111010101
% 1011001011111110000100101001101011000011010111110110000100111011
% 0111000011001010110001101001011100110110110001100110100100101000
% 1111111111111110110010101100110100010001110111110100001010101110
% 0011011000101001000001001001001100110001001110101000110001111011
% 1100110001000110101010000000110110000110000010110000101101101010
% 0001111111101001101110001111111011101001011010001110110101100001
% 1000011100001001101010001001111101101000100011001110100101000101
% 0110000000000111001111011001001001110010110001000010111101011010
% 0110101010000110010110111010111000011111001000000011000010100111
% 1011000011101100010111111010101110101000011101110001111011010011
% 0010100010011010001001000011111001001101111101110010000001000000
% 1011110011001111011101001110001110110111001111111111100110000111
% 1000001000001100000011010101110101111001110001101101100000010011
% 0110000111011000100100100101000010101111101111010011010010010000
% 1001000111100100110100011010101001000110010110111011001111011001
% 1111000110100001100111110010111010001010011000101000101100000101
% 0111010101000010001111010000100001010010111111000001011011010011
% 0100011000011101110111100000011100011101001100101010010110100011
% 1000101000010010001000010110111111001101101110000010100011011100
% 0100000100111101001100001100011100010110001111101011100010111011
% 0111001100000010101011110101101101100101010111011001110011100111
% 1110010110011101100110001000111001100101000000001010000101100000
% 1110000011100000001100000000010010000111100010100101010000000001
% 0000000100110000100111100101111000110101110000010000011100110001
% 0010110010111000011000100111100011110100001111111000100010000000
% 1100111100111110101101000101011101001111100011101001010101000100
% 1101000101000001110011101111110000101010011111111111101100011010
% 0000100010110011011111011001010000010111101010101011010111110011
% 1110100000010111100011011110000011100110111100001110101100001000
% 0001001110001010010111100100111100101001110100110010011000011001
% 0001011011100100101111011011010001110000010100110110100010000001
% 0000111000110110101100101111101000010110000100011110000101011110
% 0000000010001001001110101101011010010011011111010000000000100010
% 1111100111000001010010100001000000001000001011100101110100000000
% 0011011100110011010110111001111010110111000110001101111011111001
% 0001011001010011010111010001110100110111111000001011101111010110
% 0010010100100000}


\end{document}
