什么是QUBO模型？什么是量子退火算法？他们之间有什么关系，又该如何轻松上手？本文整理了量子退火算法科普以及新手零基础设计QUBO的详细教程，期望帮助更多感兴趣的朋友快速了解相关内容，达到可以python实战的水准。

量子退火方式可以用来解决组合优化问题，而用户只需要设计QUBO矩阵。本文将按照以下目录对量子退火和QUBO进行介绍。

目录

一、量子计算机和量子退火
       1.1 量子计算机
       1.2 模拟退火算法
       1.3 量子退火算法的物理基础
             1.3.1 量子涨落替换热涨落，提出量子退火算法
             1.3.2 绝热量子演化解决横向磁场强度缓慢变化
             1.3.3 D-Wave Systems公司实现物理量子退火机
二、量子退火和QUBO
       2.1 量子退火法能解决什么问题？
       2.2 QUBO模型设计
       2.3 Python演示模拟退火算法如何利用QUBO求解
三、有约束优化问题的QUBO
       3.1 有约束优化问题
       3.2 约束条件转换为【哈密顿算符H】
       3.3 Pyqubo：自动把二次多项式转换为QUBO
       3.4 常见条件约束对应的H
四、QUBO中三次多项式的转换
       4.1 三次多项式的例题
       4.2 Python实现

一、量子计算机和量子退火

1.1 量子计算机

量子计算机就是使用量子bit实现的计算机。之前提到过，可以分为两类，量子门(gate)方式和量子退火(annealing)方式。量子门方式的实现和现代计算机的电子逻辑门很像，比较容易理解，但是需要自己设计逻辑电路，现在开发的算法太少了，而且量子bit容易收到周围环境的影响，噪音比较多。

量子退火方式的话，只能用来解决组合优化问题，但是用户只需要设计QUBO就可以黑盒操作。但是要理解QUBO真正的硬件计算逻辑，还是需要一些物理知识的，本篇就讲一下需要的物理知识。

下面是NTT公司的量子计算指南总结的各种流派。

这个分类我觉得，量子退火机其实还是应该属于Ising machine的。因为，量子退火机解决的还是寻找Ising model的ground state的问题。当然这个分类也不是很重要，大家只要理清楚量子退火方式和Ising model的关系就好了。

用来解决组合优化问题的特殊机器，除了基于激光实现的CIM，还有以下几个：

1.基于一种叫空间光学伊辛机的特殊硬件
2.基于现代计算机电路进行物理模拟的算法（Simulated CIM，Hopfield-Tank，STATICA，Restricted Boltzmann machine）
使用量子退火机解决组合优化问题的步骤如下图所示：

1.2 模拟退火算法

想理清楚量子退火的物理模型的物理机制，我们要先理解模拟退火算法的原理。

纵轴H 代表需要最小化的Hamilton量，Si代表求解的binary变量，所以Si应该是不连续的，函数曲线不应该是一个平滑的曲线，这里为了方便说明，大家不要误解。

Si模拟退火算法中，有一个和物理温度成反比的参数β 。算法运行时，越过山峰的概率和下面👇的式子成比例。

所以，以下温度的变化过程，也被称作热涨落。

·温度越高，参数β 越小，上面👆的式子的值越大，越过山峰的概率越高；

·温度降到足够低时，越过山峰的概率就很低了，算法就找到一个谷底的最优解。

这里有一个设定，非常重要：

·温度必须降低得足够慢，降低得足够慢，降低得足够慢，模拟退火才可以可靠地获得最优解，但如果温度降低得太快，则可能会陷入局部解中。

1.3 量子退火算法的物理基础

1.3.1 量子涨落替换热涨落，提出量子退火算法

1998年在东京工业大学的門脇正史（当时在读博士课程）和西森秀稔教授（当时的指导教授）提出了使用基于薛定谔动力学的 Ising 模型作为问题哈密顿量和横向磁场作为量子涨落（fluctuation）项，来替代模拟退火中的热涨落，从而提出量子退火算法。这个研究，只是理论上的探索，当时没有太多人关注。

