量子科技中心_量科网

该研究团队提出了一种面向图分割问题的量子比特与逻辑门高效高阶无约束二进制优化（HUBO）编码方案，特别适用于需要最小化标签数量的场景。这类具有广泛应用前景的问题包括最小图着色、最小k割和社区检测。据该团队所知，这是首个在量子计算环境下解决此类问题优化版本的研究，而非仅停留在决策问题层面。该方案采用⌈log₂k⌉个量子比特编码每个k值顶点变量，并创新性地引入字典序惩罚机制，无需额外指示变量即可隐式最小化分区数量。研究团队推导出所有惩罚系数（包括罗森伯格二次化产生的系数）的可证明充分条件，确保最低能量解的最优性与可行性。为进行对照分析，团队还推导出独热编码的相应充分条件。研究证明，相较于独热编码每层QAOA电路Θ(|V||k|² + |E||k|)的双量子比特门数量，该对数编码方案可将门数量降至Θ(|E|·|k|⌈log₂|k|⌉)。量子退火实验表明，在最小图着色问题上，该对数编码方案相比独热编码能显著提升解的质量与求解速度，且问题规模越大优势越明显。