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

Back to Random Numbers

So now that we know something about Bell’s theorem, and the inherent randomness of quantum measurement outcomes, what are the implications for our original subject—how to generate numbers that are guaranteed to be random? You might think that the problem is now solved! After all, Bell’s theorem reassures us that quantum measurement outcomes really are unpredictable, just as quantum mechanics always claimed they were.

Well, not so fast. There’s still the problem that you might not believe that some particular quantum random-number generator is free of hardware problems that introduce subtle biases. Or you might even worry about more bizarre possibilities, such as that nature delivers true random numbers “when it needs to” (as in the specific case of the CHSH game) but reverts back to determinism for other quantum experiments.

For both reasons, a natural idea would be to use Alice and Bob’s outputs in the CHSH game themselves as a source of random numbers. After all, if we find Alice and Bob winning the CHSH game 85.4 percent of the time, despite being far away from each other, then we become authorized to make an extremely strong statement: “Either Alice and Bob’s outputs had genuine unpredictability to them, or else the causal structure of spacetime itself is nothing like what we thought it was.”

Crucially, nowhere in this statement do we need to assume the correct functioning of Alice and Bob’s hardware, or even the truth of quantum mechanics itself. Yes, both of those assumptions are relevant to explaining why Alice and Bob can win the CHSH game 85.4 percent of the time. However, once a skeptic sees that they are winning the game with the requisite probability, that fact (plus the causal structure of spacetime) is all the skeptic needs to know. There’s nothing further about physics that needs to be accepted on faith.

However, when we think more about this idea of using the CHSH game as a random number source, a new difficulty crops up. Namely, for Alice and Bob to play the CHSH game in the first place, they need inputs (the colors of their respective cards), and those inputs are already supposed to be random! So to get randomness out, we need to put randomness in, and it’s not clear that there’s ever any net benefit.

Maybe there’s a way to modify the game, so that we get out more randomness than we have to put in. If so, then even if we had to start with a small random “seed,” there could still be an immense gain as we use CHSH to grow our seed into a much larger number of random bits.

The question of whether this sort of “quantum-certified randomness expansion” is possible was firrst asked by Roger Colbeck, in his 2006 Ph.D. thesis. Along with Adrian Kent, Colbeck gave a protocol that used a CHSH-like game to increase the number of random bits available by a fixed percentage. For example, starting with 100 random bits, the scheme could produce 130 or so as output, whereas starting with 1,000, it could produce 1,300. Then, in a 2010 Nature paper, Stefano Pironio of the Free University of Belgium and his colleagues did better, showing how to use CHSH to expand an n-bit random starting seed into about n2 bits of random output. How far could this go? In 2012, Umesh Vazirani and Thomas Vidick showed for the first time how to achieve exponential randomness expansion, using only about n bits of random input to get 2n bits of random output.

The central idea in all of these protocols is simply to be stingy with the use of randomness. We ask Alice and Bob to play the CHSH game over and over again. However, in almost all of the plays, they simply both receive red cards—leading to a boring but also “cheap” (in terms of randomness) game. Only for a few randomly chosen plays does one of them receive a blue card. However, if, say Alice receives a red card, she has no idea whether this is one of the rare plays that “counts” and is one where Bob received a blue card, and vice versa. So, not knowing which plays they’re being “tested on,” Alice and Bob have no choice but to play the game correctly, and therefore generate random bits, for almost all of the plays. The cleverer you are at sticking in the “spot checks,” the more randomness expansion you can get.

comments powered by Disqus


Subscribe to American Scientist