Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

On the Impossibility of Extracting Classical Randomness Using a Quantum Computer

Yevgeniy Dodis, Renato Renner

Published Jan 1, 2006• 2 citations
Publisher
DOI
10.1007/11787006_18

Related papers

Analysis of Quantum Computers and Randomness

Deepak Chahal, Preethi Ravichandran Kumar

•Apr 21, 2020•0 citations

On the impossibility of extracting classical randomness using a quantum computer

Yevgeniy Dodis, Renato Renner

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.

arXiv:quant-ph/0612012•Dec 1, 2006•1 citation

Extraction of quantum randomness

Igor M. Arbekov, S. N. Molotkov

Uspekhi Fizicheskih Nauk•Nov 1, 2020•16 citations

On the Impossibility of Extracting Classical Randomness Using a Quantum Computer

Yevgeniy Dodis, Renato Renner

Abstract. 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 [SV86,MP91,DOPS04] 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 p ⊥ ≤ δ the (perfectly performed) measurement will result in some distinguished symbol ⊥ (indicating an “erasure”). Specifically, we assume that if an element x was supposed to be observed with probability px, in reality it might be observed with probability p ′ x ∈ [(1−δ)px, px], for some small δ> 0 (so that p ⊥ = 1 − P

•Dec 1, 2006•0 citations

ON QUANTUM RANDOMNESS

WORLD SCIENTIFIC eBooks•Apr 1, 1998•0 citations

An Explicit Non-Malleable Extraction Scheme for Quantum Randomness Amplification With Two Untrusted Devices

Mingfeng Xu, Wei Pan, Lianshan Yan +4 more

Quantum random number is a particularly important physical resource both for quantum communication and quantum cryptography. Quantum randomness amplification, as a key technology in quantum random number generation, has a significant counterintuitive effect: one can amplify weak randomness to almost perfect randomness by quantum systems, which is impossible in classical cryptography. In this letter, we propose an explicit quantum randomness amplification scheme with two untrusted devices, from which we could extract one single perfect random bit from weak random bits. An explicit non-malleable two-source extractor is introduced to extract perfect randomness from two independent min-entropy sources, which are derived from a Bell test with two untrusted devices. The universally composable security of the proposed protocol is proved.

IEEE Communications Letters•Oct 30, 2017•2 citations
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.
Abstract. 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 [SV86,MP91,DOPS04] 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 p ⊥ ≤ δ the (perfectly performed) measurement will result in some distinguished symbol ⊥ (indicating an “erasure”). Specifically, we assume that if an element x was supposed to be observed with probability px, in reality it might be observed with probability p ′ x ∈ [(1−δ)px, px], for some small δ> 0 (so that p ⊥ = 1 − P
Quantum random number is a particularly important physical resource both for quantum communication and quantum cryptography. Quantum randomness amplification, as a key technology in quantum random number generation, has a significant counterintuitive effect: one can amplify weak randomness to almost perfect randomness by quantum systems, which is impossible in classical cryptography. In this letter, we propose an explicit quantum randomness amplification scheme with two untrusted devices, from which we could extract one single perfect random bit from weak random bits. An explicit non-malleable two-source extractor is introduced to extract perfect randomness from two independent min-entropy sources, which are derived from a Bell test with two untrusted devices. The universally composable security of the proposed protocol is proved.