Quantum computing without weirdnessBy Eric Smalley, Technology Research News
Researchers laying the groundwork for software that will run on quantum computers could be barking up the wrong tree by assuming that one of the weirder aspects of quantum mechanics, entanglement, is a necessary ingredient.
When two or more atoms or subatomic particles are entangled, any change to one is immediately reflected by the same change in the other regardless of the physical distance between them.
Researchers have demonstrated that quantum computers have the potential to be much faster than normal computers for certain tasks like factoring and searching databases. Many researchers have argued that entanglement is the reason quantum computers will be more efficient.
But some computer scientists who are working on quantum algorithms are questioning that assumption. David A. Meyer, a research professor in the mathematics department at University of California in San Diego, has demonstrated that, contrary to appearances, a particular quantum search algorithm does not use entanglement.
"The point of that paper was to say that [interference] is really the crucial feature of how quantum algorithms work" rather than entanglement, he said.
Interference is the interaction of two or more waves. When atoms and subatomic particles are in their quantum states, they exist as waves.
"Interference is the same phenomenon you see with water waves," Meyer said. "If you start waves from two sides of a pool that make a corner, you'll get points where they reinforce so that the waves will be higher and points where they cancel out so the surface will be flat."
Atoms and particles spin in one of two directions, up or down, which can represent the ones and zeros of binary computing. A particle has a probability of spinning in either direction when it is in its quantum state. A quantum computer acts on a set of particles by influencing the probabilities of the particles' spins so that when the particles leave their quantum state the resulting spin directions represent a specific number.
Influencing the probabilities of the particles' spins is accomplished by creating specific patterns of interference among the particles' waves.
"If you're trying to get some specific outcome, what you want to do is set up the internal workings of the [quantum] computer so that the computational paths which correspond to outcomes that you don't want -- the answers that are wrong -- cancel out, and the computational paths which lead to the [outcome] that you do want -- the correct answer -- reinforce," said Meyer.
The crux of the debate is whether entanglement is the key to creating the correct interference patterns. According to Meyer, any process that controls interference should be sufficient.
The issue of whether entanglement is necessary in quantum algorithms might seem like an esoteric debate given that many researchers say that practical quantum computers are at least 20 years away. But the stakes for developing quantum algorithms are actually quite high, Meyer said.
"If we're trying convince the government and industry to fund the incredible expense and commitment of resources that's going to be necessary to get [quantum computers] built, we have to demonstrate that they're going to be able to do something useful," he said. "We really need to find more algorithms which will motivate this development. Figuring out how algorithms work and what's necessary to design them is really a crucial thing at this point in the history of quantum computing."
Consequently it's very important that researchers not get sidetracked by worrying about entanglement in their algorithms, Meyer said.
"It is a healthy thing that Meyer tries to debunk some of the claims that entanglement is the essential ingredient for quantum computation," said Wim van Dam, a computer scientist and member of the Center for Quantum Computation at the University of Oxford. "Entanglement is somewhat of a pet topic for physicists," he said. Computer scientists who are trying to come up with new quantum algorithms are less interested in this, he said.
Meyer published his work in the August 28, 2000 issue of the journal Physical Review Letters. The research was funded by the Army Research Office and the Advanced Research Development Agency.
Timeline: >20 years
TRN Categories: Quantum Computing; Data Structures and Algorithms
Story Type: News
Related Elements: Technical paper "Sophisticated Quantum Search Without Entanglement" in August 28, 2000 Physical Review Letters Vol. 85, Page 2014
October 18, 2000
Nanotubes gain larger kin
Quantum computing without weirdness
Pyramid pixels promise sharp pictures
Molecule movement could make memory
Researchers make cheap telecom laser
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog | Books
Buy an ad link
Ad links: Clear History
Buy an ad link
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.