COMPUTING SCIENCE

# The Square Root of NOT

# Quantum Parallelism

The extraordinary power of quantum computing comes from exploiting superposition and interference. Consider what happens when a classical computer is asked to search among all possible patterns of *n* bits for a particular pattern that satisfies some stated condition. With a single processor, the computer must examine each pattern sequentially, and since there are 2^{n} such patterns, the task is intractable for large values of *n*. With parallel processing the search can be completed in a single step, but only if you can build 2^{n} processors, which again becomes impractical as *n* grows large. A quantum computer might break the logjam, at least for some problems. After setting up the right initial superposition of states, and allowing it to evolve according to the right unitary transition matrix, a single quantum processor could sift through all the qubit patterns simultaneously. Destructive interference would suppress those patterns that were not of interest, while constructive interference would enhance those that met the stated conditions.

Factoring an integer can be formulated as such a search problem. The aim is to find a pattern of *n*/2 or fewer bits that evenly divides a given *n*-bit number. The simplest classical algorithm (albeit not the best one) searches for a factor by trial division, requiring either 2^{n}/2 steps on a single processor or 2^{n}/2 processors. In principle, a quantum computer might be designed to perform the search directly in a single step, by starting with a superposition of all 2^{n}/2 qubit patterns and allowing them to interfere with one another according to some carefully crafted unitary transition matrix. When the computer halted, it would be in a state representing a factor of the number. Unfortunately, no one has any idea how to create the appropriate transition matrix or how to build a machine that would implement it.

Shor's quantum factoring algorithm is less direct, but it still relies on quantum interference to identify one special qubit pattern out of many. Quantum computation is used to solve the congruence *x*^{r} = 1 modulo *N*, where *N* is the number to be factored and *x* is a random integer. Having found the least value of *r* that satisfies this relation, a straightforward classical calculation yields a factor of *N*.

If a quantum factoring algorithm is faster than any known classical algorithm, does that mean quantum computers are more powerful than classical ones? Curiously, the answer to this question is still unclear. Part of the difficulty of resolving it is that the computational status of factoring itself is uncertain. No classical polynomial-time factoring algorithm is known, but no one has proved that such an algorithm cannot exist. Thus factoring could yet turn out to be an "easy" problem, in which case the quantum computer's prowess in this special realm will not have much general significance. Far more convincing would be an efficient quantum method for a problem with better credentials attesting to its intractability, such as the traveling-salesman problem; but such a discovery is considered unlikely *(16)*.

Whatever the theoretical standing of the factoring problem, its practical importance is unquestioned. "Public-key" cryptography depends for its security on the difficulty of factoring large integers. If it appears possible to build quantum computers, or even special-purpose quantum factoring engines, the secrecy of encrypted messages will be in jeopardy. But if quantum mechanics undermines one form of cryptography, it could also supply a replacement. Standing alongside the new study of quantum computing is the equally novel field of quantum cryptography, which derives its strength from the same mysterious physical laws.

© Brian Hayes

EMAIL TO A FRIEND :