[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Mapping Quantum Circuits in IBM Q Devices Using Progressive Qubit Assignment for Global Ordering

  • Published:
New Generation Computing Aims and scope Submit manuscript

Abstract

One major challenge in executing a quantum circuit is the restriction on physical qubit interaction. The elementary gates in a quantum circuit must strictly conform to the hardware’s qubit coupling constraints before they are executed. This requires doing an initial mapping of input circuit qubits to physical qubits alongside satisfying qubit couplings specified by a qubit coupling map. Currently, quantum computing architectures possess the restrictions of limited qubit interaction distance and the inability of multi-qubit interaction. Two qubits of a quantum gate can interact if they locate adjacent to each other. During the execution of a quantum circuit, it is essential to re-arrange qubits for adjacency. As a result, the number of gates increases. We can address these issues by mapping the qubits of the input circuit to hardware and performing qubit re-ordering with minimal additional gates. In the proposed work, we efficiently generate a good initial qubit mapping that attempts to keep frequently interacting qubits together and use a multi-window look-ahead technique for qubit re-ordering. The proposed work is evaluated on the most recent IBM Q 16 Melbourne device. The experimental evaluation confirms the effectiveness of our work for minimizing the circuit cost and depth.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Alfailakawi, M.G., Ahmad, I., Hamdan, S.: Harmony-search algorithm for 2D nearest neighbor quantum circuits realization. Expert Syst. Appl. 61(C), 16–27 (2016) https://doi.org/10.1016/j.eswa.2016.04.038

  2. Bhattacharjee, D., Chattopadhyay, A.: Depth-optimal quantum circuit placement for arbitrary topologies. CoRR abs/1703.08540 (2017). arXiv:org/abs/1703.08540

  3. Chakrabarti, A., Sur-Kolay, S., Chaudhury, A.: Linear nearest neighbor synthesis of reversible circuits by graph partitioning. CoRR (2011). arXiv:org/abs/1112.0564

  4. Chhangte, L., Chakrabarty, A.: Optimization of local ordering technique for nearest neighbour circuits. In: A. Bhattacharjee, S.K. Borgohain, B. Soni, G. Verma, X.Z. Gao (eds.) Machine Learning, Image Processing, Network Security and Data Sciences, pp. 182–192. Springer Singapore, Singapore (2020). https://doi.org/10.1007/978-981-15-6318-8_16

  5. Chhangte, L., Chakrabarty, A.: Technique for two-dimensional nearest neighbour realisation of quantum circuits using weighted look-ahead. IET Comput. Digit. Tech. 14, 281–289 (2020). https://doi.org/10.1049/iet-cdt.2019.0257

    Article  Google Scholar 

  6. Cross, A.W., Bishop, L.S., Smolin, J.A., Gambetta, J.M.: Open quantum assembly language. arXiv e-prints arXiv:1707.03429 (2017). arXiv:org/abs/1707.03429v2

  7. Dueck, G.W., Pathak, A., Rahman, M.M., Shukla, A., Banerjee, A.: Optimization of circuits for ibm’s five-qubit quantum computers. In: 2018 21st Euromicro Conference on Digital System Design (DSD), pp. 680–684 (2018). https://doi.org/10.1109/DSD.2018.00005

  8. Green, A.S., Lumsdaine, P.L., Ross, N.J., Selinger, P., Valiron, B.: Quipper: a scalable quantum programming language. SIGPLAN Not. 48(6), 333–342 (2013). https://doi.org/10.1145/2499370.2462177

    Article  MATH  Google Scholar 

  9. IBM QX device. https://quantumexperience.ng.bluemix.net/qx/devices. Accessed: 2021-11-10

  10. Itoko, T., Raymond, R., Imamichi, T., Matsuo, A.: Optimization of quantum circuit mapping using gate transformation and commutation. Integration 70, 43–50 (2020). https://doi.org/10.1016/j.vlsi.2019.10.004

    Article  Google Scholar 

  11. Javadi Abhari, A., Patil, S., Kudrow, D., Heckey, J., Lvov, A., Chong, F.T., Martonosi, M.: Scaffcc: A framework for compilation and analysis of quantum computing programs. In: Proceedings of the 11th ACM Conference on Computing Frontiers, CF ’14. Association for Computing Machinery, New York, NY, USA (2014). https://doi.org/10.1145/2597917.2597939

  12. Kole, A., Datta, K.: Improved ncv gate realization of arbitrary size toffoli gates. In: 2017 30th International Conference on VLSI Design and 2017 16th International Conference on Embedded Systems (VLSID), pp. 289–294 (2017). https://doi.org/10.1109/VLSID.2017.11

  13. Kole, A., Datta, K., Sengupta, I.: A new heuristic for N-dimensional nearest neighbor realization of a quantum circuit. IEEE Trans. Comput. Aid. Design Integr. Circ. Syst. 37(1), 182–192 (2018). https://doi.org/10.1109/TCAD.2017.2693284

    Article  Google Scholar 

  14. Kole, A., Hillmich, S., Datta, K., Wille, R., Sengupta, I.: Improved mapping of quantum circuits to ibm qx architectures. IEEE Trans. Comput. Aid. Design Integr. Circ. Syst. 39(10), 2375–2383 (2020). https://doi.org/10.1109/TCAD.2019.2962753

    Article  Google Scholar 

  15. Li, G., Ding, Y., Xie, Y.: Tackling the qubit mapping problem for NISQ-era quantum devices. In: Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’19, pp. 1001–1014. ACM, New York, NY, USA (2019). https://doi.org/10.1145/3297858.3304023

  16. Lin, C., Sur-Kolay, S., Jha, N.K.: PAQCS: Physical design-aware fault-tolerant quantum circuit synthesis. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 23(7), 1221–1234 (2015). https://doi.org/10.1109/TVLSI.2014.2337302

  17. Lye, A., Wille, R., Drechsler, R.: Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits. In: The 20th Asia and South Pacific Design Automation Conference, pp. 178–183 (2015). https://doi.org/10.1109/ASPDAC.2015.7059001

  18. Mapping of quantum circuits. https://iic.jku.at/eda/research/ibm_qx_mapping/. Accessed: 2021-11-01

  19. Matsumoto, K., Amano, K.: Representation of quantum circuits with clifford and \(\pi /8\) gates (2008). arXiv:org/abs/0806.3834

  20. Matsuo, A., Hattori, W., Yamashita, S.: Reducing the overhead of mapping quantum circuits to ibm q system. In: 2019 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1–5 (2019). https://doi.org/10.1109/ISCAS.2019.8702439

  21. Miller, D.M., Wille, R., Sasanian, Z.: Elementary quantum gate realizations for multiple-control toffoli gates. In: 2011 41st IEEE International Symposium on Multiple-Valued Logic, pp. 288–293 (2011). https://doi.org/10.1109/ISMVL.2011.54

  22. Mohammad, A., Laila, A., Imtiaz, A., Suha, H.: Line ordering of reversible circuits for linear nearest neighbor realization. Quant. Inform. Process. 12(10), 3319–3339 (2013). https://doi.org/10.1007/s11128-013-0601-1

    Article  MathSciNet  MATH  Google Scholar 

  23. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition, 10th edn. Cambridge University Press, New York (2011)

    MATH  Google Scholar 

  24. Niemann, P., de Almeida, A.A.A., Dueck, G., Drechler, R.: Design space exploration in the mapping of reversible circuits to ibm quantum computers. In: 2020 Euromicro Conference on Digital System Design (DSD), vol. 1, pp. 401–407. IEEE Computer Society, Los Alamitos, CA, USA (2020). https://doi.org/10.1109/DSD51259.2020.00070

  25. Paler, A.: On the influence of initial qubit placement during NISQ circuit compilation. arXiv e-prints (2018). arXiv:org/abs/1811.08985v2

  26. Preskill, J.: Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018). https://doi.org/10.22331/q-2018-08-06-79

  27. Qiskit. https://qiskit.org/. Accessed: 2021-11-10

  28. Rahman, M.M., Dueck, G.W., Chattopadhyay, A., Wille, R.: Integrated synthesis of linear nearest neighbor ancilla-free MCT circuits. In: 2016 IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL), pp. 144–149 (2016). https://doi.org/10.1109/ISMVL.2016.54

  29. Saeedi, M., Wille, R., Drechsler, R.: Synthesis of quantum circuits for linear nearest neighbor architectures. Quant. Inform. Process. 10(3), 355–377 (2011). https://doi.org/10.1007/s11128-010-0201-2

    Article  MathSciNet  MATH  Google Scholar 

  30. Shafaei, A., Saeedi, M., Pedram, M.: Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures. In: 2013 50th ACM/EDAC/IEEE Design Automation Conference (DAC), pp. 1–6 (2013). https://doi.org/10.1145/2463209.2488785

  31. Shafaei, A., Saeedi, M., Pedram, M.: Qubit placement to minimize communication overhead in 2D quantum architectures. In: 2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 495–500. IEEE (2014). https://doi.org/10.1109/ASPDAC.2014.6742940

  32. Siraichi, M.Y., Santos, V.F.d., Collange, S., Pereira, F.M.Q.: Qubit allocation. In: Proceedings of the 2018 International Symposium on Code Generation and Optimization, CGO 2018, p. 113–125. Association for Computing Machinery, New York, NY, USA (2018). https://doi.org/10.1145/3168822

  33. Wille, R., Große, D., Teuber, L., Dueck, G.W., Drechsler, R.: Revlib: An online resource for reversible functions and reversible circuits. In: 38th International Symposium on Multiple Valued Logic (ismvl 2008), pp. 220–225. Dallas, TX (2008). https://doi.org/10.1109/ISMVL.2008.43

  34. Wille, R., Saeedi, M., Drechsler, R.: Synthesis of reversible functions beyond gate count and quantum cost. In: International Workshop on Logic Synthesis (IWLS) (2010). arXiv:org/abs/1004.4609

  35. Wille, R., Lye, A., Drechsler, R.: Exact reordering of circuit lines for nearest neighbor quantum architectures. IEEE Trans. Comput. Aid. Design Integr. Circ. Syst. 33(12), 1818–1831 (2014). https://doi.org/10.1109/TCAD.2014.2356463

    Article  Google Scholar 

  36. Wille, R., Keszocze, O., Walter, M., Rohrs, P., Chattopadhyay, A., Drechsler, R.: Look-ahead schemes for nearest neighbor optimization of 1D and 2D quantum circuits. In: 2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 292–297 (2016). https://doi.org/10.1109/ASPDAC.2016.7428026

  37. Wille, R., Burgholzer, L., Zulehner, A.: Mapping quantum circuits to ibm qx architectures using the minimal number of swap and h operations. In: Proceedings of the 56th Annual Design Automation Conference 2019, DAC ’19. Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3316781.3317859

  38. Yamanaka, K., Demaine, E.D., Ito, T., Kawahara, J., Kiyomi, M., Okamoto, Y., Saitoh, T., Suzuki, A., Uchizawa, K., Uno, T.: Swapping labeled tokens on graphs. Theor. Comput. Sci. 586, 81–94 (2015). https://doi.org/10.1016/j.tcs.2015.01.052

    Article  MathSciNet  MATH  Google Scholar 

  39. Zhang, X., Xiang, H., Xiang, T., Fu, L., Sang, J.: An efficient quantum circuits optimizing scheme compared with qiskit. In: Collaborative Computing: Networking, Applications and Worksharing, pp. 467–476. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12981-1_32

  40. Zulehner, A., Paler, A., Wille, R.: Efficient mapping of quantum circuits to the IBM QX architectures. In: 2018 Design, Automation Test in Europe Conference Exhibition (DATE), pp. 1135–1138 (2018). https://doi.org/10.23919/DATE.2018.8342181

  41. Zulehner, A., Wille, R.: Compiling su(4) quantum circuits to ibm qx architectures. In: ASPDAC ’19: Proceedings of the 24th Asia and South Pacific Design Automation Conference, pp. 185–190. Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3287624.3287704

Download references

Acknowledgements

We acknowledge the use of IBM Quantum services for this work. The views expressed are those of the authors, and do not reflect the official policy or position of IBM or the IBM Quantum team.

Author information

Authors and Affiliations

  1. National Institute of Technology Meghalaya, Shillong, Meghalaya, India

    Lalengmawia Chhangte & Alok Chakrabarty

Authors
  1. Lalengmawia Chhangte
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alok Chakrabarty
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lalengmawia Chhangte.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chhangte, L., Chakrabarty, A. Mapping Quantum Circuits in IBM Q Devices Using Progressive Qubit Assignment for Global Ordering. New Gener. Comput. 40, 311–338 (2022). https://doi.org/10.1007/s00354-022-00163-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00354-022-00163-5

Keywords

Search

Navigation