Abstract
In this paper, based on the implementation of semiclassical quantum Fourier transform, 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 k ’s NAF representation and further find that its number of nonzero is not more than [(⌈log k⌉ + 1)/2]. 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 O(⌈logN⌉3), and our circuit requires 2 qubits more than Parker’s). However, our circuit is twice as fast as Parker’s.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput, 1997, 26: 1484–1509
Childs A M, Dam W V. Quantum algorithms for algebraic problems. Arxiv:quant-ph/0812038}0v1, 20
Fang X M, Zhu X W, Hong M, et al. Realization of quantum discrete Fourier transform with NMR. Chinese Sci Bull, 2000, 45: 1071–1075
He Y G, Sun J G. Complete quantum circuit of HAAR wavelet based MRA. Chinese Sci Bull, 2005, 50: 1796–1798
Mehring M, Müller K, Averbukh I S, et al. NMR experiment factors fumbers with Gauss sums. Phys Rev Lett, 2007, 98, 120502: 1–4
Mahesh T S, Rajendran N, Peng X H, et al. Factoring numbers with the Gauss sum technique: NMR implementations. Phys Rev A, 2007, 75, 062303: 1–4
Vedral V, Barenco A, Ekert A. Quantum networks for elementary arithemetic operations. Phys Rev A, 1996, 54: 147–153
Beckman D, Chari A N, Devabhaktuni S, et al. Efficient networks for quantum factoring. Phys Rev A, 1996, 54: 1034–1063
Zalka C. Fast versions of Shor’s quantum factoring algorithm. Arxiv: quant-ph/9806084v1, 1998
Parker S, Plenio M B. Efficient factorization with a single pure qubit and logN mixed qubits. Phys Rev Lett, 2000, 85: 3048–3052
Griffiths R B, Niu C S. Semiclassical fourier transform for quantum computation. Phys Rev Lett, 1996, 76: 3228–3232
Long G L, Xiao L. Parallel quantum computing in a single ensemble quantum computer. Phys Rev A, 2004, 69: 052303
Wang W Y, Shang B, Wang C, et al. Prime factorization in the duality computer. Commun Theor Phys, 2007, 47: 471–473
Long G L. General quantum interference principle and duality computer. Commun Theor Phys, 2006, 45: 825–844
Solinas J A. Efficient arithmetic on Koblitz curves. Designs Codes Cryptography, 2000, 19: 195–249
Author information
Authors and Affiliations
Corresponding author
About this article
Cite this article
Fu, X., Bao, W. & Zhou, C. Speeding up implementation for Shor’s factorization quantum algorithm. Chin. Sci. Bull. 55, 3648–3653 (2010). https://doi.org/10.1007/s11434-010-3039-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11434-010-3039-1