小黄人分房子遇难题啦？本源最新上线“从零学量子计算解决组合优化问题”系列课程
阿白
格鲁家的小黄人们打起来了!
阿囡
打起来了？什么情况？
阿白
听说是因为争抢食物闹矛盾了
阿囡
这可怎么办？拯救世界的任务还要靠它们呢！
阿白
格鲁为了解决这个问题，花重金给它们建了一幢相同的城堡。
阿囡
可是格鲁碰到难题了，该怎么来给小黄人分配房间？
本源量子
量子计算可以解决这个问题啊。
阿白、阿囡
咋还要用到量子计算？怎么解决的？
本源量子
可以去看看本源量子新上线的“从零学量子计算解决组合优化问题”系列课程，那里有你们要的答案。
阿白、阿囡
我们一起去看看吧！
给小黄人们分房屋涉及到了最大切割问题，你知道什么是最大切割问题吗？
最大切割问题就是给定一张无向加权图，将图的顶点分成两组，若图的某条边两个顶点位于不同的组，则称这条边满足条件，求一种分割方案，使满足条件的边的权重和最大。
对于4个小黄人的方形图
它对应的分割方案如下：
我们可以将方形图中小黄人的分屋方案全部枚举出来：
当格鲁有很多小黄人，例如1000个，10000个或者更多，我们还能通过枚举的方式来解决这个问题吗？
以目前的时间节点来看，答案是不能的。当人数超过10000后，就算把全球的计算资源都加起来，也要计算很长很长时间。
那有没有其它解决方案呢？
当然有，量子近似优化算法QAOA其实就是解决最大切割问题的恰当方案。
那什么是量子近似优化算法呢？
发表该算法的作者爱德华·法希，杰弗里·戈德斯通和山姆·古特曼等人都是现今量子计算领域有名的教授。
其中爱德华·法希和杰弗里·戈德斯通还是麻省理工学院的名誉教授。
他们在2000年的时候一起发表了绝热演化量子计算算法。在此基础上，在2014年他们又共同发表了量子近似优化算法QAOA。
量子近似优化算法(QAOA)，是一个多项式时间的近似优化算法，是用于寻找最优化问题的解决方案。
除此之外，QAOA还具有展示量子霸权的潜力。
绝热量子计算是量子计算的一种形式，它依赖于绝热定理进行计算。
首先，对于一个特定的问题，找到该问题的一个哈密顿量，该哈密顿量可能会有点复杂，但其基态描述了该问题的解决方案。
接下来，准备一个具有简单哈密顿量的系统并初始化为基态。最后，简单的哈密顿量绝热地演化为期望的复杂哈密顿量。
根据绝热定理，系统保持在基态，因此最后系统的状态描述了问题的解决方案。
绝热量子计算算法已经被证明在线路模型中与传统的量子计算是多项式等价的。
我们可以通过泡利算符来表示最大切割问题对应的哈密顿量。最大切割问题对应的哈密顿量为：
QAOA定义初始哈密顿量Hb是泡利X算符在每个量子位上的和。
该哈密顿量具有基态，该基态是泡利算子最高能量对应的特征向量(ket正)的张量积。
QAOA线路表示为以Hb为生成元的酉变换跟以Hp为生成元的酉变换乘积的累积。
其中m表示演化步数。
对于方形图，我们知道求解其最大切割问题需要使用到4个量子比特。
对于A，B，C，D这4个节点我们分别用0号比特、1号比特、2号比特和3号比特进行映射。
其对应的量子线路如下：
红色框起来的部分就是步数为1时对应的线路，当我们增加步数，相当于把红色框起来的线路重复执行了几次，只不过线路对应的参数不同。
那对于步数为m的量子线路，我们如何得到一组合适的beta和gamma参数呢？
QAOA的工作流程如下图所示
第1步.制备线路的初始状态
第2步.初始化待优化的参数β和γ，主要是用来确定RZ门和RX门的旋转角度，通常我们把参数都初始化为0
第3步.根据参数生成量子线路
第4步.测量量子状态计算每一个子项的期望
第5步.计算当前参数对应的总的期望值
第6步.将当前参数及其对应的期望值传入到经典优化器进行优化得到一组新的参数
重复执行3-6步，一直到满足预先设定好的结束条件。
通常我们把计算问题对应的哈密顿量
下面是对应的量子处理器和经典处理器的工作过程。
量子处理器里面执行量子线路，测量量子状态，随后将得到的期望值传给经典处理器。
经典处理器通过优化算法对参数进行优化。
如此循环往复，最终将会得到一组合适的参数。以该参数生成的量子线路作用在初态上，随后测量末态我们就可以高概率得到问题的解。
是不是被上面给的公式搞的晕乎乎的，本源量子最新上线了“从零学量子计算解决组合优化问题”的系列课程，每一课都会对上面涉及到的部分概念进行详细讲解，并带领你用本源量子提供的QPanda软件开发套件，一步一步实现QAOA。
下面是“从零学量子计算解决组合优化问题”系列视频之一，赶紧抢先观看吧！看看给小黄人分房屋的问题到底是怎么解决的~
附注：文章部分图片采集自网络，仅用于说明解释问题，如有问题请及时联系我们调整，谢谢！
扫码关注
“本源量子！”
听说好看的人都点了好看哦