Quantum computational advantage and counting particles and waves

Many people take the beginning of the field of quantum computation to be a paper by Feynman titled “There is plenty of room at the bottom” (1959, but unnoticed till the early 80s). The title suggests that physical systems can store way more information than the transistors used at the time of writing. That turned out to be true, however, Feynman was making an even more interesting point, namely that by storing bits into smaller and smaller systems, the laws of quantum physics will at some point become necessary and the quantum behaviour of bits would be dominant.

Photo by Google DeepMind

Feynman famously suggested that, as a result, we might have an increase in computational power, which is in addition to the storage capacity due to the diminishing size of the physical bits. His example was very simple. Classical computers are notoriously bad at simulating systems of many interacting electrons. For instance, the famous Hubbard model, which is possibly the simplest model to account for the electrical conduction in the quantum world, cannot be solved exactly. Computationally too, it happens to be a hard problem, meaning roughly that as you add one more electron into the system, the time of computation needed to simulate the resulting dynamics doubles. Already with hundreds of electrons it would take classical computers more than the age of the universe to solve the Hubbard model (meaning: to predict the dynamics of the electrons therein).

However, a quantum computer consisting of 100 electrons, interacting according to Hubbard, would evolve exactly as prescribed. Ergo, concludes Feynman, a quantum computer would be exponentially more efficient than classical one at simulating itself! And, as you add one more electron to the quantum computer, the time of computation barely changes (it could even stay the same).

The field of quantum computers has exploded since. The key contribution was due to Deutsch in 1985 when he presented the blueprint for quantum computers outlining exactly how to do logical operations on them. This triggered an avalanche of experiments implementing quantum logic with all sorts of physical systems (5 of which have received Nobel Prizes to date – there will be many more, I think).

Now, a surprize followed by an intuition based on waves and particles. Feynman chose electrons because they are fermions. It seems intuitive that fermions would be more quantum than the other type of a quantum particle, called a boson. Generally speaking, fermions provide the building blocks for matter while bosons “implement” the forces holding the fermions together. The reason why fermions appear to be more quantum is that they obey the Pauli exclusion principle, namely that no two fermions can be in the same total state at the same time.

This property leads to the stability of matter. In a typical atom, the energy required to excite electrons from the lowest energy level is about 40 times larger than the thermal energy at room temperature. Therefore, a single electron would be in the lowest state since it doesn’t have enough energy to go higher. The next electron, however, cannot go there because of Pauli, and it therefore has to occupy the next, higher energy, level. So, the reason why everything has not collapsed into the lowest energy, even at room temperature, is that no two electrons can be in the same state. This is why your table is a table and your pen is a pen rather than both being just blobs of electrons all sitting at the lowest possibly available energy.

If, on the other hand, matter was made of bosons (things like photons) they could indeed all end up in the same state. Clearly a disaster.

Now the surprize. It is exactly because of the fact that the fermions avoid each other (“anti-bunch” in the jargon of physics) and bosons like to cluster together (“bunch”) that it turns out that the collections of even non-interacting bosons are harder to simulate! This is not to say that in general fermions could, under many circumstances, also be difficult to simulate – it’s just that the bosons are intrinsically so precisely because they do not obey Pauli’s exclusion principle.

I’ll give you an example in a minute and then tell you about the intuition behind it. Before that, I’d just like to say that we still do not understand why there are fermions and bosons out there (and only fermions and bosons?). Namely, the rules of quantum physics do not tell us that the particles need to be of two kinds only. This seems to be an extra assumption we need on top of the standard quantum axioms. This is a very exciting and active area of research with all sorts of fancy ideas around (such as that fermions are actually made up of bosons and vice-versa, so that, after all, there is only one kind of particle out there).

Now, think of a mind-numbingly boring task of counting the total number of particles that could exist in one thousand different places. What’s the problem?, you’ll say. Just measure the number of them in each place and add them up. Seems to require 1000 computational steps. Yes, but this is true only of fermions. This is because at each location there is either one or no fermions (we cannot have two or more). So, indeed, to get the total number we need only add up 1000 zeros and ones. Dead easy.

But for bosons, we could have any number of them in any location (subject to restricting the total number to make it on a par with fermions). However, the measurement outcome we get of the number of bosons in one location the first time we do this, may not be the same as the next time we measure! Bosons fluctuate because, in principle, any number of them could be in the same place. So, we have to keep measuring. In fact, the fluctuation in the number of bosons is of the same magnitude as the average number of bosons which means that we should repeat the measurements a million times simply because we may get a thousand photons in one place or none or anything in between and to get the average we need to evaluate the size of the fluctuations.

Now the insight. It is helpful to think of the bosons behaving like classical waves and fermions like classical particles (that cannot occupy the same place, hard-core in other words). Measuring the number of particles in a box is easy as we just have to count them all. With waves, it is difficult as in some place they may all add up destructively (so even though we have a thousand of waves the final signal is zero) and – on the other side of the spectrum – 1000 waves could produce a million times stronger intensity is they interfere constructively. That’s why the bosonic fluctuations are large.

Einstein was, in fact, the first person to show that waves could also behave like particles when it comes to quantum fluctuations but this is not the regime that concerns us here (which is that of many waves). In his calculation of the fluctuations in the energy of the black body he found that the fluctuations consist of a sum of the particle-like and wave-like fluctuations.

Ok. So, bosons are exponentially more difficult to count than fermions. Interestingly, this is related to the mathematical difference between computing the determinant and permanent. The permanent is much harder and, in quantum physics, the permanent represents the state of bosons, while the determinant is the encoding of the state of fermions. I recommend the great paper by Troyanski and Tishby on this topic (1995).

But, you will protest, who cares about counting particles? It is surely just an artificially constructed irrelevant problem to show that one particular computation is harder with bosons than fermions. Not so fast! It turns out that if you can count, add and subtract, you can actually compute anything that can be computed. An equivalent to the Turing machine of this kind was suggested by Hao Wang in 1957. His computer is just a collection of containers, each containing some number of marbles, and its processor needs to be able to do only three tasks: access each of the containers, count the number of balls, and depending on the outcome, add or subtract a ball from them. This is perhaps not surprizing given that our computers almost work this way. They can only count, add and subtract, but they do it so quickly that we are able to concatenate these operations in order to construct more complex operations. When you ask your computer to multiply two numbers, like 7 times 6, it actually does 6+6+6+6+6+6+6, but this is done so quickly that even two huge numbers are multiplied seemingly instantaneously.

This is of course a classical computer, but a quantum one could be made by allowing counting, addition, subtraction and the number of marbles to be in superpositions of different states. As far as I know, no one has worked out in detail the quantum version of the Wang computer, but I don’t expect anything surprizing to happen here. It does, however, illustrate the fact that, if counting happens to be difficult (such as in the case of bosons), then that could actually affect most computations since counting is at the core of more or less everything.

The key physical issue is whether such superpositions can be maintained and it is the same problem in any instantiation of quantum computations. So, Wang’s machine doesn’t give us an easier route to the full-scale quantum computers than the usual circuit model.

But, there is an even more interesting physics question here (there always is, as far as I am concerned). If the universe is a ginormous quantum computer, and, if bosons are so much more efficient than fermions, wouldn’t you – assuming you are tasked with programming the universe – make all particle bosonic and then get them to simulate fermions? In other words, if you are a computer scientist, fermions would just appear to be redundant.

I’ve indeed speculated on this with Chiara Marletto, but following a different intuition altogether. The key idea is that bosons coupled though gravity give us fermions, however I’d better leave this for another blog…