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 for a 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 ti