# Is a quantum system mandatory for generating true random sequence?

Is a quantum system necessary if we want to generate true random sequence? The mathematical framework used for classical mechanics doesn't involve any random value. But the mathematical framework of quantum mechanics involves randomness by definition. Can we argue based on these information that a true random number generator must use quantum mechanics? If anyone claims that s/he has a true random number generator and fails to prove that s/he is exploiting quantum mechanics can I discard the claim on the basis that s/he is not using quantum mechanics?

-

Classical chaotic systems can be used to generate random numbers. Specifically, if a system is chaotic then it will have a positive Lyapunov exponent and so will be unpredictable. Although classical mechanics is deterministic, it is not possible to know the initial conditions to infinite precision. Therefore it is not possible to predict the future state of a chaotic system. If the future state cannot be predicted by any means, then it is random. You would have to make a study of the particular system in order to determine the rate at which randomness is produced, and the best way to extract it, but it can be done. Chaotic systems are all around us (the weather, turbulence, various electronic circuits, etc.)

However, in a practical sense, it is not possible to do anything without quantum mechanics since you live in a quantum world. In other words, anything you build in this physical world will, underneath it all, be quantum mechanical.

Now, with quantum mechanics there is something very nice that you can do. It is in fact possible to build a random number generator in which the numbers produced are certifiably random, even if you do not trust the hardware (say, the hardware was built by your adversary). For more information on this, search for "Certifiable quantum dice" by Umesh Vazirani (which I have not read).

-
Is this a the orem that 'Although classical mechanics is deterministic, it is not possible to know the initial conditions to infinite precision.'? –  Omar Shehab Mar 11 '13 at 21:13
Well, I don't think anyone would claim detailed knowledge of the initial conditions of the universe. If you did know, it would probably take an infinite amount of paper to write down to infinite precision. And it really is the entire universe that you have to consider, since no system can be perfectly isolated from the outside world. Entropy (in the information theoretical sense) will always leak in to your system from the outside world. –  Dan Stahlke Mar 12 '13 at 1:36
Is this because of the universe itself or the math we use to understand it? For example, take a circle of unit radius. You will never be able to determine the area with exact precision as you can never know the value of Pi with exact precision. In case of universe is it because of infinite parameters to consider or just the math? –  Omar Shehab Mar 12 '13 at 1:45
I don't think anyone can say either way. It could be that the universe had some initial conditions that were expressible by a simple equation, but I don't think we'll ever know. It's just speculation. Nobody's ever going to be able to use that to predict every detail of some chaotic system though. That is to say, I don't think anyone's going to work out from first principles whether it's going to be raining in my hometown on this day next year. So, there is no theorem, just strong intuition that in a practical sense exact initial conditions are unknowable. –  Dan Stahlke Mar 12 '13 at 2:08
right now I am taking a quantum optics course. We use coherent states to describe single photon, double photon, triple photon states etc. We consider a power series which eventually make us to approximate up to some point based on a parameter of the experimental setup. As it is a power series we can never do the exact calculation but always try to approximate. Can I argue that when ever there is a multi unit systems (two units and beyond) we have to think about interactions (or single unit system interacting with itself) and eventually these kind of approximations (contd...) –  Omar Shehab Mar 12 '13 at 5:00

It helps to review Sidney Coleman's Quantum Mechanics In Your Face lecture starting around minute 52:00 and more specifically after min 55:00. There he talks about the difficulty in determining the randomness of sequences. Particularly, it is not possible to determine if a finite sequence is random in classical theory, we can only really consider infinite sequences for tests of randomness.

So a test for randomness would look to see if sum value $\sigma$ sums to $0$ at $\infty$.

$$\lim_{N\to\infty} \bar{\sigma}^N = \lim_{N\to\infty}\dfrac{1}{N}\sum_{r=1}^N \sigma_r = 0$$

as well as seeing if correlations are not present in long strings of data.

$$\lim_{N\to\infty} \bar{\sigma}^{N,a} = \lim_{N\to\infty}\dfrac{1}{N}\sum_{r=1}^N \sigma_r \sigma_{r+a}= 0$$ for all a

$$\lim_{N\to\infty} \bar{\sigma}^{N,a,b} = \lim_{N\to\infty}\dfrac{1}{N}\sum_{r=1}^N \sigma_r \sigma_{r+a} \sigma_{r+b}= 0$$ for all a,b etc.

This situation can be explained in quantum mechanics by asking whether a particular sequence of information can be seen as an eigenstate of an operator with an eigenvalue of zero.

