QAOA Sampling Boosts Sparsity in Graph Decompositions, Enabling Solutions for 25, 76, and 111 Qubit Instances

Decomposing complex networks into simpler components is a fundamental challenge with applications in areas like efficient resource allocation, and particularly relevant to emerging peer-to-peer energy exchange systems. George Pennington, Naeimeh Mohseni, Oscar Wallis, and colleagues at The Hartree Centre STFC, alongside Francesca Schiavello, Stefano Mensa, and Corey O’Meara, now demonstrate a significant advance in tackling this problem. The team developed a new algorithm, E-FCFW, which combines classical optimisation techniques with the power of quantum computation, specifically utilising a QAOA-based approach to generate diverse potential solutions. Through extensive simulations on various graph types and utilising both standard and quantum simulators, including Kingston, the researchers show that E-FCFW consistently achieves sparser network decompositions and reduced approximation errors compared to existing methods, suggesting a promising pathway for integrating quantum subroutines into practical classical algorithms.

Sparse Graph Decomposition via Quantum Sampling

This research investigates methods for decomposing graphs into a small number of graph matchings, a problem relevant to network resource allocation and combinatorial optimisation. Current decomposition approaches often produce dense results, limiting their practical use. The team develops a novel method leveraging the Quantum Approximate Optimisation Algorithm, or QAOA, to identify sparse decompositions, effectively reducing the number of edges within the resulting matchings. Results demonstrate that this QAOA-based sampling method achieves significant improvements in sparsity compared to classical algorithms, particularly for larger graphs, indicating more efficient resource allocation.

The team also proposes a hybrid quantum-classical algorithm, E-FCFW, for solving this problem. E-FCFW builds upon the Fully-Corrective Frank-Wolfe algorithm by incorporating a matching-sampling subroutine that can be implemented either classically or with a quantum approach using QAOA. Experiments on complete, bipartite, and heavy-hex graphs demonstrate the potential of this hybrid approach.

Heavy-Hex Graph Decomposition via Quantum Algorithms

This work explores the application of quantum algorithms to decompose graphs with a heavy-hex topology, a structure relevant to quantum error correction. The team compares the performance of several algorithms, including a classical method, FCFW, an enhanced version, E-FCFW, which incorporates quantum algorithms, and the Quantum Approximate Optimisation Algorithm, or QAOA. Experiments were conducted on graphs of increasing size, 50, 70, and 100 nodes, and performance was assessed using both quantum hardware and classical simulation. Results indicate that algorithm performance varies with graph size.

For smaller graphs, 50 and 70 nodes, E-FCFW, when combined with Matrix Product State simulation, performs best, with QAOA also showing reasonable performance. However, for 100-node graphs, E-FCFW with Simulated Annealing sampling becomes the most effective algorithm. QAOA performs poorly on these larger graphs, likely due to increased hardware noise and the resulting errors in deeper quantum circuits. The team suspects that increased circuit depth explains this performance decline, and that the use of Matrix Product State simulation for smaller graphs allowed for better performance, suggesting that quantum hardware introduces errors that hinder algorithm performance.

Sparser Graph Decomposition via Quantum Enhancement

This research presents a new approach to decomposing graphs into weighted sums of matchings, a problem with applications in network resource allocation. The team developed a hybrid quantum-classical algorithm, E-FCFW, which extends an existing classical method by incorporating a subroutine powered by the Quantum Approximate Optimisation Algorithm, or QAOA. This allows the algorithm to explore a wider variety of potential matchings during the decomposition process. Experiments conducted on complete, bipartite, and heavy-hex graphs demonstrate that E-FCFW, when utilising QAOA, consistently achieves sparser decompositions than traditional methods for smaller graphs, indicating improved efficiency.

Notably, simulations using the Matrix Product States method yielded better results than execution on current quantum hardware, suggesting that hardware noise remains a limiting factor. The researchers observed that performance diminished with 100-node graphs, and acknowledge that further investigation is needed to fully understand this limitation. Future research directions include refining parameter strategies for QAOA, exploring deeper quantum circuits, and investigating post-processing techniques for selecting matchings within the algorithm, aiming to improve performance and address current limitations.