Tadashi Kadowaki and Hidetoshi Nishimori, "Quantum annealing in the transverse Ising model." Phys. Rev. E 58, 5355 (1998), arXiv:9804280

 

1994年发表的下面👇论文里就出现过Quantum annealing的提法。

Tadashi Kadowaki and Hidetoshi Nishimori, "Quantum annealing in the transverse Ising model." Phys. Rev. E 58, 5355 (1998), arXiv:9804280

其实，在門脇和西森之前，利用量子隧穿效应来寻找自旋玻璃模型本身的最小能态的想法，已经在下文👇里提出了。

P. Ray, B. K. Chakrabarti, and Arunava Chakrabarti, "Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations." Phys. Rev. B 39 11828

下图👇代表，量子退火算法有趣的地方时，m mm个状态，不是独自寻找最优解，它们直接互相干涉，同时去寻找最优解。

量子退火算法中，有一个和模拟退火算法中的物理温度概念相似的概念，叫横向磁场强度。

·横向磁场强度越弱，相邻S i 就会偏向于朝着不同方向，系统能量就越高，各个S i 就各自寻找自己的局部解。
·横向磁场强度越强，相邻S i 就会偏向于朝着相同方向，系统能量就越低，就越容易找到最优解。

和模拟退火算法类似，如果横向磁场强度下降太快，量子退火算法也会找不到最优解。

1.3.2 绝热量子演化解决横向磁场强度缓慢变化

绝热量子计算（AQC：adiabatic quantum computation）是由 Edward Farhi 等人在 2000 年提出的。然而，此时并没有证明通用量子计算是可能的，所做工作与解决组合优化问题的量子退火研究几乎相同。新颖之处在于，作为量子算法提出（和模拟退火无关）和使用绝热定理分析。相关论文如下：

E. Farhi, et al. "Quantum computation by adiabatic evolution." arXiv preprint quant-ph/0001106 (2000)
E. Farhi, et al. "A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem." Science 292, 5516 (2001), arXiv:quant-ph/0104129

 

绝热量子计算和量子退火的关系可以总结为：

绝热量子计算，解决了量子退火算法中的横向磁场强度缓慢变化问题。

1.3.3 实现物理量子退火机

在 2010 年左右，根据的門脇和西森的理论设计，以及Edward Farhi 等人提出绝热量子演化算法，基于超导量子bit制造出了第一台量子退火机。细节论文，如下：

M. B. Hastings, "The Power of Adiabatic Quantum Computation with No Sign Problem" arXiv:2005.03791

简单来说，量子计算机是利用“量子叠加”，“纠缠”等量子力学现象实现并行计算的计算机。传统计算机需要大量时间才能得出答案的问题，量子计算机可能会在短时间内解决，因此有望在各个领域得到应用。根据解决问题的方法，量子计算机可以大致分为量子门法（门:gate）和量子退火法（退火:annealing）两种。本文只讲解量子退火法相关的建模和计算过程。

二、量子退火和QUBO

2.1 量子退火法能解决什么问题？

量子退火法就是模拟退火算法的量子实现版。本章面对实际问题，专注于量子退火法的输入。

量子退火法都必须把问题映射成一个叫【哈密顿算符(Hamiltonian) 】的能量表达式，一般用H表示，然后求出让H值最小的变量组合。这个表达式是个二次多项式，里面的变量只能取0或1。下面举个例子。

也就是x1和x2都只能取值0或1，我们要算出来，让H最小的x1和x2的值。因为x1和x2的取值组合和对应的H值，如下表所示：

从上面的表格可以看出，(x1, x2) = (0, 1)的时候，H=0，是最小值。使用量子退火解决法，可以解决所有可以转变成二次多项式的，变量取值只能是0或1的问题。

上面的例子只有两个变量，所以很容易算出(x1, x2)的最优解，但是当有成千上万个x变量时，普通计算机就要花很久来计算，而量子退火机可以在数分钟内得出结果（计算时间依赖问题规模而定）。

那怎么把一次多项式和高次多项式转变成二次多项式呢？下面先举一个把一次多项式，转换成二次多项式的例子。

