LETTERS Random numbers certified by Bell's theorem

Randomness is a fundamental feature of nature and a valuable resource for applications ranging from cryptography and gambling to numerical simulation of physical and biological systems. Random numbers, however, are difficult to characterize mathematically 1 , and their generation must rely on an unpredictable physical process The characterization of true randomness is elusive. There exist statistical tests used to verify the absence of certain patterns in a stream of numbers These considerations are of direct relevance to applications of randomness, and in particular cryptographic applications. Imperfections in random number generators Here we establish a fundamental link between the violation of Bell inequalities and the unpredictable character of the outcomes of quantum measurements and show, as originally proposed in ref. 14, that the non-local correlations of quantum states can be used to generate certified private randomness. The violation of a Bell inequality 15 guarantees that the observed outputs are not predetermined and that they arise from entangled quantum systems that possess intrinsic randomness. For simplicity, we consider the Clauser-HornShimony-Holt (CHSH) form of Bell inequality 19 , but our approach is general and applies to any Bell inequality. We thus consider two separate systems that can each be measured in two different ways, with a measurement on each system resulting in one of two values where P(a 5 bjxy) is the probability that a 5 b when settings (x, y) are chosen, and P(a ? bjxy) is defined analogously. Systems that admit a local, hence deterministic 20 , description satisfy I # 2. Certain measurements performed on entangled states, however, can violate this inequality. In order to estimate the Bell violation, the experiment is repeated n times in succession. The measurement choices (x, y) for each trial are generated by an identical and independent probability distribution P(xy). We denote the final output string after the n runs r 5 (a 1 , b 1 ; … ; a n , b n ) and the input string s 5 (x 1 , y 1 ; … ; x n , y n ). An estimatorÎ of the CHSH expression, equation where N(a 5 b, xy) is the number of times that the measurements x, y were performed and that the outcomes a and b were found equal after n realizations, and where N(a ? b, xy) is defined analogously. The randomness of the output string r can be quantified by the min-entropy 21 H ' (RjS) 5 2log 2 [max r P(rjs)], where P(rjs) is the conditional probability of obtaining the outcomes r when the measurements s are made and the maximum is taken over all possible values of the output string r. We show (Supplementary Information A) that the min-entropy of the outputs r is bounded by *These authors contributed equally to this work