Hybrid quantum-classical algorithms for approximate graph coloring

Abstract

We show how to apply the recursive quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We compare this proposal to the best known classical and hybrid classical-quantum algorithms. First, we show that the standard (non-recursive) QAOA fails to solve this optimization problem for most regular bipartite graphs at any constant level $p$: the approximation ratio achieved by QAOA is hardly better than assigning colors to vertices at random. Second, we construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs. In particular, these hybrid algorithms give rise to efficient classical algorithms, and no benefit arising from the use of quantum mechanics is to be expected. Nevertheless, they provide a suitable testbed for assessing the potential benefit of hybrid algorithm: We use the simulation algorithm to perform large-scale simulation of level-$1$ QAOA and RQAOA with up to $300$ qutrits applied to ensembles of randomly generated $3$-colorable constant-degree graphs. We find that level-$1$ RQAOA is surprisingly competitive: for the ensembles considered, its approximation ratios are often higher than those achieved by the best known generic classical algorithm based on rounding an SDP relaxation. This suggests the intriguing possibility that higher-level RQAOA may be a potentially useful algorithm for NISQ devices.

27 pages, 5 figures

References in corpus (7)

• A Quantum Approximate Optimization Algorithm
• Warm-starting quantum optimization
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Low depth mechanisms for quantum optimization
• Bridging Classical and Quantum with SDP initialized warm-starts for QAOA

Cited by in corpus (42)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Edge AI: A Taxonomy, Systematic Review and Future Directions
• Challenges and Opportunities in Quantum Optimization
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Quantum variational optimization: The role of entanglement and problem hardness
• Graph neural network initialisation of quantum approximate optimisation
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Quantum-Informed Recursive Optimization Algorithms
• Quantum approximate optimization algorithm for qudit systems
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• A Grover search-based algorithm for the list coloring problem
• Reinforcement Learning Assisted Recursive QAOA
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Data re-uploading with a single qudit
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
• Classification of Hybrid Quantum-Classical Computing
• Characterizing Error Mitigation by Symmetry Verification in QAOA
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers
• Variational Quantum Multi-Objective Optimization
• Noise-Robust End-to-End Quantum Control using Deep Autoregressive Policy Networks
• Recursive Quantum Relaxation for Combinatorial Optimization Problems
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• BBQ-mIS: a parallel quantum algorithm for graph coloring problems
• Twisted hybrid algorithms for combinatorial optimization
• Noise tailoring for Robust Amplitude Estimation
• Inequality constraints in variational quantum circuits with qudits
• Limits of Short-Time Evolution of Local Hamiltonians
• Path Matters: Industrial Data Meet Quantum Optimization
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Optimal Quantum Likelihood Estimation
• QTIS: A QAOA-Based Quantum Time Interval Scheduler
• Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles
• Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
• Q-CHOP: Quantum constrained Hamiltonian optimization
• Synthesis of Single Qutrit Circuits from Clifford+R
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems