A pseudo quantum computer, really?
If you know what a quantum computer is than the post title should make you suspicious. Let me explain. The power of a quantum computer comes from its ability to have its cubits in superposition while it is “calculating” a solution. This means that the cubits have all values at once, i.e. not just 1 or 0, but both. This superposition happens in the quantum domain and one viewpoint is to consider that each quantum state is in its own world and the many worlds make up all the possible states. It’s a neat explanation since the superposition never collapses, we merely pick the state that works best for us.
In my previous blog post, I explained that we can simulate cubits that live in the quantum domain with random bits that exist in the (familiar) time domain. If I pick a 1 or a 0 randomly, then within a given period, either will appear. Or both, if you prefer. If you combine a number of these random bits, which I have named “arbits”, then all possible configurations of these arbits will appear in a certain time. For example, if I take a random 8-bit number, i.e. between 0 and 255, then normally any value in that range will appear at some point. But we don’t know when. We could pick the number 172 randomly with the first pick, or it could take an infinite time. It might never come up, though this is unlikely.
In my previous post, I wrote a simulation program that calculated square roots by selecting random answers and checking whether these were correct until the right answer randomly appeared. Although this may not appear to be efficient, this is not a given. It may not be less efficient than a mathematical algorithm. What’s magical is that this little programme produces square roots without knowing how to calculate them…! It just knows how to verify that they are correct.
One thing has bothered me with the simulation programme, aside from the fact that it runs on a traditional computer. The question is: how random is a random number generated by a computer? The experts all say that these pseudo random numbers are not random at all.
Hence was born the idea to build a random number generator with electronics hardware. It took me a while to get around doing this because although I was once a hardware engineer, I have now become a software dude and had no equipment to design, build and test the hardware.
But the urge was greater than the lack thereof so genetic fractals labs is a real thing now. Aside from the electronics equipment, it also houses my 3D printer and home built CNC machine.
This random computer was my first project in the new lab and this is only the first iteration. The main focus is on the arbit generator. The idea is that we take a random hardware process and turn it into a stream of random bits. These are then read by a microcontroller that uses the arbits to calculate something.
The circuit diagram of the arbit generator is deceptively simple but it hides some amazing processes that are rarely appreciated by those that make these sort of circuits.
The magic all happens in T1, a general purpose NPN transistor which has been mounted in reverse. Normally the current flows from the base to the emitter but this time it is the opposite. Normally in this configuration the current will block but if you increase the voltage enough, the reverse barrier will break down and current can flow from the emitter to the base, as in this circuit. It so happens, that this happens at a voltage between 11.5 and 12.5 V. When the reverse barrier breaks down, it causes avalanches of electrons across the PN junction. Once an avalanche starts, it decreases the voltage over the junction and the avalanche of electrons will stop. The voltage over the barrier will increase again and another avalanche starts.
This sequence of electron avalanches is totally random, it all depends individual electrons that trigger the avalanches. For the record, these individual electrons are also subject to quantum randomness. QED.
The overall process of voltage breakdown and electron avalanches produces a random voltage signal of about hundred millivolts at the emitter of T1. The other transistor is just a high gain amplifier with a high impedance that translates the noise into a 5V peak-to-peak signal by driving the transistor (T2) into saturation. The Schmitt inverter then turns these spikes into sharp rectangular pulses, as shown on the oscilloscope on the picture at the top of this post.
The random computer below uses the output of the arbits generator as a random input to a Teensy 3.5 microcontroller. One concern I had was that the sequence of ones and zeros, although random, wan’t necessarily evenly distributed. From the oscilloscope signal, I could tell that there were more zeros than ones and that would not generate all numbers evenly. After some experimentation I established that there were 3 times more zeros than ones. The easy solution was to ignore 2 out of 3 zeros in order to get an even change of generating a zero or a one.
In addition to the arbit generator (components at the bottom left), there is the Teensy 3.5 mothership and a push button with a LED. Once the Teensy is programmed with a problem, it will read the random arbit stream and once it has found a solution, the LED in the button lights up. Then when I push the button, the results are sent to a serial monitor.
Above is an example where the Teensy is given a number, 237427, that is composed of two unknown prime numbers. It then reads the random arbit stream to find the prime factors, 233 and 1019. As you can see, it took close to 40 million trials of random ones and zeros to find the solution. It turns out that the speed of my random computer is limited by the generation of arbits. For some reason, the electron avalanches occur about 50’000 per second. For a 10 bit value, that means 5000 random values per second. Not brilliant. In particular when you consider that the Teensy 3.5 has a 120M clock.
And the point is?
The point is not that this random computer is an efficient tool for factoring large numbers. It is very slow in fact. No, the surprising property of this random computer is that it can solve problems WITHOUT needing an algorithm. An algorithm-free computer. Think about that. Algorithms are the lifeblood of computing. Well, in the pre-quantum computing at least.
The part that fascinates me is that this random computer finds solutions in a random space, as implemented by the arbit stream generator. I have written about the philosophical implications of the concept of finding solution in randomness. In the same way that this random computer does not need an algorithm, I believe that we can find many other solutions in random space without the need for sophistication. Human creativity is perhaps overrated. There is only one quality that this random computer has that people need as well: knowing when you have a solution. Not how you find it.
Next: knowing when you have a solution
How can we know that we have a solution. Finding a square root is easily validated by squaring that number and comparing to the number we started with. Factorization (which is actually very difficult) is also easily verified by multiplying the random factors and check that they produce the right result.
I’m far from finished with this hobby research into randomness. Most likely I will look into the “knowing when you have a solution” question. The last time I tried, I found myself developing optimization algorithms until I stopped myself. This type of computing should not use algorithms. There must be another way to recognize solutions. And so I will seek and who knows, find.
Hopefully, before another two years come to pass.