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)]. 

Categories: Talks Friday July 1