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|
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.
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