Local to Global: A Distributed Quantum Approximate Optimization Algorithm for Pseudo-Boolean Optimization Problems#

伪布尔优化简介#

伪布尔优化形式及其松弛形式#

一个伪布尔优化的目标函数可以表示为如下形式（不考虑常数项）：

f_0(x_1, x_2, \dots, x_K) = \sum_ia_ix_i + \sum_{i<j}a_{ij}x_ix_j + \dots

我们可以把这种形式进行改写：

f_0(x_1, x_2, \dots, x_K) = \sum_{\mathcal{S}_0^l \in 2^{[K]}}c_l\prod_{i \in \mathcal{S}^l_0 }x_i

其中， 表示出现在目标函数中的变量数， 表示集合， 表示集合 的幂集的一个子集（这是因为，即：

2^{[K]} = \{\emptyset, \{1\}, \{2\}, \dots, [K] \}

于是 表示幂集中的元素，其中 为子集的标签（也就是函数中的某一项）， 表示项的系数

f_0(x_1, x_2, x_3) = x_1 + 2 \times x_3 + 4 \times x_2x_3

\begin{aligned}
\mathcal{S}^l_0 &\in \{\{1\}, \{3\}, \{2, 3\}\} \\
c_l &\in \{1, 2, 4\}
\end{aligned}

那么对于 PBO 问题，我们还存在多条约束（假设均为 的类型），我们可以将约束统一松弛为一种形式：

g_i(x_1, x_2, \dots, x_N) = 0

这里的 为变量的总数（注意，，这是因为在松弛时，我们会引入新变量）

例如约束：

x_1 + x_2 \leq 1

我们可以引入一个新的布尔变量 ，使得：

x_1 + x_2 = x_3 + 1 \rightarrow x_1 + x_2 - x_3 -1 = 0

松弛形式#

通过上面的松弛变换后，我们可以得到如下形式的 PBO 问题：

\begin{aligned}
\min_{x_1, \dots, x_N} &f_0(x_1, \dots, x_N) \\
s.t. \quad &g_1(x_1, \dots, x_N) = 0 \\
&g_2(x_1, \dots, x_N) = 0 \\
&\quad\vdots \\
&g_W(x_1, \dots, x_N) = 0 \\
\end{aligned}

这里 表示约束的个数

更进一步的，我们可以将约束作为函数的惩罚项，加在优化函数的后面，形式如下（此方法称为序列无约束最小化方法）：

\min f = f_0(x_1, \dots, x_N) + \mu \sum^W_{w = 1}g^2_w(x_1, \dots, x_N)

我们只需要保证 是一个足够大的整数即可，于是，当函数有最小值时，我们可以保证惩罚项为 （也就是满足约束）

而由于 与后面的惩罚项 均为多项式，于是，我们可以将其合并同类项后，写成一个类似伪布尔优化目标函数的形式：

f(x_1, \dots, x_N) = \sum_{\mathcal{S}^l \in 2^{[N]}} d_l \prod_{i \in \mathcal{S}^l} x_i

这里的 与上文中的 类似，都是项的系数

PBO 到 Ising 模型#

这一步显然是使用 QAOA 的关键，我们需要将目标函数写为 Ising 模型的格式，将其作为哈密顿量进行求解

解耦变量#

这里定义了一种解耦变量，其定义为：

\min f(x_1, \dots, x_N) = \min f(x_1, \dots, x_i = -\frac{d_l}{2|d_l|} + \frac{1}{2}, \dots, x_N)

二次化#

为了编码为 Ising 模型(方便量子退火进行求解)，我们需要对高次的多项式进行二次化，关于这一点，我们的做法为引入额外的辅助变量

于是，考虑原来的优化函数 ，我们的做法是：

1. 对于 的项 ，我们选择其中两个不相同的变量
2. 我们引入一个新的变量 ，将此项写为
3. 于是，对于新的优化函数，我们将其写为 ，也就是再新增一条等式约束的平方，与前面类似的，这里的 也是一个非常大的整数

于是，重复迭代这个过程，我们就可以得到一个完全由二次项构成的优化函数 （虽然会引入非常多的新变量）

Ising 模型#

现在我们拿到的函数为 ，这里的 指代 或 ，并且

这里，我们的问题就转化为，如何把 转化为 的形式

我们考虑引入一组新的变量 ，并构建一个新的映射 ，其中 ，于是，对于 ，我们有：

\hat{f} (x_1, \dots, x_N, y_1, \dots, y_M) \xrightarrow{\phi} \hat{f}(z_1, \dots, z_{N+M})

这里的

然而，由于 为一个二次项函数， 也必然是二次的，我们将其展开，即可写为如下形式（我们可以不用关注常数项，因为这不影响我们的优化目标）：

