Hyper-Computing 277
original proof. Again we have reached a dead end. We need something qualitatively different to a traditional computer in order to break the Turing limit. The obvious place to turn is the quantum world.
Quantum Computers
Quantum computers have had an extraordinary run in the press recently. It has been variously claimed they offer limitless computing power and can break all known security schemes; cracking, for example, the prime factors that form the basis of public key cryptography. This is big news. These codes are used to protect all the financial transactions we make on the web.
Ina regular computer, bits of information are processed by switches that make simple ‘yes’ or ‘no’ decisions. In a quantum computer each switch can take both the yes and no branches, at least fora short time called the decoherence interval. The calculations are said to be superposed. This allows a quantum computer to calculate exponentially, rather than linearly, as the number of logic gates increases. Grover’s algorithm and Shor’s algorithm use this superposition to speed up factoring numbers and looking things up in databases, respectively.
Grover’s algorithm gives us the ability to find something stored ina random place without having to look in every box. If you think about a standard search, say for your lost car keys, you must look everywhere to guarantee finding them. It does not much matter in what order you do it. When you are halfway through the search, you will be 50% likely to have found your keys. But, with a quantum computer, you can be fuzzy and look in many places at once. A quarter of the way through a quantum search, you are 50% likely to have found your keys. That might sound like a small improvement, but when working with very big numbers, it makes an enormous difference.
Shor’s algorithm works a little differently and, yes, it does allow a quantum computer to break Internet encryption, so the newspaper headlines are true up to a point. Some time in the future we will need to move to a more secure type of encryption.
The largest quantum computers today can process 300 qubits at a time or remain ‘coherent’ for about two seconds. These results are pitifully low. The largest prime number factored so far is 143, a mere 7 bits long! By way of comparison, internet security routinely uses 1024 bits. But, quantum computers are improving exponentially faster than classical computers: They really do change the rules of the game. If you remember our discussion of chess, the quantity of space needed for a
HOUSE_OVERSIGHT_015967