Dissipative search of an unstructured database

The search of an unstructured database amounts to finding one element having a certain property out of N elements. The classical search with an oracle checking one element at a time requires on average N/2 steps. The Grover algorithm for the quantum search and its unitary Hamiltonian evolution analog accomplish the search asymptotically optimally in O(root N) time steps. We reformulate the search problem as a dissipative, incoherent Markov process acting on an N-level system weakly coupled to a thermal bath. Assuming that the energy levels of the system represent the database elements, we show that, with a proper choice of the spectrum and long-range but bounded transition rates between the energy levels, the system relaxes to the ground state, corresponding to the sought element, in time O(ln N).

Automated summary

This paper investigates the search problem in an unstructured database and introduces the Grover algorithm for quantum search. By reformulating the search problem as a Markov process, the authors find that the desired element can be found in a shorter time.