TDAG: Tree-based Directed Acyclic Graph Partitioning for Quantum Circuits
Joseph F. Clark, Travis S. Humble, Himanshu Thapliyal
Abstract
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.
Topics & Concepts
Directed acyclic graphComputer scienceParallel computingTree (set theory)Overhead (engineering)Electronic circuitGraphAlgorithmSequential logicBinary treeDirected graphTheoretical computer scienceLogic gateMathematicsCombinatoricsEngineeringOperating systemElectrical engineeringQuantum Computing Algorithms and ArchitectureLow-power high-performance VLSI designParallel Computing and Optimization Techniques