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 <
[hidden email]> On Behalf Of u?l? ???
Sent: Tuesday, April 27, 2021 8:07 AM
To: FriAM <
[hidden email]>
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.comFRIAM-COMIC
http://friam-comic.blogspot.com/archives:
http://friam.471366.n2.nabble.com/- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
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.comFRIAM-COMIC
http://friam-comic.blogspot.com/archives:
http://friam.471366.n2.nabble.com/
Locked
