December 1, 2022

Planning for compilation of a QAOA algorithm for Graph Coloring

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 compilation task, specifically, the routing of circuits that implement the Quantum Alternating Operator Ansatz (QAOA) applied to the MaxCut problem on a quantum processor architecture.

Researchers at NASA have extended 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.

They evaluated the approach on state-of-the-art hardware architectures from leading quantum computing companies.

Additionally, they applied a planning approach to qubit initialization. Their empirical evaluation showed that temporal planning compared well to reasonable analytic upper bounds, and that solving qubit initialization with a classical planner generally helped 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.

Read more.