Reversible Logic Circuit for One-Dimensional Quantum Walk Based on NCP Quantum Gates Library

ZHU Wan-ning, CHEN Han-wu, LI Zhi-gang, RUAN Yue, WANG Dong, ZHOU Gang

ACTA ELECTRONICA SINICA ›› 2013, Vol. 41 ›› Issue (1) : 91-97.

PDF(2126 KB)
CIE Homepage  |  Join CIE  |  Login CIE  |  中文 
PDF(2126 KB)
ACTA ELECTRONICA SINICA ›› 2013, Vol. 41 ›› Issue (1) : 91-97. DOI: 10.3969/j.issn.0372-2112.2013.01.017

Reversible Logic Circuit for One-Dimensional Quantum Walk Based on NCP Quantum Gates Library

  • ZHU Wan-ning1, CHEN Han-wu1,3, LI Zhi-gang1, RUAN Yue1,2, WANG Dong1, ZHOU Gang1
Author information +

Abstract

The design proposal of reversible logic circuit for one-dimensional quantum walk based on NCP quantum gates library is presented.According to the features of the one-dimensional quantum walk,this circuit is divided to two parts,one part is quantum coin tossing and the other part is S operation.Besides the work above,this paper thoroughly analyses the one-dimensional quantum walk and builds a mathematical model of the one-dimensional quantum walk and uses controlled add-sub circuit to realize the S operation.At present the researches on quantum walk often limited to the mathematical theory and analysis.Depend on the primitive recursive,Mathematical expression of every step of the one-dimensional quantum walk is given in this paper;the circuit studied in this paper describes element operation of the one-dimensional quantum walk,and make this modular which contribute to the realization for the algorithm of one-dimensional quantum walk.

Key words

one-dimensional quantum walk / NCP quantum gates library / reversible logic / controlled add-sub circuit / primitive recursive

Cite this article

Download Citations
ZHU Wan-ning, CHEN Han-wu, LI Zhi-gang, RUAN Yue, WANG Dong, ZHOU Gang. Reversible Logic Circuit for One-Dimensional Quantum Walk Based on NCP Quantum Gates Library[J]. Acta Electronica Sinica, 2013, 41(1): 91-97. https://doi.org/10.3969/j.issn.0372-2112.2013.01.017

References

[1] P W Shor.Algorithms for quantum computation:discrete logarithms and factoring[A].Proceedings of the 35th Annual Symposium on Foundations of Computer Science [C].Los Alamitos,California :IEEE Press,1994.124-134.
[2] L K Grover.Quantum mechanics helps in searching for a needle in a haystack[J].Physical Review Letters,1997,79(2):325-328.
[3] Y Aharonov,L Davidovich,N Zagury.Quantum random walks[J].Physical Review A,1993,48(2):1687-1690.
[4] A Ambainis.Quantum search algorithms[J].SIGACT News,2004,35(2):22-35.
[5] A Ambainis.Quantum walk algorithm for element distinctness[A].Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science[C].USA:IEEE Press,2004.22-31.
[6] F Magniez,A Nayak,J Roland,M Santha.Search via quantum walk[A].Proceedings of the 39th Annual ACM Symposium on theory of Computing[C].USA:ACM Press,2007.575-584.
[7] A M Childs,R Cleve,E Deotto,E Farhi,S Gutmann,D A Spielman.Exponential algorithmic speedup by quantum walk[A].Proceedings of the 35th ACM Symposium on Theory of Computing[C].USA:ACM Press,2003.59-69.
[8] A M Childs,L J Schulman,U V Vazirani.Quantum algorithms for hidden nonlinear structures[A].Proceedings of the 45th IEEE Symposium on Foundations of Computer Science[C].USA:IEEE Press,2007.395-404.
[9] A M Chids.Universal computation by quantum walk[J].Physical Review Letters,2009,102(18):180501.
[10] A Ambainis,E Bach,A Nayak,A Vishwanath,J Watrous.One-dimensional quantum walks[A].Proceedings of the 33rd ACM Symposium on the Theory of Computing [C].New York:ACM,2001.60-69.
[11] D Deutsch.Quantum theory,the Church-Turing principle and the universal quantum computer[J].Proceedings of the Royal Society of London Series A,1985,400(1818):96-117.
[12] D Deutsch.Quantum computational networks[J].Proceedings of the Royal Society of London Series A,1989,425(1868):73-90.
[13] Feynman R.Quantum mechanical computers[J].Foundations of Physics,1986,16(6):507-531.(Originally appeared in Optics News,1985,11(2):11-20.)
[14] Peres A.Reversible logic and quantum computers[J].Physical Review:A,1985,32(6):3266-3276.

Funding

National Natural Science Foundation of China (No.61170321); Research Fund for the Doctoral Program of Higher Education of China (No.20110092110024); Key Laboratory of Computer Network and Information Integration of Ministry of Education
PDF(2126 KB)

3553

Accesses

0

Citation

Detail

Sections
Recommended

/