QUANTUM ALGORITHMS FOR SHIFTED SUBSET PROBLEMS

作     者：Montanro, Ashley 

作者机构：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.