上面是这个一次多项式，因为里面的x（x1，x2，x3）只能取0或1，所以，x = x2。那么就可以转换成下面👇的二次多项式了。

同理，下面的四次多项式，可以这么转换。（三次多项式的转换比较麻烦，会在后文详细讲解。）

因为即使把H里面的【每一项都乘以整数倍】和【去除常数项】也不会影响的最小值的解。所以，下面的转化没有任何问题。这里用→表示经过整数倍或者去掉常数项的过程。

 

2.2 QUBO模型设计

上面的哈密顿算符H是个二次多项式，那么为了容易用数学描述，我们可以把他们用矩阵表示。

中间这个数字的矩阵，叫做QUBO矩阵，QUBO是（Quadratic Unconstrained Binary Optimization）的缩写，翻译成汉语就是，二次无约束二值优化。

为了和物理模型对应，我们一般会把QUBO变换以下的形式，

1.把二次项的下标按照从小到大排列，比如（x2x1）→（x1x2）。

2.把能转换的二次项转换为一次项，并写在二次项后面。

下面是个例子：

这样所有的哈密顿算符H都可以写成下面的形式了。

2.3 Python演示模拟退火算法如何利用QUBO求解

最后用python的代码看一下怎么使用QUBO求解哈密顿算符H最小值。这次使用pip install wildqat安装wildqat包，然后用模拟退火算法演示。以后用D-Wave替换就是量子退火版了。

只需获得二项式的QUBO矩阵，就可以得到让哈密顿算符H取最小值的解。

下面的二项式，化简后的到QUBO矩阵。

然后把QUBO矩阵输入到下面的程序中，就可以得到（x1, x2, x3）=（0, 1, 0）就是让y取最小值的解。

import wildqat as wq
a = wq.opt()
a.qubo = [[-3,4,-2],
		  [0,-5,6],
		  [0,0,3]]
a.sa()
>>> [0, 1, 0]

 三、有约束优化问题的QUBO

3.1 有约束优化问题

上一章讲了怎么从二次多项式获得QUBO，获得QUBO后，量子退火法就可以直接给你最优解（没有特殊说明的话，所有的变量都是0或1）。其实，实际问题一般都是有约束的，比如上章的例题加上约束条件后。

这种带约束的优化问题，我们要求出满足约束条件下的令H值最小的，（x1,x2）的组合。没有约束的情况，（x1,x2）的组合和H的取值如下表，最优解为（x1,x2）=（0,1）：

从上面的表中可以看到，因为需要满足约束条件，最优解变为（x1,x2）=（0,0）。这道例题变量比较少，可以很快找到满足约束条件的最优解。

其实，正常有约束的优化问题会变换成下面的形式，然后求解。

其中惩罚函数g()就是从约束条件获得。怎么把约束条件转化为惩罚函数呢？答案就是，把约束条件转化为对应的**【哈密顿算符(Hamiltonian) 】**

3.2 约束条件转换为【哈密顿算符H】

我们可以这么想，如果有一个二次多项式，让它取最小值的解，刚好是某个【哈密顿算符H】的最小值（H=0）的解。以上面的约束条件为例：

那么满足约束条件的（x1, x2）有[ (0, 0), (1, 0), (1, 1) ]三个组合。逆向思维，这三个组合会是哪个【哈密顿算符H】的最小值的解呢？有兴趣的读者可以自己想一想，这里我直接给出答案。

上面H=0的解，就是满足约束条件的，（x1, x2）=[ (0, 0), (1, 0), (1, 1) ]。对应的QUBO矩阵就是。

这时候带有惩罚函数项的新的H变为：

很多读者到这里，就会有疑问，每次都要把二次多项式写成QUBO矩阵的话，很麻烦。能不能直接输入二项式呢？答案是，可以的。

3.3 Pyqubo：自动把二次多项式转换为QUBO

# neal是模拟退火的库 
import neal 
# pyqubo 可以使用Binary定义变量，Constarint定义约束
from pyqubo import Binary, Constraint 
x1, x2 = Binary('x1'), Binary('x2')

