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

Joseph Clark, Travis Humble, Himanshu Thapliyal

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

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.

Original languageEnglish
Title of host publicationGLSVLSI 2023 - Proceedings of the Great Lakes Symposium on VLSI 2023
PublisherAssociation for Computing Machinery
Pages587-592
Number of pages6
ISBN (Electronic)9798400701252
DOIs
StatePublished - Jun 5 2023
Event33rd Great Lakes Symposium on VLSI, GLSVLSI 2023 - Knoxville, United States
Duration: Jun 5 2023Jun 7 2023

Publication series

NameProceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI

Conference

Conference33rd Great Lakes Symposium on VLSI, GLSVLSI 2023
Country/TerritoryUnited States
CityKnoxville
Period06/5/2306/7/23

Keywords

  • circuit partitioning
  • directed acyclic graph
  • quantum computing

Fingerprint

Dive into the research topics of 'TDAG: Tree-based Directed Acyclic Graph Partitioning for Quantum Circuits'. Together they form a unique fingerprint.

Cite this