03-27

Certifiable Quantum Dice

A source of independent and uniform random bits is a basic resource in many computational tasks, such as cryptography, game theoretic protocols, algorithms and physical simulations. In the classical world it is impossible to construct a random number generator whose output can be certified to be a uniformly random n-bit string, since there seems to be no basis on which to reject any particular output in favor of any other. Quantum mechanics allows for a remarkable random number generator: its output is certifiably random in the sense that if the output passes a simple statistical test, and a no-signaling condition is met between the two boxes in the randomness generating device (based, say, on the speed of light limit imposed by special relativity), even a quantum skeptic (viz Einstein's famous quote ``God does not play dice with the Universe''), would be convinced that the output is truly random, independent of the validity of quantum mechanics. Based on joint work with Thomas Vidick.