v(z_1, \dots, z_{N+M}) = \sum_{1 \leq i \lt j \leq N+M} w_{ij}z_iz_j + \sum_{1\leq k \leq N+M}w_kz_k

化简 Ising 模型#

在 中，如果有一些变量只存在于一个二次项中，因此我们认为这些变量存在唯一依赖关系，即：当确定了其他变量的值以最小化目标时，可以确定这些变量的值。

换而言之，这类变量的决策与否，对最小化目标函数并没有实质的贡献，因此我们可以延迟决策这些变量。

删除这类变量后，我们可以简化 Ising 模型，最终，我们将函数表示为：

\min \tilde{v}(z_{q1}, \dots, z_{qD}) = \sum_{1 \leq i \lt j \leq D}w_{ij}z_{qi}z_{qj} + \sum_{1 \leq k \leq D}w_kz_{qk}

QAOA 算法#

得到了 的表示后，我们可以很轻松的将其转变为哈密顿量 ：

H = \sum_{1 \leq i \lt j \leq D}w_{ij}\sigma^z_{qi}\sigma^z_{qj} + \sum_{1 \leq k \leq D}w_k\sigma^z_{qk}

这里的 表示 的矩阵形式（量子比特）：

\sigma^z_{qi} = I_1 \otimes \dots \otimes I_{i-1} \otimes \sigma^z \otimes I_{i+1} \otimes \dots \otimes I_D

这里的 ,

分布式 QAOA#

考虑到单台机器上的量子比特有限（如果不是模拟的话），因此，我们需要将问题拆分为多个子问题，对每个子问题使用 QAOA，这样就能在每个子问题上使用有限的量子比特了

我们已经在 #化简 Ising 模型 中将问题转化为了图上的加权集合分割问题， 现在，如果我们将图进行子图划分，并在每个子图上使用 QAOA 来进行求解，最后将所有子问题的解合并，即可得到最终解

那么如何找到一个好的划分成为了我们需要考虑的问题

这里采用的做法是：

1. 使用社区检测算法有效地将图划分为子图，并使用 QAOA 求解子图
2. 在社区表示下，迭代压缩并合并不同级别的子图
3. 使用更高级别的启发式策略来更新子图的局部解

这种分层的方法，能够为全局最优提供更良好的近似

工作流#

我们通过这个节点数为 24 的最大割问题，来讲述算法的工作流程

首先，我们需要明确，在全局中，我们存在一个 Task 队列，这里使用 来表示，其容纳的为划分出来的子图

最开始时，我们通过社区检测算法（ Louvain 算法），将原图划分为多个不重叠的社区（子图），如上面的 所示，最终，我们保证每个子图中的顶点数不超过 （量子计算机最多可容纳的量子比特数），并将所有子图 加入到任务队列 中去

接着，我们会开始分发任务（本质上就是使用 QAOA 求解子图）

首先，我们对分发到的子图 做出压缩操作，对于所有的 in-node，我们将其视为一个顶点，记作 ，此时， 与 所有 out-node 顶点之间边的权重通过下式计算：

\frac{-\tilde{v}(\neg z_i^{in} \oplus z_i^{out}) + \tilde{v}(z_i^{in} \oplus z_i^{out})}{2}

这里， 表示子图上的目标函数， 表示 in-node 和 out-node 的取值串，而 表示将其按位取反， 为拼接操作

压缩求解之后，我们将此图放到任务队列 中，并将其标记为需要被合并的图。

接着，我们需要将压缩后的图进行合并，成为新的子图，以这里的 为例，我们将 out-node 之间相连（因为这在就有边存在），成为一个新图，然后再进行 QAOA 的求解。

然后不断重复这个过程，直到 为空

这里的问题在于，我们在求解合并的子图时，假设得到了解 ，那么一定会出现如下情况：

1. 与合成此图的子图解 不同
2. 与合成此图的子图解 相同（或等于其按位取反）

第二种情况是显然的，我们不需要做任何事，因为局部解已经变为了全局解；对于第一种情况，我们需要对解进行修正。

以下图的加权最大割（不考虑点权）为例：

我们考虑在这两个子图上，对于传统的最大割方法，我们得到的解为： ，合并后得到解为

然而这显然不是最优解，我们求解完后进行压缩合并，得到的集合为：，在这个图上，QAOA 求得的最优解为：，展开为

可以发现， 与 不相同，我们的更新策略为： 更新 ，并将其与合并后得到的 拼接，以得到更好的局部解

例如这里，我们将 更新为 ，然后与 拼接，得到最终的解为

更新的算法如下图所示：