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

Bao Wan

Published Jan 1, 2011• 0 citations
OpenAlex

Abstract

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.

Related papers

A quantum algorithm for searching a target solution of fixed weight

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

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.

Chinese Science Bulletin•Feb 1, 2011•12 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

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

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

Grover quantum searching algorithm based on weighted targets

Panchi Li, Shiyong Li

The current Grover quantum searching algorithm cannot identify the difference in importance of the search targets when it is applied to an unsorted quantum database, and the probability for each search target is equal. To solve this problem, a Grover searching algorithm based on weighted targets is proposed. First, each target is endowed a weight coefficient according to its importance. Applying these different weight coefficients, the targets are represented as quantum superposition states. Second, the novel Grover searching algorithm based on the quantum superposition of the weighted targets is constructed. Using this algorithm, the probability of getting each target can be approximated to the corresponding weight coefficient, which shows the flexibility of this algorithm. Finally, the validity of the algorithm is proved by a simple searching example.

Journal of Systems Engineering and Electronics•Apr 1, 2008•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-\pi/3 search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from \epsilon to \epsilon^{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-\pi/3 search algorithm but much better average-case behavior. Furthermore the new algorithm gives \epsilon^{2q+1} convergence for all integral q, whereas the Phase-\pi/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.

Quantum Information and Computation•Sep 1, 2006•14 citations
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.
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.
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.
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 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.
The current Grover quantum searching algorithm cannot identify the difference in importance of the search targets when it is applied to an unsorted quantum database, and the probability for each search target is equal. To solve this problem, a Grover searching algorithm based on weighted targets is proposed. First, each target is endowed a weight coefficient according to its importance. Applying these different weight coefficients, the targets are represented as quantum superposition states. Second, the novel Grover searching algorithm based on the quantum superposition of the weighted targets is constructed. Using this algorithm, the probability of getting each target can be approximated to the corresponding weight coefficient, which shows the flexibility of this algorithm. Finally, the validity of the algorithm is proved by a simple searching example.
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-\pi/3 search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from \epsilon to \epsilon^{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-\pi/3 search algorithm but much better average-case behavior. Furthermore the new algorithm gives \epsilon^{2q+1} convergence for all integral q, whereas the Phase-\pi/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.