Cavity algorithms under global constraints: classical and quantum problems

The starting point of my thesis work was the study of optimization algorithms based on cavity method. These algorithms have been developed to a high degree of complexity in the last decade and they are also known as message passing algorithms (MPAs). My work has started by a question posed by my supervisor: what links can be found between those different approaches to the same problems? The starting aim of the PhD project was to explore the new ideas and algorithms that could result from a cross-fertilization between different approaches. During the first years we made a long and accurate comparison between different algorithms on a specific COP: the prize collecting Steiner tree problem. Looking to MPAs as an evolution of probability distributions of discrete variables led me to find some possible links with many body quantum physics, where typically we deal with probability amplitudes over discrete variables. In the recent years several results have appeared concerning the extension of the cavity method and message passing technics to quantum context. In 2012 Ramezanpour proposed a method, the variational quantum cavity method (VQCM), for finding approximate ground state wave functions based on a new messages passing algorithm used in stochastic optimization. Ramezanpour and I have extended this approach to find low excited states. In the last year of my Ph.D. I simplify the VQCM using imaginary time evolution operator. Moreover I extend this approach to find finite temperature density matrix.