高薪凯,倪 明,周 明,吴永政

(中国电子科技集团第三十二研究所,上海 201808)

1 概述

最大割问题(max-cutproblem)是指对给定的无向加权图求解出一个最大分割,使得顶点集的互补子集I与R之间所有割边的权值之和最大.作为图论问题中典型的组合优化问题,最大割问题被广泛应用于图像处理、网络优化,超大规模集成电路等诸多工程中,研究最大割问题的有效求解算法具有十分重要的应用价值[1].在文献[2,3]中,Khot和Ageev 证明了最大割问题是NP-Hard 问题.从理论上看,最大割问题不存在多项式时间的精确算法.因此发展出许多以损失精度为代价提高计算效率的启发式算法[4],如模拟退火算法,蚁群算法,人工神经网络等.基于量子效应的量子计算是以量子比特作为信息编码和存储的基本单元.Deutsch 等人提出在计算方面量子计算的性能要优于电子计算[5],选用合适的量子算法可使经典计算机中某些NP 问题指数级加速[6].根据量子绝热模型设计的量子绝热算法以绝热定理为基础,可对如同最大割问题、旅行商问题的布尔可满足性问题(Sat 问题)进行求解[7].量子绝热算法核心是构造一个量子绝热系统,控制系统哈密顿量从初始哈密顿量演化到目标哈密顿量,通过求解目标哈密顿量的基态间接获得待求解问题的近似解[8].

文献[9]中利用ProjectQ 编程包初步实现了量子绝热算法对最大割问题的求解程序,并通过计算顶点数为3和6的无向图的最大割问题验证了算法的可行性.但实……