Google May Give Quantum Computing a Job in Search
Quantum computing may be coming to a search engine near you. Google and D-Wave are working together on a project to bring quantum computing to searches in a way that would, in a sense, teach machines to recognize images. If it works in image search, the technology could be applied to other search technologies as well.
12/16/09 2:24 PM PT
Quantum computing will help Google with the sophisticated artificial intelligence technologies such as machine learning and pattern recognition that its services are based on.
Solving the more difficult problems inherent in machine learning and pattern recognition using more conventional methods would require server farms so large that they could never realistically be built, wrote Harmut Neven, Google's technical lead manager of image recognition, on Google's research blog. Instead, quantum computing may hold the key.
What Is Quantum Computing?
Quantum computers make direct use of phenomena in quantum mechanics, such as superposition and entanglement, to work on data. The idea is that quantum properties can be used to represent data and to perform operations on these data.
Quantum superposition, which defines the collection of all possible states that an object can have, is the fundamental law of quantum mechanics.
This is based on probability theory -- more or less. Essentially, probability theory assigns a real number between zero and one to every possible event. You can add or multiply the numbers of two events to calculate the probability of their outcome. Quantum mechanics expands on this by assigning complex numbers called "amplitudes" to events instead of a number between zero and one.
In superposition, you assign a complex number to every possible situation in order to describe the world. These complex numbers can be positive or negative. To describe how things change, you add or multiply these complex numbers.
Quantum entanglement simply means a state in which two or more objects have their quantum states linked together so that you have to include both if you want to describe either. It's rather like describing one partner in a marriage -- it's impossible without describing the other.
Who Is D-Wave Systems?
D-Wave Systems is a company that is developing a new class of high-performance computing systems designed to solve complex search and optimization problems. The initial emphasis is on artificial intelligence and machine learning.
The company has developed processors that use a computational model known as "adiabatic quantum computing" (AQC). These are made using superconducting metals instead of semiconductors and are operated at ultra-low temperatures in a magnetic vacuum.
In fact, D-Wave's products use unconventional D-Wave superconductors. These are materials that display superconductivity which does not conform to conventional theories. High-temperature singlet D-Wave superconductors operate at 35 degrees Kelvin, or -238 degrees Celsius.
AQC relies on the adiabatic theorem to do calculations. Basically, this theorem holds that a quantum mechanical system can change its form when subjected to gradually changing external conditions, but cannot do so when the conditions vary rapidly. Think of it as parallel to evolution -- species can evolve and adapt to changing conditions over long periods of time, but rapid changes kill them off.
Doing More, Faster to Win
Quantum computers can find a ball hidden in a cabinet with 1 million drawers by looking into only 1,000 of them, using something called "Grover's algorithm," Google's Neven said. This is a quantum algorithm for searching an unsorted database in a given length of time with a given amount of storage space that provides answers with high probability.
In other words, the answers Grover's algorithm turns up are those with the highest probability of being correct. Repeating the search will improve the accuracy of its results.
"The sheer amount of data Google has to deal with is so large that it's basically testing various approaches to see if it's even worth considering them," Carl Howe, Yankee Group's director of anywhere consumer research, told TechNewsWorld.
Google is testing the quantum computing approach with images because the problem can be decomposed easily, Howe said. "You can take apart the problem of recognizing however many millions of images they get each day and farm different processes out to different groups of computers in the server farm. Then they can compare the results of a new process to the standard results," he explained.
"This could lead to smart services that better anticipate users' needs and quickly customize themselves to the user," Rob Enderle, principal analyst at the Enderle Group, told TechNewsWorld. "This could be a game changer."