Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2002.10917 · Frontiers in artificial intelligence and applications

Planning for Compilation of a Quantum Algorithm for Graph Coloring

Do Minh, Wang Zhihui, Bryan O’Gorman, Davide Venturelli, Eleanor Gilbert Rieffel, Jeremy Frank

Published Jan 1, 2020• 14 citations
arXivHTMLPDF

Abstract

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.

DOI
10.3233/faia200363

Related papers

Compiling quantum circuits to realistic hardware architectures using temporal planners

Davide Venturelli, Minh Do, Eleanor Gilbert Rieffel +1 more

Abstract To run quantum algorithms on emerging gate-model quantum hardware, quantum circuits must be compiled to take into account constraints on the hardware. For near-term hardware, with only limited means to mitigate decoherence, it is critical to minimize the duration of the circuit. We investigate the application of temporal planners to the problem of compiling quantum circuits to newly emerging quantum hardware. While our approach is general, we focus on compiling to superconducting hardware architectures with nearest neighbor constraints. Our initial experiments focus on compiling Quantum Alternating Operator Ansatz (QAOA) circuits whose high number of commuting gates allow great flexibility in the order in which the gates can be applied. That freedom makes it more challenging to find optimal compilations but also means there is a greater potential win from more optimized compilation than for less flexible circuits. We map this quantum circuit compilation problem to a temporal planning problem, and generated a test suite of compilation problems for QAOA circuits of various sizes to a realistic hardware architecture. We report compilation results from several state-of-the-art temporal planners on this test set. This early empirical evaluation demonstrates that temporal planning is a viable approach to quantum circuit compilation.

arXiv:1705.08927•Quantum Science and Technology•Dec 20, 2017•140 citations

Temporal Planning for Compilation of Quantum Approximate Optimization Circuits

Davide Venturelli, Minh Do, Eleanor Gilbert Rieffel +1 more

We investigate the application of temporal planners to the problem of compiling quantum circuits to emerging quantum hardware. While our approach is general, we focus our initial experiments on Quantum Approximate Optimization Algorithm (QAOA) circuits that have few ordering constraints and thus allow highly parallel plans. We report on experiments using several temporal planners to compile circuits of various sizes to a realistic hardware architecture. This early empirical evaluation suggests that temporal planning is a viable approach to quantum circuit compilation.

International Joint Conference on Artificial Intelligence•Jul 28, 2017•47 citations

Quantum circuit compilation by genetic algorithm for quantum approximate optimization algorithm applied to MaxCut problem

Lis Arufe, Miguel Ángel González, Angelo Oddi +2 more

The Quantum Circuit Compilation Problem (QCCP) is challenging to the Artificial Intelligence community. It was already tackled with temporal planning, constraint programming, greedy heuristics and other techniques. In this paper, QCCP is formulated as a scheduling problem and solved by a genetic algorithm. We focus on QCCP for Quantum Approximation Optimization Algorithms (QAOA) applied to the MaxCut problem and consider Noisy Intermediate Scale Quantum (NISQ) hardware architectures. Based on the fact that these algorithms apply a set of basic quantum operations repeatedly over a number of rounds, we propose a genetic algorithm approach, termed Decomposition Based Genetic Algorithm (DBGA), that in each round extends the partial solutions obtained for the previous ones. DBGA is compared to the state of the art across a set of conventional instances. The results of the experimental study provided interesting insight in the problem structure and showed that DBGA is quite competitive with the state of the art. In particular, DBGA outperformed the best current method on the largest instances and provided new best solutions to most of them.

Swarm and Evolutionary Computation•Jan 7, 2022•27 citations

Problem-Driven Compilation of Quantum Optimization Algorithms for Graph Coloring

Schulte, Linus

Quantum computing holds the potential to efficiently solve certain problems believed to be intractable for classical computers. Realizing this potential, however, requires substantial physical resources, including large qubit counts, sufficient connectivity, and long coherence times. As current quantum devices are still far from this regime, the efficient compilation of quantum algorithms into hardware-compatible instructions remains a central challenge in quantum computing, especially for near-term applications. A representative example of such applications is combinatorial optimization, where exponentially large search spaces motivate quantum algorithms that leverage interference to approximate solutions more efficiently than classical heuristics, even at modest system sizes. Two prominent paradigms in this context are quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA): Quantum annealing realizes optimization via continuous-time quantum dynamics implemented on analog hardware, while QAOA is a variational, gate-based approach that builds parameterized quantum circuits from problem-specific Hamiltonians. Both paradigms require compilation strategies tailored to the constraints of their respective hardware architectures. Most existing compilation strategies are problem-agnostic and therefore broadly applicable, yet often suboptimal for specific tasks. This thesis uses the graph coloring problem as a case study to investigate a problem-driven approach to quantum compilation, where structural features of the problem class are exploited to design tailored compilation schemes that offer improved efficiency and scalability for the targeted application. To address hardware connectivity constraints, the presented approaches adopt the parity framework, which encodes long-range interactions into single-qubit terms. This thesis develops two novel problem-driven compilation methods for the graph coloring problem, the Bandwidth-Optimized LHZ layout and the 2D-Twine circuit. The former leverages bandwidth minimization to optimize parity encodings for analog quantum annealers, while the latter constructs QAOA unitaries for gate-based optimization using parallelized Parity Twine circuits. Both approaches are benchmarked against general-purpose methods and demonstrate substantial improvements in qubit usage or circuit complexity. These results illustrate the advantages of incorporating problem structure into the compilation process and provide a proof-of-concept for the effectiveness of problem-driven compilation strategies.

