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

Infinite Expansion

For technical reasons, the protocol of Vazirani and Vidick couldn’t provide more than exponential expansion. But, frustratingly, there was no proof that even greater expansion wasn’t possible. Indeed, no one could rule out the amazing possibility of so-called infinite expansion: Starting from a fixed random seed (say of 1,000 bits), we could use Alice and Bob to get as many more random bits as we wanted, with no limit whatsoever. There was even an intuitive argument that suggested that infinite expansion should be possible; why not reinvest the randomness? That is, after running the Vazirani-Vidick protocol to turn n random bits into 2n bits, why not use the 2n bits to get 22n bits, and so on forever?

The difficulty comes down to a simple question: The output bits might be random, but to whom? They may look random to you, or to any third party (say, an eavesdropper), but not to Alice and Bob, because they generated the bits. So for example, suppose you were foolhardy enough to use those 2nbits as the seed for a second run of the Vazirani-Vidick protocol—greedily asking Alice and Bob, like the mythical Rumpelstiltskin, to spin them into 22n random bits. In that case, Alice and Bob could quickly figure out that your new “random challenges” were deterministically generated by the seed that they themselves had given you in the last round. So from that point forward, Alice and Bob could cheat, giving you bits that were almost entirely deterministic, and using randomness only to pass your occasional, predictable challenges. Maybe there’s a way to confuse Alice and Bob and force them to spin more randomness, but no one has figured it out yet.

In the meantime, a simple fix is to bring in additional players. Suppose we have not only Alice and Bob, but also Charlie, Diane, Edith, and Frank. In that case, we can use Alice and Bob to spin n random input bits into 2n random output bits (random to everyone else, though not to Alice and Bob), then use Charlie and Diane to spin Alice and Bob’s 2n bits into 22n random bits, then use Edith and Frank to spin 22n bits into 222nbits, and so on. However, an obvious problem with this approach is that the more random bits we want, the more players we need.

If we want infinite randomness expansion with a fixed number of players, then we also need a “randomness-laundering scheme,” a way of taking random bits that are “dirty” (correlated with the players’ knowledge in some complicated way), and converting them into random bits that are “clean” (uncorrelated with at least some players’ knowledge). Crucially, such a randomness-laundering scheme would need to work even though Alice, Bob, and anyone we might use to execute the scheme might try to cheat, and keep the randomness “dirty” (that is, predictable to at least some of them).

Fortunately, it turns out that the CHSH game is a multipurpose tool: It also lets us launder randomness! That this ability is possible emerged from a seemingly unrelated 2012 breakthrough by Ben Reichardt, Falk Unger, and Umesh Vazirani. They proved a “rigidity theorem” for the CHSH game, showing that, if Alice and Bob play many instances of the game and win about 85.4 percent of them, then they must be measuring their entangled particles in a way that’s nearly “isomorphic” to the procedure shown in the figure on the first page. Even if we allow unlimited quantum entanglement, there’s no fundamentally different strategy that does as well at the CHSH game.

In 2013, MIT graduate students Matt Coudron and Henry Yuen put all the pieces together. First, by using Reichardt, Unger, and Vazirani’s rigidity theorem, they showed how to design a randomness laundering protocol which uses the two players Alice and Bob, takes n “dirty” random bits as input, and produces nc “clean” random bits as output, where c is some small positive constant (say, 1/10). The “dirty” bits could be correlated with anything except Alice and Bob themselves, whereas the “clean” bits are guaranteed to be uncorrelated with anything except Alice and Bob themselves. Notice that, just like a real laundry machine, the protocol actually shrinks the number of random bits every time it runs—the exact opposite of what we wanted! However, this polynomial shrinkage will be dwarfed by the exponential expansion provided by the Vazirani-Vidick protocol, so ultimately it won’t matter.

2014-07TechnoAaronsonFp270.jpgClick to Enlarge ImageCoudron and Yuen’s final protocol (illustrated at right) involves six players who perform alternating rounds of expanding and laundering. First Alice and Bob expand the original n-bit random seed into 2n dirty random bits. Next Charlie and Diane launder the 2n dirty bits to get 2cn clean bits. Then, having been laundered, these 2cn clean bits are ready for Alice and Bob to expand again, into 22cn dirty bits. Then Edith and Frank launder these 22cn dirty bits into 2c2cn clean bits, which Alice and Bob expand, and so on forever. We need two laundromats, working in alternate shifts, to clean the bits for the other players, so no one sees the same “dirty” bits twice.

Earlier this year, a simpler approach to infinite randomness expansion emerged from work by Carl Miller, Yaoyun Shi, Kai-Min Chung, and Xiaodi Wu. The new approach bypasses the need for Reichardt, Unger, and Vazirani’s rigidity theorem, and requires only four players rather than Coudron and Yuen’s six. It’s still not known whether infinite randomness expansion is possible using just two or three players. Also unknown, at present, is the exact number of random seed bits needed to jump-start this unending process: Do 1,000 seed bits suffice? 100? (In general, the answer will depend somewhat on just how statistically certain we want to be that the output bits are random.)

comments powered by Disqus


Subscribe to American Scientist