Generating "infinite" randomness from a constant number of sources I recently came across a paper by Coudron and Yuen on randomness expansion using quantum devices. The main result of the work is that it is possible to generate "infinite" randomness from a constant number of sources (that is, the number of random bits generated depends only on the number of rounds of the protocol and not on the number of sources). 

Naively, this sounds to me like the result allows derandomization of any randomized algorithm with quantum sources, and would imply some kind of containment of randomized complexity classes inside a corresponding quantum class. 

But I don't really understand quantum information theory, and am sure there are many subtleties I'm missing. Not to mention that if such claims were possible, the authors would have made it. So my question is:


  Does the existence of "infinite randomness expansion" as described in the paper (and all the related work) imply some kind of derandomization statements for randomized complexity classes ? And if not, why not ? 


Update: I was pointed to this excellent high level overview of the area and of the above paper by Scott Aaronson. Unfortunately I'm still confused :).
This is a great question, Suresh!

Our randomness expansion result does not imply any complexity theoretic result. Here's one way to understand the result: we believe that quantum mechanics governs the world, and under this assumption, there are quantum devices that generate genuine, true, information-theoretic randomness.

However, imagine that you're mistrustful of these boxes that claim to do this wonky quantum stuff and generate randomness (for some, this may not take too much imagining). You don't want to deal with qubits. All you understand are classical bit strings. 

Randomness expansion is a protocol where you, as a classical verifier, can interact with a bunch of black boxes (think of them as non-communicating provers), and after running a protocol with these black boxes, you've certified that their outputs contain very high entropy -- if the provers pass. Furthermore, the amount of randomness you started with is much less than the output entropy you certified. 

In other words, it's an interactive proof for randomness generation. 

So, the only "derandomization" aspect of it is to argue that the protocol itself requires small startup randomness. But the outcome is very un-derandomized: the output produced by the boxes is true randomness, not pseudorandomness (i.e. no computational assumptions).