Multilevel Combinatorial Optimization Across Quantum Architectures

Abstract

Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore's law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this paper, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. In order to demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave's quantum annealer and IBM's gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitudes larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution.

References in corpus (6)

• Modularity and community structure in networks
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Benchmark graphs for testing community detection algorithms
• A quantum-classical cloud platform optimized for variational hybrid algorithms
• Network Community Detection On Small Quantum Computers
• Quantum Isomer Search

Cited by in corpus (13)

• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• Many-Qudit representation for the Travelling Salesman Problem Optimisation
• Highly Versatile FPGA-Implemented Cyber Coherent Ising Machine
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• On the Baltimore Light RailLink into the quantum future
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Surrogate Modeling via Factorization Machine and Ising Model with Enhanced Higher-Order Interaction Learning