•Jan 1, 2025•0 citations

Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation

Do, Minh, Kyle E. C. Booth, Jeremy Frank +3 more

Recently, the makespan-minimization problem of compiling a general class of quantum algorithms into near-term quantum processors has been introduced to the AI community. The research demonstrated that temporal planning is a strong solution approach for the studied class of quantum circuit compilation (QCC) problems. In this paper, we explore the use of methods from operations research, specifically constraint programming (CP), as an alternative and complementary approach to temporal planning. We also extend previous work by introducing two new problem variations that incorporate important characteristics identified by the quantum computing community. We apply temporal planning and CP to the baseline and extended QCC problems as both stand-alone and hybrid approaches. The hybrid method uses solutions found by temporal planning to warm-start CP, leveraging the ability of temporal planning to find satisficing solutions to problems with a high degree of task optionality, an area that CP typically struggles with. These solutions are then used to seed the CP formulation which significantly benefits from inferred bounds on planning horizon and task counts provided by the warm-start. Our extensive empirical evaluation indicates that while stand-alone CP is not competitive with temporal planning, except for the smallest problems, CP in a hybrid setting is beneficial for all temporal planners in all problem classes.

•Jan 1, 2018•69 citations

Toward Quantum Gate-Model Heuristics for Real-World Planning Problems

Tobias Stollenwerk, Stuart Hadfield, Zhihui Wang

Many challenging scheduling, planning, and resource allocation problems come with real-world input data and hard problem constraints, and reduce to optimizing a cost function over a combinatorially defined feasible set, such as colorings of a graph. Toward tackling such problems with quantum computers using quantum approximate optimization algorithms, we present novel efficient quantum alternating operator ansatz (QAOA) constructions for optimization problems over proper colorings of chordal graphs. As our primary application, we consider the flight-gate assignment problem, where flights are assigned to airport gates as to minimize the total transit time of all passengers, and feasible assignments correspond to proper graph colorings of a conflict graph derived instancewise from the input data. We leverage ideas from classical algorithms and graph theory to show our constructions have the desirable properties of restricting quantum state evolution to the feasible subspace, and satisfying a particular reachability condition for most problem parameter regimes. Using classical preprocessing we show that we can always find and construct a suitable initial quantum (superposition) state efficiently. We show our constructions in detail, including explicit decompositions to a universal set of basic quantum gates, which we use to bound the required resource scaling as low-degree polynomials of the input parameters. In particular, we derive novel QAOA mixing operators and show that their implementation cost is commensurate with that of the QAOA phase operator for flight-gate assignment. A number of quantum circuit diagrams are included such that our constructions may be used as a template toward development and implementation of quantum gate-model approaches for a wider variety of potentially impactful real-world applications.

