Dissipative search of an unstructured database

Abstract

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 analogue, accomplish the search asymptotically optimally in $\mathcal{O}(\sqrt{N})$ time steps. We reformulate the search problem as a dissipative 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 physically admissible, long-range transition rates between the energy levels, the system relaxes to the ground state, corresponding to the sought element, in time $\mathcal{O}(\ln N)$.

arXiv comment8 pages, 2 figures, published version

References in corpus (5)

• Quantum Mechanics helps in searching for a needle in a haystack
• Carnot Cycle at Finite Power: Attainability of Maximal Efficiency
• Open Quantum System Dynamics: recovering positivity of the Redfield equation via Partial-Secular Approximation
• Quantum simulations of dissipative dynamics: time-dependence instead of size
• The speed of Markovian relaxation towards the ground state

Cited by in corpus (3)

• Optimal Thermometers with Spin Networks
• Quantum thermodynamic advantage in work extraction from steerable quantum correlations
• Quantum Dissipative Search via Lindbladians