量子科技中心_量科网

旅行商问题(TSP)是一个重要的经典NP难组合优化问题。该研究工作表明，在文献 [1]作者优秀工作的基础上，将经典动态规划与量子搜索相结合，可以为TSP带来可实现的量子优势。该团队设计了量子分治策略，并为此种结合提供了一个参数化谱系。文献 [1]中提出的混合算法对应于该谱系中的一个特定情况，而谱系的两个极端则分别代表纯经典的Held-Karp算法和纯量子搜索算法。在该团队的参数化谱系内，该研究证明了最优查询复杂度为\(O^*(1.865666\ldots^n)\)，通过4-子集方案实现，而文献 [1]中的计数忽略了半数递归分支。其算法在所选参数(\(α\approx0.055362\))下的正确查询复杂度为\(O^*(2.225880\ldots^n)\)，并且对于任何\(α\)都不能低于\(O^*(2^n)\)——这意味着，经过正确分析后，其8-子集方案从未超越经典Held-Karp界限。此外，在以往关于NP难组合优化问题量子优势的研究中，研究人员仅关注查询复杂度的提升。然而，该团队的工作指出，量子优势不仅源于量子搜索的二次加速，还源于结构化的量子态制备。该团队认为，结构化态制备对于实现预言算子，同时维持\(O^*(1.865666\ldots^n)\)的总时间复杂度是不可或缺的。因此，该团队设计了一种优雅的集合划分态制备方法，使得该团队的TSP求解器具有实际可执行性。