| 最长公共子序列的量子算法 |
| |
| 引用本文： | 徐文旭,廖明宏.最长公共子序列的量子算法[J].电子学报,2007,35(Z2). |
| |
| 作者姓名： | 徐文旭 廖明宏 |
| |
| 作者单位： | 哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨,150001 |
| |
| 摘 要： | 本文给出了求给定两个序列最长公共子序列(Longest Common Subsequence,LCS)问题的量子算法,能在O(n)时间内求解两个长为n字符序列的最长公共子序列.算法在分析传统动态规划填表过程潜在并行性的基础上,对填表过程进行量子化,并通过带有量子存储器的量子Oracle,完成量子并行填表的计算.算法最后对前面计算获得的所有局部LCS的均匀叠加态应用Grover搜索,找出最终解,相对于经典动态规划实现了二次加速.
|
| 关 键 词： | 量子算法 最长公共子序列 量子Oracle |
Quantum Algorithm for Longest Common Subsequence |
| |
| XU Wen-xu,LIAO Ming-hong.Quantum Algorithm for Longest Common Subsequence[J].Acta Electronica Sinica,2007,35(Z2). |
| |
| Authors: | XU Wen-xu LIAO Ming-hong |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
