Quantum computers could help search engines keep up with the Internet's growth

ScienceDaily (June 12, 2012) — Most people don't think twice about how Internet search engines work. You type in a word or phrase, hit enter, and poof -- a list of web pages pops up, organized by relevance.

Behind the scenes, a lot of math goes into figuring out exactly what qualifies as most relevant web page for your search. Google, for example, uses a page ranking algorithm that is rumored to be the largest numerical calculation carried out anywhere in the world. With the web constantly expanding, researchers at USC have proposed -- and demonstrated the feasibility -- of using quantum computers to speed up that process.

"This work is about trying to speed up the way we search on the web," said Daniel Lidar, corresponding author of a paper on the research that appeared in the journal Physical Review Letters on June 4.

As the Internet continues to grow, the time and resources needed to run the calculation -- which is done daily -- grow with it, Lidar said.

Lidar, who holds appointments at the USC Viterbi School of Engineering and the USC Dornsife College of Letters, Arts and Sciences, worked with colleagues Paolo Zanardi of USC Dornsife and first author Silvano Garnerone, formerly a postdoctoral researcher at USC and now of the University of Waterloo, to see whether quantum computing could be used to run the Google algorithm faster.

As opposed to traditional computer bits, which can encode distinctly either a one or a zero, quantum computers use quantum bits or "qubits," which can encode a one and a zero at the same time. This property, called superposition, some day will allow quantum computers to perform certain calculations much faster than traditional computers.

Currently, there isn't a quantum computer in the world anywhere near large enough to run Google's page ranking algorithm for the entire web. To simulate how a quantum computer might perform, the researchers generated models of the web that simulated a few thousand web pages.

The simulation showed that a quantum computer could, in principle, return the ranking of the most important pages in the web faster than traditional computers, and that this quantum speedup would improve the more pages needed to be ranked. Further, the researchers showed that to simply determine whether the web's page rankings should be updated, a quantum computer would be able to spit out a yes-or-no answer exponentially faster than a traditional computer.

This research was funded by number of sources, including the National Science Foundation, the NASA Ames Research Center, the Lockheed Martin Corporation University Research Initiative program, and a Google faculty research award to Lidar.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by University of Southern California.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

Silvano Garnerone, Paolo Zanardi, Daniel Lidar. Adiabatic Quantum Algorithm for Search Engine Ranking. Physical Review Letters, 2012; 108 (23) DOI: 10.1103/PhysRevLett.108.230506

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Quantum computers could help search engines keep up with the Internet's growth

ScienceDaily (June 12, 2012) — Most people don't think twice about how Internet search engines work. You type in a word or phrase, hit enter, and poof -- a list of web pages pops up, organized by relevance.

Behind the scenes, a lot of math goes into figuring out exactly what qualifies as most relevant web page for your search. Google, for example, uses a page ranking algorithm that is rumored to be the largest numerical calculation carried out anywhere in the world. With the web constantly expanding, researchers at USC have proposed -- and demonstrated the feasibility -- of using quantum computers to speed up that process.

"This work is about trying to speed up the way we search on the web," said Daniel Lidar, corresponding author of a paper on the research that appeared in the journal Physical Review Letters on June 4.

As the Internet continues to grow, the time and resources needed to run the calculation -- which is done daily -- grow with it, Lidar said.

Lidar, who holds appointments at the USC Viterbi School of Engineering and the USC Dornsife College of Letters, Arts and Sciences, worked with colleagues Paolo Zanardi of USC Dornsife and first author Silvano Garnerone, formerly a postdoctoral researcher at USC and now of the University of Waterloo, to see whether quantum computing could be used to run the Google algorithm faster.

As opposed to traditional computer bits, which can encode distinctly either a one or a zero, quantum computers use quantum bits or "qubits," which can encode a one and a zero at the same time. This property, called superposition, some day will allow quantum computers to perform certain calculations much faster than traditional computers.

Currently, there isn't a quantum computer in the world anywhere near large enough to run Google's page ranking algorithm for the entire web. To simulate how a quantum computer might perform, the researchers generated models of the web that simulated a few thousand web pages.

The simulation showed that a quantum computer could, in principle, return the ranking of the most important pages in the web faster than traditional computers, and that this quantum speedup would improve the more pages needed to be ranked. Further, the researchers showed that to simply determine whether the web's page rankings should be updated, a quantum computer would be able to spit out a yes-or-no answer exponentially faster than a traditional computer.

This research was funded by number of sources, including the National Science Foundation, the NASA Ames Research Center, the Lockheed Martin Corporation University Research Initiative program, and a Google faculty research award to Lidar.

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by University of Southern California.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Journal Reference:

