Why I don’t think that Quantum Computers will work, ever

I have just made a bet that quantum computers will not turn out to be better than classical computers within the next fifteen years. I would rather want to bet on “ever”, but how could I win such a bet? We could also do a lifetime thing: if you die before the first superclassically fast quantum computer is built, I inherit all your stuff, but that might set the wrong incentives for me. So, 15 years it is. Now let me go out on a limb and explain my intuition that quantum computation will turn out to not really be a thing, ever.

The company D-Wave just made some headlines when their quantum annealing machine managed to be a hundred million times faster than a classical simulation of a quantum annealing machine. This sounds amazing until you realize that the best known classical algorithm for the same problem is actually faster than quantum annealing. Perhaps will turn out to be possible to get much greater improvements out of the D-Wave machine, or use one of the many other quantum computer designs currently in the pipeline. But I don’t think so.

The very basic, handwavy idea of how quantum computers are faster than classical computers is this: If a part of the universe is not closely observed, it may get “disentangled” from the rest, and enter a state of superposition, in which the universe is fundamentally undecided about its state. For instance, before we (or anybody else) have measured the position of an electron, the electron will behave as if it is in all of its possible positions at the same time. It may “tunnel” through (very thin) solid walls and interfere as if it was a wave. But when we entangle ourselves with it, i.e. measure its position, it will manifest as a local interaction. It is as if we are reaching into a foggy cloud of possible electron positions, and suddenly feel the pinprick of a single electron bouncing into our hand, upon which the foggy cloud is gone, and we are now left with the big mystery of the “collapse of the wavefunction”: where did all the other possible electron positions end up? Did they perhaps all manifest, creating a cloud of different, non-interacting universes, each distinguished only by a different position of this single electron? (This is the many worlds interpretation of quantum mechanics.)

This undecidedness of particles gave rise to Schrödinger’s famous cat experiment, in which we stuff a feline into a physics proof box, along with a superpositional particle (such as a radioactive isotope atom that will randomly decay) where the collapse of the wavefunction may trigger a death machine that kills the cat with 50% probability. According to quantum mechanics, the cat will now enter a state of being dead and alive at the same time, which persists until an observer opens the box and gets entangled with its internal state, upon which the cat will have turned out as having been retroactively dead or …annoyed. Schrödinger meant to point out the absurdity of such an interpretation of quantum mechanics, but today, most physicists have come to terms with half-dead cats, and quantum computers actually exploit them.

The important thing to realize is that a particle in a superpositional state (i.e. one that has two states at the same time before we have committed it to a single, definite state a by measuring it) is like a memory cell that holds two different values at the same time. A quantum computer works by using multiple superpositional registers to encode superpositional numbers, which cover the whole range of desired values. Instead of killing or not killing the cat, we kindly ask it to use the status of the ~death machine~ quantum memory cell as an input value in a computation. As a result, the cat will not be alive and dead at the same time, but will have diligently performed all computations based on all possible input values at the same time. For instance, we could try to use our cat to crack a password by making sure that the superpositional quantum memory cell encodes all possible passwords simultaneously. Since the cat inherits the superposition until the outside universe gets entangled, all possible cats will now try to use one of the possible passwords, one of them will find the solution, and when we open the box, we will discover if we happen to share a universe with the particular cat that found the solution that we are interested in. This in itself is not very helpful, so we are going to build additional constraints (entanglements) into the interaction between cat and quantum memory cell, to make sure that the cat can in principle only end up in one of the states we are interested in (like one where the key decrypts a bunch of text into something that looks like plain English).

In practice, nobody seems to have found a way to make a physics proof box large enough to put a full-size cat in (we would have to shield it against all interactions, including gravity). Instead, we usually make the cat very small, like a gold atom, so we are less likely to interact with it prematurely.

