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