By Marlene Cimons, National Science Foundation

When people ask computational theorist Scott Aaronson if working quantum computers will become widely available soon, he likens this to asking the same of 19th Century English mathematician Charles Babbage, whose designs were the basis for the earliest all-purpose computers. It took about 150 years from Babbage’s time before classical computers were almost everywhere.

“I think if we can beat that, we’re doing well,” Aaronson says.

There certainly is reason to believe that successful quantum computers, eventually, will become a reality, although no one can predict when. “We have small quantum computers already,” Aaronson says. “We need to scale them up. It’s a huge engineering challenge.”

But, then again, so is the potential. “One of the most exciting things about quantum computing is that it gives us a powerful new language for understanding quantum mechanics itself, a new language for understanding physics, “Aaronson says.

Quantum mechanics, which Aaronson calls “the single most important thing that has been discovered about the physical world,” is a mathematical theory that describes the behavior of subatomic particles that can move from one point to another as if they were waves. During the past century, the field has revolutionized electrical circuits that power computers, cell phones and the many other devices that are an integral part of our daily lives.

Successful quantum computers could allow researchers to simulate quantum processes, and better understand how high-temperature superconductors work. Furthermore, “if you are designing new drugs, or nano-material, any problem in chemistry and materials science where the quantum behavior of your material is important, then such a computer might help you,” he adds.

Aaronson is an associate professor of electrical engineering and computer science at the Massachusetts Institute of Technology (MIT) where he focuses his research on what quantum computers can--and cannot--do. More specifically, he is exploring what physical resources are needed for quantum computers to surpass classical computers, as well as the barriers to solving computer science’s vexing P versus NP question, that is, whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.

He is conducting his work under a a National Science Foundation (NSF) Faculty Early Career Development (CAREER) award, which he received in 2009 as part of NSF’s American Recovery and Reinvestment Act. The award supports junior faculty who exemplify the role of teacher-scholars through outstanding research, excellent education and the integration of education and research within the context of the mission of their organization. NSF is funding his work with $580,000 over four years.

The NSF also recently announced that Aaronson and Robert Wood, associate professor in Harvard University’s school of engineering, would receive the Alan T. Waterman Award, which recognizes outstanding researchers younger than 35 in any field of science or engineering NSF supports. In addition to a medal, each of this year’s awardees will receive a $1 million grant over three years for further advanced study.

Aaronson, also the founder of the “Complexity Zoo” wiki, which catalogs more than 500 computational complexity classes, and author of the blog “Shtetl-Optimized,” explains that the sole reason for having quantum computers is that the sub-atomic world obeys different laws of probability than the ones most people are accustomed to.

“It would be silly to speak of a ‘minus 30 percent chance of rain tomorrow,’ much less a ‘square root of minus 1 percent chance,’” he says. “However, quantum mechanics is based on numbers called amplitudes, which are closely related to probabilities, but can also be negative.”

More importantly, “if an event, for example, a photon hitting a screen, can happen one way with positive amplitude, and a different way with negative amplitude, then the two amplitudes can cancel each other out, so that the event never happens at all,” he adds. ‘The goal in quantum computing is to choreograph a computation so that the amplitudes leading to wrong answers cancel each other out, while the amplitudes leading to right answers reinforce.”





Also, quantum computers could factor enormous numbers quickly, an insight that grew from the research of Aaronson’s MIT colleague, Peter Shor, who discovered a quantum algorithm for factoring exponentially faster than the best known algorithm running on a classical computer. This means that quantum computers would be capable of breaking almost all the cryptography used to protect information in the world today.

“Everyone would have to switch to different cryptographic codes,” Aaronson says, adding, that, predictably, officials in the federal government’s National Security Agency have become quite interested in the possibilities. “Everyone jokes that the NSA already has a quantum computer in its basement that nobody know about,” he says. “I doubt it.”

The goal is to build upon today’s small quantum computers by adding more and more qubits (units of quantum information, rather than the “bits” of traditional computers) beyond what is currently possible, which is about ten qubits, he says.

“The problem is that they fall apart quickly due to decoherence,” or unwarranted interaction between the computer and its outside environment, he says. With this exposure, “the system loses its quantum behavior.”