There are many variants of quantum computing devices, but they all exploit the fact that quantum processes involve an uncertainty that is intrinsically costly to compute in classical systems: If we want to simulate what happens in a quantum system, our data center grows much much faster than the number of particles in the simulation. For instance, if we want to determine how an electron that inhabits an orbital will interact with other electrons, we might have to do simulations for all possible positions of the electrons, even only one will eventually be actualized. This gives rise to the notion that quantum computation is intrinsically more powerful than classical computation. No, it won’t mysteriously enable consciousness in ways that classical computation cannot, because we are still looking at good old Turing computability. Quantum systems compute the same things as classical systems, only much, much more efficiently.

Or not.

What if the difficulties of computing the position or spin of a particle in a classical paradigm do not result from the fact that quantum processes require more complexity, but from the fact that this position or spin does actually not exist? In the spacetime paradigm, we assign a position in space to every particle, and discover that our equations do not result in a single solution, but rather in multiple solutions (for spin) or a distribution (for positions). This is only confusing if we believe in the reality of space. But what if we accept that the universe is not a continuous space with stuff in it, but a computation?

I am not a physicist, but a computer scientist. If I wanted to program a universe like ours, I would try to implement it as a hypergraph. This graph consists of nodes with typed links and is stored as a finite, fixed number of bits. Each node is a “particle”, and the type of the particle is given by the types of links it has. Each link stores a discrete value. If two or more particles are connected by a link, they share the value of that link, and we call them “entangled”. The graph is mostly transitive: if two nodes A and B are entangled, and B and C are entangled, then there is a high probability that A and C are entangled, too. On the other hand, the particles cannot have arbitrarily many links, so the entangled particles largely tend to form something that looks like a multi-dimensional grid. In this grid, the particles do not have absolute coordinates, but the links act like distances. If the nodes had coordinates in space, which they really don’t, we often could compute these coordinates from the distances the particles hold from each other. In many cases, however, there will not be enough entanglements to result in a single solution.

If someone lives in this universe, they will be made from the links between the particles, and will try to make sense of their environment by bringing these links into a meaningful connection. When the links can be mapped into a spatial order, we get a virtual space: it will look like there are particles with specific absolute coordinates. If there is no single solution, the particles will look like a distribution of potential positions. Additional observation results in additional entanglement: the observers add further constraints to the particle, until the solution seems to collapse into a single defined position in our virtual space. But we did not make any potential positions disappear! The particle simply never had a real, well-defined position in space before it was observed, and it does not have one now: it just happens that there now is a unique solution to the question where it would be if it had one, and we get consistency in the virtual space.

How can we program our universe to be dynamic? A possible solution might be that we add up a sum of the values of each link at each node, and require that neighboring nodes have the same value. Whenever two neighboring nodes do not have the same value, we change the link between them to equalize the value and restore the symmetry. Links have to stay in certain value ranges, so it may even be necessary to add or remove additional links. All our changes have the unfortunate property that we will likely have introduced another symmetry breach on another link, so in the next step, another link has to be updated too, and the asymmetry spreads through the network.

From the viewpoint of the internal observer, it will now look as if there are two types of interactions: one that continuously spreads through space, changing positions and properties of particles, and adding and removing constraints, so particles go into superpositional states or actualize in specific positions. This spread is limited to a constant upper speed, given by the density of particles in the projected space, and the need to successively alter their links. This will look like a lightspeed barrier. The other interaction occurs if two particles with intransitive neighborhood but a shared link update this link: it will look like a “spooky action at a distance”.

In this universe, a quantum computer will not provide any benefit over a classical computer. A superpositional bit won’t be in two states at once, but simply in no state. If we encode constraints into the quantum computer, the algorithm to encode and decode the quantum register’s contents will have at least the same complexity as a classical algorithm for the same problem. It will still take enormous resources to calculate all possible virtual states of the quantum computer in a classical system, but the universe itself does not bother computing these states at all, and thus, an algorithm implemented on this quantum computer effectively always runs at the same speed as a classical one.

At the moment, my discrete hypergraphical universe simulator is a rather foggy idea. There are quite a few ways in which the details and datastructures could be implemented, and it is absolutely not clear to me if we indeed live in the kind of computational universe described above. If someone would find an implementation that gives rise to a virtual weakly Einsteinian universe that looks like ours, it will probably result in a Nobel price. Until then, at least my bet stands.