Searching a Quantum Phone Book

See allHide authors and affiliations

Science  31 Jan 1997:
Vol. 275, Issue 5300, pp. 627-628
DOI: 10.1126/science.275.5300.627

You are currently viewing the summary.

View Full Text

Log in to view the full text

Log in through your institution

Log in through your institution


Finding a phone number in a directory when one knows the name is easy; much harder is finding the name given the number. On average, a search algorithm will have to scan half the total number of entries. If the database or directory is extremely large, the search may be impossible with classical computers. New possibilities emerge, however, with quantum computing. As Brassard discusses in his Perspective, a new algorithm developed by L. K. Grover enables much faster searching of large databases if one uses a quantum computer.