Diode vs quantum computer

Question

Consider everyone's favourite pseudo random number generator, RANDU where V is the output of any successive iteration.

$$ V_{j+1} = 65539 \cdot V_j \; mod \; 2^{31} $$

I've purposefully chosen RANDU because it's not so good a PRNG, but works well in my example. Such linear congruential generators can be easily inverted to recover the state, and hence predict all future values.

Now let's replace the 65539 constant with a normal probability distribution, A. And let's define A as:-

A = NORMAL(μ =~ 65538.5, σ =~ 998) where the values are rough approximations obtained by mysterious empirical means. An integer rounding operation happens somewhere. It's my cunning model of a diode that might be used for an entropy source inside a TRNG. A represents the Avalanche Effect inside certain diodes, and looks like a children's Galton board as electrons tumble through the semiconductor material.

Lastly, assume we have a mega quantum computer slurping up all the output from this random generator. Are we able to predict the future output, given enough samples? And if not, can we say anything at all about the security of this generator? Would it now be a true unpredictable entropy source, or would we able to get almost perfect estimates of the future output sequence?

This is a highly theoretical question, but I'm trying to get a perspective on what may /may not be possible in derandomising entropy sources given quantum computers. I emphasise derandomising, as this and equivalent terms have previously been used in discussions of classical entropy sources for true random number generation. There is a long list of Similar Questions on my screen suggesting the upcoming end of traditional randomness. Some will posit that if the quantum computer can form sufficient simultaneous equations, it can determine the internal state of the diode via ersatz linear cryptanalysis. This is my attempt at countering.

Even some at America's NIST say that only a quantum device can produce true randomness, and that everything else produced by classical physics is just not. They say:

No device that relies on classical physical principles or operations can certify that its output is absolutely unpredictable.

News(?) to the UK government who regularly certify ERNIE running the country's national savings scheme. And he runs on diodes. Are NIST suggesting that he can be predicted, perhaps in the future with bigger computers?

Answer 1

Summary: an ounce of math wins over computers, quantum or not.

For most natural distributions of A (including samplings from a physical process like diode noise, not too much affected by conversion to digital or feedback from the state of the generator) and common rounding methods, we are able to predict future output given enough samples. A stream of zeroes is all it takes. With good likelihood that will start to match the generator's output, and keep on that way from there on, before $2^{32}$ steps, or just $2^6$ if A is rounded to integer before multiplication.

This follows from the fact that once and if $V_j$ reaches zero, it remains stuck there. And that if A is rounded to integer (either to nearest, lower, or higher) before multiplication, an iteration removes from $V_j$ as many bits of entropy as there are low-order bits at zero in the integer multiplicand that turns out to be used. This problem does not touch the original RANDU, because its multiplier is always odd.

---

Hereafter I consider using $V_{j+1}=65539\cdot(V_j+1)\bmod2^{31}$, which at least may avoid that issue.

Now the generator can be be fully predicted from future output, or not, depending on characteristics of A that are not explicitly stated in the question. It is entirely possible to have A such that after rounding it is always in a small set of integer values equal modulo $2^{31}$, and then A will have no influence on output.

However, for distributions of A arising from sampling a quantum phenomena similar to diode noise and not too much affected by conversion to digital or feedback from the state of the generator, the output will indeed be significantly influenced by A. Output will not be fully predictable from past output, because the multiplier is likely to vary unpredictably (for reasons explained in that other answer, for diode noise). I do not believe (or see anyone believing) that a quantum computer without a direct physical link to the particular source used for A is able to change that; at best it could improve to some degree on the advantage obtainable by a classical computer, or turn something almost predictable to totally predictable.

With the hypothesis in the previous paragraph, the generator will remain utterly distinguishable from random; but if we believe in the hypothesis of quantum physics to any degree (as overwhelmingly most physicians and engineers do), there will be some exploitable entropy in its output, so that seeding enough of that into a sound and generously dimensioned CSPRNG will yield a RNG computationally indistinguishable from random, including by the quantum computer in the question.

Answer 2

You cannot predict the future condition in this specific case, if you are assuming the avalanche model in a hardware context. The assumption is that you do not hit the maximum power dissipation of the device. You have two things happen: forced recombination, and tunneling. The tunneling has a work function and therefore a probability, and the recombination is based on the energy and the mean-time to collisions. You can get a feel for this by the following band picture:

As $W_b$ decreases due to the increasing voltage, the tunneling and recombination increases until you hit a thermal limit.

Specifically, in the circuit, you also have a random injection of noise due to the time it takes to go across the resistor as well. This circuit will generate a "random" condition relative to a clock, and this has been proven (trying to find reference from 1950s), but you then have to deal with the fact it is not temperature robust as I can supercool it to make it stick on a condition.

The point is: I cannot model this precisely due to the randomness of interface collisions (assuming a non-super cooled environment), which means that it does not have a correlation in a series. This then means that I cannot create a base coherence model. If I cannot create a coherence model, I cannot use a quantum system to tease out a probability of an answer.