Quantum Circuit Optimization by Graph Coloring

Abstract

This work shows that minimizing the depth of a quantum circuit composed of commuting operations reduces to a vertex coloring problem on an appropriately constructed graph, where gates correspond to vertices and edges encode non-parallelizability. The reduction leads to algorithms for circuit optimization by adopting any vertex coloring solver as an optimization backend. The approach is validated by numerical experiments as well as applications to known quantum circuits, including finite field multiplication and QFT-based addition.