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.
We propose a physical realization of the unstructured database search that works via classical, dissipative model of spherical spins. The database is implemented via spin-spin couplings, where the selected coupling refers to a larger ferromagnetic interaction between two selected spins. The low-temperature equilibrium of this model leads to magnetization strongly concentrated on the selected spins, which means that the search is complete. The search time refers to the relaxation time to equilibrium from a homogeneous initial state, and is described via Langevin equations. This time scales as O(Ma) with a<1/2, where M is the database volume. This is faster than Grover's search, showing how a dissipative, classical analog computer can overcome the quantum unitary computer.
Sorting is a fundamental computational process that facilitates subsequent searching of a database. It can be thought of as factorization of the search process. The location of a desired item in a sorted database can be found by classical queries that inspect one letter of the label at a time. For an unsorted database, no such classical quick search algorithm is available. If the database permits quantum queries, however, then mere digitization is sufficient for efficient search. Sorting becomes redundant with the quantum superposition of states. A quantum algorithm is written down that locates the desired item in an unsorted database a factor of two faster than the best classical algorithm can in a sorted database. This algorithm has close resemblance to the assembly process in DNA replication.