A quantum algorithm for searching a target solution of fixed weight

• 来源期刊: 科学通报(英文版)
• 学科: 物理学
• 关键词: 搜索目标 量子算法 重量 布尔向量 恢复算法 算法设计 经典算法 NTRU
• 年，卷（期）: 2011,（6）
• 页码范围: 484-489
• 页数: 6页
• 分类号: O413
• 语种: 中文

摘要

To search for a target n-product Boolean vector of fixed weight d, we propose an important method involving the notion of a fixed-weight "vector label" accompanied with a vector label restoration algorithm. Based on these, we present a new quantum algorithm designed to search for a fixed-weight target whose computation complexity, specifically O ((Cdn+1)1/2) , is better than that for a classical algorithm. Finally, we use the procedure to search for the NTRU private key as an example to verify the efficiency of the new algorithm in searching for fixed-weight target solutions.