01065nas a2200097 4500008004100000245006500041210006300106520074400169100001700913856003700930 2018 eng d00aA belief propagation algorithm based on domain decomposition0 abelief propagation algorithm based on domain decomposition3 a
This note provides a detailed description and derivation of the domain decomposition algorithm that appears in previous works by the author. Given a large re-estimation problem, domain decomposition provides an iterative method for assembling Boltzmann distributions associated to small subproblems into an approximation of the Bayesian posterior of the whole problem. The algorithm is amenable to using Boltzmann sampling to approximate these Boltzmann distributions. In previous work, we have shown the capability of heuristic versions of this algorithm to solve LDPC decoding and circuit fault diagnosis problems too large to fit on quantum annealing hardware used for sampling. Here, we rigorously prove soundness of the method.
1 aLackey, Brad uhttps://arxiv.org/abs/1810.10005