Network Community Detection On Small Quantum Computers

Abstract

In recent years a number of quantum computing devices with small numbers of qubits became available. We present a hybrid quantum local search (QLS) approach that combines a classical machine and a small quantum device to solve problems of practical size. The proposed approach is applied to the network community detection problem. QLS is hardware-agnostic and easily extendable to new quantum computing devices as they become available. We demonstrate it to solve the 2-community detection problem on graphs of size up to 410 vertices using the 16-qubit IBM quantum computer and D-Wave 2000Q, and compare their performance with the optimal solutions. Our results demonstrate that QLS perform similarly in terms of quality of the solution and the number of iterations to convergence on both types of quantum computers and it is capable of achieving results comparable to state-of-the-art solvers in terms of quality of the solution including reaching the optimal solutions.

References in corpus (33)

• Modularity and community structure in networks
• Quantum Computing in the NISQ era and beyond
• Quantum information with Rydberg atoms
• A Quantum Approximate Optimization Algorithm
• Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
• High-fidelity quantum logic gates using trapped-ion hyperfine qubits
• High-fidelity two-qubit quantum logic gates using trapped calcium-43 ions
• The European Quantum Technologies Roadmap
• Experimental Demonstration of Blind Quantum Computing
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Nonnegative/binary matrix factorization with a D-Wave quantum annealer
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Efficient universal blind computation
• Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
• Parallel Quantum Computing in a Single Ensemble Quantum Computer
• Blind quantum computation with noise environment
• Experimental realization of a fetching algorithm in a 7 qubit NMR quantum computer
• Building an iterative heuristic solver for a quantum annealer
• Computational speedups using small quantum devices
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
• Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays
• From local to global ground states in Ising spin glasses
• Boosting quantum annealer performance via sample persistence
• The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
• Exploring More-Coherent Quantum Annealing
• Fetching marked items from an unsorted database in NMR ensemble computing
• Multi-Community Detection in Signed Graphs Using Quantum Hardware
• Quantum Speedups for Exponential-Time Dynamic Programming Algorithms

Cited by in corpus (20)

• $XY$-mixers: analytical and numerical results for QAOA
• Multistart Methods for Quantum Approximate Optimization
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Multilevel Combinatorial Optimization Across Quantum Architectures
• Quantum Machine Learning for Finance
• Evaluating Quantum Approximate Optimization Algorithm: A Case Study
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• Partitioning Dense Graphs with Hardware Accelerators
• Effective electromagnetic actions for Lorentz violating theories exhibiting the axial anomaly
• Quantum Local Search with the Quantum Alternating Operator Ansatz
• Impacts of Noise and Structure on Quantum Information Encoded in a Quantum Memory
• Reinforcement-Learning-Based Variational Quantum Circuits Optimization for Combinatorial Problems
• Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
• ELRUNA: Elimination Rule-based Network Alignment
• Ising-Based Louvain Method: Clustering Large Graphs with Specialized Hardware
• NISQ-ready community detection based on separation-node identification
• Multi-Community Detection in Signed Graphs Using Quantum Hardware