Logo IMG
HOME > PAST ISSUE > Article Detail


Quantum Randomness

If there’s no predeterminism in quantum mechanics, can it output numbers that truly have no pattern?

Scott Aaronson

2014-07TechnoAaronsonFp267.jpgClick to Enlarge ImageHow can you know whether a sequence of numbers is random? Suppose, for example, that you buy an alleged random-number generator for use in creating cryptographic keys, and suppose the generator spits out something like:

84, 67, 33, 68, 81, 29, 83, 90, 26, . . .

The numbers look pretty random, but can you be confident that there’s no hidden pattern—perhaps because of a backdoor secretly inserted by the manufacturer or some other privacy interloper?

So certifying randomness is both a philosophical problem and an urgently practical one. In the last issue’s Technologue column, I discussed an abstract, conceptual solution to the problem of how to certify randomness, based on a seminal idea from the 1960s called Kolmogorov complexity. To recap, the Kolmogorov complexity of a string of bits is defined as the length of the shortest computer program that produces the string as output. In several ways that one can make precise, a string of n bits can be called “random for all practical purposes” if its Kolmogorov complexity is close to n. In such a case, the string is “algorithmically incompressible”: The shortest computable description of it is the string itself.

Alas, although Kolmogorov complexity might lead to deep insights about the nature of randomness, there’s a huge problem with applying it to real life. Namely, as I proved in the last issue, there’s no algorithm to compute the Kolmogorov complexity of a given string! People sometimes try to get around this problem by approximating Kolmogorov complexity but it’s not always effective.

If we really want to be sure that a sequence is random, we’ll have to exploit some knowledge about how the numbers were generated: Did they come from die rolls? Radioactive decays? A computer program? Whichever physical process produced the numbers, what reasons do we have to believe the process was random?

comments powered by Disqus


Subscribe to American Scientist