首页| English| 中国科学院

权重判定问题的精确量子算法

副标题:

时间:2018-01-16  来源:数学机械化重点实验室

题目:           权重判定问题的精确量子算法

报告人:      孙晓明  (中国科学院计算技术研究所)

时间地点:  2018.01.19  9:00am  N204

摘要:      The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length-n input is k or it is l. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of k, l and sufficiently large n, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of with matching upper and lower bounds, and finally we generalize to other cases via a new quantum

相关附件
相关文档