Quantum Circuit Depth Optimization using Graph Coloring

Quantum algorithms are typically implemented using the quantum circuit model in which computations are represented as sequences of quantum operations (known as quantum gates) acting on qubits. These circuit models are highly susceptible to errors and inefficiencies due to quantum noise and the limited capabilities of existing quantum hardware. Also, quantum computers are highly susceptible to decoherence which is qubit loss of quantum information over a period of time. Thus, optimizing quantum circuits becomes critical for enhancing computational speed and mitigating errors caused by quantum noise. Over the past years, researchers have devised innovative techniques and algorithms to optimize quantum circuits focusing on characteristics of circuits such as circuit depth, gate count, qubit count, gate fidelity etc. In this work, we mainly focus on optimizing circuit depth. For a given quantum circuit, some operations in it can be parallelizable (can be simultaneously executed on the system) depending on the hardware machine. This concept of parallelizability leads to the notion of depth (of a circuit) which corresponds to the number of sequential layers of gates, where gates within a layer can be executed in parallel. Circuits with smaller depth are generally preferable as shorter execution time reduces exposure to decoherence and limits accumulation of noise. Rearranging commuting gates can help in reducing depth. Recent work by Lee et al. (2026) use this property of commuting circuits and model circuit depth minimizing problem as a graph coloring task. However, their model is restricted for fully commuting circuits. However, general quantum circuits may contain noncommuting gates, requiring execution order constraints. We therefore generalize the prior formulation for arbitrary circuits by modeling the quantum circuit as a mixed graph $G(V, E_d, E_u)$ where each node represents a quantum gate and edges are added based on dependencies. A directed edge from gate $g_1$ to $g_2$ represents a hard dependency that $g_1$ must be executed before $g_2$ whereas an undirected edge between $g_1$ and $g_2$ implies that the two gates commute but share at least one qubit. For this formulation, the problem of minimizing circuit depth becomes equivalent to minimizing the number of colors used. Now, any arbitrary vertex coloring algorithm could work only for undirected graphs. The dependencies gives rise to a sequence of executable subgraphs $G_{exec}(V',E'_u)$ which only consist of vertices with indegree $0$ and corresponding undirected edges between these vertices. The vertices can only be colored in this sequence and moreover within each subgraph it is intuitive to find maximum size subsets of gates that form independent sets (in the graph). Thus, we propose a framework that performs graph coloring by sequentially extracting large independent sets. To this end, we adopt the learning-based independent set generation technique proposed by Li et al. (2018) and further use a guided beam search approach which makes use of specifically designed metrics that allow selection of suitable independent sets that can reduce the number of colors used. We assess our approach on benchmark quantum circuits comparing it against Qiskit DAG method which converts a given quantum circuit to a directed acyclic graph (DAG) and then find circuit depth as length of longest directed path. This method simply computes depth for the given circuit ordering whereas our method exploits commutativity relations. We could achieve significant depth reduction on all tested instances. Also, a key advantage of the proposed approach is that it reduces circuit depth solely through gate reordering without modifying the circuit functionality or introducing additional gates. One must note that gate reordering alone cannot reduce the depth of every quantum circuit. Nevertheless, the results obtained indicate that many practical circuits contain significant latent parallelism that can be effectively exploited by this commutativity-aware gate reordering approach.