The limits of quantum computing

Alan Turing

In an interview in a major Spanish newspaper (La Vanguardia) published on July 27, 2019, David Pérez García, a researcher in quantum physics, says this: We are just in the beginning of some technologies that we still don’t know how far they will go. He is right, because the future is hardly predictable, but when it comes to quantum computing we tend to think that these computers, if they are viable, will let us solve problems quite different from those that can be addressed by the traditional computers to which we are used. In this context, however, mathematics can help us distinguish between what can be done, and what is completely impossible.

Although quantum computing is a fairly modern concept, its theoretical foundation was established by Alan Turing during the 1930s. Let us review a little of what he showed, for in this way we can correct a few optimistic ideas spread by the media, often driven by experts who approach the issue from very different points of view, compared to Turing.

Alan Turing designed a special type of computing machine that, in his honor, is called a deterministic Turing machine. Although it isn't usually built with hardware, it is easy to simulate in an electronic computer. Essentially it consists of an infinite tape where one can write symbols, and a head that makes it possible to read and write them. The symbols the tape contains at the beginning of the process are the input of the machine, which is in a state chosen among a set of possible states. When it reads a symbol from the tape, the Turing machine writes another symbol in the same position, changes its state, and moves (or not) the head to read the symbol located in the next box, or in the previous one, or in the same. The machine is deterministic: when it is in a certain state and reads a specific symbol from the tape, its action is always the same.

A Turing Machine built with Lego

Each deterministic Turing machine is designed to run a single program. However, Turing proved that it is possible to design a special machine (the universal Turing machine), which can simulate the operation of any other Turing machine if it is provided, as input, with the definition of the other machine (its state transition matrix) and with the input of the simulated machine. The universal Turing machine has a computing capacity equivalent to that of our traditional electronic computers, and was devised almost one decade before they were invented. Actually it’s even more powerful, for it’s supposed to have infinite memory. But this difference is now less important, considering the size of the memory of modern computers.

On the other hand, Turing designed another type of computing machine, the non-deterministic Turing machine, which has the peculiarity that, after reading a symbol from the tape, it can perform several actions (go to several different states, writing different characters and move in different directions). The machine does not choose one among several possible actions, but performs all of them at the same time, in parallel. This machine is a good approximation of the quantum computers we are speaking about today, which at Turing time were unpredictable.

Turing did not just define those two machines, which represent ordinary and quantum computers, but he proved a theorem asserting that any non-deterministic Turing machine can be simulated by an equivalent determinist machine, which solves exactly the same problem (although much more slowly). An informal proof of this theorem can be found in section 2.3.1 of the book Teoría de Autómatas y Lenguajes Formales (Theory of Automata and Formal Languages, McGraw Hill 2007), which I wrote with my son Enrique and Professor Roberto Moriyón, to be used as a text in University studies on Computer Science.

The consequence of this theorem is evident: quantum computers won’t be able to solve new problems that up to now couldn’t be solved. Perhaps they’ll solve quickly some problems that we can already solve with traditional machines, although more slowly. Yes, some of those problems (called NP-complete) take a long time to be solved (sometimes too much time) with the computers we use today, and maybe we’ll be able to solve them in a reasonable time with quantum computers, but solving new problems with them is totally excluded. Mathematics gives us the proof.

The Wikipedia expresses this idea clearly and categorically:

Problems which are undecidable using classical computers remain undecidable using quantum computers.

The same post in Spanish
Thematic thread on Natural and Artificial Intelligence: Preceding Next

Manuel Alfonseca