Google exploring quantum computing algorithms

DEC 16, 2009

Physics Today

Physics Today : Google is working on developing a quantum computer , announced Google’s Hartmut Neven at the Neural Information Processing Systems conference (NIPS 2009) in Vancouver, Canada, last week.Neven, who is the company’s technical lead manager for image recognition, gave details of the presentation on the Google research blog .The reason for Google’s interest in quantum computing is speed. As the size of the internet increases exponentially it is becoming harder and harder for Google to maintain the fast speed of the service without having to resort to building massive server farms.A quantum-based computer could speed up searches dramatically and add a new layer of features to google’s existing features, especially on images. As Neven states in the blog:

Assume I hide a ball in a cabinet with a million drawers. How many drawers do you have to open to find the ball? Sometimes you may get lucky and find the ball in the first few drawers but at other times you have to inspect almost all of them. So on average it will take you 500,000 peeks to find the ball. Now a quantum computer can perform such a search looking only into 1000 drawers. This mind boggling feat is known as Grover’s algorithm .

The company has spent three years working on quantum adiabatic algorithms with the Canadian company D-Wave providing the hardware.D-Wave’s processors work by magnetically coupling superconducting loops called rf-SQUID flux qubits . “It is not easy to demonstrate that a multi-qubit system such as the D-Wave chip indeed exhibits the desired quantum behavior,” says Neven.At NIPS 2009 Neven demonstrated what google had achieved so far. The company built a detector that has learned to spot cars by looking at example pictures. “There are still many open questions,” says Neven, “but in our experiments we observed that this detector performs better than those we had trained using classical solvers running on the computers we have in our data centers today.” Related Links Primer in quantum algorithms Training a large scale classifier with the quantum adiabatic algorithm NIPS 2009 demonstration: Binary classification using hardware implementation of quantum annealing