# M是约束强度
M = 5.0 
#定义哈密顿算符H
H = 3 * x1**2 - 2 * x2**2 + M * Constraint((x2 - x1*x2), label='x1>=x2') 
model = H.compile()

# 无视offset就行了，QUBO用来做模拟退火的输入
qubo, offset = model.to_qubo() 
sampler = neal.SimulatedAnnealingSampler()
raw_solution = sampler.sample_qubo(qubo)

raw_solution.first.sample
>>> {'x1': 0, 'x2': 0}

我们可以看到，最后的结果是（x1, x2）=（0, 0）。确实是最优解。但是M值（就是前面公式里的λ）如果太小，可能得不到最优解。

3.4 常见条件约束对应的H

前任栽树，后人乘凉，常见的约束条件对应的H如下表所示：

四、QUBO中三次多项式的转换

本章还是大部分截图来自于：《最適化問題とWildqatを用いた量子アニーリング計算入門》 https://booth.pm/ja/items/1415833

 

关于怎么将QUBO中的三次多项式转换为二次多项式，这里以一个例题开始讲解。

4.1 三次多项式的例题

 

 

 

下面讲解如何导出对应的QUBO矩阵。

 

Step1. 变量替换。

 

首先，把两个变量的乘积用一个变量替代，这里用x 4 替代x 2 x 3 

 

因为我们使用了上面的变量替换，所以我们要满足以下约束：

 

Step2. 加入约束项。

 

上面的约束对应的约束项H ′ 

 

 如下👇，由x 2 , x 3 , x 4能构成的二次多项式构成。

 

这里补充一句，在本系列第二篇中，直接给大家列出了常见约束的H表达式，这次我们需要手动推导。大家从头到尾，要谨记一句话：

 

【我们最终的目标是令目标H 最小化的同时，满足约束。所以，约束H ′ 代入令目标H HH最小化的变量x 2 , x 3 , x 4 具体值时，也是最小化的。】

 

于是，接下来所有的变换都是为了寻找H ′的适当的系数（a, b, c, d, e, f）。本系列第二篇中每个常见约束的求解，都经历了寻找对应系数的过程。

 

Step3. 寻找合适的约束项系数。

 

我们可以这么想，通过合适的系数（a, b, c, d, e, f），使得x 2 , x 3 , x 4 满足式(2)时，令H ′ = 0 ；不满足式(2)时，H ′ > 0 。那就这么约定了。

 

这时，上表中的x 2 , x 3 , x 4  按行代入式(4)后，对应的只包含系数（a, b, c, d, e, f）的等式如下：

 

当x 2 x 3 ≠ x 4 时，如我们约定好的，令H ′ > 0，整理入下表：

 

Step4. 获得确定系数的约束项H ′ 

把已经确定的（a, b, c, d, e, f）和（ k 1 , k 2 , k 3 , k 4 ） 代入式(4)就行了。得到最终的H ′如下：

Step5. 获得最终的二次多项式H 。

这里就不必多说了，别忘了还有个 λ  系数，需要手动指定。

我们把 λ  =1，代入上式，得到下面最终的QUBO矩阵。

4.2 Python实现

引入库

import wildqat as wq
import numpy as np

H_A = np.array([
	[1,0,0,-1],
	[0,0,0,0],
	[0,0,0,0],
	[0,0,0,0]])
H_A = np.array([
	[0,0,0,0],
	[0,0,1,-2],
	[0,0,0,-2],
	[0,0,0,3]])
k, l = 1, 1

a = wq.opt()
a.qubo = k * H_A + l * H_B

for i in range(5):
	print("x = {}".format(a.sa()))
	print("H = {}".format(a.E(-1)))

 

结果打印如下，有兴趣的可以看看，取值是否满足约束。

还是挺麻烦的，不过不难理解，是可以写程序自动化的，这也是为什么我们需要pyqubo这中自动化转换QUBO的程序。

 

本文介绍了什么是QUBO，如何设计QUBO，下一篇讲些经典的组合优化问题的建模与python实战：量子退火算法（2）。

 

---

本文改编转载自CSDN博主：gang_unerry

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/gangshen1993/article/details/123235957

