量子科技中心_量科网

旅行商问题（TSP）是组合优化中经典的NP-hard问题，随着问题规模增大，确定一组城市间最短路径的计算开销会变得难以承受。该工作探索了量子计算作为解决这一复杂问题的替代方案。与现有主要依赖量子退火的方法不同，该团队提出了一种集成量子相位估计（QPE）和Grover搜索算法的量子迭代框架。路径成本被编码为量子相位，使得QPE能够高效评估它们，而通过Grover-Long算法实现的振幅放大则迭代地缩小解空间，直至找到最优路径。在一个小规模TSP实例上的概念验证案例研究证明了该方法的可行性及其扩展到更大规模优化问题的潜力。此外，在基于期望的分析下，该算法表现出预期计算复杂度为 \(O(\frac{m^2\log_2(m)\log_2(1/ε)}{\sqrtε})\)，该复杂度依赖于误差容忍参数 \(ε\)。该估计省略了初始化项，该团队预期未来的改进将使其在相位估计中成为次主导项。