Quantum bits help yield some computer ESP
If you don't ask somebody a question and they give you the answer to the question you were thinking about asking but didn't, you might mark it down to an odd coincidence, or to ESP.
If your computer is on and you don't run a Google search and you still get an answer, you might think a hacker has taken over the machine, or a cyber-savvy poltergeist.
But University of Illinois researchers are attracting attention for showing how to get an answer from an algorithm – a formula for performing a certain task on a computer in this case – without actually running the algorithm on the computer.
Physics Professor Paul Kwiat and graduate student Onur Hosten aren't attributing their results to clairvoyance or to a ghost in the machine, however.
The phenomenon, called "counterfactual computation," stems from the oft-bizarre physics at the quantum level, where atoms and other basic particles live, which sometimes seems like the paranormal stuff of an X-Files episode.
"It's as though it did run even though it didn't," Kwiat said of the results of the experiment by Hosten, which appeared in the journal Nature last week.
The problem involved searching a simple database of four entries and identifying an entry the researchers had flagged, the purpose of the algorithm.
But the computer that didn't run the algorithm and still yielded an answer wasn't at all like the one on your desk.
This computer consisted of an array with a laser, lenses, mirrors and other equipment in Kwiat's lab, designed to produced and manipulate particles of light, or photons.
One law of quantum mechanics, called "superposition," says properties such as the spin of an electron or the polarization of a photon can be in a range of different states at once down at the atomic and subatomic levels.
In classic computing, computers work by combining zeros and ones into coded instructions that tell the machine what to do. But those "bits" can symbolize only a single thing at a time, a zero or a one.
Quantum bits, called "qubits," made, say, by having a photon polarized one way symbolize a one and another way a zero, can be all combinations at once because of superposition. In theory, that would allow every combination to be processed simultaneously, making everything work exponentially faster for some types of problems. Which has a lot of researchers looking at the technique, among other things for computing muscle-hungry cryptography and code-breaking routines.
Meanwhile, superposition also is at the root of the experiment by Hosten.
In essence, he sets photons to run and not to run the search algorithm and sends them through the array, which includes a region where the data is held. The way the mirrors are set up sometimes prevents the photons from passing through that area and running the algorithm.
In fact, when a photon beats the system and passes through the data it's considered undesirable in this context, because the researchers are trying to get an answer without doing so.
Because of superposition, some of the photons blocked from the data come out as if they had passed through it and run the algorithm, while others come out as if they hadn't. Capturing the state of the particles thus allows the UI researchers to infer information about the data as if it had been searched.
"You can go through sequentially and exclude the different answers without ever running the program," Kwiat said.
If that runs counter to anything you've experienced, well, that's why they call it counterfactual computing, and why the quantum world can be weirder than any Dali painting.
The UI experiment is a good way of examining quantum principles but pretty much a nonstarter as a practical method of quantum computing. The apparatus already is unwieldy and scaling it up to do any more than working with a simple database would make it worse.
But some of the ideas the UI researchers have for preventing photons from running the algorithm might be useful for error correcting in quantum computing in general, a key issue in making the technique useful, Kwiat said.
Besides Hosten, graduate students Julio Barreiro, Nicholas Peters and Matthew Rakher worked on the study, which was funded by the federal Disruptive Technologies Office and the National Science Foundation.