什么是QUBO模型？什么是量子退火算法？他们之间有什么关系，又该如何轻松上手？本文整理了量子退火算法科普以及新手零基础设计QUBO的详细教程，期望帮助更多感兴趣的朋友快速了解相关内容，达到可以python实战的水准。

量子退火方式可以用来解决组合优化问题，而用户只需要设计QUBO矩阵。本文将按照以下目录对量子退火和QUBO进行介绍。

目录

一、量子计算机和量子退火
       1.1 量子计算机
       1.2 模拟退火算法
       1.3 量子退火算法的物理基础
             1.3.1 量子涨落替换热涨落，提出量子退火算法
             1.3.2 绝热量子演化解决横向磁场强度缓慢变化
             1.3.3 D-Wave Systems公司实现物理量子退火机
二、量子退火和QUBO
       2.1 量子退火法能解决什么问题？
       2.2 QUBO模型设计
       2.3 Python演示模拟退火算法如何利用QUBO求解
三、有约束优化问题的QUBO
       3.1 有约束优化问题
       3.2 约束条件转换为【哈密顿算符H】
       3.3 Pyqubo：自动把二次多项式转换为QUBO
       3.4 常见条件约束对应的H
四、QUBO中三次多项式的转换
       4.1 三次多项式的例题
       4.2 Python实现

一、量子计算机和量子退火

1.1 量子计算机

量子计算机就是使用量子bit实现的计算机。之前提到过，可以分为两类，量子门(gate)方式和量子退火(annealing)方式。量子门方式的实现和现代计算机的电子逻辑门很像，比较容易理解，但是需要自己设计逻辑电路，现在开发的算法太少了，而且量子bit容易收到周围环境的影响，噪音比较多。

量子退火方式的话，只能用来解决组合优化问题，但是用户只需要设计QUBO就可以黑盒操作。但是要理解QUBO真正的硬件计算逻辑，还是需要一些物理知识的，本篇就讲一下需要的物理知识。

下面是NTT公司的量子计算指南总结的各种流派。

这个分类我觉得，量子退火机其实还是应该属于Ising machine的。因为，量子退火机解决的还是寻找Ising model的ground state的问题。当然这个分类也不是很重要，大家只要理清楚量子退火方式和Ising model的关系就好了。

用来解决组合优化问题的特殊机器，除了基于激光实现的CIM，还有以下几个：

1.基于一种叫空间光学伊辛机的特殊硬件
2.基于现代计算机电路进行物理模拟的算法（Simulated CIM，Hopfield-Tank，STATICA，Restricted Boltzmann machine）
使用量子退火机解决组合优化问题的步骤如下图所示：

1.2 模拟退火算法

想理清楚量子退火的物理模型的物理机制，我们要先理解模拟退火算法的原理。

纵轴H 代表需要最小化的Hamilton量，Si代表求解的binary变量，所以Si应该是不连续的，函数曲线不应该是一个平滑的曲线，这里为了方便说明，大家不要误解。

Si模拟退火算法中，有一个和物理温度成反比的参数β 。算法运行时，越过山峰的概率和下面👇的式子成比例。

所以，以下温度的变化过程，也被称作热涨落。

·温度越高，参数β 越小，上面👆的式子的值越大，越过山峰的概率越高；

·温度降到足够低时，越过山峰的概率就很低了，算法就找到一个谷底的最优解。

这里有一个设定，非常重要：

·温度必须降低得足够慢，降低得足够慢，降低得足够慢，模拟退火才可以可靠地获得最优解，但如果温度降低得太快，则可能会陷入局部解中。

1.3 量子退火算法的物理基础

1.3.1 量子涨落替换热涨落，提出量子退火算法

1998年在东京工业大学的門脇正史（当时在读博士课程）和西森秀稔教授（当时的指导教授）提出了使用基于薛定谔动力学的 Ising 模型作为问题哈密顿量和横向磁场作为量子涨落（fluctuation）项，来替代模拟退火中的热涨落，从而提出量子退火算法。这个研究，只是理论上的探索，当时没有太多人关注。

