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.

References in corpus (16)

• Quantum Computing in the NISQ era and beyond
• Fault-tolerant quantum computation by anyons
• A variational eigenvalue solver on a quantum processor
• Grover's quantum searching algorithm is optimal
• Synthesis and Optimization of Reversible Circuits - A Survey
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Measurement Optimization in the Variational Quantum Eigensolver Using a Minimum Clique Cover
• Automated optimization of large quantum circuits with continuous parameters
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum arithmetic with the Quantum Fourier Transform
• Instantaneous Quantum Computation
• Efficient evaluation of quantum observables using entangled measurements
• The MQT Handbook: A Summary of Design Automation Tools and Software for Quantum Computing
• Depth optimization of CZ, CNOT, and Clifford circuits
• Sachdev-Ye-Kitaev model on a noisy quantum computer
• Hardness of braided quantum circuit optimization in the surface code