Quantum-informed graph shrinking improves some optimization benchmarks

A new preprint by Matthew Brunet, Leah Prepchuk and Rebekah Herrman at the University of Tennessee Knoxville proposes a way to simplify network optimization problems before solving them. Called Quantum Enhanced Graph Decomposition, or QEGD, the method uses local correlations from a quantum algorithm to guide the simplification. The reported gains come from numerical experiments, not a demonstration on quantum hardware.

The preprint was submitted to arXiv on November 10, 2026. Its central question is practical: can a problem be made smaller without discarding too much information about its best solution?

The problem with shrinking a graph

The researchers study MaxCut. Given a graph—a collection of vertices joined by edges—the task is to divide its vertices into two groups so that as many edges as possible cross between them. For weighted graphs, the goal is to maximize the total weight of those crossing edges.

The Quantum Approximate Optimization Algorithm, or QAOA, searches for good solutions using a quantum circuit whose parameters are adjusted by a classical optimizer. Larger problems can require more qubits and more demanding circuits. Reducing the graph first offers a way to reduce those requirements.

An existing method, Graph Decomposition for Optimization Algorithm, removes portions of a graph and adjusts the remaining edge weights to account for what was removed. Its key feature is a vertex separator: a set of vertices whose removal disconnects the graph.

When that separator contains at most three vertices, the reweighting can preserve the optimal objective exactly. Larger separators make the calculation more expensive and can introduce approximation errors. QEGD tries to reduce those troublesome separators before applying the older method.

Letting local correlations guide a merge

For a large separator, QEGD examines the separator together with a smaller disconnected component. It uses a single layer of QAOA to estimate correlations between pairs of separator vertices.

A positive correlation suggests that two vertices tend to receive the same assignment in the QAOA state. QEGD treats sufficiently positive correlations as evidence for combining vertices into a single “supernode.” A group merge requires qualifying pairwise correlations throughout the group, rather than merely a chain of qualifying pairs.

This is a heuristic, not proof that the vertices belong together in a globally optimal cut. The method records the merges so that assignments in the reduced problem can later be expanded back to the original vertices.

The quantum label also needs qualification. For the single-layer QAOA calculations used here, closed-form equations can supply the correlations without running a quantum computer. The regular-graph experiments used Qiskit Aer simulation; the comparison with other decomposition methods used analytical expectation values.

Better cuts, with a quality–time trade-off

The authors measure performance using an approximation ratio: the achieved objective relative to the optimum. A value closer to one is better.

In one experiment using 100-vertex graphs where every vertex had five neighbors, the average ratio rose from 0.8309 with the older decomposition method to 0.9301 with QEGD at a merge threshold of 0.2. For six-neighbor graphs, it rose from 0.8009 to about 0.9502. Those are improvements of approximately 9.9 and 14.9 percentage points, respectively.

A separate comparison used random graphs with 20–30 vertices and varying connection probabilities. QEGD produced higher average approximation ratios than QAOA-in-QAOA and ParaQAOA across the tested settings. It slightly exceeded DC-QAOA on sparse graphs, while DC-QAOA performed better on the densest graphs. QEGD nevertheless ran substantially faster than DC-QAOA in these local computer experiments. ParaQAOA remained the fastest method.

Local evidence can make global mistakes

The authors report that roughly 8–11% of merges in a separate 100-vertex analysis produced suboptimal assignments. Local correlations do not necessarily capture the best arrangement of the whole graph.

Larger tests, extending to 800 vertices, also showed declining approximation ratios, particularly for higher-degree graphs. A stricter merge threshold often improved quality, but the results do not establish a universally best setting.

These benchmarks support QEGD as a promising problem-reduction heuristic, not as evidence of superiority over leading classical optimization solvers. The timing comparisons concern the tested implementations on a classical computer. Whether the approach offers a practical advantage on quantum hardware, or transfers successfully to constrained optimization problems, remains unresolved.