Skip to main content

TDAG: Tree-based Directed Acyclic Graph Partitioning for Quantum Circuits

by Joseph Clark, Travis S Humble, Himanshu Thapliyal
Publication Type
Conference Paper
Book Title
GLSVLSI '23: Proceedings of the Great Lakes Symposium on VLSI 2023
Publication Date
Page Numbers
587 to 592
Publisher Location
New York, United States of America
Conference Name
Great Lakes Symposium on VLSI 2023 (GLSVLSI)
Conference Location
Knoxville, Tennessee, United States of America
Conference Sponsor
Conference Date

We propose the Tree-based Directed Acyclic Graph (TDAG) partitioning for quantum circuits, 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 an existing method called ScanPartitioner (an exhaustive search algorithm) with an 95% average reduction in execution time. Furthermore, TDAG improves compared to a faster partitioning method called QuickPartitioner by 38% in terms of quality of the results with minimal overhead in execution time.