General Quantum Meet-in-the-Middle Search Algorithm Based on Target Solution of Fixed Weight  

作　　者：Xiang-Qun Fu Wan-Su Bao Xiang Wang Jian-Hong Shi 付向群;鲍皖苏;汪翔;史建红(Information Engineering University;Synergetic Innovation Center of Quantum Information and Quantum Physics,University of Science and Technology of China)

机构地区：[1]Information Engineering University [2]Synergetic Innovation Center of Quantum Information and Quantum Physics,University of Science and Technology of China

出　　处：《Communications in Theoretical Physics》2016年第10期401-406,共6页理论物理通讯（英文版）

基　　金：Supported by the National Basic Research Program of China under Grant No.2013CB338002;the National Natural Science Foundation of China under Grant No.61502526

摘　　要：Similar to the classical meet-in-the-middle algorithm,the storage and computation complexity are the key factors that decide the efficiency of the quantum meet-in-the-middle algorithm.Aiming at the target vector of fixed weight,based on the quantum meet-in-the-middle algorithm,the algorithm for searching all n-product vectors with the same weight is presented,whose complexity is better than the exhaustive search algorithm.And the algorithm can reduce the storage complexity of the quantum meet-in-the-middle search algorithm.Then based on the algorithm and the knapsack vector of the Chor-Rivest public-key crypto of fixed weight d,we present a general quantum meet-in-th√e-middle search algorithm based on the target solution of fixed weight,whose computational complexity is∑(d to j=0)(O((1/2)(C^(d-j)_(n-k+1))+O(C^j_klog C^j_k))with∑(d to i=0)C^i_k memory cost.And the optimal value of k is given.Compared to thequantum meet-in-the-middle search algorithm for knapsack problem and the quantum algorithm for searching a target solution of fixed weight,the computational complexity of the algorithm is lower.And its storage complexity is smaller than the quantum meet-in-the-middle-algorithm.

关 键 词：quantum search algorithm meet-in-the-middle public-key crypto knapsack problem 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]