量子计算机
量子计算机是利用“量子叠加”,“纠缠”等量子力学现象实现并行计算的计算机。传统计算机需要大量时间才能得出答案的问题,量子计算机可能会在短时间内解决,因此有望在各个领域得到应用。根据解决问题的方法,量子计算机可以大致分为量子门法(门: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 = x2。那么就可以转换成下面👇的二次多项式了。
同理,下面的四次多项式,可以这么转换。(三次多项式的转换比较麻烦,以后有机会再说。)
因为即使把H里面的【每一项都乘以整数倍】和【去除常数项】也不会影响的最小值的解。所以,下面的转化没有任何问题。这里用→表示经过整数倍或者去掉常数项的过程。
量子退火法和QUBO
上面的哈密顿算符H是个二次多项式,那么为了容易用数学描述,我们可以把他们用矩阵表示。
中间这个数字的矩阵,叫做QUBO矩阵,QUBO是(Quadratic Unconstrained Binary Optimization)的缩写,翻译成汉语就是,二次无约束二值优化。
为了和物理模型对应,我们一般会把QUBO变换以下的形式,
1.把二次项的下标按照从小到大排列,比如(x2x1)→(x1x2)。
2.把能转换的二次项转换为一次项,并写在二次项后面。
下面是个例子:
这样所有的哈密顿算符H都可以写成下面的形式了。
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。
————————————————
本文转载自CSDN博主:gang_unerry
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/gangshen1993/article/details/123235957