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

关键词：量子算法 最长公共子序列 量子oracle 

单位：哈尔滨工业大学计算机科学与技术学院; 黑龙江哈尔滨150001