This repository contains the code for the Tree-based Directed Acyclic Graph (TDAG) Partitioning algorithm (paper), which is intended for partitioning quantum circuits for peephole optimization or certain compilation tasks (e.g. Quest).
TDAG is a novel quantum circuit partitioning method which partitions circuits by viewing them as a series of binary trees and selecting the tree containing the most gates. TDAG produces results of comparable quality (number of partitions) to BQSKit's ScanPartitioner (an exhaustive search algorithm) with an 95% average reduction in execution time. Furthermore, TDAG improves compared to BQSKit's faster partitioning method QuickPartitioner by 38% in terms of quality of the results with minimal overhead in execution time.
The partitioner is built on the BQSKit quantum synthesis toolkit, and can be used the same way as BQSKit's ScanPartitioner. The benchmark.py benchmarking file (which is similar to the one used to generate the results in the paper) can be run to generate a .csv file containing benchmark performance for this algorithm compared to BQSKit's QuickPartitioner and ScanPartitioner.
Clark, J., Humble, T., & Thapliyal, H. (2023, June). Tdag: Tree-based directed acyclic graph partitioning for quantum circuits. In Proceedings of the Great Lakes Symposium on VLSI 2023 (pp. 587-592).
This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. 1938092.