量子科技中心_量科网

参数化复杂性理论使得当某些参数较小时，能够实际解决通常难以处理的NP难问题，这使其在现实应用中特别有用。在这一框架下对字符串问题的研究尤为丰硕，产生了许多最先进的经典算法，这些算法在特定参数范围内运行效率很高，与最坏或平均情况下的表现形成鲜明对比。受基因组数据急剧增长及其日益增加的计算需求的推动，该研究团队首次开展了关于“最近字符串问题”（CSP）及其相关“最近子串问题”（CSSP）的量子参数化复杂性研究。该工作提出了三种针对CSP的量子算法和一种针对CSSP的量子算法。每种算法在特定参数范围内均展现出优于经典算法的性能，凸显了量子方法在结构化组合场景中的应用潜力。此外，研究人员还推导出二元字母表下CSP的条件性下界，表明所提出的第一个算法在其主导比例因子方面已达到最优。