On the Impossibility of Extracting Classical Randomness Using a Quantum Computer

Yevgeniy Dodis and Renato Renner

Automata, Languages and Programming — ICALP 2006, Springer-Verlag, pp. 204–215, Jul 2006, Available at http://arxiv.org/abs/quant-ph/0612012.

In this work we initiate the question of whether quantum computers can provide us with an almost perfect source of classical randomness, and more generally, suffice for classical cryptographic tasks, such as encryption. Indeed, it was observed that classical computers are insufficient for either one of these tasks when all they have access to is a realistic imperfect source of randomness, such as the Santha-Vazirani source.

We answer this question in the negative, even in the following very restrictive model. We generously assume that quantum computation is error-free, and all the errors come in the measurements. We further assume that all the measurement errors are not only small but also detectable: namely, all that can happen is that with a small probability the (perfectly performed) measurement will result in some distinguished symbol (indicating an erasure).

BibTeX Citation

@inproceedings{DodRen06,
    author       = {Yevgeniy Dodis and Renato Renner},
    title        = {On the Impossibility of Extracting Classical Randomness Using a Quantum Computer},
    booktitle    = {Automata, Languages and Programming --- ICALP 2006},
    pages        = 204--215,
    year         = 2006,
    month        = 7,
    note         = {Available at http://arxiv.org/abs/quant-ph/0612012},
    publisher    = {Springer-Verlag},
}

Files and Links

There are currently no associated files available.