最长公共子序列的量子算法

• 作者: 廖明宏 徐文旭
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 量子算法 最长公共子序列 量子Oracle
• 年，卷（期）: 2007,（z2）
• 页码范围: 99-103
• 分类号: TP301.6
• 字数: 6049字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	廖明宏	哈尔滨工业大学计算机科学与技术学院	48	708	14.0	25.0
2	徐文旭	哈尔滨工业大学计算机科学与技术学院	3	12	2.0	3.0