量子退火算法入门(1):QUBO是什么?

薛定谔了么
2024-11-08 10:52:39

量子计算机

量子计算机是利用“量子叠加”,“纠缠”等量子力学现象实现并行计算的计算机。传统计算机需要大量时间才能得出答案的问题,量子计算机可能会在短时间内解决,因此有望在各个领域得到应用。根据解决问题的方法,量子计算机可以大致分为量子门法(门: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

67
0
0
0
关于作者
相关文章
  • 量子退火算法入门(7):QUBO中的三次多项式怎么转换? ...
    前言本文还是大部分截图来自于:《最適化問題とWildqatを用いた量子アニーリング計算入門》 http ...
    了解详情 
  • 量子退火算法入门(6):初识量子退火算法的发明过程 ...
    一、量子计算机量子计算机就是使用量子bit实现的计算机。之前提到过,可以分为两类,量子门(gate ...
    了解详情 
  • 量子退火算法入门(5):旅行商问题的QUBO建模「下篇之Python实现」 ...
    一,旅行商问题QUBO的两种实现看过上篇的读者应该已经注意到,因为旅行商问题需要最终返回到初始 ...
    了解详情 
  • 量子退火算法入门(4):旅行商问题的QUBO建模「上 篇」 ...
    了解详情 
  • 量子退火算法入门(3):整数分割问题的QUBO建模
    整数分割问题:QUBO建模最重要的就是,把建模对象中的变量映射为binary(0/1 或者 -1/+1)的变量 ...
    了解详情 
在本版发帖返回顶部
快速回复 返回顶部 返回列表