本文给出了求给定两个序列最长公共子序列（Longest Common Subsequence，LCS）问题的量子算法，能在O（n）时间内求解两个长为n字符序列的最长公共子序列．算法在分析传统动态规划填表过程潜在并行性的基础上，对填表过程进行量子化，...本文给出了求给定两个序列最长公共子序列（Longest Common Subsequence，LCS）问题的量子算法，能在O（n）时间内求解两个长为n字符序列的最长公共子序列．算法在分析传统动态规划填表过程潜在并行性的基础上，对填表过程进行量子化，并通过带有量子存储器的量子Oracle，完成量子并行填表的计算．算法最后对前面计算获得的所有局部LCS的均匀叠加态应用Grover搜索，找出最终解，相对于经典动态规划实现了二次加速．展开更多
文摘本文给出了求给定两个序列最长公共子序列（Longest Common Subsequence，LCS）问题的量子算法，能在O（n）时间内求解两个长为n字符序列的最长公共子序列．算法在分析传统动态规划填表过程潜在并行性的基础上，对填表过程进行量子化，并通过带有量子存储器的量子Oracle，完成量子并行填表的计算．算法最后对前面计算获得的所有局部LCS的均匀叠加态应用Grover搜索，找出最终解，相对于经典动态规划实现了二次加速．
