Faculty @ Yerevan Physics Institute, Armenia
Friday July 1 – 8.00 BST
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 analogue, accomplish the search asymptotically optimally in $O(\sqrt{N})$ time steps. Here we propose a new computational model based on dissipative dynamics, where the quantum search is reformulated as a problem in non-equilibrium statistical mechanics. Now the search amounts to relaxing to the ground state for a quantum system having a specific, gapped energy spectrum. We show that under proper conditions, a dissipative Markov process in the $N$-level system coupled to a thermal bath leads to the system’s relaxation to the ground state during time $O(\ln N)$.
[A. E. Allahverdyan and D. Petrosyan, Dissipative search of an unstructured database, Phys. Rev. A 105, 032447 (2022)].