Boosting Sparsity in Graph Decompositions with QAOA Sampling
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908652293586944 |
|---|---|
| author | Pennington, George Mohseni, Naeimeh Wallis, Oscar Schiavello, Francesca Mensa, Stefano O'Meara, Corey Cortiana, Giorgio Valls, Víctor |
| author_facet | Pennington, George Mohseni, Naeimeh Wallis, Oscar Schiavello, Francesca Mensa, Stefano O'Meara, Corey Cortiana, Giorgio Valls, Víctor |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10657 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Boosting Sparsity in Graph Decompositions with QAOA Sampling Pennington, George Mohseni, Naeimeh Wallis, Oscar Schiavello, Francesca Mensa, Stefano O'Meara, Corey Cortiana, Giorgio Valls, Víctor Quantum Physics 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. |
| title | Boosting Sparsity in Graph Decompositions with QAOA Sampling |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2509.10657 |