Boosting Sparsity in Graph Decompositions with QAOA Sampling

George Pennington, Naeimeh Mohseni, Oscar Wallis, Francesca Schiavello, Stefano Mensa, Corey O’Meara, Giorgio Cortiana, Víctor Valls · 2025

Read Boosting Sparsity in Graph Decompositions with QAOA Sampling by George Pennington, Naeimeh Mohseni, Oscar Wallis, Francesca Schiavello, Stefano Mensa, Corey O’Meara, Giorgio Cortiana, Víctor Valls (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-10657.txt.

Introduction

Splitting a network's traffic into a few simple lanes is the problem here. George Pennington and seven co-authors tackle it in this 2025 quantum computing paper. Formally, a graph is decomposed into a weighted sum of matchings. The fewer matchings, the better. The task arises in peer-to-peer energy exchange and similar allocation problems. Classical algorithms strain at it, even at small sizes.

Their hybrid algorithm is called E-FCFW. It extends a classical Frank-Wolfe method. A matching sampler, run on a quantum optimizer called QAOA, does the sampling. Benchmarks cover complete, bipartite, and heavy-hex graphs. Runs used simulators and IBM's Kingston quantum hardware, with up to one hundred eleven qubits. On small graphs, the quantum version gave sparser decompositions, again and again. On hundred-node graphs, it gave lower error. One caveat stands out. At the largest scale, hardware noise badly hurt results, compared with simulation.

Catalog record

CREATORGeorge Pennington, Naeimeh Mohseni, Oscar Wallis, Francesca Schiavello, Stefano Mensa, Corey O’Meara, Giorgio Cortiana, Víctor Valls
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-10657

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Boosting Sparsity in Graph Decompositions with QAOA Sampling George Pennington, Naeimeh Mohseni, Oscar Wallis, Francesca Schiavello, Stefano Mensa, Corey O’Meara, Giorgio Cortiana, Víctor Valls Abstract We study the problem of decomposing a graph into a weighted sum of a small number of graph matchings. This problem arises in network resource allocation problems such as peer-to-peer energy exchange, and it is challenging to solve with current classical algorithms even for small instances. To address this problem, we propose a hybrid quantum-classical algorithm, E-FCFW, based on the Fully-Corrective Frank-Wolfe (FCFW) algorithm. In particular, E-FCFW extends FCFW by incorporating a matching-sampling subroutine that can be carried out classically or with a quantum approach. We show how to design such a subroutine using QAOA, which aims at solving a constrained discrete optimisation problem approximately to obtain solution-variety. We benchmark our approach on complete, bipartite, and heavy-hex graphs, conducting experiments using the Qiskit Aer state-vector simulator (9–25 qubits), the Qiskit Aer MPS simulator (52-76 qubits) and on IBM Kingston (52-111 qubits), demonstrating performance at a utility-scale quantum hardware level. Our results show that E-FCFW with QAOA consistently yields sparser decompositions (mean and median) than the other methods (random sampling and simulated annealing) for small complete and bipartite graphs. For large heavy-hex graphs with 50 and 70 nodes, E-FCFW with QAOA also outperforms the other methods in terms of approximation error. Our findings highlight a promising role for quantum subroutines in classical algorithms. I Introduction Quantum optimisation harnesses the principles of quantum mechanics to solve optimisation problems that are beyond the reach of classical algorithms AAA+ 24 . A key example is quantum adiabatic evolution FGGS 00 , which aims to minimise a cost function that is hard to optimise classically (e.g. non-convex, discrete) by encoding its solution as the ground state of a Hamiltonian. These characteristics have generated significant interest in applying quantum optimisation to real-world problems such as portfolio optimisation BBD+ 22 , network design EKC+ 22 , job shop scheduling KPS+ 23 , peer-2-peer energy trading BBC+ 24 and coalition formation MMM+ 24 ; BPW+ 24 . The typical approach in quantum optimisation has been to model a problem of interest and solve it directly using a quantum algorithm GKD 19 ; DPSP 19 . However, the scale of many real-world problems often exceeds the capabilities of current quantum hardware. For instance, practically-relevant instances of Quadratic Unconstrained Binary Optimisations (QUBOs) are usually challenging to solve classically when the number of decision variables is over a hundred thousand GHG+ 21 ; MIP 17 , which is orders of magnitude larger than what today’s quantum computers can handle. An alternative to solving a problem directly with a quantum approach is to use quantum optimisation to carry out a specific subroutine within a classical algorithm. That is, use quantum computing to solve a smaller yet crucial subproblem within a classical algorithm—e.g. computing a gradient in first-order methods Bec 17 . Such an approach is appealing because the subproblem might be smaller than the main optimisation task, making it more suitable for current or near-term quantum computers. Also, by integrating quantum optimisation into the workflow of a classical algorithm, it is possible to tackle a broader range of problems than what purely quantum approaches allow today. In this paper, we explore the use of quantum optimisation to solve a subproblem within a heuristic algorithm designed to solve a combinatorial problem. In short, the mathematical problem consists of decomposing a weighted graph into a small collection of graph matchings (subgraphs where no two edges share a common node), and it is a generalisation of the Birkhoff Decomposition problem for bipartite graphs Bru 82 ; DC 17 . The Birkhoff Decomposition problem is known to be NP-hard when the objective is to find decompositions with the minimum number of matchings DU 16 . Notably, the problem can be computationally challenging for classical algorithms, even for graphs with just 10 nodes KNC+ 25 . The problem is motivated by scheduling problems in networks with operational constraints GOC 24 ; LML+ 15 ; PVT 23 . Fig. 1 shows a toy example of the problem in the context of a power grid, where nodes represent sites (e.g. EVs, battery energy storage systems) and edges represent the possible connections between sites. The weights in the graph indicate the fraction of time a given pair of nodes are willing to be connected, during which they can exchange energy (in either direction), while the matchings correspond to system configurations in which energy can be exchanged in practice (we assume each node can only be connected to at most one other node at a time). Each matching is assigned a weight that corresponds to the fraction of time that a particular system configuration must be utilised for transferring energy. The goal is to decompose the original graph using a small number of matchings since this maximises the amount of energy that can be exchanged. Fig. 2 shows an example of how the graph in Fig. 1 can be decomposed as the sum of four graph matchings. Figure 1: Example of a (complete) demand graph with 6 nodes and 15 edges. The nodes in the graph indicate devices (e.g. EVs), and the edges show the possibility of connecting two nodes to exchange a resource such as energy. The number on each edge (connecting two nodes) indicates the fraction of time two nodes are willing to be connected. Fig. 2 shows how the graph can be decomposed as the sum of four different matchings. Figure 2: Example of how the graph in Fig. 1 can be decomposed as the sum of graph matchings. A matching captures how nodes can exchange resources in practice. The number below each matching indicates the fraction of time each matching should be used to satisfy the demand graph in Fig. 1 The motivation for considering quantum for this problem is twofold. First, algorithms addressing this type of problem typically rely on a subroutine that computes graph matchings, which can be encoded as bitstrings. This encoding aligns well with existing quantum algorithms and is compatible with current quantum devices. The second motivation stems from the observation that classical algorithms often struggle to identify matchings that yield highly sparse decompositions. This issue is illustrated in Fig. 3 for the Birkhoff+ algorithm VIT 21 and bipartite graphs of size n\in\{3,4,\dots,30\} . Observe from the figure that, for a given number of nodes, the algorithm consistently produces decompositions that use approximately the same total number of matchings (green area) regardless of the instance. This behaviour is puzzling, particularly because it happens across all instances and there is a large gap between the solutions found and the best-known solution (red line). Hence the question: how can quantum optimisation help in computing graph matchings? Existing classical algorithms often employ a greedy strategy to identify a single matching with maximum-weight; however, this may not be the most effective approach when the goal is to minimise the number of matchings required to fully decompose a graph. In contrast, quantum algorithms are capable of exploring a broader and more diverse set of solutions, potentially offering better coverage of the solution space. This, however, introduces several challenges such as designing an algorithm

Read the complete text