A quantum algorithm for searching a target solution of fixed weight
Xiang Wang, Wan‐Su Bao, Xiang-Qun Fu · Chinese Science Bulletin · 2011
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\left( {\sqrt {C_{n + 1}^d } } \right) $$ , 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.