Abstract
Elementary gate decomposition of larger Toffoli operations is often carried out using additional qubits (ancilla). The number of gates and the circuit depth vary in such transformation depending on the type of ancilla used (clean or dirty). The present Noisy Intermediate Scale Quantum (NISQ) devices have limited number of coherent qubits with faulty native operation support. Superconducting devices also have coupling restrictions or Nearest-Neighbor (NN) constraints, which require additional gates to map the transformed netlist for execution. While the mapping overhead is correlated with the number of 2-qubit gates and involved qubits, the fidelity of execution is inversely proportional to the number of gates and circuit depth. There is a tradeoff in devising the transpilation (i.e. low-level transformation and mapping) approach — dirty ancilla demands less qubits and overhead at the expense of more gates and depth as compared to clean ancilla, which involves less gates and depth at the expense of more qubits and overhead. This paper analyzes the disparity in gates, depth and qubits between: (i) the low-level transformation approaches without considering device coupling information, and (ii) the mapping schemes based on netlist transformation using a specific type of ancilla. We analyze the benefits of using NN-constraints at the transformation stage, and the impact of distributing clean ancilla across architectures. We have carried out experiments on IBM Q20 and Hexagonal Q20 architectures, which show improvements of 17% and 13% respectively in terms of number of gates.
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
References
Ibm, Q.: https://www.research.ibm.com/ibm-q. Accessed 20 Mar 2019
IBM Quantum Processor Types. https://quantum-computing.ibm.com/services/d-ocs/services/manage/systems/processors/ (2017)
The IBM Hummingbird Architecture. https://quantum-computing.ibm.com/serv-ices/docs/services/manage/systems/processors#hummingbird/ (2021). Accessed 1 Dec 2021
Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput.-Aided Design Integrated Circ. Syst. 32(6), 818–830 (2013)
Baker, J.M., Duckering, C., Hoover, A., Chong, F.T.: Decomposing quantum generalized Toffoli with an arbitrary number of ancilla. ArXiv abs/1904.01671 (2019)
Balauca, S., Arusoaie, A.: Efficient constructions for simulating multi controlled quantum gates. In: Computational Science - ICCS 2022, pp. 1–14 (2022)
Barenco, A., et al.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457–3467 (1995)
Chow, J., Dial, O., Gambetta, J.: IBM Quantum breaks the 100-qubit processor barrier. https://research.ibm.com/blog/127-qubit-quantum-processor-eagle/ (2021). Accessed 16 Nov 2021
Kole, A., Hillmich, S., Datta, K., Wille, R., Sengupta, I.: Improved mapping of quantum circuits to IBM QX architectures. IEEE Trans. Comput.-Aided Design Integr. Circuit. Syst. 39(10), 2375–2383 (2020)
Nation, P., Paik, H., Cross, A., Nazario, Z.: The IBM Quantum heavy hex lattice. https://research.ibm.com/blog/heavy-hex-lattice/ (2021). Accessed 7 July 2021
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge Univ, Press (Oct (2000)
Niemann, P., Bandyopadhyay, C., Drechsler, R.: Improved NCV gate realization of arbitrary size Toffoli gates. In: Design, Automation and Test in Europe (DATE), pp. 200–205 (2021)
Rahman, M., Dueck, G.W.: Synthesis of linear nearest neighbor quantum circuits. In: 10th International Workshop on Boolean Problems, pp. 1–9 (2012)
Selinger, P.: Quantum circuits of t-depth one. Phys. Rev. A 87(4), 042302 (2013)
Tang, H., et al.: Experimental quantum fast hitting on hexagonal graphs. Nat. Photonics 12(12), 754–758 (2018)
Wille, R., Große, D., Teuber, L., Dueck, G., Drechsler, R.: RevLib: an online resource for reversible functions and reversible circuits. In: International Symposium on Multi-Valued Logic, pp. 220–225 (2008). http://www.revlib.org
Wille, R., Lye, A., Drechsler, R.: Optimal SWAP gate insertion for nearest neighbor quantum circuits. In: Proceedings Design Automation Conference (DAC), pp. 489–494. IEEE, Suntec, Singapore (2014)
Zulehner, A., Paler, A., Wille, R.: An efficient methodology for mapping quantum circuits to the IBM QX architectures. EEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 38(7), 1226–1236 (2019)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Kole, A., Datta, K., Niemann, P., Sengupta, I., Drechsler, R. (2023). Exploiting the Benefits of Clean Ancilla Based Toffoli Gate Decomposition Across Architectures. In: Kutrib, M., Meyer, U. (eds) Reversible Computation. RC 2023. Lecture Notes in Computer Science, vol 13960. Springer, Cham. https://doi.org/10.1007/978-3-031-38100-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-031-38100-3_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-38099-0
Online ISBN: 978-3-031-38100-3
eBook Packages: Computer ScienceComputer Science (R0)