Researchers at the University of Tennessee Knoxville have developed a new algorithm, the Quantum Enhanced Graph Decomposition (QEGD), that improves the efficiency of solving complex optimization problems with quantum computers. QEGD uses the Quantum Approximate Optimization Algorithm (QAOA) to simplify graphs through a process of local vertex-merging, a technique that demonstrably outperforms the existing Graph Decomposition for Optimization Algorithm (GDOA) on random 5-regular and 6-regular graphs.

Testing on Erdős-Rényi graphs further revealed that QEGD consistently achieved higher average approximation ratios than QAOA and ParaQAOA, and comparable results to DC-QAOA, while significantly reducing computation time, averaging between 0.4% and 5% of DC-QAOA’s wall-clock time.

Quantum-Informed Recursive Algorithms (QIRAs) for Graph Reduction

Classical approaches to graph decomposition for optimization often rely on integer programs, a method hampered by exponentially growing computational demands and the potential introduction of inaccuracies through slack variables. In contrast, the newly proposed Quantum Enhanced Graph Decomposition (QEGD) algorithm uses insights from the Quantum Approximate Optimization Algorithm (QAOA) to guide classical optimization, representing a shift toward quantum-informed recursive algorithms (QIRAs).

This innovative approach uses QAOA as a subroutine specifically for sparsifying graphs through localized vertex-merging, a technique designed to reduce problem complexity. QEGD achieves higher approximation ratios across all tested graphs than GDOA for random 5-regular and 6-regular graphs.

Further testing involved comparing QEGD against other distributed QAOA variants, DC-QAOA and ParaQAOA and the standard QAOA implementation, using sets of Erdős-Rényi (ER) random graphs containing between 20 and 30 nodes. M.B. and L.P. were instrumental in the experiment design and code development, while R.H. contributed to the overall experimental framework. The QEGD code and the experiment graphs used throughout the study are publicly available, promoting reproducibility and further research. All authors contributed to the writing, review and approval of the final manuscript, ensuring a collaborative and rigorous approach to the research.

Graph Decomposition for Optimization Algorithm (GDOA) Limitations

This improvement stems from QEGD’s use of the Quantum Approximate Optimization Algorithm (QAOA) as a subroutine within its graph sparsification process, a departure from GDOA’s reliance on integer programs that can introduce suboptimal solutions due to slack terms. While GDOA tackles graph reduction by solving potentially complex integer programs, QEGD streamlines this process by using QAOA to identify nodes suitable for merging into “supernodes”.

These gains are particularly relevant because QAOA’s accuracy and resource demands often increase with problem size, making effective decomposition important for practical application. The algorithm also exhibited comparable performance to DC-QAOA on denser Erdős-Rényi graphs, suggesting a robust ability to maintain accuracy even as graph connectivity increases.

The algorithm’s design, rooted in Quantum Informed Recursive Algorithms (QIRAs), prioritizes iterative problem reduction using QAOA expectation values to guide the decomposition heuristic. The team’s work builds upon previous efforts in recursive QAOA (RQAOA) and Quantum Informed Recursive Optimization (QIRO), but distinguishes itself by eliminating the need for parallel architecture, complex graph partitioning, or exponential solution reconstruction. QEGD’s simplicity and efficiency are key advantages, potentially making it more accessible and scalable than other quantum-enhanced graph decomposition methods.

The algorithm’s ability to reduce problem size while maintaining solution quality is critical for enabling QAOA to tackle larger and more complex optimization challenges. The researchers emphasize that QEGD is a heuristic, meaning it does not guarantee an optimal solution in all cases. However, the observed improvements in approximation ratios suggest that it provides a valuable trade-off between solution quality and computational cost.

Quantum Enhanced Graph Decomposition (QEGD) Algorithm Design

This performance stems from QEGD’s design, which uses Quantum Informed Recursive Algorithms (QIRA) and utilizes QAOA as a subroutine to guide a heuristic node merge based on expectation values exceeding a threshold, τ. The algorithm’s efficiency in these graph types suggests a potential advantage in scenarios where these structures are prevalent. The method iteratively reduces a problem instance by merging nodes into “supernodes” until the remaining graph reaches a predetermined size, M, suitable for solving with either classical or quantum algorithms.

Once solved, the algorithm assigns values to the original nodes based on their supernode affiliation, effectively reconstructing the solution for the initial, larger problem. This approach prioritizes iterative problem reduction without the computational overhead of more complex decomposition strategies. The core of QEGD’s functionality lies in its use of QAOA expectation values to inform the graph decomposition process.

The algorithm’s design, as detailed in the research, involves a specific process for identifying minimum vertex cuts within a graph, denoted as K. Removing this minimum vertex cut yields disconnected subgraphs, allowing for iterative reduction of the problem’s complexity. This process is then coupled with the QAOA-driven node merging, creating a synergistic approach to graph decomposition. The resulting reduced graph, with fewer vertices, can then be solved using either classical or quantum methods, offering a pathway to tackling larger, more complex optimization problems.

The team’s work builds on the foundation of QIRA principles, refining the approach to achieve improved performance and scalability. The work, led by Matthew Brunet, Leah Prepchuk and Rebekah Herrman of the Department of Industrial and Systems Engineering at the University of Tennessee Knoxville, represents a step toward more efficient quantum optimization techniques. This innovative use of QAOA as a subroutine within a graph decomposition algorithm highlights a promising direction for future research in the field of quantum computing.

QEGD Performance: Approximation Ratios on Erdös-Rényi Graphs

Experiments focused on MaxCut problems reveal that QEGD consistently outperforms GDOA across these graph types, suggesting a refined approach to problem reduction. On sparse Erdős-Rényi graphs, QEGD achieved approximation ratios exceeding those of QAOA and ParaQAOA by over 12% and 15% respectively, while maintaining comparable computational speeds to QAOA. The algorithm aims to reduce this cut set whenever it exceeds three, as GDOA guarantees optimality when the cut set is at or below this threshold, allowing for iterative reduction.

👉 More information
🗞 Quantum-Informed Graph Decomposition
✍️ Matthew Brunet, Leah Prepchuk and Rebekah Herrman (Department of Industrial and Systems Engineering, University of Tennessee Knoxville, USA)
🧠 ArXiv: https://arxiv.org/abs/2611.14180v1

More like this