Quantum Stalking

Continuing with today's theme...


The following text comes from John Preskill's typed lecture notes for Ph/CS 219 (Quantum Information Theory):

"But now suppose that you know someone's phone number, and you want to look up her name. Unless you are fortunate enough to have access to a reverse directory, this is a tedious procedure. Chances are you will need to check quite a few entries in the phone book before you come across her number.

"In fact, if the N numbers are listed in a random order, you will need to look up (1/2)N numbers before the probability is P = 1/2 that you have found her number (and hence her name). What Grover discovered is that, if you have a quantum phone book, you can learn her name with high probability by consulting the phone book only about \sqrt{N} times."


There you have it---the real reason Lov Grover's factoring algorithm is such an important scientific achievement! People want to implement it for stalking.