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
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
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.
{{custom_fnGroup.title_en}}
Footnotes
{{custom_fn.content}}
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
{{custom_fund}}