Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Chinese Science Bulletin

A quantum algorithm for searching a target solution of fixed weight

Xiang Wang, Wan‐Su Bao, Xiang-Qun Fu

Published Feb 1, 2011• 12 citations
Publisher

Abstract

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.

DOI
10.1007/s11434-010-4113-4

Related papers

A quantum algorithm for searching a target solution of fixed weight

Bao Wan

To search for a target n-product Boolean of fixed weight d, we propose an important method involving the notion of a fixed-weight vector accompanied with a 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.

Chinese Science Bulletin•Jan 1, 2011•0 citations

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

Xiang-Qun Fu, Wan‐Su Bao, Xiang 翔 Wang 汪 +1 more

Abstract 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-the-middle search algorithm based on the target solution of fixed weight, whose computational complexity is ∑ j = 0 d ( O ( C n - k + 1 d - j ) + O ( C k j log C k j ) ) with Σ d i =0 C k i memory cost. And the optimal value of k is given. Compared to the quantum 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.

Communications in Theoretical Physics•Oct 1, 2016•1 citation

A quantum algorithm for searching a target solution of fixed weight

Wang, ■ Xiang, Bao +3 more

在固定重量 d 的布尔向量找目标 n 产品，我们建议包含伴有一个向量标签恢复算法的一个改正重量向量标签的观点的一个重要方法。基于这些，我们在场一个新量算法设计了寻找一个改正重量目标谁的计算复杂性，明确地$ O\left ({ \sqrt {C_{ n + 1 }^ d }} \right )$ O\left ({ \sqrt {C_{ n + 1 }^ d }} \right )，对一个古典算法比那好。最后，我们使用过程作为一个例子寻找 NTRU 私人钥匙在寻找改正重量目标答案验证新算法的效率。

中国科学通报：英文版•Jan 1, 2011•0 citations

An efficient quantum meet-in-the-middle attack against NTRU-2005

Hong Wang, Zhi Ma, Chuan-gui Ma

NTRU is one of the most widely used public-key cryptosystems and its security has been an active research topic. This paper proposes a new way to find NTRU-2005 private key. The algorithm is based on meet-in-the-middle attack and a quantum algorithm for searching the fixed weight target. Compared with the current classical and quantum meet-in-the-middle attacks, our algorithm has lower time and space complexity. Moreover, this attack can also be applied against different versions of NTRU. The result can help to understand the security of NTRU better.

Chinese Science Bulletin•Oct 1, 2013•11 citations

A new algorithm for fixed point quantum search

Tathagat Tulsi, Lov K. Grover, Apoorva D. Patel

The standard quantum search lacks a feature, enjoyed by many classical algorithms, of having a fixed point, i.e. monotonic convergence towards the solution. Recently a fixed point quantum search algorithm has been discovered, referred to as the Phase-$π/3$ search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from $ε$ to $ε^{2q+1}$ using $q$ oracle queries, which has since been proved to be asymptotically optimal. A different algorithm is presented here, which has the same worst-case behavior as the Phase-$π/3$ search algorithm but much better average-case behavior. Furthermore the new algorithm gives $ε^{2q+1}$ convergence for all integral $q$, whereas the Phase-$π/3$ search algorithm requires $q$ to be $(3^{n}-1)/2$ with $n$ a positive integer. In the new algorithm, the operations are controlled by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations applied to these ancillas. It is an example of how measurement can allow us to bypass some restrictions imposed by unitarity on quantum computing.

arXiv:quant-ph/0505007•May 2, 2005•0 citations

Quantum search algorithm based on fixed weight target

Rong Liu

The current quantum search algorithms do not consider the difference of improtance among the targets.To solve this problem,this paper proposed a quantum search algorithm based on distributed weight target.It analyzed the iteration results by changing the amplitude of initial states in superposition state,and demonstrated the conditions in order to keep the quantum searching algorithm still effective with endowing the weight coefficient to target states.Based on this condition,it constructed a new quantum superposition state containing the weight information of target states,and the new algorithm kept the characters of original Grover algorithm as the same time.The simulation results show that this algorithm can search each target state successfully with the probability of endowed weight coefficient.

Jisuanji yingyong yanjiu•Jan 1, 2013•0 citations
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(Cn+1d)O\left( {\sqrt {C_{n + 1}^d } } \right)O(Cn+1d​​) , 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.
To search for a target n-product Boolean of fixed weight d, we propose an important method involving the notion of a fixed-weight vector accompanied with a 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.
Abstract 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-the-middle search algorithm based on the target solution of fixed weight, whose computational complexity is ∑ j = 0 d ( O ( C n - k + 1 d - j ) + O ( C k j log C k j ) ) with Σ d i =0 C k i memory cost. And the optimal value of k is given. Compared to the quantum 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.
在固定重量 d 的布尔向量找目标 n 产品，我们建议包含伴有一个向量标签恢复算法的一个改正重量向量标签的观点的一个重要方法。基于这些，我们在场一个新量算法设计了寻找一个改正重量目标谁的计算复杂性，明确地$ O\left ({ \sqrt {C_{ n + 1 }^ d }} \right )$ O\left ({ \sqrt {C_{ n + 1 }^ d }} \right )，对一个古典算法比那好。最后，我们使用过程作为一个例子寻找 NTRU 私人钥匙在寻找改正重量目标答案验证新算法的效率。
NTRU is one of the most widely used public-key cryptosystems and its security has been an active research topic. This paper proposes a new way to find NTRU-2005 private key. The algorithm is based on meet-in-the-middle attack and a quantum algorithm for searching the fixed weight target. Compared with the current classical and quantum meet-in-the-middle attacks, our algorithm has lower time and space complexity. Moreover, this attack can also be applied against different versions of NTRU. The result can help to understand the security of NTRU better.
The standard quantum search lacks a feature, enjoyed by many classical algorithms, of having a fixed point, i.e. monotonic convergence towards the solution. Recently a fixed point quantum search algorithm has been discovered, referred to as the Phase-π/3π/3π/3 search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from εεε to ε2q+1ε^{2q+1}ε2q+1 using qqq oracle queries, which has since been proved to be asymptotically optimal. A different algorithm is presented here, which has the same worst-case behavior as the Phase-π/3π/3π/3 search algorithm but much better average-case behavior. Furthermore the new algorithm gives ε2q+1ε^{2q+1}ε2q+1 convergence for all integral qqq, whereas the Phase-π/3π/3π/3 search algorithm requires qqq to be (3n−1)/2(3^{n}-1)/2(3n−1)/2 with nnn a positive integer. In the new algorithm, the operations are controlled by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations applied to these ancillas. It is an example of how measurement can allow us to bypass some restrictions imposed by unitarity on quantum computing.
The current quantum search algorithms do not consider the difference of improtance among the targets.To solve this problem,this paper proposed a quantum search algorithm based on distributed weight target.It analyzed the iteration results by changing the amplitude of initial states in superposition state,and demonstrated the conditions in order to keep the quantum searching algorithm still effective with endowing the weight coefficient to target states.Based on this condition,it constructed a new quantum superposition state containing the weight information of target states,and the new algorithm kept the characters of original Grover algorithm as the same time.The simulation results show that this algorithm can search each target state successfully with the probability of endowed weight coefficient.