  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.
