  In quantum embedding theories, a quantum many-body system is divided into
localized clusters of sites which are treated with an accurate `high-level'
theory and glued together self-consistently by a less accurate `low-level'
theory at the global scale. The recently introduced variational embedding
approach for quantum many-body problems combines the insights of semidefinite
relaxation and quantum embedding theory to provide a lower bound on the
ground-state energy that improves as the cluster size is increased. The
variational embedding method is formulated as a semidefinite program (SDP),
which can suffer from poor computational scaling when treated with black-box
solvers. We exploit the interpretation of this SDP as an embedding method to
develop an algorithm which alternates parallelizable local updates of the
high-level quantities with updates that enforce the low-level global
constraints. Moreover, we show how translation invariance in lattice systems
can be exploited to reduce the complexity of projecting a key matrix to the
positive semidefinite cone.
