计算科学 - 约束二次二元问题和量子绝热演化 - 吾爱随笔录

我正在阅读一篇标题为“通过量子绝热演化解决约束二次二元问题”的文章（参考文献 1）。有几点让我很困惑。

本文旨在解决具有以下格式的 CBQP（约束二元二次规划）。

\begin{aligned} min & x^{T} Q x \\ subject to & A x \leq b \end{aligned}

$\begin{align} &\min &x^{T}Qx \cr &\text{subject to} &Ax\leq b \end{align}$ 和，其中和。让我们将此优化问题称为问题。

x \in {0, 1}^{n}

$x\in \lbrace0,1\rbrace^{n}$

Q \in Z^{n \times n}

$Q\in Z^{n\times n}$

A \in Z^{m \times n}

$A\in Z^{m\times n}$

P

$P$

大纲是这样的。假设有一个 UBQP（无约束二元二次规划）预言机，随着 LP（线性规划）的相继应用，的拉格朗日对偶（或可以提供的下界）可以得到解决。然后用branch-bound-approach，问题就可以解决了。 $P$ $P$ $P$

在第 9 页的第 5 节计算解决方案密度之前，我几乎可以理解它。我不确定如何将分支绑定过程与优化过程相结合以最终解决这个问题。有人可以指出方向或分享一些想法吗？任何意见将不胜感激。

Ronagh, P.、Woods, B. 和 Iranmanesh, E. (2015)。通过量子绝热演化求解约束二次二元问题。arXiv 预印本：1509.05001。