量子科技中心_量科网

最大团问题（MCP）旨在寻找无向图中的最大完全子图，即该子图中任意两个不同顶点间均存在边连接。作为NP难问题，其在生物信息学、社交网络、数据挖掘等领域具有广泛应用。本研究提出一种改进算法：通过量子线路预检测将顶点数量的先验约束（源自Turán定理和完全图性质）编码为全局变量，动态追踪最大团规模，并进一步与Grover搜索协同优化解空间。本工作的辅助量子比特编码方案能在量子搜索过程中动态追踪团规模，消除迭代测量需求，仅需Ο(2ⁿ)次Grover迭代和Ο(1)次测量即可求解MCP问题。相较于目前最先进的基于Grover的方法——其求解n顶点图需要Ο(n2ⁿ)次迭代和Ο(n)次测量——本方案实现了n倍的性能提升。研究团队通过IBM Qiskit平台的仿真验证了算法正确性，并就量子比特/门效率与现有基于Grover的MCP求解器进行了基准测试。