Distributed VQLS · Chapter 02

A graph Laplacian makes the objective local

The Laplacian of a connected undirected graph has every zero-sum vector in its image. Local auxiliary variables can remove residual disagreement, but cannot change the component representing the original equation.

An exact least-squares equivalence

Write $d=2^q$ and let $L$ be the Laplacian of the common connected, undirected row graph. For each block row, stack the local residuals and auxiliary vectors. Column copies of each solution block are assumed to agree, so they define one vector $x$ .

Definition

The lifted residual

$A_{ij}$ is $d\times d$ ; $x$ , $\bar b_i$ , and $z_i$ have dimension $md$ . $I_d$ is the identity matrix, $\otimes$ is the Kronecker product, and $z$ denotes all auxiliary vectors together. Each correction $\bar Lz_i$ sums to zero across that block row.

\begin{aligned} \bar A_i&=\operatorname{diag}(A_{i1},\ldots,A_{im}),\qquad \bar L=L\otimes I_d,\\ \bar b_i&=(b_{i1}^{\top},\ldots,b_{im}^{\top})^{\top},\qquad \sum_j b_{ij}=b_i,\\ z_i&=(z_{i1}^{\top},\ldots,z_{im}^{\top})^{\top},\qquad z_{ij}\in\mathbb R^d,\\ F(x,z)&=\sum_{i=1}^{m}\|\bar A_i x-\bar b_i-\bar Lz_i\|_2^2. \end{aligned}

Manuscript · Distributed Optimization Reformulation

Lemma

Eliminating disagreement preserves the minimizers

Assume a connected undirected row graph, unrestricted real auxiliary vectors, and the consistent block copies defined above. Then $x^*$ minimizes the original least-squares objective if and only if some pair $(x^*,z^*)$ minimizes $F$ . Connected column graphs support the required agreement of local copies. No invertibility of $A$ is needed.

\min_z F(x,z)=\frac1m\|Ax-b\|_2^2\qquad\text{for every }x\in\mathbb R^{md}.

Proof / derivation

Put $r_i=\bar A_i x-\bar b_i$ and let $\mathbf1$ be the all-ones vector of length $m$ . Connectivity and symmetry give $\ker\bar L=\operatorname{span}\{\mathbf1\}\otimes\mathbb R^d$ and $\operatorname{im}\bar L=(\ker\bar L)^\perp$ . Minimizing over $z_i$ therefore leaves the orthogonal projection onto the consensus subspace, with projector $P=(\mathbf1\mathbf1^\top/m)\otimes I_d$ .

The sum of the blocks of $r_i$ is $A_i x-b_i$ , where $A_i=[A_{i1}\ \cdots\ A_{im}]$ . Thus the remaining residual consists of $m$ identical copies of the average block residual. Sum the identity below over $i$ to obtain the result. The positive factor $1/m$ does not change the minimizers.

\begin{aligned} Pr_i&=\mathbf1\otimes\frac{A_i x-b_i}{m},\\ \min_{z_i}\|r_i-\bar Lz_i\|_2^2 &=\|Pr_i\|_2^2=\frac1m\|A_i x-b_i\|_2^2. \end{aligned}

Manuscript · Lemma 1 and Appendix A

Objective

A cost evaluable by one agent and its row neighbors

$\mathcal N_{ij}$ contains the column indices of row neighbors of agent $(i,j)$ . The Laplacian term redistributes residuals without changing their sum. Away from column agreement, the sum of local costs is not the reduced global objective; coordination is part of the algorithm, not an optional extra.

\begin{aligned} C_{ij}&=\left\|A_{ij}x_{ij}-b_{ij}-\sum_{k\in\mathcal N_{ij}}(z_{ij}-z_{ik})\right\|_2^2,\\ F&=\sum_{i,j}C_{ij}\quad\text{when }x_{ij}=x_j. \end{aligned}

Manuscript · Distributed Optimization Reformulation

Parameterize direction and magnitude separately

The lemma concerns unrestricted vectors. The quantum algorithm substitutes a circuit-generated state and a trainable scale for each vector, preserving magnitude information but introducing an expressivity constraint.

Model

Two local variational states

$U$ and $V$ are fixed-layout parameterized circuits; $\alpha$ and $\beta$ are their angles. The real scalars $\rho$ and $\sigma$ restore vector scale. The experiments use $R_y$ rotations and nearest-neighbor controlled-Z gates, preserving real amplitudes. The least-squares equivalence does not guarantee that this restricted ansatz reaches a global minimizer.

\begin{aligned} x_{ij}&=\rho_{ij}|x_{ij}(\alpha_{ij})\rangle =\rho_{ij}U(\alpha_{ij})|0\rangle^{\otimes q},\\ z_{ij}&=\sigma_{ij}|z_{ij}(\beta_{ij})\rangle =\sigma_{ij}V(\beta_{ij})|0\rangle^{\otimes q},\\ \tilde\alpha_{ij}&=(\alpha_{ij},\rho_{ij}),\qquad \tilde\beta_{ij}=(\beta_{ij},\sigma_{ij}). \end{aligned}

Manuscript · Variational Ansatz and Cost Function

From a squared norm to quantum overlaps

Expand each local squared residual into operator expectation values and overlaps. An efficient linear combination of unitaries for each block then reduces these quantities to Hadamard-test measurements. Neighbors exchange circuit parameters and scales so the necessary states can be prepared locally; no state is transmitted through a quantum channel.

Identity

The measurement primitive

$s_{ij}$ counts unitary terms and $c_{ijh}$ are their coefficients. For normalized states $|u\rangle$ , $|v\rangle$ and a unitary $W$ , measuring Pauli $X$ on the ancilla gives the real overlap. The displayed identity explains the Hadamard-test primitive; state preparation and controlled-unitary implementation remain required resources. Gradients use parameter-shift evaluations of these terms.

\begin{aligned} A_{ij}&=\sum_{h=1}^{s_{ij}}c_{ijh}W_{ijh},\qquad W_{ijh}^{\dagger}W_{ijh}=I,\\ |\Psi\rangle&=\frac{|0\rangle|u\rangle+|1\rangle W|v\rangle}{\sqrt2},\\ \langle\Psi|X\otimes I|\Psi\rangle&=\operatorname{Re}\langle u|W|v\rangle. \end{aligned}

Manuscript · Data Encoding, Cost Function, and Hadamard Test Circuits

Track a shared gradient, not only a shared parameter

Column agents mix their parameters and gradient trackers; Adam uses the tracked signal for its adaptive update. Row agents exchange auxiliary-state parameters and the gradients needed to update them. The proposed scheme uses two communication rounds per iteration.

Model

The delayed column gradient tracker

$\mathcal M_{ij}$ indexes column neighbors; $w_{ik}$ are the manuscript's column-mixing weights. $y$ is the gradient tracker and $g$ is a local cost gradient. This is the tracker component, not the entire Adam update. The one-step gradient difference is delayed in the quantum implementation. Convexity in unrestricted vectors does not transfer to the circuit parameters.

\begin{aligned} g_{ij}(t)&=\nabla_{\tilde\alpha_{ij}}C_{ij}(t),\\ y_{ij}(t+1)&=\sum_{k\in\mathcal M_{ij}}w_{ik}y_{kj}(t) +g_{ij}(t)-g_{ij}(t-1). \end{aligned}

Manuscript · The Distributed VQLS Algorithm

Last updated September 26, 2026