量子退火算法入门（1） : QUBO是什么？

大家好，欢迎来到IT知识分享网。

量子计算机

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

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

量子退火法就是模拟退火算法的量子实现版。我们先撇开量子力学的相关知识，关注于实际问题。本篇文章专注于量子退火法的输入，输入，输入！

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

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

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

同理，下面的四次多项式，可以这么转换。（三次多项式的转换比较麻烦，以后有机会再说。）

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

量子退火法和QUBO

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

1. 把二次项的下标按照从小到大排列，比如（x2x1）→（x1x2）。
2. 把能转换的二次项转换为一次项，并写在二次项后面。

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

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

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

下一篇讲讲为什么要写成这样的形式，这样的形式怎么和物理模型对应。以及实际问题怎么转换成QUBO。

备注