一种基于量子计算近似求解旅行商问题的方法和系统

本发明公开了一种基于量子计算近似求解旅行商问题的方法和系统，该方法包括：获取无向完全加权图G；对图G进行划分，以将其划分为多个子图，每个子图中的节点数量小于等于阈值；确定每个子图的连接顺序以及相邻子图之间的连接边；将相邻子图之间的连接边的两个端点分别作为相邻子图中的起点和终点，利用量子最优路径搜索算法寻找每个子图中的最短哈密顿路径；将子图的连接顺序和所有子图的最短哈密顿路径进行整合，得到关于整张图G的哈密顿回路，即旅行商问题的最终解。本发明摆脱了量子硬件设备对问题规模的约束，大幅度减少所需量子资源，能够利用现有的量子计算机求解大规模的旅行商问题，提高了求解的稳定性和近似比。