Obviously, regular computers can't generate random numbers on their own, since they're inherently systematic machines. Would quantum computing be able to run a true RNG without a seed based off user input (or any other external variables)?
11
-
2$\begingroup$ Are you talking about usual models of quantum computing (such as quantum circuits and quantum Turing machines) or physical implementations of quantum computers? $\endgroup$– Tsuyoshi ItoCommented Feb 5, 2013 at 20:45
-
1$\begingroup$ In which sense is this question a soft question? $\endgroup$– Tsuyoshi ItoCommented Feb 5, 2013 at 20:46
-
$\begingroup$ @TsuyoshiIto I'm talking about the physical implementations, although the usual models sound interesting as well. $\endgroup$– JulesCommented Feb 5, 2013 at 21:12
-
1$\begingroup$ We do not know how scalable quantum computers will look like, and therefore the question is in the realm of future prediction or fortune telling. But my guess is that quantum computers will be controlled by classical computers, and that it is plausible that these classical computers require some randomness. $\endgroup$– Tsuyoshi ItoCommented Feb 5, 2013 at 21:17
-
1$\begingroup$ @NeelKrishnaswami: Yes, but actually you can do a little better. Radioactive decay can actually be triggered deliberately, so it doesn't necessarily serve as a way to generate randomness in a sufficiently adversarial setting. The recent work on randomness certified by Bell's theorem actually gives you something stronger. You have a protocol which treats the devices as black boxes, but still convinces you the string is random (without you ever needing to open the box).The way this works is to generate correlations which are not possible by classical pre-agreement,and which hence must be random. $\endgroup$– Joe FitzsimonsCommented Feb 6, 2013 at 9:11
|
Show 6 more comments
3 Answers
$\begingroup$
$\endgroup$
9
Actually, today's computers can generate truly random data on their own, and many in fact do. The random data is produced as a byproduct of the physics of the components, not as the product of a given algorithm, so it necessarily has to be implemented in hardware. But the hardware is readily available.
The popular TPM chip, for example, typically has an embedded TRNG, as do many security-oriented peripherals, such as some authentication tokens.
The actual mechanism used to harvest sources of entropy varies by component, but a simple-to-understand mechanism is the analysis of noise generated at the avalanche breakdown of a P-N junction of a diode or transistor. The noise from such a cascade is actually the amplification of the random movement of electrons at the junction - essentially amplifying the randomness of quantum mechanics to the level where it can be read by traditional electronics.
Obviously this isn't the only mechanism you can use to harvest randomness in today's computers, but it's an easy one to understand. In fact it's worth pointing out that the Intel's recent Ivy Bridge architecture introduced a new instruction: RDRAND, which yields the output of an on-chip TRNG. IEEE Spectrum has a detailed write-up of how it works.
-
1$\begingroup$ As with the other answer, a definition of "truly random" would help me understand what this means a lot better! I would guess some might not classify these sources as "truly random" because someone might be able to guess the bits better than 50-50 if they know something about, say, the operations the CPU is doing or the current temperature in the transistor. Is that correct? $\endgroup$– usulCommented Feb 6, 2013 at 5:33
-
3$\begingroup$ As Joe wrote: "Unfortunately commercial systems are not that sophisticated just yet, and so produce random numbers in a way that is difficult to test". I think the method Joe is referring to is different, i.e. it is quite simple to test if the generated numbers are really random. See this article for more details. $\endgroup$– KavehCommented Feb 6, 2013 at 7:21
-
2$\begingroup$ I guess I should jump in here and explain what I meant. Quantum mechanics allows for true randomness in the sense that the outcome of certain experiments is independent of the prior state of both the system and the environment. Most of the ways people currently generate randomness does not really come from this, but rather from either classical chaotic systems (where some minor uncontrolled imprecission in initial preparation leads to vastly different outcomes) or by extracting noise from the environment. $\endgroup$ Commented Feb 7, 2013 at 6:31
-
2$\begingroup$ (Continued) The problem with these systems is illustrated nicely by Dilbert, here: dilbert.com/strips/comic/2001-10-25 But while quantum mechanics can provide the same results, and may underly the randomness captured from the environment in other systems, there are certain quantum protocols, such as those pointed to by @Kaveh and YonatanN, which go further and actually provide an interactive protocol which proves randomness. This is something which is totally impossible classically, and which can't be mimiced by systems which extract noise from the environment alone. $\endgroup$ Commented Feb 7, 2013 at 6:32
-
1$\begingroup$ As noted by one anonymous editor, the output of RDRAND is post-processed through a whitening mechanism. This does not set it apart from other TRNGS; whitening is a necessary aspect of turning any truly random bit generator into something cryptographically usable. $\endgroup$– tylerlCommented Feb 6, 2015 at 5:49
$\begingroup$
$\endgroup$
10
Yes, quantum computation allows the generation of truly random numbers, and the operations necessary are so simple companies like id Quantique are already selling quantum random number generators. It is even possible to generate random numbers in a way that proves to the person generating them that they are random (via a violation of Bell's inequality) but this does need a short seed for the proof to be complete (though the numbers are random anyway). Unfortunately commercial systems are not that sophisticated just yet, and so produce random numbers in a way that is difficult to test.
-
2$\begingroup$ @RickyDemer I believe Joe's referring to this paper: arxiv.org/abs/0911.3427 . $\endgroup$ Commented Feb 6, 2013 at 4:57
-
1$\begingroup$ @RickyDemer, check these recent article by Umesh Vazirani: "Certifiable Quantum Dice", "Certifiable Quantum Dice: or, true random number generation secure against quantum adversaries" $\endgroup$– KavehCommented Feb 6, 2013 at 6:30
-
2$\begingroup$ @usul: Consider a device which generates random numbers which has an internal state $\rho$, and the environment is in state $\epsilon$. Then for anything which can reasonably be called a random number generator, which has possible outcomes $x_i$ we have $P(x_i) \notin \[0,1\]$, since otherwise there is no randomness at all. For a pseudo random number generator, this equation is satisfied, but $P(x_i|\rho)\in \[0,1\]$. Hardware random number generators, such as in the other answer satisfy a stronger condition: $P(x_i|\rho)\notin \[0,1\]$. $\endgroup$ Commented Feb 6, 2013 at 9:01
-
2$\begingroup$ (continued) However, these are generally based on processes which are deterministic, even though they outcome is not dictated solely by the state of the device, and so $P(x_i|\rho,\epsilon) \in \[0,1\]$. Quantum random number generators operate via a process which is inherently stochastic, and hence satisfy the strongest possible such definition of randomness: $P(x_i|\rho,\epsilon)\notin \[0,1\]$. $\endgroup$ Commented Feb 6, 2013 at 9:04
-
2$\begingroup$ @JuanBermejoVega: The commercial systems (i.e. id Quantique's RNG) are not yet at the stage of being able to do device independent randomness amplification, but it is something that is possible. There have been a bunch of papers in recent years showing how to extract more and more randomness from a short random seed in an entirely device independent manner. However, ultimately you do need a short seed to kick off the whole process, so you can only really hope to expand the randomness rather than generating it from nothing (at least if you want device independence). $\endgroup$ Commented Oct 9, 2014 at 18:42
$\begingroup$
$\endgroup$
Besides what tylerl says, there's another reason why quantum computers aren't necessary for this. The main difficulty today with implementing quantum computers is to make it be able to do computations on many qubits together. We already have working quantum computers with only one or a few qubits. Those simple systems are enough to produce true randomness of the kind you have requested. In fact, the technology in the quantum cryptography hardware that are already commercially available is enough to produce random bits.
