HomeEmail

Distributed VQLS · Chapter 01

One linear system, many local views

The mathematical target is ordinary least squares. The constraints concern where the matrix lives, how vectors are represented, and which agents can communicate.

A solution encoded in amplitudes

Quantum linear solving prepares a state proportional to a solution, rather than printing every entry of that solution. Direction and magnitude must therefore be distinguished.

Definition

Amplitude encoding

For a nonzero real vector v∈R2nv\in\mathbb R^{2^n}, ∣k⟩|k\rangle denotes a computational-basis state. An nn-qubit state represents the direction of vv; its norm is separate classical information. Reading all amplitudes is not a free consequence of preparing the state.

∣v⟩=1∥v∥2∑k=02n−1vk∣k⟩,⟨v∣v⟩=1,v≠0.\begin{aligned} |v\rangle&=\frac{1}{\|v\|_2}\sum_{k=0}^{2^n-1}v_k|k\rangle,\\ \langle v|v\rangle&=1,\qquad v\ne0. \end{aligned}

Manuscript · Quantum Linear System Problem

Block rows couple equations; block columns share unknowns

Assign block AijA_{ij} to agent (i,j)(i,j). Each block row contributes to one equation, while each block column acts on one part of the same unknown vector. Solving the blocks independently would lose both relationships.

Definition

The block-partitioned problem

Agent (i,j)(i,j) knows AijA_{ij} and a right-hand-side share bijb_{ij}. It maintains an estimate xijx_{ij} of the shared block xjx_j. Row neighbors coordinate equation contributions; column neighbors seek agreement on xjx_j. The manuscript uses identical connected, undirected row graphs and identical connected, undirected column graphs.

d=2q,m=2n−q,A=[Aij]∈Rmd×md,Aij∈Rd×d,x=(x1⊤,…,xm⊤)⊤,xj,bi∈Rd,(Ax−b)i=∑j=1mAijxj−bi,∑j=1mbij=bi.\begin{aligned} d&=2^q,\qquad m=2^{n-q},\\ A&=[A_{ij}]\in\mathbb R^{md\times md},\qquad A_{ij}\in\mathbb R^{d\times d},\\ x&=(x_1^\top,\ldots,x_m^\top)^\top,\qquad x_j,b_i\in\mathbb R^d,\\ (Ax-b)_i&=\sum_{j=1}^{m}A_{ij}x_j-b_i,\qquad \sum_{j=1}^{m}b_{ij}=b_i. \end{aligned}

Manuscript · Problem Formulation, Assumption 1

The global target is still least squares

A consistent system permits a zero residual. An inconsistent system does not, so agreement between agents is necessary but is not itself a solution criterion.

Objective

Residual minimization and column agreement

The first line is exactly min⁡x∥Ax−b∥22\min_x\|Ax-b\|_2^2. The second line describes the agreement required of local copies. Since each column graph is connected, edge-wise agreement makes every copy in a column equal.

min⁡x1,…,xm  ∑i=1m∥∑j=1mAijxj−bi∥22,xij=xkjfor column neighbors (i,j),(k,j).\begin{aligned} \min_{x_1,\ldots,x_m}\;&\sum_{i=1}^{m}\left\|\sum_{j=1}^{m}A_{ij}x_j-b_i\right\|_2^2,\\ x_{ij}&=x_{kj}\quad\text{for column neighbors }(i,j),(k,j). \end{aligned}

Manuscript · Problem Formulation

A capacity tradeoff, not free capacity

Every qubit removed from the local state doubles the block-grid width and quadruples the number of agents in this construction. Smaller local circuits are purchased with more processors, measurements, and coordination.

Identity

Local dimension versus agent count

nn and qq count global and local system qubits. This is a representation-size identity for a square block partition, not a runtime or hardware-resource advantage theorem.

Nagents=m2=4n−q,q=n−12log⁡2Nagents.N_{\mathrm{agents}}=m^2=4^{n-q},\qquad q=n-\tfrac12\log_2N_{\mathrm{agents}}.

Manuscript · Problem Formulation

Last updated