You can also observe Brownian motion in colloids, like milk, that won’t settle out (I’ve done the experiment, with middle-schoolers). Though milk has its own problems, practically speaking.
I think there’s still confusion as to what’s being claimed. The point is, again, not the generation of randomness—there are, as has been pointed out, many much more simple ways to achieve that. The point is that this protocol allows you to create genuine randomness even on an untrusted device—that is, you get a random number, you know it’s a random number, and you know it hasn’t been spoofed in any way. This isn’t something that can be achieved classically: an attacker can always just manipulate any device in a clever way so as to output, say, a pre-chosen string of pseudorandom data.
To do this, you simply create arbitrary quantum circuits (which encode quantum operations performed on a set of qubits, i.e. a quantum computation) and send those to a quantum computer. That quantum computer will be able to solve these circuits much faster than any known classical method—what’s sometimes called ‘quantum supremacy’—and thus, you’ll know that what you get back originates in some quantum operation if it does so faster than any classical computer could produce the result, and it actually solves the problem you posed—that is, if it’s a valid output of the quantum circuit.
The latter is what’s being then verified by use of classical computation—essentially, checking whether the distribution of answers matches the challenge circuits you sent (technically, computing something called the linear cross-entropy benchmark). Unfortunately, this is not one of the cases where quantum computers solve a problem whose solution is easily verified, like e.g. factoring. So this is basically as hard as trying to spoof the output, but you, unlike any hypothetical adversary, have time.
But if now the answer you got matches the problem you sent, and was given to you in a time shorter than any amount of classical computation currently existing on the planet could produce it, you know that it must be the output of a quantum computation and therefore, also know it to be genuinely random (since quantum measurement outcomes are very strongly believed to be algorithmically random). So it’s not the case that you do any classical randomness tests on the output, which could really only ever be inconclusive; it’s the laws of physics that guarantee you the randomness of the obtained data.
This is something you couldn’t achieve without a quantum computer that genuinely outperforms any classical computation, so it’s prima facie useful task that can only be solved by quantum computing, and it’s really currently the only task for which this is true. Of course, the practical applicability is severely hampered by the amount of classical computation still necessary to verify the result—the simulation becomes intractable even for a few tens of qubits on any classical hardware, so you might at most get an output rate of a few bits per hour.
OK, so it protects you against some hypothetical attacks, but there are still plenty of other attacks of comparable difficulty that it doesn’t protect against. If you don’t trust that your RNG hasn’t been compromised, then how much trust do you have that the classical computation you’re using to verify the quantum computation hasn’t been compromised? Or, how do you choose what problems you sent? Maybe someone precomputed the answers to some problems, taking as much time as is needed, and then compromised your problem-choosing system so it would only ask the questions to which they already knew the answers. Or maybe the quantum random bit supplier has not just one quantum computer, but ten of them, gets the answers from all ten of them, and then picks the one that they want to serve back to you.
Well, the aim isn’t to safeguard against all possible attacks—in the end, you can always imagine that the adversary has perfect control over all the involved systems. And the trustworthiness of the verifier is indeed a necessary assumption, but one that might be less troublesome than a source of randomness accessed via the public internet, say. (An approach to mitigate the risk from a compromised verifier is discussed in the paper, which is to just use a bunch of them and XOR their results, which results in a certifiably random output as long as at least one of them is honest.)
Also, manipulation on the end of the quantum computer isn’t going to help: the procedure for spoofing the output there is going to be exponentially hard even with access to quantum resources (modulo the usual compexity theoretic assumptions).
But really, the claim is just that there is a real cryptographic problem, the generation of certifiably random numbers, that is shown to have a solution using quantum computers that isn’t possible with classical resources. It doesn’t solve any of a host of unrelated problems, but it didn’t set out to.
If a video feed of lava lamps is a valid source of randomness can’t any video feed also be used? They could aim a camera at Times Square or the sky or anywhere else really, ultimately the conversion to a string would yield a random number. Or am I missing something?
I think you might be right as long as the image the camera sees is forever changing in an unpredictable way. Times Square is probably changing a lot at 6p but maybe not enough at 3a.
The sky may change or it may be a clear sky with no visible change.
The Lava Lamps guarantee a perpetually morphing picture in an unpredictable way.
As an aside:
Welcome to the SDMB! I think you will like it here.
Nothing more than “lava lamps are neat.”
Well, you don’t want it to be possible for anyone to deliberately influence what the camera feed is saying. Which means that, even if you’re using lava lamps, putting them in the lobby of your public offices is a bad idea.
Unless the entire point is just “lava lamps are neat”.
I wondered about this but I am not so sure.
Doubtless people walk in and stand in front of the wall looking at it blocking some lamps from the camera’s view. But there are 100 of them and it can always see some, probably most of them. And, you just become part of the randomness.
Unless you walked in with a screen to block the view of all the lamps I am not sure you could affect the random number generator (and, as I mentioned earlier, I am willing to bet their real RNG is happening elsewhere and not subject to someone smashing some lamps in the lobby).
It really is just “lava lamps are neat”. It’s a source of secondary entropy that is added to a larger entropy pool which is then used to seed a downstream PRNG, at least in the production version that’s talked about most often. It’s not meant to have any particularly robust properties beyond being an independent source, and even just a single bit flipping is enough to salt the whole entropy pool and make the final output unpredictable. If the rest of the entropy pool were somehow compromised, then you’d want more than one bit of variation in this secondary source, but, fine, flip three bits out of the tens of millions and you already have an uncomputably large output space that can’t be brute forced.
Also software regression testing after fixing a bug.
I am not a mathematician, but if you are applying formulas to data to change the distribution, is the data still considered random? Also, what application would you want truly random data for, yet also want it to be uniformly distributed? It seems like conflicting goals. (I have seen questions like, “I want a series of random numbers, but I don’t wany any to be repeated.” OK, then you don’t really want random numbers.)
Random from a distribution is perfectly fine. Something like a Gaussian distribution is common. So long as I know the distribution drawn from, it remains perfectly random. If I assumed a different distribution to what I am getting, then randomness is degraded.
Adding Gaussian noise is useful in some applications. As are other noise distributions.
Choice of distribution depends upon the domain and the problem. Anything involving simulating physical processes or models of processes will want appropriate distributions.
Monte-Carlo methods might use a whole range of distributions, including flat. Gambling likes flat. Same for cryptography.
Random with no repeats is a matter of where you stand. Shuffling a card deck is just that. Can be perfectly random. But once you start dealing the cards the expectation of the next card dealt changes. Clearly it also depends on the range of values available and how many you choose. A few hundred choices from a 64 bit RNG is never going to matter. Drawing from the deck when you know how many picture cards have already gone is a different matter.
So a demand for no repeats is more a matter of how you defined the random process you need.
Most often, when people say “random”, they mean “random from a uniform distribution”. If someone says “pick a random number from 1 to 6”, for instance, they probably don’t mean “50% chance for 1, 25% chance for 2, 12.5% chance for 3, 6.25% chance for 4, and 3.125% chance for either of 5 or 6”, even though that’s a perfectly valid random distribution. They probably mean “roll a 6-sided die”, which is a uniform distribution.
If you know the distribution of your random numbers, and you need a different one, like a uniform distribution, then you can transform your results. For example, going from a Gaussian distribution to a uniform distribution can be accomplished via an inverse Box–Muller transform or many other alternatives.
What is the distinction here?
If I roll a fair die I might get an uneven distribution of numbers on six rolls. If I rolled the die one million times I would expect a near uniform distribution. If not, should I call those rolls random?
I get we would expect streaks in one million rolls (e.g. ten sixes in a row) but, overall, the numbers should be close to uniform.
If it is a fair die, rolling one time produces a single number, but the point is that the probability of any given number was the same. If you roll it a million times and it keeps coming up 6 (or whatever), you want to find a different casino— the die was almost certainly not fair.
In addition to @DPRK’s excellent point, you can also consider the idea of rolling a pair of perfectly fair 6-sided dice and summing the result of the two dice.
That distribution ranges from 2 to 12, and is totally random. But is very much non-uniform. 7 is more likely than 6 or 8 which are more likely than 5 or 9 … which are more likely than 2 or 12. And 1 is flat impossible despite a 1-spot appearing on both dice.
That gives a very crude and lumpy approximation of a Gaussian distribution. Call it a “badly pixelated Gaussian” and you have the flavor even if that’s mathematically not strictly true.
Bottom line: “random” does not mean “equally likely”. It can have that equality as one of its global properties, but need not.
Central Limit Theorem being what it is, it actually is sort of true. And becomes more true as you add more dice.
Which is also one way to create a random number with a uniform distribution, since it’s straightforward to transform a Gaussian distribution.