Using ZDDs in the Mapping of Quantum Circuits

Kaitlin Smith
Mathias Soeken
Bruno Schmitt
Giovanni De Micheli
Mitchell Thornton

A critical step in quantum compilation is the transformation of a technology-independent quantum circuit into a technology-dependent form for a targeted device. In addition to mapping quantum gates into the supported gate set, it is necessary to map pseudo qubits in the technology-independent circuit into physical qubits of the technology-dependent circuit such that coupling constraints among qubits acting in multiple-qubit gates are satisfied. It is usually not possible to find such a mapping without adding SWAP gates into the circuit. To cope with the technical limitations of NISQ-era quantum devices, it is advantageous to find a mapping that requires as few additional gates as possible. The large search space of possible mappings makes this task a difficult combinatorial optimization problem. In this work, we demonstrate how zero-suppressed decision diagrams (ZDDs) can be used for typical implementation tasks in quantum mapping algorithms. We show how to maximally partition a quantum circuit into blocks of adjacent gates, and if adjacent gates within a circuit do not share common mapping permutations, we attempt to combine them using parallelized SWAP operations represented in a ZDD. Boundaries for the partitions are formed where adjacent gates are unable to be combined. Within each partition block, ZDDs represent all possible mappings of pseudo qubits to physical qubits.

In Bob Coecke and Matthew Leifer: Proceedings 16th International Conference on Quantum Physics and Logic (QPL 2019), Chapman University, Orange, CA, USA., 10-14 June 2019, Electronic Proceedings in Theoretical Computer Science 318, pp. 106–118.
Published: 1st May 2020.

ArXived at: http://dx.doi.org/10.4204/EPTCS.318.7 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org