Quantum Supremacy: How the Quantum Computer Revolution Will Change Everything

by Michio Kaku

In 1981, Feynman emphasized that only a quantum computer can truly simulate a quantum process. But Feynman did not elaborate on precisely how a quantum computer might be built. The next person who picked up the torch was David Deutsch of Oxford University. Among other achievements, he was able to answer the question: Can you apply quantum mechanics to a Turing machine? Feynman had hinted at this problem, but never wrote down the equations for a quantum Turing machine. Deutsch went on to fill in all the details. He even designed an algorithm that could run on this hypothetical quantum Turing machine. A Turing machine, as we have seen, is a simple classical device, based on a processor, that turns the number on an infinitely long tape into another number and therefore performs a series of mathematical operations. The beauty of a Turing machine is that it summarizes all the properties of a digital computer in a simple, compact form, which can then be rigorously studied by mathematicians. The next step is to add the quantum theory to Turing’s invention, which would allow scientists to study the bizarre properties of quantum computers in a rigorous way. In a quantum Turing machine, thought Deutsch, one replaces a classical bit with a quantum qubit. This introduces several important changes. First, the basic manipulations of the Turing machine (e.g., replacing a 0 with a 1 and vice versa, and moving the tape forward or backward) remain roughly the same. But the bits are radicall...