'

Quantum computing without computing

The optical quantum computer designed by researchers from the University of Illinois at Urbana-Champaign (UIUC) can find the answer to an algorithm without running it by using "counterfactual computation." Even the leader of the scientists' team thinks it's bizarre: "To my mind, quantum mechanics doesn't get any more mysterious than this."

What would happen if you powered up your computer and it gave you some results before opening any program? You would probably think that some kind of malware has infested your system. But with the optical quantum computer designed by researchers from the University of Illinois at Urbana-Champaign (UIUC), this is now a reality. This quantum computer can find the answer to an algorithm without running it by using "counterfactual computation." And if you think it's bizarre, even the leader of the scientists' team agrees with you: "To my mind, quantum mechanics doesn't get any more mysterious than this."

Let's start with a quote from Professor Paul Kwiat from UIUC.

"It seems absolutely bizarre that counterfactual computation – using information that is counter to what must have actually happened – could find an answer without running the entire quantum computer," said Kwiat, a John Bardeen Professor of Electrical and Computer Engineering and Physics at Illinois. "But the nature of quantum interrogation makes this amazing feat possible."

And here is a short explanation of the technique used by Paul Kwiat's Quantum Information Group.

Sometimes called interaction-free measurement, quantum interrogation is a technique that makes use of wave-particle duality (in this case, of photons) to search a region of space without actually entering that region of space. Utilizing two coupled optical interferometers, nested within a third, Kwiat's team succeeded in counterfactually searching a four-element database using Grover's quantum search algorithm.

Below is a diagram showing "the optical circuit realizing the search algorithm in a database of four elements" (Credit: Paul Kwiat's group, UIUC).

Kwiat's quantum computing experiment #1

And it becomes more and more strange: the team was able to search simultaneously for all the elements in the database.

Through clever use of beam splitters and both constructive and destructive interference, the researchers can put each photon in a superposition of taking two paths. Although a photon can occupy multiple places simultaneously, it can only make an actual appearance at one location. Its presence defines its path, and that can, in a very strange way, negate the need for the search algorithm to run.

Below is the "optical schematic of the method to interrogate for all database elements simultaneously" (Credit: Paul Kwiat's group, UIUC).

Kwiat's quantum computing experiment #2

But what can you conclude from such experiments?

"In a sense, it is the possibility that the algorithm could run which prevents the algorithm from running," Kwiat said. "That is at the heart of quantum interrogation schemes, and to my mind, quantum mechanics doesn't get any more mysterious than this."

And will this mysterious technology be useful?

While the researchers' optical quantum computer cannot be scaled up, using these kinds of interrogation techniques may make it possible to reduce errors in quantum computing, Kwiat said. "Anything you can do to reduce the errors will make it more likely that eventually you'll get a large-scale quantum computer."

For more information, this research work has been published by Nature under the title "Counterfactual quantum computation through quantum interrogation" (Volume 439, Number 7079, Page 949, February 23, 2006). Here are two links to the abstract and to the editor's summary, "An off day for computing." Here is an excerpt.

Counterfactual computation has been proposed as a logical consequence of quantum mechanics. Using appropriate algorithms, the theory goes, it should be possible to infer the outcome of a quantum computation without actually running the computer. Hosten et al. now report experimental confirmation that this does indeed happen. Their all-optical quantum computer was prepared in a superposition of interacting with and not interacting with an algorithm, and they obtained information about the result even when the photon did not interact with the algorithm. Surprisingly, the counterfactual approach worked better than randomly guessing the solution.

The above illustrations have been extracted from the supplementary infos supplied to Nature by the researchers (PDF format, 11 pages, 498 KB).

And for other angles about this research work -- but written in a 'lighter' language -- you also should read these two short articles from the Telegraph "Mysterious feats of new quantum computer" and the Inquirer, "Quantum Computer solves problem before asked."

Sources: James E. Kloeppel, University of Illinois at Urbana-Champaign (UIUC) news release, February 22, 2006; and various web sites

You'll find related stories by following the links below.