Planning for Compilation of a Quantum Algorithm for Graph Coloring
This work addresses the compilation challenge for quantum computing, specifically for graph coloring algorithms, but it is incremental as it builds on prior methods for MaxCut.
The authors tackled the problem of compiling quantum algorithms for graph coloring onto near-term quantum processors by extending a temporal planning approach previously used for MaxCut. They showed that their method compares well to analytic upper bounds and that incorporating qubit initialization planning helps find shorter-makespan compilations.
The problem of compiling general quantum algorithms for implementation on near-term quantum processors has been introduced to the AI community. Previous work demonstrated that temporal planning is an attractive approach for part of this compilationtask, specifically, the routing of circuits that implement the Quantum Alternating Operator Ansatz (QAOA) applied to the MaxCut problem on a quantum processor architecture. In this paper, we extend the earlier work to route circuits that implement QAOA for Graph Coloring problems. QAOA for coloring requires execution of more, and more complex, operations on the chip, which makes routing a more challenging problem. We evaluate the approach on state-of-the-art hardware architectures from leading quantum computing companies. Additionally, we apply a planning approach to qubit initialization. Our empirical evaluation shows that temporal planning compares well to reasonable analytic upper bounds, and that solving qubit initialization with a classical planner generally helps temporal planners in finding shorter-makespan compilations for QAOA for Graph Coloring. These advances suggest that temporal planning can be an effective approach for more complex quantum computing algorithms and architectures.