Tadashi Kadowaki and Hidetoshi Nishimori, "Quantum annealing in the transverse Ising model." Phys. Rev. E 58, 5355 (1998), arXiv:9804280

 

1994年发表的下面👇论文里就出现过Quantum annealing的提法。

Tadashi Kadowaki and Hidetoshi Nishimori, "Quantum annealing in the transverse Ising model." Phys. Rev. E 58, 5355 (1998), arXiv:9804280

其实，在門脇和西森之前，利用量子隧穿效应来寻找自旋玻璃模型本身的最小能态的想法，已经在下文👇里提出了。

P. Ray, B. K. Chakrabarti, and Arunava Chakrabarti, "Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations." Phys. Rev. B 39 11828

下图👇代表，量子退火算法有趣的地方时，m mm个状态，不是独自寻找最优解，它们直接互相干涉，同时去寻找最优解。

量子退火算法中，有一个和模拟退火算法中的物理温度概念相似的概念，叫横向磁场强度。

·横向磁场强度越弱，相邻S i 就会偏向于朝着不同方向，系统能量就越高，各个S i 就各自寻找自己的局部解。
·横向磁场强度越强，相邻S i 就会偏向于朝着相同方向，系统能量就越低，就越容易找到最优解。

和模拟退火算法类似，如果横向磁场强度下降太快，量子退火算法也会找不到最优解。

1.3.2 绝热量子演化解决横向磁场强度缓慢变化

绝热量子计算（AQC：adiabatic quantum computation）是由 Edward Farhi 等人在 2000 年提出的。然而，此时并没有证明通用量子计算是可能的，所做工作与解决组合优化问题的量子退火研究几乎相同。新颖之处在于，作为量子算法提出（和模拟退火无关）和使用绝热定理分析。相关论文如下：

E. Farhi, et al. "Quantum computation by adiabatic evolution." arXiv preprint quant-ph/0001106 (2000)
E. Farhi, et al. "A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem." Science 292, 5516 (2001), arXiv:quant-ph/0104129

 

绝热量子计算和量子退火的关系可以总结为：

绝热量子计算，解决了量子退火算法中的横向磁场强度缓慢变化问题。

1.3.3 实现物理量子退火机

在 2010 年左右，根据的門脇和西森的理论设计，以及Edward Farhi 等人提出绝热量子演化算法，基于超导量子bit制造出了第一台量子退火机。细节论文，如下：

M. B. Hastings, "The Power of Adiabatic Quantum Computation with No Sign Problem" arXiv:2005.03791

简单来说，量子计算机是利用“量子叠加”，“纠缠”等量子力学现象实现并行计算的计算机。传统计算机需要大量时间才能得出答案的问题，量子计算机可能会在短时间内解决，因此有望在各个领域得到应用。根据解决问题的方法，量子计算机可以大致分为量子门法（门:gate）和量子退火法（退火:annealing）两种。本文只讲解量子退火法相关的建模和计算过程。

二、量子退火和QUBO

2.1 量子退火法能解决什么问题？

量子退火法就是模拟退火算法的量子实现版。本章面对实际问题，专注于量子退火法的输入。

量子退火法都必须把问题映射成一个叫【哈密顿算符(Hamiltonian) 】的能量表达式，一般用H表示，然后求出让H值最小的变量组合。这个表达式是个二次多项式，里面的变量只能取0或1。下面举个例子。

也就是x1和x2都只能取值0或1，我们要算出来，让H最小的x1和x2的值。因为x1和x2的取值组合和对应的H值，如下表所示：

从上面的表格可以看出，(x1, x2) = (0, 1)的时候，H=0，是最小值。使用量子退火解决法，可以解决所有可以转变成二次多项式的，变量取值只能是0或1的问题。

上面的例子只有两个变量，所以很容易算出(x1, x2)的最优解，但是当有成千上万个x变量时，普通计算机就要花很久来计算，而量子退火机可以在数分钟内得出结果（计算时间依赖问题规模而定）。

那怎么把一次多项式和高次多项式转变成二次多项式呢？下面先举一个把一次多项式，转换成二次多项式的例子。

