Linear Nearest Neighbor Quantum Circuit Synthesis and Optimization Based on the Matrix

doi:10.3969/j.issn.0372-2112.2018.03.026

PDF(1266 KB)

ACTA ELECTRONICA SINICA ›› 2018, Vol. 46 ›› Issue (3) : 688-694. DOI: 10.3969/j.issn.0372-2112.2018.03.026

Linear Nearest Neighbor Quantum Circuit Synthesis and Optimization Based on the Matrix

LU Yu¹, GUAN Zhi-jin^1,2, CHENG Xue-yun^1,2, TAN Ying-ying², ZHANG Zong-yuan²

Author information +

History +

Abstract

In order to construct linear nearest neighbor(LNN) quantum circuit and reduce its total quantum cost, a matrix-based synthesis and optimization method is proposed. The linear reversible circuit is represented by matrix, and the CNOT(Controlled NOT Gate) analysis based on the matrix is put forward. The best strategy of matrix partition is given, which ensures the number of CNOT gate used in the circuit synthesis is optimal. The matrix representation of swap gate and the NN(Nearest Neighbor) rules are proposed to realize the LNN circuits. The equivalence of two insertion methods of swap gates is proven. Deletion rules of swap gates which are used to make gates adjacent to NN in different cases are proposed, and they can reduce the quantum cost. Experimental results on typical benchmark circuits and comparison against previous algorithms for LNN quantum circuit optimization, the average optimization rate in quantum cost is 34. 31%.

Key words

quantum circuit / matrix transformation / linear nearest neighbor / circuit synthesis / optimization / quantum cost

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

LU Yu, GUAN Zhi-jin, CHENG Xue-yun, TAN Ying-ying, ZHANG Zong-yuan. Linear Nearest Neighbor Quantum Circuit Synthesis and Optimization Based on the Matrix[J]. Acta Electronica Sinica, 2018, 46(3): 688-694. https://doi.org/10.3969/j.issn.0372-2112.2018.03.026

References

[1] B Schaeffer,M Perkowski.Linear reversible circuit synthesis in the linear nearest-neighbor model[J].IEEE International Symposiumon Multiple-Valued Logic,2012,19(10):157-160.
[2] Z Sasanian,R Wille,DM Miller.Realizing reversible circuits using a new class of quantum gate[J].Design Automation Conference,2012,8(8):36-41.
[3] O Golubitsky,D Maslov.A study of optimal 4-bit reversible Toffoli circuits and their synthesis[J].IEEE Transactions on Computers,2011,61(6):1341-1353.
[4] VV Shende,SS Bullock,IL Markov.Synthesis of quantum-logic circuits[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2006,25(6):1000-1010.
[5] AlFailakawi M,AlTerkawi L,Ahmad I,et al.Line ordering of reversible circuits for linear nearest neighbor realization[J].Quantum Information Processing,2013,12(10):3319-3339.
[6] K Patel,I Markov,J Hayes.Optimal synthesis of linear reversible circuits[J].Quantum Information and Computation,2008,8(3):282-294.
[7] P Yu,Y Yan,J Lin,H Huang,W Wu.An efficient method to synthesize reversible logic by using positive-davio decision diagrams[J].Circuits,Systems,and Signal Processing,2014,33(7):3107-3121.
[8] R Wille,R Drechsler.The SyReC hardware description language:Enabling scalable synthesis of reversible circuits[A].2013 IEEE 56th International Midwest Symposium on Circuits and Systems (MWSCAS)[C].Boise:IEEE,2013.1063-1066.
[9] M Saeedi,R Wille,R Drechsler.Synthesis of quantum circuits for linear nearest neighbor architectures[J].Computer Science,2012,10(3):355-377.
[10] Abhoy Kole,Kamalika Datta,Indranil Sengupta.A heuristic for linear nearest neighbor realization of quantum circuits by swap gate insertion using N-gate lookahead[J].IEEE Journal on Emerging and Selected Topics in Circuits and Systems,2016,6(1):62-72.
[11] Lye A,Will R,Drechsler R.Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits[A].Design Automation Conference (ASP-DAC),201520th Asia and South Pacific[C].Austin:IEEE,2015.178-183.
[12] Md.Mazder Rahman,Gerhard W.Dueck,Anupam Chattopadhyay.Integrated synthesis of linear nearest neighbor ancilla-free MCT circuits[A].2016 IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL)[C].Japan:IEEE,2016.144-149.

Funding

National Natural Science Foundation of China (No.61402244); General Program of Basic Research Project of Jiangsu Provicne (Natural Science Foundation) (No.BK20151274); Open project of Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University (No.93K172016K03); Graduate Science and Technology Innovation Program of Nantong University (No.KYC15016)