Time Window-based Optimization of Communication Costs in Distributed Quantum Computing

Time Window-based Optimization of Communication Costs in Distributed Quantum Computing

Abstract:

This work develops and evaluates a two-stage optimization strategy that reduces communication costs in distributed quantum circuits. First, quantum circuits are modeled as undirected graphs and decomposed into two nearly equal-sized clusters using the Kernighan-Lin algorithm, which eliminates up to 60% of inter cluster CNOT edges. The remaining gates are divided into time windows. A heuristics-based allocation procedure prioritizes windows with maximum qubit overlap and even load distribution. This window structure reduces the simultaneous use of individual qubits and thus lowers the communication costs between execution units. The experiments on the Qiskit QASM simulator compare this method with a linear baseline in which the gates are processed sequentially and without partitioning. The study demonstrates that pairing graph partitioning with carefully tuned time window scheduling yields substantial savings while preserving logical correctness. Future work will target validation on physical hardware, integration of fault tolerant codes, and ML driven adaptive window sizing.

Author:

Rama Malhis

Advisors:

Leo Sünkel, Maximilian Zorn, Claudia Linnhoff-Popien

Student Thesis | Published June 2025 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors