SCIENCE CHINA Information Sciences, Volume 59 , Issue 4 : 042406(2016) https://doi.org/10.1007/s11432-015-5411-x

Improved quantum ripple-carry addition circuit

More info
  • ReceivedJun 23, 2015
  • AcceptedJul 9, 2015
  • PublishedFeb 19, 2016


A serious obstacle to large-scale quantum algorithms is the large number of elementary gates, such as the controlled-NOT gate or Toffoli gate. Herein, we present an improved linear-depth ripple-carry quantum addition circuit, which is an elementary circuit used for quantum computations. Compared with previous addition circuits costing at least two Toffoli gates for each bit of output, the proposed adder uses only a single Toffoli gate. Moreover, our circuit may be used to construct reversible circuits for modular multiplication, $Cx\mod M$ with $x<M$, arising as components of Shor's algorithm. Our modular-multiplication circuits are simpler than previous constructions, and may be used as primitive circuits for quantum computations.

Funded by

Natural Science Foundation of Shandong Province(ZR2015FL024)

Science Foundation Ireland(SFI)

"source" : null , "contract" : "KJR1502"

National Natural Science Foundation of China(61373131)

Fundamental research Funds for the Central Universities(2682014CX095)

National Natural Science Foundation of China(61303039)

under the International Strategic Cooperation Award(SFI/13/ISCA/2845)

PAPD and CICAEET Funds Open Foundation of Jiangsu Engineering Center of Network Monitoring(Nanjing University of Information Science and Technology)


[1] Nielsen M, Chuang I. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2000. 150--280. Google Scholar

[2] hou C, Bao W S, Fu X Q. Sci China Inf Sci, 2011, 41: 1136-1145 Google Scholar

[3] u H, Wang X B, Pan J W. Sci China Inf Sci, 2014, 44: 296 Google Scholar

[4] uo M X, Ma S Y, Chen X B, et al. Phys Rev A, 2015, 91: 042326 CrossRef Google Scholar

[5] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Santa Fe, 1994. 124--134. Google Scholar

[6] hor P W. SIAM J Comput, 1997, 26: 1484-1509 CrossRef Google Scholar

[7] ivest R L, Shamir A, Adleman L. Comm ACM, 1978, 21: 120-126 CrossRef Google Scholar

[8] uo P, Wang J, Geng X H, et al. J Internet Tech, 2014, 15: 929-936 Google Scholar

[9] u Z, Sun X, Liu Q, et al. IEICE Trans Commun, 2015, 98: 190-200 Google Scholar

[10] en Y, Shen J, Wang J, et al. J Internet Tech, 2015, 16: 317-324 Google Scholar

[11] Xia Z, Wang X, Sun X, et al. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE Trans Parall Distr Syst, in press. doi:10.1109/TPDS.2015.2401003. Google Scholar

[12] i J, Li X, Yang B, et al. IEEE Trans Inf Foren Secur, 2015, 10: 507-518 CrossRef Google Scholar

[13] eynman R P. Inter J Theor Phys, 1982, 21: 476-487 Google Scholar

[14] eutsch D. Proc Royal Society London A, 1985, 400: 97-117 CrossRef Google Scholar

[15] an Dam W, Hallgren S I L. SIAM J Comput, 2006, 36: 763-778 CrossRef Google Scholar

[16] uo M X, Deng Y. Inter J Theor Phys, 2014, 53: 3124-3134 CrossRef Google Scholar

[17] uo M X, Chen X B, Yang Y X, et al. Sci Rep, 2014, 4: 4044-3134 Google Scholar

[18] uo M X, Wang X. Sci Rep, 2014, 4: 4732-3134 Google Scholar

[19] artin-Lopez E, Laing A, Lawson T, et al. Nature Phot, 2012, 6: 773-776 CrossRef Google Scholar

[20] ucero E, Barends R, Chen Y, et al. Nature Phys, 2012, 8: 719-723 CrossRef Google Scholar

[21] ao L, Long G L. Sci China Phys Mech Astronomy, 2011, 54: 936-941 CrossRef Google Scholar

[22] hende V, Bullock S S, Markov I L. IEEE Tran Comput AID Design, 2006, 26: 1000-1010 Google Scholar

[23] eauregard S. Quantum Inform Comput, 2003, 3: 175-185 Google Scholar

[24] roos J, Zalka C. Quantum Inform Comput, 2003, 3: 317-344 Google Scholar

[25] owler A G, Devitt S J, Hollenberg L C L. Quantum Inform Comput, 2004, 4: 237-251 Google Scholar

[26] artí-López E, Laing A, Lawson T, et al. Nature Photon, 2012, 6: 773-776 CrossRef Google Scholar

[27] akahashi Y, Kunihiro N. Quantum Inform Comput, 2005, 5: 440-448 Google Scholar

[28] akahashi Y, Kunihiro N. Quantum Inform Comput, 2008, 8: 636-649 Google Scholar

[29] Draper T G, Kutin S A, Rains E M, et al. Quantum Inform Comput, 2006, 6: 351-369 Google Scholar

[30] akahashi Y, Tani S, Kunihiro N. Quantum Inform Comput, 2010, 10: 0872-0890 Google Scholar

[31] Cuccaro S A, Draper T G, Kutin S A, et al. A new quantum ripple-carry addition circuit, In: 8th Workshop on Quantum Information Processing, Cambridge, 2005. 1--9. Google Scholar

[32] homsen M K, Axelsen H B. LNCS, 2008, 5204: 228-241 Google Scholar

[33] arkov I L, Saeedi M. Quantum Infor Comput, 2012, 12: 0361-0394 Google Scholar

[34] u N K, Duan R Y, Ying M S. Phys Rev A, 2013, 88: 010304-0394 CrossRef Google Scholar