Network Community Detection On Small Quantum Computers
arXiv:1810.12484 · doi:10.1002/qute.201900029
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 (11)
- Modularity and community structure in networks
- A Quantum Approximate Optimization Algorithm
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
- A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
- Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
- 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
- Exploring More-Coherent Quantum Annealing
- Multi-Community Detection in Signed Graphs Using Quantum Hardware
Cited by in corpus (20)
- -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