23 September 2008--Alexei Kitaev, a professor of theoretical physics and computer science at Caltech, was named a MacArthur Fellow today for his theoretical work on quantum computing systems. The five-year fellowship includes a stipend of US $500 000 with no strings attached, ”to provide recipients with the flexibility to pursue their creative activities,” according to the John D. and Catherine T. MacArthur Foundation, which determines the 25 yearly recipients.
At their core, quantum computers use the quantum properties of particles to manipulate and store data. Kitaev is quick to point out that such devices are still just theoretical, although experimentalists have managed to create qubits (the quantum equivalent of a classical bit) and simple quantum logic circuits in the lab. One of quantum computing's biggest hurdles is that nearly any interaction with outside forces can cause qubits to change state inadvertently, causing inaccurate computations. Physicists have devised error-correction codes to account for this problem, but using them greatly increases the number of qubits needed to perform the calculation you're interested in.
As an alternative, in 1997, Kitaev proposed a different type of system, called a topological quantum computer, in which errors are mitigated naturally by the system's inherent physical properties. It was for this work that Kitaev was nominated for, and ultimately awarded, the MacArthur Fellowship. ”I was surprised when I found out,” he says, laughing. ”Of course it's very exciting to receive such a prize.”
Kitaev's interest in quantum computing started in 1982, when he read in the introduction to Yuri I. Manin's book Computable and Uncomputable that quantum mechanics might provide a way to solve otherwise intractable computing problems. ”That paragraph really impressed me,” says Kitaev. ”It was really interesting, but I didn't yet know how to develop those ideas.”
While Kitaev made his way through his undergraduate coursework, Richard Feynman and David Deutsch were working on laying down the theoretical groundwork of how quantum computers could operate. Kitaev eventually learned of their work while he was pursuing his Ph.D. from the L.D. Landau Institute for Theoretical Physics, in Chernogolovka, Russia. He was still working at the Landau Institute as a research associate in 1994 when Peter Shor, a theoretical computer scientist at AT&T Bell Labs, made quantum computing's next big breakthrough.
Shor had discovered an algorithm that would allow a quantum computer to determine prime factors of a large integer much more efficiently than a conventional computer can. (Multiplying two large prime numbers is a snap for a computer, but factoring the product of two primes is incredibly time-consuming. So much so that the security of many of today's encryption technologies rests on the difficulty of finding prime factors.) ”A colleague of mine told me there was such a breakthrough result,” recalls Kitaev, ”but at that time, the library at our institute didn't have the journal with that paper in it.” Kitaev was energized by the knowledge that a quantum algorithm for factoring was possible, and he started to work on the problem himself. By the time he found a copy of Shor's paper a couple of months later, Kitaev had independently developed his own similar algorithm, which generalizes to an even wider range of calculations than Shor's.
Three years later, Kitaev formulated his original proposal for a topological quantum computer. In the theoretical system, information is stored on pairs of quantum particles called anyons. These arise only in special two-dimensional systems and take the form of imperfections in a layer of electrons that tend to behave as a gas. In a rough sense, anyons are the quantum equivalent of holes in a semiconductor--they're empty spots in a regular field of electrons. What's bizarre about a topological computing system is that the individual qubits are actually subject to greater fluctuations than the qubits in other experimental quantum computer schemes. But when errors occurs, topological systems are easier to correct.
Now that the MacArthur Fellowship will free him from some of the demands of academia, Kitaev plans to spend more time studying the properties of topological systems in general.
Kitaev is optimistic for the future of quantum computing but thinks it's still too early to predict which of the many approaches will ultimately lead to a working device. ”I think there are many unresolved problems with quantum computing,” says Kitaev. ”But hopefully some of them will work.”