Quantum Algorithms for Weighted Constrained Sampling and Weighted Model Counting

Given a Boolean formula and a functions assigning weights to assignments of values to the Boolean variable, we consider the problems of Weighted Constrained Sampling (WCS) and Weighted Model Counting (WMC). The first, also called distributionaware sampling (Chakraborty et al, 2014), involves sampling assignments to the Boolean variables with a probability proportional to their weight given that the formula is satisfied. The latter (Sang et al, 2005) consists in computing the sum of the weights of the models of the formula, i.e. the weighted model count. WCS has important applications in a variety of domanis, including statistical physics (Jerrum and Sinclair, 1996), statistics (Madras and Piccioni, 1999), hardware verification (Naveh et al, 2006), and probabilistic reasoning, where it can be used to solve the problem of Most Probable Explanation (MPE) and Maximum A Posteriori (MAP). MPE (Sang et al, 2007) involves finding an assignment to all variables that satisfies a Boolean formula and has the maximum weight. The related MAP problem means finding an assignment of a subset of the variables such that the sum of the weights of the models of the formula that agree on the assignment is maximum. WMC was successfully applied, among others, to the problem of performing inference in graphical models (Chavira and Darwiche, 2008; Sang et al, 2005).