Silvano Garnerone, Paolo Zanardi, Daniel Lidar. Adiabatic Quantum Algorithm for Search Engine Ranking. Physical Review Letters, 2012; 108 (23) DOI: 10.1103/PhysRevLett.108.230506

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here

Chips as mini Internets: Data-routing techniques that undergird Internet could increase efficiency of multicore chips

ScienceDaily (Apr. 10, 2012) — Computer chips have stopped getting faster. In order to keep increasing chips' computational power at the rate to which we've grown accustomed, chipmakers are instead giving them additional "cores," or processing units.

Today, a typical chip might have six or eight cores, all communicating with each other over a single bundle of wires, called a bus. With a bus, however, only one pair of cores can talk at a time, which would be a serious limitation in chips with hundreds or even thousands of cores, which many electrical engineers envision as the future of computing.

Li-Shiuan Peh, an associate professor of electrical engineering and computer science at MIT, wants cores to communicate the same way computers hooked to the Internet do: by bundling the information they transmit into "packets." Each core would have its own router, which could send a packet down any of several paths, depending on the condition of the network as a whole.

At the Design Automation Conference in June, Peh and her colleagues will present a paper she describes as "summarizing 10 years of research" on such "networks on chip." Not only do the researchers establish theoretical limits on the efficiency of packet-switched on-chip communication networks, but they also present measurements performed on a test chip in which they came very close to reaching several of those limits.

Last stop for buses

In principle, multicore chips are faster than single-core chips because they can split up computational tasks and run them on several cores at once. Cores working on the same task will occasionally need to share data, but until recently, the core count on commercial chips has been low enough that a single bus has been able to handle the extra communication load. That's already changing, however: "Buses have hit a limit," Peh says. "They typically scale to about eight cores." The 10-core chips found in high-end servers frequently add a second bus, but that approach won't work for chips with hundreds of cores.

For one thing, Peh says, "buses take up a lot of power, because they are trying to drive long wires to eight or 10 cores at the same time." In the type of network Peh is proposing, on the other hand, each core communicates only with the four cores nearest it. "Here, you're driving short segments of wires, so that allows you to go lower in voltage," she explains.

In an on-chip network, however, a packet of data traveling from one core to another has to stop at every router in between. Moreover, if two packets arrive at a router at the same time, one of them has to be stored in memory while the router handles the other. Many engineers, Peh says, worry that these added requirements will introduce enough delays and computational complexity to offset the advantages of packet switching. "The biggest problem, I think, is that in industry right now, people don't know how to build these networks, because it has been buses for decades," Peh says.

Forward thinking

Peh and her colleagues have developed two techniques to address these concerns. One is something they call "virtual bypassing." In the Internet, when a packet arrives at a router, the router inspects its addressing information before deciding which path to send it down. With virtual bypassing, however, each router sends an advance signal to the next, so that it can preset its switch, speeding the packet on with no additional computation. In her group's test chips, Peh says, virtual bypassing allowed a very close approach to the maximum data-transmission rates predicted by theoretical analysis.

The other technique is something called low-swing signaling. Digital data consists of ones and zeroes, which are transmitted over communications channels as high and low voltages. Sunghyun Park, a PhD student advised by both Peh and Anantha Chandrakasan, the Joseph F. and Nancy P. Keithley Professor of Electrical Engineering, developed a circuit that reduces the swing between the high and low voltages from one volt to 300 millivolts. With its combination of virtual bypassing and low-swing signaling, the researchers' test chip consumed 38 percent less energy than previous packet-switched test chips. The researchers have more work to do, Peh says, before their test chip's power consumption gets as close to the theoretical limit as its data transmission rate does. But, she adds, "if we compare it against a bus, we get orders-of-magnitude savings."

Luca Carloni, an associate professor of computer science at Columbia University who also researches networks on chip, says "the jury is always still out" on the future of chip design, but that "the advantages of packet-switched networks on chip seem compelling." He emphasizes that those advantages include not only the operational efficiency of the chips themselves, but also "a level of regularity and productivity at design time that is very important." And within the field, he adds, "the contributions of Li-Shiuan are foundational."

Share this story on Facebook, Twitter, and Google:

Other social bookmarking and sharing tools:

Story Source:

The above story is reprinted from materials provided by Massachusetts Institute of Technology. The original article was written by Larry Hardesty.

Note: Materials may be edited for content and length. For further information, please contact the source cited above.

Note: If no author is given, the source is cited instead.

Disclaimer: Views expressed in this article do not necessarily reflect those of ScienceDaily or its staff.

View the original article here