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.
Fields of Study & Subjects
Quantum Computing Algorithms and Architecture
Publication details
- Journal / source
- Quantum
- Publisher
- Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
- Volume
- 10
- Pages
- 1996–1996
- Publication date
- 6 February 2026
- Language
- EN