COMPUTING SCIENCE

# The Square Root of NOT

# Feynman's Question

An early investigator of quantum computing was the physicist Richard P. Feynman *(1)*, although he looked at the issue mainly through the other end of the telescope, asking not what quantum mechanics could do for computing but what computing could contribute to the understanding of quantum physics. A classical computer bogs down when it is made to simulate a quantum system; Feynman suggested that a quantum computer might be better suited to the task.

At about the same time, Paul Benioff of the Argonne National Laboratory devised an elaborate quantum-mechanical simulation of a Turing machine, the standard benchmark of classical computing *(2)*. Then in 1985 David Deutsch of the University of Oxford published another conceptual model of a quantum computer, one relying directly on the interference of quantum states *(3)*. In 1992 Deutsch and Richard Jozsa, also of Oxford, formulated a few problems that could be solved faster with such a quantum computer than with a conventional Turing machine *(4)*. This was the first direct evidence that quantum computers might be superior to classical ones.

There followed a sequence of papers reporting further developments and refinements in quantum computing *(5, 6, 7)*, but the most arresting news was the announcement of a quantum-mechanical algorithm for factoring, devised by Peter W. Shor of AT&T Bell Laboratories *(8)*. In all known classical factoring algorithms, the amount of time needed to find the prime factors of a number grows as an exponential function of the size of the number, making the algorithms impractical for very large numbers. (The factoring record at the moment is less than 150 decimal digits.) With Shor's quantum algorithm, the time needed grows as a polynomial function of the number's size. For example, factoring an *n*-digit number by classical methods might require 2^{n} steps (an exponential function) whereas the quantum algorithm could find the factors in *n*^{2} steps (a polynomial). (The actual functions are different from these, but for any choice of functions, there is always a value of *n* beyond which the exponential function is larger than the polynomial one.)

**IN THIS SECTION**

EMAIL TO A FRIEND :