Quantum computer solves problem, without running

February 22, 2006
Quantum

By combining quantum computation and quantum interrogation, scientists at the University of Illinois at Urbana-Champaign have found an exotic way of determining an answer to an algorithm – without ever running the algorithm.

Using an optical-based quantum computer, a research team led by physicist Paul Kwiat has presented the first demonstration of "counterfactual computation," inferring information about an answer, even though the computer did not run. The researchers report their work in the Feb. 23 issue of Nature.

Quantum computers have the potential for solving certain types of problems much faster than classical computers. Speed and efficiency are gained because quantum bits can be placed in superpositions of one and zero, as opposed to classical bits, which are either one or zero. Moreover, the logic behind the coherent nature of quantum information processing often deviates from intuitive reasoning, leading to some surprising effects.

"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."

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. "By placing our photon in a quantum superposition of running and not running the search algorithm, we obtained information about the answer even when the photon did not run the search algorithm," said graduate student Onur Hosten, lead author of the Nature paper. "We also showed theoretically how to obtain the answer without ever running the algorithm, by using a 'chained Zeno' effect."

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.

"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."

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."

Source: University of Illinois at Urbana-Champaign

Explore further: Artificial intelligence in quantum systems, too

Related Stories

Artificial intelligence in quantum systems, too

February 22, 2017

Quantum biomimetics consists of reproducing in quantum systems certain properties exclusive to living organisms. Researchers at University of the Basque Country have imitated natural selection, learning and memory in a new ...

Success by deception

February 13, 2017

Theoretical physicists from ETH Zurich deliberately misled intelligent machines, and thus refined the process of machine learning. They created a new method that allows computers to categorize data—even when humans have ...

Machine learning method accurately predicts metallic defects

February 6, 2017

For the first time, researchers at the Lawrence Berkeley National Laboratory (Berkeley Lab) have built and trained machine learning algorithms to predict defect behavior in certain intermetallic compounds with high accuracy. ...

Researchers apply machine learning to condensed matter physics

February 13, 2017

A machine learning algorithm designed to teach computers how to recognize photos, speech patterns, and hand-written digits has now been applied to a vastly different set of data: identifying phase transitions between states ...

Designing new materials from 'small' data

February 17, 2017

Finding new functional materials is always tricky. But searching for very specific properties among a relatively small family of known materials is even more difficult.

Recommended for you

ZTE launches world's first 5G-ready smartphone

February 26, 2017

Chinese telecoms giant ZTE unveiled Sunday what it said is the world's first smartphone compatible with the lightening-fast 5G mobile internet service that networks expect to have up and running by 2020.

Stargazers applaud as moon eclipses sun

February 26, 2017

Stargazers applauded as they were plunged into darkness Sunday when the moon passed in front of the sun in a spectacular "ring of fire" eclipse.

Canada conservationist warns of 'cyber poaching'

February 25, 2017

Photographers, poachers and eco-tour operators are in the crosshairs of a Canadian conservationist who warns that tracking tags are being hacked and misused to harass and hunt endangered animals.

Polymer additive could revolutionize plastics recycling

February 24, 2017

When Geoffrey Coates, the Tisch University Professor of Chemistry and Chemical Biology, gives a talk about plastics and recycling, he usually opens with this question: What percentage of the 78 million tons of plastic used ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.