[FRIAM] interesting scoping

[Marcus Daniels]

The paragraph under Implementation is consistent with my experience.   I guess Newman comes in with use cases that have more local connectivity (e.g. social networks).   For other types of networks like highly overlapped constraint problems, this will fall on its ass.   For quantum annealers (at least those using superconductors) it isn't really possible to directly realize globally dense connections because there is no way to route all the qubit inductors loops in 3-D space.  Belief propagation is one thing that has been tried in that community.  I think the factorize the Hamiltonian idea only make sense if you know something about the problem ahead of time. 

-----Original Message-----
From: Friam <friam-bounces at redfish.com> On Behalf Of u?l? ???
Sent: Tuesday, April 27, 2021 8:07 AM
To: FriAM <friam at redfish.com>
Subject: [FRIAM] interesting scoping


Belief propagation for networks with loops https://advances.sciencemag.org/content/7/17/eabf1211.abstract

> Our method operates by dividing a network into neighborhoods (20).  A  neighborhood  Ni(r)  around  node i  is  defined  as  the  node  iitself and all of its edges and neighboring nodes, plus all nodes and edges along paths of length r or less between the neighbors of i. See Fig. 1 for examples. The key to our approach is to focus initially on networks  in  which  there  are  no  paths  longer  than  r  between  the  neighbors of i, meaning that all paths are inside Ni(r).  This  means that all correlations between spins within Ni(r) are accounted for by edges that are also within Ni(r), which allows us to write exact mes-sage passing equations for these networks. Equivalently, we can de-fine a primitive cycle of length r starting at node i to be a cycle (i.e., a self-avoiding loop) such that at least one edge in the cycle is not on any shorter cycle beginning and ending at i. Our methods are then exact on any network that contains no primitive cycles of length greater than r + 2.
> ...
> Having defined the initial neighborhood Ni, we further define a neighborhood Nj  ∖  i  to  be  node  j  plus  all  edges  in  Nj  that  are  not  contained in Ni and the nodes at their ends. Our method involves writing the marginal probability distribution on the spin at node i in terms of a set of messages received from nodes j that are in Ni, in-cluding nodes that are not immediate neighbors of i. (This contrasts with  traditional  message  passing  in  which  messages  are  received  only from the immediate neighbors of i.) These messages are then, in turn, calculated from further messages j receives from nodes k∈Nj ∖ i and so forth.


--
↙↙↙ uǝlƃ
- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6  bit.ly/virtualfriam un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/