$$\lim_{N\to\infty} \bar{\sigma_z}^N = \lim_{N\to\infty}\dfrac{1}{N}\sum_{r=1}^N \sigma_z^{(r)} = 0$$

The derivation is:

$$\| \bar{\sigma_z}^N | \psi \rangle \|^2 = \dfrac{1}{N^2} \langle\psi| \sum_{r,s}^N \sigma_z^{(r)}\sigma_z^{(s)}| \psi\rangle$$

$$\langle\psi| \sigma_z^{(r)}\sigma_z^{(s)}| \psi\rangle = \delta^{rs}$$

$$\therefore \lim_{N\to\infty} \| \bar{\sigma_z}^N | \psi \rangle \|^2 =\lim_{N\to\infty} \dfrac{1}{N^2}N=0$$

which is definitely a deterministic calculation and a random sequence.

IOW, the sequence is random, however the means to derive it is deterministic. Quantum mechanics itself is a deterministic theory, however the random sequence can be transformed into an observable within the framework of the theory.

UPDATE

In order to address a criticism that the question was not fully answered.

Is a quantum system necessary if we want to generate true random sequence?

This somewhat depends on whether one believes there is a quantum explanation behind all natural phenomenon. What we do know is that a true random number sequence can not be generated with a digital computer. Computers can only generate pseudo-random numbers which are produced deterministically via some algorithm (with the exception of the possibility that one could conceivably build some type of analog circuit like a mini-lava lamp and then take random numbers from that object and digitize them, unbeknownst to the user).

Can we argue based on these information that a true random number generator must use quantum mechanics?

As explained above, quantum mechanics is deterministic, however random sequences can be understood as observables within the theory. If you took some amount of a radioactive material and surrounded it with some detection sensors, the particular sequence of emissions detected would be random in nature.

If anyone claims that s/he has a true random number generator and fails to prove that s/he is exploiting quantum mechanics can I discard the claim on the basis that s/he is not using quantum mechanics?

At a fundamental level the answer is yes. All processes so far encountered can in principle be described using quantum mechanics (although it is not always convenient to do so). However, one must be careful in distinguishing the words randomness and unpredictable. In a classical deterministic system, such as classical mechanics, by definition randomness doesn't exist. So it is nonsensical in a deterministic system to talk about randomness. Again, quantum mechanics side steps this particular issue by making states indeterminate before observation. However, some advocates for super-determinism will argue, even quantum mechanics is fundamentally deterministic and every outcome is still ultimately the result of a "conspiracy". This is arguably an absurd position since it is in some sense tautological.

It is helpful to think in terms of Algorithmic Randomness (Martin-Lof randomness), which can be most simply understood in terms of Kolmogorov complexity where an string of binary digits is considered algorithmically random if it is incompressible. An equation that can generate a string of pseudorandom numbers is intuitively viewed as a compression of that string, which gets back to the argument about digital computers not being able to generate anything but pseudorandom numbers.

Sidney Coleman's approach, as discussed above, is to show that we can sensible talk about random outcomes and deterministic processes and still be consistent with quantum mechanics. In this sense quantum mechanics is superior to pure classical determinism, which effectively rules out any possibility of true randomness.

-
I will watch the vide asap. –  Omar Shehab Mar 12 '13 at 5:07

If you believe in decoherence the the randomness is only apparent and not real. It arises from the interaction with the huge number of degrees of freedom in the environment. So quantum mechanics cannot (by itself) produce a true random number generator.

-
whether you believe in decoherence not, like Hal Sawyers you have not really answered the question: is there any other way to get a true random sequence. I should add that any computed sequence could not be truly random, but there may be other methods. –  hdhondt Mar 11 '13 at 9:08
@hdhondt: surely the question is "Can we argue based on these information that a true random number generator must use quantum mechanics?". The answer is no. –  John Rennie Mar 11 '13 at 9:51
@JohnRennie, If I have a photon of horizontal polarization and I direct it at a diagonal beam splitter, isn't weather or not the photon will pass through completely random? Could you please elaborate how decoherence would make it deterministic? –  Mew Mar 11 '13 at 11:07
@Chris: not according to the theory of decoherence. I normally point people to Wikipedia but their article on decoherence is a bit technical. A quick Google should find plenty of relevant articles. –  John Rennie Mar 11 '13 at 11:10
Yes wikipedia's article on it doesn't seem very clear. I'll keep looking online. –  Mew Mar 11 '13 at 11:14