Quantum computing, or the procedure for using quantum mechanics to perform operations on data, is a technology that is still largely in the theoretical stages. But at the Associate for Computing Machinery's 43rd Symposium on Theory of Computing, to be held in San Jose, California, in June, a group from the Massachusetts Institute of Technology (MIT) may make a major step toward changing that.

Scott Aaronson, associate professor of computer science, and his graduate student, Alex Arkhipov, will present a paper titled "The Computational Complexity of Linear Optics," which describes an experiment offering new evidence of the work quantum computers may be capable of that traditional computers are not&mash;assuming the described experiment were to work, that is.

Aaronson and Arkhipov will propose a variation on a 1987 experiment conducted at the University of Rochester. It relied on a beam splitter, which splits an incoming light beam into two beams traveling in different directions: If two identical photons reached the splitter simultaneously, they will both assume that they traveled the same path rather than different ones. Over enough runs of a test using a sufficient number of photon detectors, it may be possible to predict the photons' path.

According to an MIT press release, however, there are numerous challenges to overcome. "Calculating...the likelihood of photons striking a given combination of detectors...is a hard problem. The researchers' experiment doesn't solve it outright, but every successful execution of the experiment does take a sample from the solution set. One of the key findings in Aaronson and Arkhipov's paper is that, not only is calculating the distribution a hard problem, but so is simulating the sampling of it. For an experiment with more than, say, 100 photons, it would probably be beyond the computational capacity of all the computers in the world."

Aaronson says that he and Arkhipov have not successfully proven that designing a device capable of testing the theory is impossible—which is an important first step, whether to eventually building a quantum computer, or even just laying the initial framework for using the microscopic secrets of the universe to let humans better understand the world that surrounds them.

For more information on Aaronson and Arkhipov's paper, read the abstract at Symposium on Theory of Computing's Web site.