Waiting for Quantum Computing? Try Probabilistic Computing

Computer scientists and engineers have started down a road that could one day lead to a momentous transition: from deterministic computing systems, based on classical physics, to quantum computing systems, which exploit the weird and wacky probabilistic rules of quantum physics. Many commentators have pointed out that if engineers are able to fashion practical quantum computers, there will be a tectonic shift in the sort of computations that become possible.

But that’s a big if.

Quantum computers hold great theoretical promise, sure, but the hurdles that need to be overcome to build practical machines are enormous. Some skeptics have argued that the technical challenges are so immense that it’s very unlikely that general-purpose quantum computers will become available anytime in the foreseeable future. Others, including the engineers now working very hard to build these machines at Google, IBM, Intel, and elsewhere, are more sanguine, anticipating that 5 or 10 more years of work may be enough to bring the first practical general-purpose quantum computers on line. Only time will tell.

But even if the whole quantum-computing enterprise were to develop far more slowly than its proponents anticipate, one thing seems certain. Quantum computing has already inspired a deeper understanding of the role of probability in computing systems—just as the late physicist Richard Feynman had hoped it would when he brought the idea to people’s attention back in the early 1980s.

It was just this understanding that we were seeking in 2012 when our group began research on probabilistic bits, or “p-bits,” a play on the word used to describe the fundamental unit of information in a quantum computer, the qubit. Feynman had considered such a probabilistic computer as a counterpoint to the quantum computer he was envisioning. So, we asked ourselves: How could we build one?

One way to store a bit is to use a magnet with two possible directions of magnetization. Early computers used that approach for what was known as magnetic-core memory. It’s hard to miniaturize magnetic memory, though, because magnets become unstable as they are made smaller. We have turned this seeming bug into a feature, using tiny unstable magnets to implement p-bits. In 2019, with the help of collaborators at Tohoku University, in Japan, we built a probabilistic computer with eight such p-bits.

We didn’t really need the new magnet-based p-bit to build a probabilistic computer, though. Indeed, earlier we had built probabilistic computers that implement p-bits using elaborate electronic circuits to generate pseudorandom sequences out of deterministic bits. Companies like Fujitsu are already marketing similar probabilistic computers. But using unstable magnets as the fundamental building block allows a p-bit to be implemented with a few transistors instead of a few thousand, making it possible to build much larger probabilistic computers.

In such a computer, a system of p-bits evolves from an initial state to a final state, transiting through one of many possible intermediate states. Which path the computer takes depends on pure chance, with each path having a certain probability. Add together the probabilities of all possible paths there, and you get the overall probability of getting to a given final state.

A quantum computer does something similar, but it uses qubits instead of p-bits. This means that each path now has what physicists call a probability amplitude, which can be negative. More precisely it is a complex number, meaning that it has both a real part and an imaginary part.

To determine the overall probability of going from an initial state to some final state in a quantum computer, you first have to add the amplitudes for all the possible paths between the two to get the probability amplitude of the final state. That final amplitude is also a complex number, whose magnitude you then square to get the actual probability, a number that ranges between 0 (never happens) and 1 (always happens).

That, in a nutshell, is the essential difference between a probabilistic computer and a quantum computer. The former adds probabilities; the latter adds complex probability amplitudes.

This difference is more important than it might seem. Probabilities are positive numbers less than one. So adding an extra path can only increase the final probability. But probability amplitudes are complex numbers. That means that adding an additional path can cancel out an existing path. It is as if a path can have a negative probability.

The power of quantum computing comes directly from this ability to negate probabilities. Celebrated quantum algorithms—like the one Peter Shor developed for integer factorization or the one Lov Grover devised for searching through data—carefully orchestrate the intermediate paths available so that those leading to the wrong outputs cancel, while those leading to the right answers add constructively.

But this power comes at a price. The qubits that carry these complex amplitudes have to be carefully protected from the environment, often requiring the electronics to be maintained at cryogenic temperatures. A probabilistic computer by contrast can be built with simpler technology operating at room temperature. But such a computer lacks the magic of negative probabilities, making it effective only for algorithms that do not require path cancellation.

In truth, it’s theoretically possible to emulate a quantum computer using probabilistic bits, but it may not be a practical strategy. Still, there are important problems for which probabilistic computers could provide significant speedup over deterministic ones, which is why we’ve been so interested in building this new type of computing machine.

How would such a probabilistic computer work? The principles are very different from those underlying the digital systems we use every day, making them foreign even to most students of computer engineering. So we wanted to offer a gentle introduction to the topic, which we present here in the form of a dialogue. [READ MORE]