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

量子计算机

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

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

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

量子退火法都必须把问题映射成一个叫【哈密顿算符(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 = x²。那么就可以转换成下面声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】