If there’s no predeterminism in quantum mechanics, can it output numbers that truly have no pattern?
How can we know for sure if something is random? In this two-part series, I’ve tried to cover a century’s worth of thought about that question. We’ve seen statistical randomness tests, Kolmogorov complexity, Bell’s theorem, the CHSH game, the “Free Will Theorem,” and finally, recent protocols for generating what’s been called “Einstein-certified randomness.” Starting with a small random seed, these protocols use quantum entanglement to generate as many additional bits as you want that are guaranteed to be random—unless nature resorted to faster-than-light communication to bias the bits.
Pironio’s group has already done a small, proof-of-concept demonstration of their randomness expansion protocol, using it to generate about 40 “guaranteed random bits.” Making this technology useful will require, above all, improving the bit rate (that is, the number of random bits generated per second). But the difficulties seem surmountable, and researchers at the National Institute of Standards and Technology are currently working on them. So it’s likely that before too long, we will be able to have copious bits whose randomness is guaranteed by the causal structure of spacetime itself, should we want that. And as mentioned before, for cryptographic purposes it can matter a lot whether your randomness is really random.
Although there is a need for randomness, we normally don’t need huge amounts of it. Even for cryptographic applications, our computers rely heavily on pseudorandom number generators: Deterministic functions that start with a small random seed and stretch it out into a long string that “looks random for all practical purposes.” To clarify, the output is certainly not completely random, because the number of possible seeds is so much tinier than the number of possible long strings. However, according to current understanding in theoretical computer science, even if the seed was only a few thousand bits long, and the output was thousands of terabytes, telling the output apart from a truly random string could require astronomical amounts of computation. Indeed, even if the entire observable universe were converted into supercomputers working on telling the output from random, those supercomputers would probably have degenerated into black holes and radiation before they’d made a dent in the problem. Assuming that’s true, it would seem fair to say that the pseudorandom string is “random- looking enough,” and that the only true randomness we needed was that in the initial seed. When it comes to randomness, then, a little can go a long way—but you do need a little to get things started.
- Aaronson, S. 2002. Book review of A New Kind of Science. Quantum Information and Computation 2:410–423. quant-ph/0206089.
- Colbeck, R.. 2006. Quantum and Relativistic Protocols for Secure Multi-Party Computation. PhD thesis, Trinity College, University of Cambridge. http://arxiv.org/pdf/0911.3814.pdf
- Conway, J. H., and S. Kochen. 2009. The strong free will theorem. Notices of the American Mathematical Society 56:226–232.
- Coudron, M., and H. Yuen. 2014 Infinite randomness expansion and amplification with a constant number of devices. Proceedings of the ACM Symposium on Theory of Computing. http://arxiv.org/abs/1310.6755
- Pironio, S., et al. 2010. Random numbers certified by Bell’s theorem. Nature 464:1021–1024.
- Wolfram, S. 2002. A New Kind of Science. Champaign, IL: Wolfram Media.