Using ZDDs in the mapping of quantum circuits

Kaitlin Smith (Southern Methodist University), Mathias Soeken (Ecole Polytechnique Fédérale de Lausanne), Bruno Schmitt (Ecole Polytechnique Fédérale de Lausanne), Giovanni De Micheli (Ecole Polytechnique Fédérale de Lausanne), Mitchell Thornton (Southern Methodist University)

A critical step in quantum compilation is the transformation of a technology-independent quantum circuit into a technology-dependent form for a targeted device. Besides 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 crucial 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. Uncombinable gates form the boundaries for the partitions. Within each partition block, ZDDs represent all possible mappings of pseudo qubits to physical qubits.