Abstract
Most quantum architectures restrict qubit interactions. They allow a qubit to interact with another qubit only if they are directly connected, and this constraint is the nearest neighbour (NN) constraint. If the interacting qubits are not adjacent, we need to insert swap gates appropriately to make them adjacent. Since the insertion of swap gates increases the circuit cost, a minimal number of swaps has to be performed. This paper illustrates the possibility of swap gate reduction for 2D NN circuits by better re-ordering of qubits using a multi-window look-ahead approach. Using this technique, near optimal solutions for NN circuit conversion are obtained. Experimental evaluation shows the effectiveness of our proposed local re-ordering algorithm for the reduction of swap requirements. We have compared our results with the most recent results, and a significant improvement is observed, with a maximum of 37.5% swap gate reduction.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
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
Barenco, A., et al.: Elementary gates for quantum computation. Phys. Rev. A 52, 3457–3467 (1995). https://doi.org/10.1103/PhysRevA.52.3457
Bhattacharjee, A., Bandyopadhyay, C., Wille, R., Drechsler, R., Rahaman, H.: A novel approach for nearest neighbor realization of 2D quantum circuits. In: 2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pp. 305–310 (2018). https://doi.org/10.1109/ISVLSI.2018.00063
Bhattacharjee, A., Bandyopadhyay, C., Mondal, B., Wille, R., Drechsler, R., Rahaman, H.: An efficient nearest neighbor design for 2D quantum circuits. In: Singh, A.K., Fujita, M., Mohan, A. (eds.) Design and Testing of Reversible Logic. LNEE, vol. 577, pp. 215–231. Springer, Singapore (2020). https://doi.org/10.1007/978-981-13-8821-7_12
Bhattacharjee, D., Chattopadhyay, A.: Depth-optimal quantum circuit placement for arbitrary topologies. CoRR abs/1703.08540 (2017)
Hirata, Y., Nakanishi, M., Yamashita, S., Nakashima, Y.: An efficient method to convert arbitrary quantum circuits to ones on a linear nearest neighbor architecture. In: 2009 Third International Conference on Quantum, Nano and Micro Technologies, pp. 26–33 (2009). https://doi.org/10.1109/ICQNM.2009.25
IBM QX device. https://quantumexperience.ng.bluemix.net/qx/devices
Jones, N.C., et al.: Layered architecture for quantum computing. Phys. Rev. X 2, 031007 (2012). https://doi.org/10.1103/PhysRevX.2.031007
Kole, A., Datta, K., Sengupta, I.: A new heuristic for N-dimensional nearest neighbor realization of a quantum circuit. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 37(1), 182–192 (2018). https://doi.org/10.1109/TCAD.2017.2693284
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
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
Marbaniang, L., Kole, A., Datta, K., Sengupta, I.: Design of efficient quantum circuits using nearest neighbor constraint in 2D architecture. In: Phillips, I., Rahaman, H. (eds.) RC 2017. LNCS, vol. 10301, pp. 248–253. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59936-6_19
Maslov, D., Falconer, S.M., Mosca, M.: Quantum circuit placement. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 27(4), 752–763 (2008). https://doi.org/10.1109/TCAD.2008.917562
AlFailakawi, M., AlTerkawi, L., Ahmad, I., Hamdan, S.: Line ordering of reversible circuits for linear nearest neighbor realization. Quantum Inf. Process. 12(10), 3319–3339 (2013). https://doi.org/10.1007/s11128-013-0601-1
Nickerson, N.H., Li, Y., Benjamin, S.C.: Topological quantum computing with a very noisy network and local error rates approaching one percent. Nat. Commun. 4 (2013). https://www.nature.com/articles/ncomms2773. Article no. 1756
Ohliger, M., Eisert, J.: Efficient measurement-based quantum computing with continuous-variable systems. Phys. Rev. A 85(6) (2012). https://doi.org/10.1103/physreva.85.062318
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
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
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 (2014). https://doi.org/10.1109/ASPDAC.2014.6742940
Shrivastwa, R.R., Datta, K., Sengupta, I.: Fast qubit placement in 2D architecture using nearest neighbor realization. In: 2015 IEEE International Symposium on Nanoelectronic and Information Systems, pp. 95–100 (2015). https://doi.org/10.1109/iNIS.2015.59
Taha, S.M.R.: Fundamentals of reversible logic. Reversible Logic Synthesis Methodologies with Application to Quantum Computing. SSDC, vol. 37, pp. 7–16. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-23479-3_2
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
Wille, R., Lye, A., Drechsler, R.: Exact reordering of circuit lines for nearest neighbor quantum architectures. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 33(12), 1818–1831 (2014). https://doi.org/10.1109/TCAD.2014.2356463
Wille, R., Saeedi, M., Drechsler, R.: Synthesis of reversible functions beyond gate count and quantum cost. In: International Workshop on Logic Synthesis (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Chhangte, L., Chakrabarty, A. (2020). Optimization of Local Ordering Technique for Nearest Neighbour Circuits. In: Bhattacharjee, A., Borgohain, S., Soni, B., Verma, G., Gao, XZ. (eds) Machine Learning, Image Processing, Network Security and Data Sciences. MIND 2020. Communications in Computer and Information Science, vol 1241. Springer, Singapore. https://doi.org/10.1007/978-981-15-6318-8_16
Download citation
DOI: https://doi.org/10.1007/978-981-15-6318-8_16
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-6317-1
Online ISBN: 978-981-15-6318-8
eBook Packages: Computer ScienceComputer Science (R0)