11
$\begingroup$

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 :).

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Not directly addressing the question, but here is another high-level description and discussion of the area and result by one of the two authors, on the MIT Theory blog. $\endgroup$
    – Clement C.
    Nov 1, 2015 at 23:15
  • $\begingroup$ I think quantum randomness expansion addresses an orthogonal question to derandomization. In particular, it assumes that you already have devices that can produce random bits. The question being addressed is verifying the randomness of those devices, which itself requires the use of randomized tests. The expansion refers to how much randomness is needed for the test versus how much new randomness is produced by the devices during the test. $\endgroup$
    – Thomas
    Nov 1, 2015 at 23:37

1 Answer 1

Reset to default
15
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I see. So while in a "normal" derandomization argument (say via an expander) it's the "algorithm designer" that constructs a proof of correctness. Here it's an actual interactive proof that establishes a proof of randomness, which is different. $\endgroup$
    – Suresh Venkat
    Nov 2, 2015 at 15:59
  • $\begingroup$ That's exactly right! $\endgroup$
    – Henry Yuen
    Nov 2, 2015 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.