Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding

Abstract

Current quantum computing devices have different strengths and weaknesses depending on their architectures. This means that flexible approaches to circuit design are necessary. We address this task by introducing a novel space-efficient quantum optimization algorithm for the graph coloring problem. Our circuits are deeper than the ones of the standard approach. However, the number of required qubits is exponentially reduced in the number of colors. We present extensive numerical simulations demonstrating the performance of our approach. Furthermore, to explore currently available alternatives, we perform a study of random graph coloring on a quantum annealer to test the limiting factors of that approach, too.

7 pages

References in corpus (16)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
• Demonstration of a small programmable quantum computer with atomic qubits
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Validating quantum computers using randomized model circuits
• Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
• Detecting arbitrary quantum errors via stabilizer measurements on a sublattice of the surface code
• Realization of a scalable Shor algorithm
• A case study in programming a quantum annealer for hard operational planning problems
• Coloring random graphs
• Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
• Reachability Deficits in Quantum Approximate Optimization
• Efficient variational simulation of non-trivial quantum states

Cited by in corpus (16)

• Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
• CMOS-compatible Ising and Potts Annealing Using Single Photon Avalanche Diodes
• Quadratic and Higher-Order Unconstrained Binary Optimization of Railway Rescheduling for Quantum Computing
• Understanding domain-wall encoding theoretically and experimentally
• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA
• Circuit Design for $k$-coloring Problem and Its Implementation in Any Dimensional Quantum System
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
• BBQ-mIS: a parallel quantum algorithm for graph coloring problems
• Reverse quantum annealing assisted by forward annealing
• Optimization via Quantum Preconditioning
• Calculating Nash Equilibrium on Quantum Annealers