Boosting Sparsity in Graph Decompositions with QAOA Sampling

Abstract

We study the problem of decomposing a graph into a weighted sum of a small number of matchings, a task that arises in network resource allocation problems such as peer-to-peer energy exchange. Computing such decompositions is challenging for classical algorithms, even for small instances. To address this problem, we propose E-FCFW, a hybrid quantum-classical algorithm based on the Fully-Corrective Frank-Wolfe (FCFW) algorithm that incorporates a matching-sampling subroutine. We design a QAOA version of this subroutine and benchmark it against classical approaches (random sampling and simulated annealing) on demand graphs derived from complete, bipartite, and heavy-hex topologies. The quantum subroutine is executed using the Qiskit Aer state-vector and MPS simulators and on IBM Kingston hardware (7-111 qubits). On complete and bipartite graphs with 6-10 nodes, E-FCFW with QAOA yields consistently sparser decompositions than the classical baselines, and even beats the best-known solution for one instance. On heavy-hex graphs with 50, 70 and 100 nodes, E-FCFW with QAOA outperforms the other methods in terms of approximation error, demonstrating performance on utility-scale quantum hardware. For the largest graphs (100 nodes) E-FCFW with QAOA performs much better when using MPS circuit simulation, compared to using quantum hardware. This indicates that at this scale, the performance is severely impacted by hardware noise.