Skip to main content
SpringerLink
Log in

Nearest Neighbor Synthesis of CNOT Circuit Based on Matrix Transformation

  • Conference paper
  • First Online:
Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD 2021)

Part of the book series: Lecture Notes on Data Engineering and Communications Technologies ((LNDECT,volume 89))

  • 1845 Accesses

Abstract

In order to obtain a CNOT circuit with better performance under the nearest neighbor (NN) constraint, the Boolean matrix representation of the CNOT circuit and its change in the NN synthesis process are analyzed. The matrix flipped by the center and the transpose matrix of the Boolean matrix can also be used for the NN synthesis, and the NN circuit with the least cost is chosen as the final result. In order to further reduce the runtime of the method and improve the efficiency of solving large-scale problems, the parallel implementation algorithm is put forward. Tested on different circuit lengths on five architectures, the results show that under the same parameters and environment, the number of NN CNOT gates is less than that of the existing method, and the maximum optimization rate is 29.75%. The average speedup of parallel execution is 3.02 with quad-core processor.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 219.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 279.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)

    Article  MathSciNet  Google Scholar 

  2. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212–219 (1996)

    Google Scholar 

  3. Peruzzo, A., McClean, J., Shadbolt, P., Yung, M., Zhou, X., Love, P., et al.: A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5, 4213 (2014)

    Article  Google Scholar 

  4. Versluis, R., Poletto, S., Khammassi, N., Tarasinski, B., Haider, N., Michalak, D.J., et al.: Scalable quantum circuit and control for a superconducting surface code. Phys. Rev. Appl. 8(3), 034021 (2017)

    Article  Google Scholar 

  5. Balance, C.J., Harty, T.P., Linke, N.M., Sepiol, M.A., Lucas, D.M.: High-fidelity quantum logic gates using trapped-ion hyperfine qubits. Phys. Rev. Lett. 117(6), 060504 (2016)

    Article  Google Scholar 

  6. Zhu, P., Cheng, X., Guan, Z.: An exact qubit allocation approach for NISQ architectures. Quant. Inf. Process. 19(11), 1–21 (2020)

    Google Scholar 

  7. Ding, J., Yamashita, S.: Exact synthesis of nearest neighbor compliant quantum circuits in 2d architecture and its application to large-scale circuits. IEEE T. Comput. Aid. D. 39(5), 1045–1058 (2020)

    Article  Google Scholar 

  8. Zulehner, A., Paler, A., Wille, R.: An efficient methodology for mapping quantum circuits to the IBM QX architecture. IEEE Trans. CAD Integr. Circ. Syst. 38(7), 1226–1236 (2019)

    Google Scholar 

  9. Niemann, P., Almeida, A.A, Dueck, G. Drechsler, R.: Design space exploration in the mapping of reversible circuits to IBM quantum computers. In: Proceedings of the 23rd Euromicro Conference on Digital System Design (2020)

    Google Scholar 

  10. Zhu, P., Guan, Z., Cheng, X.: A dynamic look-ahead heuristic for the qubit mapping problem of NISQ computers. IEEE T. Comput. Aid. Des. 99, 1 (2020)

    Google Scholar 

  11. Patel, K.N., Markov, I.L., Hayes, J.P.: Optimal synthesis of linear reversible circuits. Quant. Inform. Comput. 8(3), 282–294 (2008)

    MathSciNet  MATH  Google Scholar 

  12. Schaeffer, B., Perkowski, M.: Linear reversible circuit synthesis in the linear nearest neighbor model. In: Proceedings of the International Symposium on Multiple-Valued Logic, pp. 157–160 (2012)

    Google Scholar 

  13. Nash, B., Gheorghiu, V., Mosca, M.: Quantum circuit optimizations for NISQ architecture. Quant. Sci. Technol. 5(2), 025010 (2020)

    Google Scholar 

  14. Kissinger, A., Griend, A.M.: CNOT circuit extraction for topologically-constrained quantum memories. Quant. Inf. Comput. 20(7 & 8), 581–596 (2020)

    MathSciNet  Google Scholar 

Download references

Acknowledgements

This work is supported by the National Natural Science Foundation of China (62072259).

Author information

Authors and Affiliations

  1. School of Information Science and Technology, Nantong University, Nantong, 226019, China

    Xueyun Cheng, Mingqiang Zhu, Xiang Li & Zhijin Guan

Authors
  1. Xueyun Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mingqiang Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiang Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Zhijin Guan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhijin Guan .

Editor information

Editors and Affiliations

  1. Guizhou University, Guiyang, China

    Quan Xie

  2. Computer Science and Mathematics, University of São Paulo (USP), Ribeirão Preto, São Paulo, Brazil

    Liang Zhao

  3. College of Electrical and Information, Hunan University, Changsha, China

    Kenli Li

  4. Department of Mathematics, NIT Jalandhar, Jalandhar, India

    Anupam Yadav

  5. Electrical and Electronic Engineering, Nanyang Technological University, Singapore, Singapore

    Lipo Wang

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Cheng, X., Zhu, M., Li, X., Guan, Z. (2022). Nearest Neighbor Synthesis of CNOT Circuit Based on Matrix Transformation. In: Xie, Q., Zhao, L., Li, K., Yadav, A., Wang, L. (eds) Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery. ICNC-FSKD 2021. Lecture Notes on Data Engineering and Communications Technologies, vol 89. Springer, Cham. https://doi.org/10.1007/978-3-030-89698-0_16

Download citation

Publish with us

Policies and ethics

Search

Navigation