I2 Lab Distinguished Seminar Series
Quantum Searching - Old & New
Dr. Lov K. Grover
Thursday, May 4, 2006
2:00PM - CSB-232
Abstract
Computers as we know them, are classical. Recently it was realized that using computers based on quantum mechanics would allow unprecedented improvements in efficiency by allowing entirely new algorithms to be executed. The quantum search algorithm is just one of two such algorithms that has been discovered. In its simplest form it allows an unstructured database of size N to be searched in only square-root(N) steps (any classical algorithm would clearly need N steps). It has been applied to a number of problems ranging from cryptography to precision measurement. It continues to find application in new areas, the most recent of which is laser resonator design.
Short Bio
Dr. Grover is a Distinquished Member of the Technical Staff of Bell Labs Research, Lucent Technologies. He invented a novel quantum mechanical algorithm to search a database of size N in √N time. This is one of the two algorithms known where a quantum computer would have a clear advantage over a classical computer. This algorithm has been proved to be the best possible scheme for exhaustive search. Several hundred technical articles have been written about this. Experimental groups at MIT, Berkeley, IBM and Oxford, have implemented this algorithm using NMR technology. Bell Labs News featured this work in the Oct. issue under the “Today’s Innovators” column, and in June, 1998, & May 2000 in regular articles. Physics Today covered this in the October 1997 issue in their “Search & Discovery” section. Science has featured three separate Perspectives articles on this algorithm. Science News has published three news articles on this. The New York Times, USA Today, Scientific American, The Economist, EE Times, Silicon India and numerous magazines and newspapers all over the world have covered this extensively. John Preskill, Professor in Physics at Caltech and one of the leading experts in quantum computing, in an article in the October 1997 issue of Physics Today has called this – “the most important recent development in quantum complexity,” he went on to say, “if quantum computers were in use a hundred years from now, my guess is that they would be used to run Grover’s Algorithm”.
|
