量子科技中心_量科网

量子k-SAT问题是k-SAT问题在量子领域的推广。核心在于判断给定局部哈密顿量是否属于“无阻挫”系统——即该k-局部哈密顿量的基态能否同时最小化所有局部相互作用项的能量。这一问题是量子物理的核心课题，也是典型的QMA1完全问题。相较于经典k-SAT问题，量子k-SAT在特殊可解案例、近似算法和参数化复杂度方面的研究尚未充分展开。 本论文将从图论角度研究量子k-SAT问题，重点关注超图结构中的“核心”与“半径”特性。这些超图结构对求解量子k-SAT问题至关重要。当衍生超图满足：核心规模为n−m+a（其中a为常数），且半径不超过对数级时，研究人员可在多项式时间内求解量子k-SAT实例。若存在此类核心，该团队还可在多项式时间内找到半径最优的n−m+a规模核心；而寻找具有最小半径的通用最小核心则属于NP难问题。