上面是这个一次多项式，因为里面的x（x1，x2，x3）只能取0或1，所以，x = x2。那么就可以转换成下面👇的二次多项式了。

同理，下面的四次多项式，可以这么转换。（三次多项式的转换比较麻烦，会在后文详细讲解。）

因为即使把H里面的【每一项都乘以整数倍】和【去除常数项】也不会影响的最小值的解。所以，下面的转化没有任何问题。这里用→表示经过整数倍或者去掉常数项的过程。

 

2.2 QUBO模型设计

上面的哈密顿算符H是个二次多项式，那么为了容易用数学描述，我们可以把他们用矩阵表示。

中间这个数字的矩阵，叫做QUBO矩阵，QUBO是（Quadratic Unconstrained Binary Optimization）的缩写，翻译成汉语就是，二次无约束二值优化。

为了和物理模型对应，我们一般会把QUBO变换以下的形式，

1.把二次项的下标按照从小到大排列，比如（x2x1）→（x1x2）。

2.把能转换的二次项转换为一次项，并写在二次项后面。

下面是个例子：

这样所有的哈密顿算符H都可以写成下面的形式了。

2.3 Python演示模拟退火算法如何利用QUBO求解

最后用python的代码看一下怎么使用QUBO求解哈密顿算符H最小值。这次使用pip install wildqat安装wildqat包，然后用模拟退火算法演示。以后用D-Wave替换就是量子退火版了。

只需获得二项式的QUBO矩阵，就可以得到让哈密顿算符H取最小值的解。

下面的二项式，化简后的到QUBO矩阵。

然后把QUBO矩阵输入到下面的程序中，就可以得到（x1, x2, x3）=（0, 1, 0）就是让y取最小值的解。

import wildqat as wq
a = wq.opt()
a.qubo = [[-3,4,-2],
		  [0,-5,6],
		  [0,0,3]]
a.sa()
>>> [0, 1, 0]

 三、有约束优化问题的QUBO

3.1 有约束优化问题

上一章讲了怎么从二次多项式获得QUBO，获得QUBO后，量子退火法就可以直接给你最优解（没有特殊说明的话，所有的变量都是0或1）。其实，实际问题一般都是有约束的，比如上章的例题加上约束条件后。

这种带约束的优化问题，我们要求出满足约束条件下的令H值最小的，（x1,x2）的组合。没有约束的情况，（x1,x2）的组合和H的取值如下表，最优解为（x1,x2）=（0,1）：

从上面的表中可以看到，因为需要满足约束条件，最优解变为（x1,x2）=（0,0）。这道例题变量比较少，可以很快找到满足约束条件的最优解。

其实，正常有约束的优化问题会变换成下面的形式，然后求解。

其中惩罚函数g()就是从约束条件获得。怎么把约束条件转化为惩罚函数呢？答案就是，把约束条件转化为对应的**【哈密顿算符(Hamiltonian) 】**

3.2 约束条件转换为【哈密顿算符H】

我们可以这么想，如果有一个二次多项式，让它取最小值的解，刚好是某个【哈密顿算符H】的最小值（H=0）的解。以上面的约束条件为例：

那么满足约束条件的（x1, x2）有[ (0, 0), (1, 0), (1, 1) ]三个组合。逆向思维，这三个组合会是哪个【哈密顿算符H】的最小值的解呢？有兴趣的读者可以自己想一想，这里我直接给出答案。

上面H=0的解，就是满足约束条件的，（x1, x2）=[ (0, 0), (1, 0), (1, 1) ]。对应的QUBO矩阵就是。

这时候带有惩罚函数项的新的H变为：

很多读者到这里，就会有疑问，每次都要把二次多项式写成QUBO矩阵的话，很麻烦。能不能直接输入二项式呢？答案是，可以的。

3.3 Pyqubo：自动把二次多项式转换为QUBO

# neal是模拟退火的库 
import neal 
# pyqubo 可以使用Binary定义变量，Constarint定义约束
from pyqubo import Binary, Constraint 
x1, x2 = Binary('x1'), Binary('x2')

