Quantum Advantage Now: Generation of True Random Numbers
The generation of true random numbers is a quantum advantage which exists today. Classical computers can only generate pseudo-random numbers, not true random numbers. Generation of true random numbers is a feature of even the most primitive quantum computers, today, which cannot be matched by any classical computer, today, or ever.
In truth, even simplistic pseudo-random number generators commonly available on cheap classical computers are more than adequate for many if not most applications. To many people and applications it is merely sufficient that a number look random rather than that it stand up to a rigorous statistical test. But when true random numbers are needed, such as for cryptography, a pseudo-random number generator just won’t do.
There are in fact specialized hardware solutions that give classical computers access to true random numbers, or at least something much closer than simplistic pseudo-random numbers, but it’s the special hardware that generates the random numbers, not the classical computer itself. For example:
- Radioactive decay, such as using a Geiger counter
- Cosmic rays and cosmic background radiation
- Detecting quantum vacuum fluctuations — ANU Quantum Random Numbers Server
- Atmospheric noise — Random.org
- Wikipedia Hardware random number generator article
- Building a Random Number Generating Geiger Counter — SparkFun Electronics
- RANDy — A True-Random Generator Based On Radioactive Decay
- HotBits: Genuine random numbers, generated by radioactive decay
- Nuclear Random Number Generator
- Quantum Random Number Generators paper by Herrero-Collantes and Garcia-Escartin
- Ferranti Mark 1 computer (1951) had a special instruction to generate a 20-bit random number in special hardware. This feature was supposedly suggested or designed by Alan Turing based on detecting electrical noise.
- Intel RDRAND instruction using on-chip thermal noise as an entropy source.
- Unix /dev/random device driver returning random bits from an entropy pool by collecting entropy (presumably random bits) from device drivers and other environmental sources accessible from the computer. Can work well or be problematic depending on the implementation and specific environment of the computer, so it’s not absolutely guaranteed to be a true random number.
- Using user input such as keyboard timing and mouse movement to generate entropy. Sometimes used to generate random encryption keys.
- National Institute of Standards and Technology (NIST) new quantum method for generating numbers guaranteed to be random by quantum mechanics. Uses a quantum mechanical device, but not a quantum computer per se.
- NIST Interoperable Randomness Beacons.
Although some of those techniques can work to some degree on a classical computer system without a specialized hardware random number generator, the point is that true random numbers cannot be generated exclusively using an algorithm executed solely by a deterministic Turing machine — the true random number bits, the entropy, must come from some non-algorithmic source, like fluctuations in a hardware device or the environment accessible by a hardware device. And even then, environmental considerations can render such solutions problematic to varying degrees.
Quantum mechanics provides a ready source for random behavior since all quantum state is probabilistic rather than strictly deterministic.
So, by definition, every quantum computer has the capacity to generate true random numbers.
And that’s an inherent quality of being a quantum computer, rather than being the result of special hardware as with the techniques mentioned above.
The Hadamard gate is the simplest method for generating a random bit in a qubit. It generates a quantum state which is a superposition of a 0 and a 1, with equal probability. If you then attempt to measure that qubit the quantum state collapses into either a 0 or a 1 with equal probability, generating a single random bit. Execute n Hadamard (H) gates, either on the same or distinct qubits, measure the qubit state after executing each H gate, and you have n-bits of random number. All without any special, exotic hardware other than the quantum computer itself.
It’s not completely clear whether it matters much at all whether those n-random bits are generated in parallel on n qubits or sequentially on a single qubit, or maybe in groups of 8 on 8 qubits, although generating n bits in parallel would be problematic for n greater than the number of qubits available on near-term hardware.
Granted, using a quantum computer solely to generate true random numbers is going to be more expensive and less available than many of the hardware techniques listed above, but it would be advantageous in situations where the quantum computer is needed for other purposes as well.
The point of this informal paper is that if you compare a pure quantum computer side by side with a pure classical computer, the generation of true random numbers is a clear quantum advantage for the quantum computer.
Impact of quantum errors and noise
Quantum computing is inherently probabilistic, so even generating random numbers will be probabilistic. Odd to say, but the randomness would be probabilistic.
One question is how quantum errors and environmental noise might impact the probability distribution of generated random numbers.
Will quantum errors make generated random numbers even more random or possibly less random?
If quantum-generated random numbers are already true random numbers, what would it mean to make them even more random?
Might environmental noise, such as on the power line, commercial radio waves, etc. introduce some degree of periodicity which makes the generated random numbers somewhat less random? Or might any such effect tend to be swamped and lost? But even if it tended to be swamped and lost, would it be absolutely swamped and lost?
And if the use case is very large random numbers, such as 4096-bit encryption keys, unexpected periodicity over an extended interval might (or might not) be more problematic than for a shorter sequence.
Ditto for long sequences of smaller random numbers, like simulation of flipping coins or rolling dice.
Quantum errors will generally be fairly low since quantum coherence will not need to be maintained for more than the time to execute a single quantum logic gate since the circuit depth is essentially one — a single Hadamard gate followed by a measurement which forces the quantum state to be collapsed anyway, done n times for n bits of random number or for n qubits in parallel.
But none of these concerns impact the quantum advantage of quantum computers over classical computers in the area of generating true random numbers. Random numbers generated by a quantum computer might not be absolutely perfectly random, but will at least be more random than generated by pseudo-random numbers on a classical computer.
That does still beg the question of whether random numbers generated by a quantum computer are as absolutely random as some of the quantum methods listed earlier (radioactive decay, atmospheric noise, vacuum fluctuations.)
How exactly equal are the probabilities for a Hadamard gate?
The Hadamard quantum logic gate is supposedly equivalent to two rotations about the axes of the Bloch sphere (or one diagonal rotation), but rotations are expressed as angles in radians or fractions of the irrational number pi, even when they are exactly 90 or 180 degrees, which have a definite but not infinite precision in floating point, or as a unitary matrix involving an approximation of the square root of 2, which is an irrational number having no exact definite value in any programming language. All of this begs the question of whether the quantum state after execution of a Hadamard gate is indeed precisely equal probability (equal quantum amplitude) for the two basis states.
Of course the two amplitudes (probabilities) are most likely very, very close, but how close to exact equal probability will they really be? For a true random number they need to be exactly equal, not simply close.
As with all quantum computations, the results are probabilistic rather than deterministically exact, but in the case where we are expecting probability, what exactly does the probability of a probability really mean?
Effects of calibration
Real quantum computers have to be calibrated on a regular basis, but how exact and precise is that calibration process, and how un-calibrated is the quantum computer likely to be between calibrations?
In other words, is the implied rotation for a Hadamard gate exactly 180 degrees or not?
How identical are each of the qubits?
There will be inevitable differences between each qubit due to the nature of the chip fabrication process, such as differing number of atoms in each qubit, so technically a slightly different calibration might be needed for each qubit, although that level of distinction may be beyond the capabilities of current test equipment. Maybe the distinctions might be too small to impact the probabilities for the state of each qubit, or maybe not.
Generally this won’t be problematic for general computations which are probabilistic at best anyway due to the nature of quantum computation, but for an application seeking to generate absolute true random numbers it might be problematic, such as for generating very large numbers of very large random numbers, where any periodicity, even over long intervals might render the results as being less than strictly random.
Functional advantage vs. performance or capacity advantage
Generally, most discussions of quantum advantage are focused on performance or capacity advantages of quantum computers, but occasionally functional advantages are discussed. Generation of true random numbers is such a case of a functional advantage.
Software running on a classical computer can do a somewhat adequate job of simulating a quantum computer, at least a relatively small quantum computer (say, 20 qubits), but there is the question of how truly random quantum state will be simulated since the simulator may be using a pseudo-random number generator rather than a hardware source of entropy bits.
For reasonably small and relatively short quantum programs it may not be a significant issue, but for larger and longer quantum programs it could become problematic — or maybe not. There simply isn’t any significant clarity on this front at this stage.
Granted, the simulator could utilize one of the special hardware options listed earlier, but then it is not a true, pure classical simulator.
One special issue is that since execution of a quantum program will by definition produce probabilistic results and it is up to the containing application to rerun the quantum program some number of times to get an accurate distribution of the probabilistic results, it is even more important that each run of a quantum program on a quantum simulator be as uniquely random as possible, rather than starting each quantum program in the exact same random state, such as with an identical seed.
Statistical analysis of randomness
All of this is strictly theoretical at this stage. I haven’t heard of any serious statistical analyses of random numbers generated by current quantum computers.
- Wikipedia Statistical randomness article
Need for reproducibility
Not all applications can deal with absolute randomness. As one particularly important use case, replicating bug scenarios when doing randomized testing generally needs a seed number and a reproducible process for generating seemingly random numbers so that particular failure scenarios can be reliably recreated to facilitate debugging and testing of bug fixes. Pseudo-random number generators usually address this need reasonably well.
Reproducibility is one of the hallmarks of the scientific method. Too much randomness and too little determinism can make science very problematic. Some degree of randomness can be tolerated if within a threshold range which permits deterministic measurements to be made.
Direct measurements of real phenomena are a primary form of science, but simulation is another valuable tool for evaluating speculative theories. Both true random numbers and reproducible pseudo-random numbers have their place in simulation.
Simulation development can be fraught with bugs and the need for continuous incremental improvement, so reproducible pseudo-random numbers can be a valuable development aid, even though production runs of the simulation may best be run with true random numbers once all bugs and improvements have been resolved. But even then, other investigators will be unable to precisely replicate simulation runs which depended on true, non-reproducible random numbers. Maybe the answer is to report both true random and pseudo-random results.
For the near-term, true random number generation (TRNG) may remain the most defensible area of quantum advantage. Classical computers retain an advantage when deterministics results are needed, but probability and randomness are the forte of quantum computers.
How close to absolute true randomness quantum computers really are will remain an open question for the near-term, but they are definitely close enough for most practical purposes.