版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:Univ Bristol Dept Comp Sci Bristol BS8 1UB Avon England
出 版 物:《QUANTUM INFORMATION & COMPUTATION》 (Quantum Inf. Comput.)
年 卷 期:2009年第9卷第5-6期
页 面:500-512页
核心收录:
学科分类:07[理学] 070201[理学-理论物理] 0702[理学-物理学] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:EC-FP6-STREP
主 题:Quantum algorithms shifted subsets Krawtchouk polynomials
摘 要:We consider a recently proposed generalisation of the abelian hidden subgroup problem: the shifted subset problem. The problem is to determine a subset S of some abelian group, given access to quantum states of the form (S + x), for some unknown shift x. We give quantum algorithms to find Hamming spheres and other subsets of the boolean cube {0, 1}(n). The algorithms have time complexity polynomial in n and give rise to exponential separations from classical computation.