First Evidence That Quantum Processes Generate Truly Random Numbers
Quantum number generators produce random numbers that are measurably different from those that computer programs generate.
kfc 04/13/2010
- 30 Comments
There is a growing sense among physicists that all physical processes can be thought of in terms of the information they store and process; by some accounts information is the basic unit of existence in our cosmos. That kind of thinking has extraordinary implications: it means that reality is a kind of computation in which the basic processes at work simply chomp their way through a vast bedrock of information.
And yet this is at odds with another of the great challenges facing modern science: understanding the nature of randomness. While information can be defined as an ordered sequence of symbols, randomness is the opposite of order, the absence of pattern. One of the basic features of true randomness is that it cannot be produced by a computer, otherwise it wouldn't be random and that sets up a mouthwatering problem.
If all physical processes in the universe are ongoing computations, how does randomness arise? What kind of process can be responsible for its creation?
Until recently, mathematicians could only study randomness generated by classical physical processes such as coin tosses or computer programs which generate so-called pseudo-randomness. Since physical processes like coin tosses are hard to prove unbiased and difficult to manage, the work horse random number generators are programs such as Mathematica which uses the interesting properties of cellular automata to generate psedorandom sequences of numbers. Another method is simply to choose a sequence of numbers from the digits of an irrational number such as pi.
This stuff looks and feels random but because it can be computed, mathematicians treat it with suspicion.
But in the last few years, scientists have found a new source of randomness that cannot be produced by a computer program. This is called algorithmic randomness and it is the gold standard when it comes to the absence of order. The new source of this randomness is the quantum world and comes from exploiting quantum processes such as whether a photon is transmitted or reflected by a semi-silvered mirror.
This ought to produce sequences that can never be created by a computer. But are these sequences measurably different from those produced by computers?
This question is settled today by Cristian Calude at the University of Auckland in New Zealand and a few mates. These guys have carried out the first experimental comparison of randomness generated in these different ways and they've done it on a huge scale, using sequences 2^32 long.
Calude and co compare several flavours of random sequence generated in different ways.The sequences come from a quantum random number generator called Quantis, another from physicists in Vienna who also exploit quantum processes, they also use conventional sequences generated by computer programs such as Mathematica and Maple as well as a sequence of 2^32 bits from a binary expansion of pi.
The team use four different tests in their comparison, which fall into four categories based on algorithmic information theory, statistical tests involving frequency counts, a test based on Shannon's information theory and finally, a test based on random walks.
The results show that the sequence generated by Quantis is easily distinguishable from the other data sets. This say Calude and co, is evidence that quantum randomness is indeed incomputable. That means that it could not have been be generated by a computer.
Significantly, they leave unanswered the question of how convincing this evidence is that they've gathered and instead go to some length to point out that it is impossible to prove absolute randomness.
Nevertheless, if this evidence is taken at face value, it leaves us with a significant conceptual dilemma. On the one hand, it shows that Quantis produces sequences of random numbers that cannot be generated by a computer. And yet Quantis itself is a machine that must work by manipulating information in the way the laws of physics allow--it must be a computer of sorts.
This contradiction can only mean there is something wrong with the way we think about randomness or information or both (or at least with the way I've set it up here).
Of course, the answer must lie in the nature of information in the quantum world. It's easy enough to define information classically as an ordered sequence of symbols. But that definition falls apart as soon as these symbols become quantum in nature.
If each bit can be both a 1 and a 0 at the same time, what does it mean for such a such a sequence to be in order? Equally, what would the absence of order look like in such a quantum sequence?
It's in the tackling these questions that the nature of our universe is being teased apart.
Ref: arxiv.org/abs/1004.1521: Experimental Evidence of Quantum Randomness Incomputability
On Twitter
Become a Fan on Facebook
Subscribe to the Feed
jonathanmccabe
7 Comments
A classical computer could do that.
It seems to me that if you have a test for randomness, the computer could "mutate" a sequence of numbers, check if it scores higher on the test, if so keep the mutation, and repeat. Given enough classical computing resources, you could max out the randomness test.
Reply
TB1984
3 Comments
Re: A classical computer could do that.
Now that sounds like an interesting idea to me...
Reply
pgalinsky
1 Comment
Re: A classical computer could do that.
Sounds like a good idea, evolutionary methods seem to be underused in general. However... would this require truly random mutations in the number sequence in the first place to provide a maximum score on a test that actually tests randomness? (perhaps the problem is in the test itself)
Reply
alexis_teorn
1 Comment
Re: A classical computer could do that.
The permutations need not be random at all. You should be able to first select a set of digits that satisfy the general statistic tests, then go through all permutations of these digits, one by one, testing them against the order-sensitive tests until one of them passes. Therefore I do not see how a given random sequence can be "uncomputable" if the test for its uncomputability is itself computable.
Reply
TB1984
3 Comments
Re: A classical computer could do that.
Very interesting thoughts, guys. It seems we need a more detailed description of the "randomness rating function" that was used.
Some more thoughts: I think only long lists of numbers (at least several hundred) are needed in order to make any meaningful prediction on how random the numbers are. It doesn't seem to make sense to ask, for example, whether "8,4,7" is more or less random than "3,8,1". For longer series, producing a long list of random numbers by mutating "not quite random" lists and computing the new randomness might take a lot of time. I am assuming that the function used to measure randomness involves looking at every single number in the list, as well as its relationship with respect to other numbers. This process must be repeated after every mutation. Therefore, I would expect the path to a "random list" to be exponential and asymptotic, i.e. it will take infinitely long for the list to become 100% random... What do you guys think?
On the other hand, any list produced by the mechanism described in the article is 100% random right off the bat. The lists are arrived at by completely different means. At the end of the day, I think the claim that "randomness cannot be computed" may have been too strong. The interesting part of the article seems to be the device's capability to generate long lists of random numbers on demand.
Reply