Research On The Quantum Algorithms With High Probability

The presentation of Shor's quantum algorithm, which makes factorization and discrete logarithm problem can be solved in polynomial time, shows the powerful ability of quantum computer in parallel computation. Quantum computation brings huge impact to the security of modern cipher, especially for the public-key crypto. This paper does research on the following two aspects. One is the quantum algorithm with high probability, and the other is speeding up the implementation for quantum circuit. Our contributions mainly include three parts as follows:1. Research on the quantum algorithm for factorization with high probability. Based on the quantum Fourier transform, we give a new quantum algorithm for prime factorization. The algorithm turns to be phase factor under repeated application of Fourier transform and variate transformation, where is the order of a selective element in the ring of integers modulo. Furthermore the amplitude of the non-target states except zero state is modified to be 0. Our algorithm's success probability, which is more than 3/4 and higher than Shor's algorithm, doesn't depend on the size of other than Shor's algorithm. Meanwhile, we present a comparison of the required resource between the new algorithm and Shor's algorithm. rrNr2. Research on the speeding up implementation for Shor's factorization quantum algorithm. Considering the semiclassical quantum Fourier transform's input is bit flipping, we first propose the concept of generation vector of ternary binary representation, construct the generation function's truth table, prove that the generation vector of ternary binary representation is one kind of's NAF representation and further find that its number of nonzero is not more than k()log12k?+?????. Because the input of obtaining this representation is bit flipping from low-order to high-order which is opposite to the semiclassical quantum Fourier transfom. We present another semiclassical quantum Fourier transfom. Then we redesign a quantum circuit for Shor's algorithm, whose computation resource is approximately equal to that of Parker (Their requirements of elementary quantum gate are both ()3logON???? and our circuit requires 3 qubits more than Parker's). However, our circuit is twice as fast as Parker's.3. Polynomial-time quantum algorithm for Chor-Rivest knapsack public-key encryption. In this paper, we present a polynomial-time quantum algorithm for Chor-Rivest knapsack public-key encryption. Under variate transformation and repeated application of Fourier transform, our algorithm can enable the amplitude of non-target state except the zero state to be 0. The relation between measured value and (M0, M1,…, Mp-1) is depicted. And we give the exact formula between the algorithm's success probability and the public key parameter (p,h). The algorithm's success probability after one run is close to 1, its complexity is O(P3) and it needs (p+2)([logr] +1) qubits and O((P+1)r) elementary quantum gate.