On the Impossibility of Extracting Classical Randomness Using a Quantum Computer

DOI10.1007/11787006_18MaRDI QIDQ3591416zbMATH OpenOpenAlexFDO

Authors Yevgeniy Dodis, R. Renner

Publication date 11 September 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0612012

Mathematics Subject Classification ID

Quantum computation (81P68) Cryptography (94A60)

Abstract: In this work we initiate the question of whether quantum devices can provide us with an almost perfect source of classical randomness, and more generally, suffice for classical cryptographic tasks, such as encryption. Indeed, it is well known that classical computers are insufficient for either one of these tasks when all they have access to is a realistic imperfect source of randomness. On the other hand, quantum physics is inherently probabilistic which suggests that perhaps quantum computers can provide a reasonable way to overcome the above mentioned impossibility results. However, we show that this is not the case in a realistic setting where observations (measurements) are subject to noise.

Recommendations

• Quantum to classical randomness extractors
• Quantum-resilient randomness extraction. (Invited talk)
• Trevisan's extractor in the presence of quantum side information
• Randomness: quantum versus classical
• Two-source extractors secure against quantum adversaries

This page was built for publication: On the Impossibility of Extracting Classical Randomness Using a Quantum Computer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3591416)