电子学报
電子學報
전자학보
ACTA ELECTRONICA SINICA
2007年
z2期
99-103
,共5页
量子算法%最长公共子序列%量子Oracle
量子算法%最長公共子序列%量子Oracle
양자산법%최장공공자서렬%양자Oracle
本文给出了求给定两个序列最长公共子序列(Longest Common Subsequence,LCS)问题的量子算法,能在O(n)时间内求解两个长为n字符序列的最长公共子序列.算法在分析传统动态规划填表过程潜在并行性的基础上,对填表过程进行量子化,并通过带有量子存储器的量子Oracle,完成量子并行填表的计算.算法最后对前面计算获得的所有局部LCS的均匀叠加态应用Grover搜索,找出最终解,相对于经典动态规划实现了二次加速.
本文給齣瞭求給定兩箇序列最長公共子序列(Longest Common Subsequence,LCS)問題的量子算法,能在O(n)時間內求解兩箇長為n字符序列的最長公共子序列.算法在分析傳統動態規劃填錶過程潛在併行性的基礎上,對填錶過程進行量子化,併通過帶有量子存儲器的量子Oracle,完成量子併行填錶的計算.算法最後對前麵計算穫得的所有跼部LCS的均勻疊加態應用Grover搜索,找齣最終解,相對于經典動態規劃實現瞭二次加速.
본문급출료구급정량개서렬최장공공자서렬(Longest Common Subsequence,LCS)문제적양자산법,능재O(n)시간내구해량개장위n자부서렬적최장공공자서렬.산법재분석전통동태규화전표과정잠재병행성적기출상,대전표과정진행양자화,병통과대유양자존저기적양자Oracle,완성양자병행전표적계산.산법최후대전면계산획득적소유국부LCS적균균첩가태응용Grover수색,조출최종해,상대우경전동태규화실현료이차가속.
