Quantum searching was first discovered in the context of searching an unsorted database of size N in sqrt(N) steps. In contrast to other quantum algorithms which are stand-alone algorithms for specific problems, quantum searching has found application in designing numerous other important algorithms. In fact, some natural processes have recently been hypothesized to be based on quantum searching (energy transfer in photosynthesis, crack detection, number of base amino acids in genes). The above topics will be discussed.
Lov Grover received his Ph.D. in Electrical Engineering from Stanford University in 1984, having previously received master’s degrees in Electrical Engineering from Caltech and Physics from Stanford. He joined Bell Labs in 1984 as a Member of Technical Staff, working initially in computer-aided design (CAD). During 1984-1987 he designed and implemented a VLSI CAD system based on simulated annealing, which was used to design and produce several thousand AT&T commercial chips. During 1987-1994 he was Visiting Professor at Cornell in the School of Electrical Engineering. In 1994 he returned to Bell Labs and the CAD group. In his spare time he invented the quantum search algorithm that bears his name. In 1996 he published “A new quantum mechanical algorithm for database search” at STOC (ACM Symposium on the Theory of Computing). John Preskill has written “If quantum computers are being used 100 years from now, I would guess that they will be used to run Grover's algorithm or something like it”, and the paper has over 6700 citations. During 1998-2008 he moved to Physics Research at Bell Labs, and was promoted to Distinguished Member of Technical Staff in 2002. He retired in 2008 and has been an independent researcher since then.