Truly Random Numbers Found?
Headline: “Perfect randomness realized for the first time“. Perfection!
“It may seem strange, but it is almost impossible to create a perfect coin or a perfect die,” says [paper author] Renner. No matter how symmetric and smooth a die is made, after a roll one of its six faces will always point upwards slightly more often.
“Even modern random number generators, which are based on quantum mechanical effects like the reflection of photons from beam splitters, are not entirely immune to such a systematic error or ‘bias,’” adds Wallraff. But now Wallraff’s and Renner’s teams have found a way to take imperfect randomness and still extract perfectly random numbers from it. They call their method randomness amplification.
Before we discuss these curiosities, the paper is “Experimental randomness amplification” by this Renner and many others in Nature. Stick with me, because we have to get through the Abstract (with my parapgraphifications; and have no fear the loophole-free Bell or quantum computer business as we won’t really need these):
Realistic quantum information processing devices are inherently imperfect, leading to computational errors that require quantum error correction.
Likewise, random bits generated by such devices are flawed and must be enhanced to be usable for applications such as generating cryptographic keys. This enhancement of randomness quality is achieved through a protocol known as randomness amplification. Here we report on an experiment that implements such a protocol.
Randomness amplification is device-independent, making no assumptions about the internal workings of the quantum devices. It requires executing a loophole-free Bell test within a specific parameter regime that involves both a high Bell violation and a high repetition rate.
The experimental demonstration is made possible by a combination of theoretical advances, which allow for protocols with an experimentally realistic parameter regime, and experimental progress that achieves this regime with superconducting circuits. Crucially, randomness amplification has been proven to be impossible by purely classical means. This experiment therefore demonstrates a definitive quantum advantage—leveraging quantum technology to accomplish a task unattainable by classical information processing.
I’ll now define what these things mean, then say why anybody should care.
Random
What is random? Although in the colloquial it can mean surprising or unexpected, e.g. “That was random”, formally it is unknown explanation, where we must always remember explanation means cause. But cause in its full Aristotelian sense, the complete explanation of a thing. When you are missing pieces in the full-cause-slash-explanation of a thing, it is to that extent random.
There is another usage, inappropriate I think, but common, and that is uniform. “Random” numbers, to be defined in a moment, must be strictly uniform to “truly random.” So that if you have 10 items, any departure from 1/10th of each of them in any process, natural or artificial, to generate them, the process is said to be not wholly random, and thus becomes candidate for “randomness amplification” to restore the supposed imbalance.
Probability, you will recall from taking the Class, means (and only means) the uncertainty you have in some proposition given whatever evidence you consider. In the authors’ definition of “perfectly random” they mean the probability a thing is in one of the states it can take equals the probability of any other state it can take. In notation (which you don’t have to understand), Pr(S = s_i | E) = 1/n, where S can take one of n states and E is all the evidence you assume.
If for any of the states, the probability is different than 1/n (where logically, at least two states must differ if one does), then there is in a sense some predictability of the state greater than if every state had 1/n probability. Take the easy case of two states, bits, which can be on or off. If given your evidence the probability is 50-50, then that becomes the hardest prediction. Any departure, here by making a 1 or 0 greater than 50 which automatically implies the 0 or 1 less than 50, makes the prediction easier.
And it’s that uniformity the authors mean by “truly random.” They say, lamenting the problem legacy “quantum random number generators” have is that
…for any real-world implementation with experimental imperfections, this randomness is not perfect—the probability that the next bit, 0 or 1, can be correctly predicted might deviate from the ideal value of 1/2. The amount of this deviation is called the bias [their term].
What about coin flips, as mentioned in the opening? Are they “random number generators”? Coins, as I explain in this video, don’t have probabilities. Nothing has a probability.
As the authors said, you cannot have a perfectly symmetric coin: it is not possible. And even if it were possible, you cannot have a perfect “flipping environment”. What precisely would that even mean? Precisely. What we have is an object, with a varying mass, throw into the air with rotation, mostly confined to one dimension, but present in all three, that rises to some height in air of a certain temperature, moisture, density, with whatever wind, and which comes down and is grabbed, or lands, in a certain way on some surface and ultimately comes to rest with one side facing up.
This is an entirely physical process, with causes and conditions that can be known and manipulated—which I and my father did. The machine flips coins and manufactures heads. Because it turns out those causes aren’t that difficult to control.
Thus, given all this, the probability of a head in a coin flip is 1.
But given something entirely different, like the conditions under which most flip coins, the probability is very different than 1, and indeed is 1/2, given only the evidence that a flip will be made. My machine does not produce random flips because the full explanation of the flip is known.
If you need maximally unpredictable numbers (a far better term, I think), for instance for security reasons in cryptographic systems, you need a device which produces numbers whose predictions cannot be bested over predicting uniformity, even if an enemy gains access to the device afterwards. The only way this can be done is if the causes of these numbers can remain unknown to everybody.
This is what makes quantum mechanical devices appear ideal, because the ultimate causes of events are (it is claimed) unknown. Yet QM devices are still in the world, and in the world we know a lot of causes, such as why a particular counter registered whatever number it just registered, even if the counter was hooked to a QM device. The authors get it right: “unpredictability is not an inherent property of a bitstring [the numbers] itself, but rather of the process that generates it.”
Worse, in the search for perfection, is that sometimes knowledge of past values produced by whatever device is used can give relevant information about future values, even if the device produces its requisite uniform numbers. This is important because if the numbers, used in for instance cryptographic keys, can be predicted, then the keys can be guessed.
The authors’ idea is to take a partially predictable (away from uniformity) string of numbers (bits) from a QM measurement process and “amplify” the “randomness” of those numbers. A term I cannot love. Here’s their picture:
Some process (we don’t need to understand what) generates two strings of bits, X and Y, these are put into some black box which takes advantage of certain QM properties (that Bell business), which produces another “entangled” string, and finally are all joined together in a mathematical way and out pops “perfect output randomness.”
Where “perfect” here means imperfect. Because, as even the authors admit and write into their equations, the first QM process, which takes place in the world with macro measurement equipment, has a chance of erring, as does the combination process later downstream (they never state what these erring chances could be). The combining procedure itself even has an admitted chance of containing information that allows predictability beyond 1/2.
They did try their experiment with certain machinery, not important to us, which produced long strings with passed NIST tests for unpredictability. So adding in a layer of a second QM process to the first QM process works, up to point, as would be expected. But most of the causes of the QM process are not known. Thus, and enemy can gain access to your “random” number generator and, as long as it didn’t store your numbers, they could not reconstruct your sequence.
Unless that enemy can gain access to the causes behind QM events.
Now many say this is impossible because of Bell’s theorem. Which we here do not have to understand, except to state that this is a mistaken reading of that theorem. Bell merely seems to imply that if had knowledge of local causes, we could not be able to guess QM events. Which leaves open the possibility we might gain at least some knowledge of non-local causes. This article gives one idea (and there are several).
That is too much for us to go into here, except to say that the notion that QM events are uncaused or are caused by “probability” in some mysterious way, as some claim, is false. Of course QM events have causes, explanations for their being. As all things do. If things happened for “no reason”, then only absurdity results. Magic would have to be invoked to explain how the “no reason” QM regime suddenly becomes “reason” macro regime. All of which shows you how important a Reality-based philosophy of Nature is to Science.
Video
Here are the various ways to support this work:
I think I will have a second random cup of coffee before my head explodes.
So, what you're saying is, Cathy, that neither coin flips nor perfectly crafted dice can ever be "perfectly" random because the act of flipping or tossing them is a part of the *cause* of how they land, and that action is never the same, however incalculable it may be to the human observers?
Makes sense.
When I need a random number I phone up a Hollywood celebrity and ask them "what number am I thinking of?"