Network Community Detection On Small Quantum Computers

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 devices as they become available. We apply it to solve the community detection problem on networks of up to 2000 nodes using the 16-qubit IBM quantum device and D-Wave 2000Q. To the best of our knowledge, this is the first gate-model based quantum algorithm capable of tackling networks of this size. We demonstrate a potential for quantum advantage as larger quantum devices become available in future.