IEEE Transactions on Quantum Engineering•Jan 1, 2020•33 citations
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.
Abstract To run quantum algorithms on emerging gate-model quantum hardware, quantum circuits must be compiled to take into account constraints on the hardware. For near-term hardware, with only limited means to mitigate decoherence, it is critical to minimize the duration of the circuit. We investigate the application of temporal planners to the problem of compiling quantum circuits to newly emerging quantum hardware. While our approach is general, we focus on compiling to superconducting hardware architectures with nearest neighbor constraints. Our initial experiments focus on compiling Quantum Alternating Operator Ansatz (QAOA) circuits whose high number of commuting gates allow great flexibility in the order in which the gates can be applied. That freedom makes it more challenging to find optimal compilations but also means there is a greater potential win from more optimized compilation than for less flexible circuits. We map this quantum circuit compilation problem to a temporal planning problem, and generated a test suite of compilation problems for QAOA circuits of various sizes to a realistic hardware architecture. We report compilation results from several state-of-the-art temporal planners on this test set. This early empirical evaluation demonstrates that temporal planning is a viable approach to quantum circuit compilation.
We investigate the application of temporal planners to the problem of compiling quantum circuits to emerging quantum hardware. While our approach is general, we focus our initial experiments on Quantum Approximate Optimization Algorithm (QAOA) circuits that have few ordering constraints and thus allow highly parallel plans. We report on experiments using several temporal planners to compile circuits of various sizes to a realistic hardware architecture. This early empirical evaluation suggests that temporal planning is a viable approach to quantum circuit compilation.
The Quantum Circuit Compilation Problem (QCCP) is challenging to the Artificial Intelligence community. It was already tackled with temporal planning, constraint programming, greedy heuristics and other techniques. In this paper, QCCP is formulated as a scheduling problem and solved by a genetic algorithm. We focus on QCCP for Quantum Approximation Optimization Algorithms (QAOA) applied to the MaxCut problem and consider Noisy Intermediate Scale Quantum (NISQ) hardware architectures. Based on the fact that these algorithms apply a set of basic quantum operations repeatedly over a number of rounds, we propose a genetic algorithm approach, termed Decomposition Based Genetic Algorithm (DBGA), that in each round extends the partial solutions obtained for the previous ones. DBGA is compared to the state of the art across a set of conventional instances. The results of the experimental study provided interesting insight in the problem structure and showed that DBGA is quite competitive with the state of the art. In particular, DBGA outperformed the best current method on the largest instances and provided new best solutions to most of them.
Quantum computing holds the potential to efficiently solve certain problems believed to be intractable for classical computers. Realizing this potential, however, requires substantial physical resources, including large qubit counts, sufficient connectivity, and long coherence times. As current quantum devices are still far from this regime, the efficient compilation of quantum algorithms into hardware-compatible instructions remains a central challenge in quantum computing, especially for near-term applications. A representative example of such applications is combinatorial optimization, where exponentially large search spaces motivate quantum algorithms that leverage interference to approximate solutions more efficiently than classical heuristics, even at modest system sizes. Two prominent paradigms in this context are quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA): Quantum annealing realizes optimization via continuous-time quantum dynamics implemented on analog hardware, while QAOA is a variational, gate-based approach that builds parameterized quantum circuits from problem-specific Hamiltonians. Both paradigms require compilation strategies tailored to the constraints of their respective hardware architectures. Most existing compilation strategies are problem-agnostic and therefore broadly applicable, yet often suboptimal for specific tasks. This thesis uses the graph coloring problem as a case study to investigate a problem-driven approach to quantum compilation, where structural features of the problem class are exploited to design tailored compilation schemes that offer improved efficiency and scalability for the targeted application. To address hardware connectivity constraints, the presented approaches adopt the parity framework, which encodes long-range interactions into single-qubit terms. This thesis develops two novel problem-driven compilation methods for the graph coloring problem, the Bandwidth-Optimized LHZ layout and the 2D-Twine circuit. The former leverages bandwidth minimization to optimize parity encodings for analog quantum annealers, while the latter constructs QAOA unitaries for gate-based optimization using parallelized Parity Twine circuits. Both approaches are benchmarked against general-purpose methods and demonstrate substantial improvements in qubit usage or circuit complexity. These results illustrate the advantages of incorporating problem structure into the compilation process and provide a proof-of-concept for the effectiveness of problem-driven compilation strategies.
Recently, the makespan-minimization problem of compiling a general class of quantum algorithms into near-term quantum processors has been introduced to the AI community. The research demonstrated that temporal planning is a strong solution approach for the studied class of quantum circuit compilation (QCC) problems. In this paper, we explore the use of methods from operations research, specifically constraint programming (CP), as an alternative and complementary approach to temporal planning. We also extend previous work by introducing two new problem variations that incorporate important characteristics identified by the quantum computing community. We apply temporal planning and CP to the baseline and extended QCC problems as both stand-alone and hybrid approaches. The hybrid method uses solutions found by temporal planning to warm-start CP, leveraging the ability of temporal planning to find satisficing solutions to problems with a high degree of task optionality, an area that CP typically struggles with. These solutions are then used to seed the CP formulation which significantly benefits from inferred bounds on planning horizon and task counts provided by the warm-start. Our extensive empirical evaluation indicates that while stand-alone CP is not competitive with temporal planning, except for the smallest problems, CP in a hybrid setting is beneficial for all temporal planners in all problem classes.
Many challenging scheduling, planning, and resource allocation problems come with real-world input data and hard problem constraints, and reduce to optimizing a cost function over a combinatorially defined feasible set, such as colorings of a graph. Toward tackling such problems with quantum computers using quantum approximate optimization algorithms, we present novel efficient quantum alternating operator ansatz (QAOA) constructions for optimization problems over proper colorings of chordal graphs. As our primary application, we consider the flight-gate assignment problem, where flights are assigned to airport gates as to minimize the total transit time of all passengers, and feasible assignments correspond to proper graph colorings of a conflict graph derived instancewise from the input data. We leverage ideas from classical algorithms and graph theory to show our constructions have the desirable properties of restricting quantum state evolution to the feasible subspace, and satisfying a particular reachability condition for most problem parameter regimes. Using classical preprocessing we show that we can always find and construct a suitable initial quantum (superposition) state efficiently. We show our constructions in detail, including explicit decompositions to a universal set of basic quantum gates, which we use to bound the required resource scaling as low-degree polynomials of the input parameters. In particular, we derive novel QAOA mixing operators and show that their implementation cost is commensurate with that of the QAOA phase operator for flight-gate assignment. A number of quantum circuit diagrams are included such that our constructions may be used as a template toward development and implementation of quantum gate-model approaches for a wider variety of potentially impactful real-world applications.