# M是约束强度
M = 5.0 
#定义哈密顿算符H
H = 3 * x1**2 - 2 * x2**2 + M * Constraint((x2 - x1*x2), label='x1>=x2') 
model = H.compile()

# 无视offset就行了，QUBO用来做模拟退火的输入
qubo, offset = model.to_qubo() 
sampler = neal.SimulatedAnnealingSampler()
raw_solution = sampler.sample_qubo(qubo)

raw_solution.first.sample
>>> {'x1': 0, 'x2': 0}

我们可以看到，最后的结果是（x1, x2）=（0, 0）。确实是最优解。但是M值（就是前面公式里的λ）如果太小，可能得不到最优解。

3.4 常见条件约束对应的H

前任栽树，后人乘凉，常见的约束条件对应的H如下表所示：

四、QUBO中三次多项式的转换

本章还是大部分截图来自于：《最適化問題とWildqatを用いた量子アニーリング計算入門》 https://booth.pm/ja/items/1415833

 

关于怎么将QUBO中的三次多项式转换为二次多项式，这里以一个例题开始讲解。

4.1 三次多项式的例题

 

 

 

下面讲解如何导出对应的QUBO矩阵。

 

Step1. 变量替换。

 

首先，把两个变量的乘积用一个变量替代，这里用x 4 替代x 2 x 3 

 

因为我们使用了上面的变量替换，所以我们要满足以下约束：

 

Step2. 加入约束项。

 

上面的约束对应的约束项H ′ 

 

 如下👇，由x 2 , x 3 , x 4能构成的二次多项式构成。

 

这里补充一句，在本系列第二篇中，直接给大家列出了常见约束的H表达式，这次我们需要手动推导。大家从头到尾，要谨记一句话：

 

【我们最终的目标是令目标H 最小化的同时，满足约束。所以，约束H ′ 代入令目标H HH最小化的变量x 2 , x 3 , x 4 具体值时，也是最小化的。】

 

于是，接下来所有的变换都是为了寻找H ′的适当的系数（a, b, c, d, e, f）。本系列第二篇中每个常见约束的求解，都经历了寻找对应系数的过程。

 

Step3. 寻找合适的约束项系数。

 

我们可以这么想，通过合适的系数（a, b, c, d, e, f），使得x 2 , x 3 , x 4 满足式(2)时，令H ′ = 0 ；不满足式(2)时，H ′ > 0 。那就这么约定了。

 

这时，上表中的x 2 , x 3 , x 4  按行代入式(4)后，对应的只包含系数（a, b, c, d, e, f）的等式如下：

 

当x 2 x 3 ≠ x 4 时，如我们约定好的，令H ′ > 0，整理入下表：

 

Step4. 获得确定系数的约束项H ′ 

把已经确定的（a, b, c, d, e, f）和（ k 1 , k 2 , k 3 , k 4 ） 代入式(4)就行了。得到最终的H ′如下：

Step5. 获得最终的二次多项式H 。

这里就不必多说了，别忘了还有个 λ  系数，需要手动指定。

我们把 λ  =1，代入上式，得到下面最终的QUBO矩阵。

4.2 Python实现

引入库

import wildqat as wq
import numpy as np

H_A = np.array([
	[1,0,0,-1],
	[0,0,0,0],
	[0,0,0,0],
	[0,0,0,0]])
H_A = np.array([
	[0,0,0,0],
	[0,0,1,-2],
	[0,0,0,-2],
	[0,0,0,3]])
k, l = 1, 1

a = wq.opt()
a.qubo = k * H_A + l * H_B

for i in range(5):
	print("x = {}".format(a.sa()))
	print("H = {}".format(a.E(-1)))

 

结果打印如下，有兴趣的可以看看，取值是否满足约束。

还是挺麻烦的，不过不难理解，是可以写程序自动化的，这也是为什么我们需要pyqubo这中自动化转换QUBO的程序。

 

本文介绍了什么是QUBO，如何设计QUBO，下一篇讲些经典的组合优化问题的建模与python实战：量子退火算法（2）。

 

---

本文改编转载自CSDN博主：gang_unerry

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/gangshen1993/article/details/123235957