WorksPhysics and Astronomy
Max-Cut QAOA on Non-Hardware-Native Graphs via MinLA Surrogates and Configuration Recovery
Abstract
For non-hardware-native MAX-CUT instances, the Quantum Approximate Optimization Algorithm (QAOA) can incur additional two-qubit depth overhead due to SWAP-based routing of interactions between non-adjacent qubits. We propose a hybrid quantum–classical workflow that reduces this depth by selectively removing interactions and subsequently recovers solution quality through classical optimization of the original MAX-CUT objective. We employ a Minimum Linear Arrangement (MinLA)-based vertex ordering to preferentially retain short-range interactions, thereby constructing a two-qubit depth-reduced surrogate QAOA ansatz. To compensate for the information lost through interaction removal, we develop classical recovery strategies that refine QPU-sampled bitstrings directly on the original MAX-CUT objective. We develop two recovery strategies: signed-residue-based local search and bipartite-block optimization, where each conditional block problem is solved exactly using an – minimum cut. Recovery is performed independently on each sampled configuration, ensuring monotonic improvement in cut value without additional QPU executions. We evaluate the workflow on ibm\_kingston for 120 distinct non-hardware-native instances comprising -regular and Erdős–Rényi graphs with 40, 60 and 100 vertices. We verify that the surrogates substantially reduce transpiled two-qubit depth while staying within the prescribed two-qubit depth, and with recovery yield near-optimal cuts on the original graphs. These results demonstrate the potential of hardware-aware interaction selection and classical recovery to extend QAOA to graph instances whose full cost Hamiltonians exceed practical circuit-depth budgets.
Introduction
Many combinatorial optimization problems admit natural graph-based formulations, in which the objective is to identify a configuration that optimizes a function defined over the graph. The Quantum Approximate Optimization Algorithm (QAOA) [1] is a hybrid quantum–classical algorithm for approximately solving such problems, with particular relevance to near-term quantum hardware. QAOA prepares parameterized quantum states through alternating evolutions under a problem-specific cost Hamiltonian and a mixer Hamiltonian, with the parameters optimized through a classical feedback loop. In this work, we focus on MAX-CUT, an NP-hard and APX-hard problem that seeks a vertex partition into two disjoint sets so as to maximize the number of edges crossing between them.
For MAX-CUT, each graph edge corresponds to a two-qubit interaction in the QAOA cost Hamiltonian. As a result, the structure of the input graph directly determines the interactions that must be executed on quantum hardware. So MAX-CUT directly exposes the mismatch between a dense problem graph and the sparse coupling map of a superconducting quantum processor. Interactions between uncoupled qubits must be routed with SWAP gates, inflating the two-qubit depth [2, 3]. For the 100-vertex, 910-edge graph of Figure 1, the QAOA cost layer by itself requires a two-qubit depth of only 62. However, mapping the circuit onto the sparse coupling map of ibm_kingston requires many additional SWAP gates to realize non-local interactions, increasing the depth to 255. The resulting increase in circuit depth amplifies the effect of hardware noise, often overwhelming any benefit obtained from executing the full problem Hamiltonian.
Figure 1. Connectivity-induced depth inflation for the QAOA cost Hamiltonian circuit of the HAMLIB instance gnp-k_4_n-100_rinst-00. Although the 910 edge interactions require a two-qubit depth of only 62, implementing the same circuit on the sparse coupling map of ibm_kingston increases the depth to 255 because of the additional SWAP operations needed to route non-local interactions. The resulting increase in noise can negate the benefit of executing the full problem Hamiltonian, motivating hardware-aware reductions that preserve useful problem structure while remaining executable on current superconducting processors.
Earlier experimental studies on MAX-CUT investigated graphs with up to 23 and 40 vertices [2, 4]. More recent experiments involving over 100 qubits have explored two contrasting approaches. In [5], the authors execute a standard QAOA cost layer, incorporating error suppression and greedy bit-flip post-processing, on 3- and 5-regular graphs with up to 156 vertices. These instances remain relatively sparse, with the largest containing 390 edges. In contrast, [6] reduces circuit depth by retaining only interactions along a single path through the graph, limiting the executed Hamiltonian to at most interactions. Dense graphs present a different challenge. As illustrated in Figure 1, executing the full cost Hamiltonian can require excessive two-qubit depth, while restricting interactions to a single path may discard more of the original graph structure than necessary. In particular, current superconducting hardware may support circuits containing substantially more than interactions within a feasible depth budget. The objective is therefore to retain as much of the original graph structure as possible without exceeding the circuit-depth budget of the target hardware.
On sparsely connected quantum processors, non-local interactions can require costly routing, whereas their contributions to a cut can be evaluated classically at low cost. We exploit this asymmetry by reordering graph vertices to favor shorter-range interactions and selecting a subset for quantum execution based on the resulting transpiled circuit depth. Unlike hardware-aware compilation [3, 7] and graph sparsification with cut-approximation guarantees [8], our approach explicitly uses the transpiled depth on the target device to guide interaction selection. However, removing interactions modifies the cost Hamiltonian, potentially changing its optimal solutions. We therefore refine the sampled configurations classically against the original MAX-CUT objective. This motivates our central question: how can we select interactions under a hardware depth budget while retaining sufficient problem structure to recover high-quality solutions to the original problem?
We propose a hybrid quantum–classical workflow (Figure 2) that prioritizes quantum circuit depth while preserving the ability to obtain high-quality solutions to the original MAX-CUT problem. The workflow first constructs a surrogate Hamiltonian by selecting a subset of interactions that can be executed within a prescribed depth budget. QAOA is then executed using this surrogate Hamiltonian to generate candidate configurations. For the graph instances considered in this work, QAOA angles are selected using existing classical methods [9], avoiding iterative QPU-based parameter training. However, this is an experimental choice rather than a requirement of the framework, which remains compatible with QPU-based variational optimization, as considered in [5]. The top- sampled configurations are subsequently refined independently and in parallel through classical optimization of the original MAX-CUT objective, and the best recovered solution is returned.

Figure 2. Principle of the proposed hybrid quantum–classical workflow. A depth-constrained surrogate reduces the quantum workload, while the top- sampled configurations are refined independently and in parallel against the original MAX-CUT objective. Green and blue denote classical and quantum processing, respectively.
The main contributions of this paper are enlisted below:
Hardware-native surrogate construction: We reorder vertices using minimum linear arrangement (MinLA) to concentrate interactions between nearby vertices and retain a diagonal band of interactions in the reordered graph. The resulting surrogate Hamiltonian preserves substantially more of the original problem structure than a chain while remaining compatible with hardware connectivity constraints. The construction interpolates
between the two extremes above: under a path-following ordering, a band of radius one reduces to a chain, while a band as wide as the bandwidth recovers the full cost Hamiltonian. Every executed interaction belongs to the original Hamiltonian, and every decision variable is retained.
Depth-budgeted surrogate selection: We choose the widest executable interaction band whose transpiled -layer circuit remains below a device-specific depth budget , while ensuring that every vertex retains at least one incident interaction. This directly couples surrogate-graph construction to the capabilities of the target hardware.
Configuration Recovery for MAX-CUT: Motivated by configuration recovery mechanism in sample-based quantum diagonalization (SQD) [10], we propose two configuration recovery algorithms that operate directly on discrete assignments rather than through subspace diagonalization. (a) Greedy Signed-residue recovery: First, we propose a greedy procedure that flips single vertices whose signed residue on the full graph is positive, increasing the cut monotonically. (b) Bipartite-block recovery: To circumvent the local optima of single-vertex flips, we propose a multi-vertex update policy that re-optimizes the union of two colour classes with the rest of the assignment fixed. The bipartite structure of each block reduces this conditional problem to an – minimum cut [11].
Parallel recovery from a single QPU execution: For statistical accuracy, we perform independent recovery runs on each of the top- sampled QPU bitstrings. These runs share no state, so they execute in parallel on classical processors, and the best recovered cut is returned without further QPU calls.
Experimental Evaluation on Quantum Hardware: We evaluate the workflow on a combined total of 120 non-hardware-native 6-regular and Erdős–Rényi () instances from HAMLIB [12], with up to 100 vertices, using the 156-qubit IBM Heron r2 processor ibm_kingston. Our results demonstrate that selecting interactions under a hardware-specific circuit-depth budget allows reduced QAOA circuits to retain more of the original graph structure than chain-based reductions. Combined with classical recovery, this enables high-quality solutions to be obtained for the original MAX-CUT instances without executing their full cost Hamiltonians.
The proposed workflow illustrated in Figure 2 naturally aligns with futuristic hardware improvements: as lower-noise processors support deeper circuits, increasingly larger interaction bands can be executed, allowing surrogate Hamiltonians to capture more of the original problem structure and extending the range of non-hardware-native optimization problems that can be addressed.
The remainder of the paper is organized as follows. § 2 reviews the QAOA formulation, parameter-selection strategy, and hardware-aware compilation methods used in this work. § 3 presents the construction of hardware-feasible surrogate Hamiltonians through MinLA-based vertex ordering and depth-constrained interaction filtering. § 4 introduces the proposed configuration-recovery procedures for restoring information omitted during quantum execution. § 5 evaluates the complete workflow on non-hardware-native MAX-CUT instances using IBM quantum hardware, and § 7 concludes with a discussion of implications and future directions.
Background and Preliminaries
We consider an undirected, unweighted graph with vertices. The MAX-CUT problem seeks a bipartition of the vertices that maximizes the number of edges crossing the partition. Assigning a binary variable to each vertex, the cut objective is
Using , where , and replacing each spin variable with the Pauli-Z operator, the corresponding cost Hamiltonian is
The Quantum Approximate Optimization Algorithm (QAOA) [1] alternates evolution under the cost Hamiltonian and the mixer Hamiltonian . The -layer QAOA state is
where , , and denotes the variational parameters. Each cost layer comprises commuting two-qubit interactions, whose implementation depth depends on the hardware connectivity and compilation strategy. Further details on the QAOA formulation, parameter-selection methods, and connectivity-aware compilation are detailed in Appendix A.
Depth-Constrained Interaction Filtering
The techniques described in Appendix A.3 reduce routing overhead during circuit compilation. However, for dense graphs, compilation alone may not be sufficient to make QAOA circuits practical on current hardware. As illustrated in Figure 1, routing full problem Hamiltonians can increase the two-qubit depth many folds, leading to a degradation in the quality of the sampled solutions. To improve the hardware feasibility of such instances, we reduce the interaction set before circuit synthesis and modify the optimisation Hamiltonian.
Graph reordering provides a natural basis for such interaction reduction. Classical graph-layout methods, including bandwidth minimization and Minimum Linear Arrangement (MinLA), seek vertex orderings that reduce the separation between interacting vertices [13]. Efficient heuristics, including multilevel approaches, have been developed for obtaining low-cost linear arrangements [14]. In the context of QAOA, graph sparsification has also been investigated to reduce implementation complexity while approximately preserving cut values [8].
Our choice of MinLA is motivated by the path-based routing strategies employed on the near-linear hardware coupling graph of Heron architectures [3]. In such arrangements, interactions between distant vertices can incur additional routing overhead. By minimizing the cumulative separation between interacting vertices, MinLA encourages the concentration of non-zero entries along the first few superdiagonals of the reordered adjacency matrix, providing a natural basis for identifying short-range interactions. This allows a larger fraction of the original graph to be retained within a fixed interaction radius, producing a more informative surrogate Hamiltonian under the same hardware depth budget.
In this section, we describe how we exploit this structure to construct a band-limited interaction graph, preferentially retaining interactions near the diagonal while discarding longer-range ones. Unlike conventional graph reordering, which preserves all edges, our approach explicitly reduces the interaction set. Rather than imposing a fixed sparsification ratio or a cut-approximation constraint, we select the largest interaction radius satisfying two requirements: every vertex must retain at least one incident edge, and the transpiled two-qubit depth of the resulting -layer QAOA circuit must remain below a prescribed hardware depth budget . This budget reflects the practical requirement that circuit depth remain low enough to limit the impact of accumulated hardware noise.
MinLA-Based Interaction Ordering
The objective of the proposed workflow is not merely to reduce the number of interactions, but to retain as much of the original graph structure as possible subject to a hardware depth budget. To achieve this, we seek a vertex ordering that places many interacting vertex pairs close together. Such an ordering allows subsequent interaction filtering to preserve a larger fraction of the original graph while maintaining a low circuit depth. This motivates our use of the Minimum Linear Arrangement (MinLA) problem.
Let denote the adjacency matrix of the graph . A linear arrangement is defined as a bijection that assigns each vertex a distinct position. The MinLA problem identifies an ordering that minimizes the cumulative distance between adjacent vertices,
Unlike bandwidth minimization strategies like Reverse Cuthill-Mckee [15, 16] used in the context of QAOA [17], which penalizes the largest individual edge span, MinLA minimizes the sum of all edge spans. Since finding an optimal arrangement is NP-hard, we implement the heuristic proposed in [14] to obtain low-cost orderings. Let denote the MinLA ordering. The corresponding adjacency matrix is obtained by applying the same permutation to its rows and columns,
As mentioned previously, the superdiagonals of provide a natural representation of interaction span. An entry on the th superdiagonal represents an edge whose endpoints are separated by positions in the linear arrangement. Denoting the number of nonzero entries on this superdiagonal by , the arrangement cost is . Minimizing this quantity encourages the concentration of interactions along the first few superdiagonals, thereby favoring shorter interaction spans. This property motivates restricting the QAOA cost Hamiltonian to interactions lying within a narrow diagonal band, as illustrated in Figure 3. The adjacency matrices of the 200-vertex HAMLIB 6-regular and graphs [12] are displayed in their original, RCM, and MinLA vertex orders. We can clearly observe that MinLA places more edge entries close to the main diagonal than RCM, especially at short spans. Consequently, a larger fraction of the original interactions can be preserved when only a limited interaction radius is retained.
Figure 3. Original, RCM and MinLA vertex ordering of HAMLIB instances of (a) a 6-regular graph and (b) a graph.
Depth-Constrained Selection of Interactions
For a given ordering , we construct a reduced interaction graph by retaining edges whose spans do not exceed an integer radius ,
Equivalently, contains the original interactions represented within the first superdiagonals and their symmetric subdiagonals. Since , increasing progressively restores interactions from the original graph. The choice of determines the tradeoff between information retention and hardware cost: larger values preserve more interactions from the original graph, but generally increase routing overhead and circuit depth. An excessively narrow band may isolate vertices, leaving their associated variables absent from the surrogate cost Hamiltonian. To avoid this, we mandate every vertex to retain at least one incident edge. Assuming that contains no isolated vertices, the smallest radius satisfying this condition is
Equivalently, (7) can be expressed as,
where denotes the neighborhood of vertex in . This establishes the minimum admissible interaction radius, ensuring that every decision variable participates in the reduced optimization problem. Preserving vertex participation alone, however, does not guarantee that the resulting QAOA circuit can be executed within the available hardware constraints. We therefore impose an additional condition on the transpiled two-qubit circuit depth.
Let denote the two-qubit depth of a -layer QAOA circuit constructed using and transpiled for the target hardware under a fixed compilation configuration. Let denote the maximum edge span under the chosen ordering. Then, given a prescribed depth cutoff , we select the radius
The integer depends on the QAOA depth as well as the hardware depth limit . Increasing generally increases the circuit depth, potentially requiring a smaller interaction radius to satisfy the same budget. Moreover, although the retained edge sets are nested, the transpiled depth need not vary monotonically with due to compilation heuristics. We therefore select the largest feasible radius among the evaluated candidates, rather than assuming a monotonic relationship between interaction count and compiled depth. For each candidate radius, the corresponding QAOA circuit is constructed and evaluated using the hardware-aware compilation pipeline described in Section A.3. The resulting hardware-feasible surrogate Hamiltonian is given by
The fraction of interactions retained from the original graph is determined jointly by the graph structure, QAOA depth, and hardware depth budget, rather than by a prescribed sparsification ratio,
To examine the influence of vertex ordering on this edge retention fraction, Figure 4 compares the cumulative retention fraction for MinLA and RCM orderings for the representative graphs in Figure 3. We observe that MinLA exhibits substantially greater retention at smaller interaction radii. At , MinLA retains 43.5% of the edges compared with 11.2% for RCM on the 6-regular graph, and 21.3% compared with 10.0% on the graph. Moreover, MinLA reaches the minimum radius required to avoid isolated vertices at smaller values of in both instances. These observations support the use of MinLA for concentrating interactions within narrow diagonal bands. Equivalently, for any target edge-retention ratio, MinLA often achieves that ratio with a smaller interaction radius than RCM. This is advantageous for hardware-constrained QAOA because a smaller radius generally leads to lower routing overhead and hence lower circuit depth, while preserving the same fraction of the original graph structure. However, minimizing the cumulative edge span does not guarantee greater retention at every radius, and the retention curves may intersect at larger values of .
Figure 4. Cumulative edge retention as a function of the interaction radius for MinLA and RCM vertex orderings of (a) a 6-regular graph and (b) a graph.
From Surrogate Hamiltonians to Original-Graph Solutions
The surrogate Hamiltonian is not intended to replace the original optimization problem. Rather, it provides a hardware-feasible approximation that retains a substantial fraction of the original graph structure while satisfying the depth constraints of the target quantum processor. As shown in the previous subsections, the combination of MinLA reordering and band-limited interaction selection preserves significantly more interactions than aggressively reducing the graph. Consequently, solutions sampled from the surrogate Hamiltonian can still capture important structural information about the original MAX-CUT instance.
However, the surrogate Hamiltonian does not contain every edge of the original graph. The omitted interactions do not participate in the quantum evolution and therefore do not influence the objective optimized during circuit execution. As a result, a bitstring that performs well on the surrogate Hamiltonian need not be optimal with respect to the full graph, since some interactions were never considered during quantum execution. The discrepancy arises not because the surrogate represents a different optimization problem, but because it only captures part of the original objective.
Let denote the set of retained interactions and denote the omitted interactions. The original MAX-CUT objective can then be decomposed as
where the first term is represented in the surrogate Hamiltonian and influences the quantum state preparation, while the second term corresponds to interactions that were excluded to satisfy the hardware depth constraint. Note that for this study we take .
The role of the quantum stage is therefore to identify promising regions of the solution space using an executable approximation of the original problem. The omitted interactions are subsequently reintroduced during a classical recovery phase, which evaluates and refines candidate solutions against the complete graph. In this way, the surrogate Hamiltonian provides a hardware-feasible starting point for optimization, while recovery accounts for the information that was incorporated in the hardware tailored quantum circuit or was corrupted from noise during quantum execution.
The next section develops recovery procedures that exploit the candidate bitstrings generated by the surrogate Hamiltonian and improve them with respect to the full MAX-CUT objective.
Configuration Recovery for MAX-CUT
The MAX-CUT objective is a sum of edge contributions, making changes in the status of incident edges a natural basis for refining sampled configurations. We use this structure to develop two classical recovery procedures that explore different neighborhoods of a configuration, accepting an update only when it increases the full-graph objective .
We rank the distinct QPU-sampled configurations by their values of and select the highest-scoring configurations as recovery seeds. Let denote this set, or all distinct samples if fewer than are available. For a recovery procedure , the returned assignment is
Because each trajectory retains its initial assignment unless an improvement is found,
The trajectories are independent and can run in parallel on classical processors without further QPU calls.
Signed Vertex Residues
Flipping a vertex changes the cut status of every incident edge: previously uncut edges become cut, while previously cut edges become uncut. An improving move must therefore balance both contributions. For a vertex , we define
where and count its incident uncut (bad) and cut (good) edges, respectively. We note that the neighborhood is taken in the original graph, so the gain accounts for both retained and omitted interactions. The signed vertex residue is
Since only edges incident on change their cut status, this residue is the gain obtained from flipping ,
where is the binary unit vector at and denotes component-wise addition mod 2. Thus, identifies a strictly improving single-vertex move. This identity applies to a single flip at the current assignment; gains must be updated after a move and cannot generally be added to assess simultaneous flips of adjacent vertices.
Greedy Signed-Residue Recovery
We first propose a greedy recovery using signed vertex residues to perform a steep ascent on the full-graph cut. At every iteration, vertices are ranked by the residues calculated from the QPU-sampled configuration, and the highest-ranked vertex is flipped if its residue is positive. After an accepted flip, the residues must be updated to reflect the new configuration before selecting the next move. Since flipping vertex changes only its incident edges, only the residues of and its neighbors are affected. The following lemma gives an incremental update that avoids recomputing residues over the full graph. The proof is outlined in Appendix § 10.§ 1.
Lemma 1 (Local residue update). Let be the QPU-sampled configuration, and be the configuration obtained by flipping the assignment of vertex . The signed vertex residues satisfy
The algorithm terminates when no improving single-vertex move remains or when flips have been accepted. This is outlined in Algorithm 1 for one seed; recovery trajectories are run independently for all . The relation between signed residue and cut gain yields two guarantees: accepted moves improve the objective, and the bounded, integer-valued objective limits how many such moves can occur.
Theorem 1 (Monotonicity). Suppose Algorithm 1 accepts flips, and let denote the configuration after accepted flips, with the initial configuration. Then
Consequently, the returned configuration satisfies
with equality if and only if , regardless of whether recovery terminates because no improving flip remains or because the flip budget is exhausted.
Algorithm 1 Greedy signed-residue recovery
Require: Original graph $G=(V,E)$, initial configuration $\mathbf{x}^{(0)}$, flip budget $F_{\max}$
Ensure: Refined configuration $\mathbf{x}$
1: $\mathbf{x}\leftarrow\mathbf{x}^{(0)}$
2: Compute $\rho_i\leftarrow B_i(\mathbf{x})-G_i(\mathbf{x})$ for all $i\in V$
3: for $f=1,\ldots,F_{\max}$ do
4: $i^\star\leftarrow\arg\max_{i\in V}\rho_i$ ▷ Break ties by a fixed vertex order
5: if $\rho_{i^\star}\le 0$ then
6: break
7: end if
8: for $j\in N_G(i^\star)$ do
9: $\rho_j\leftarrow\rho_j-2(1-2\mathbf{1}[x_{i^\star}\ne x_j])$
10: end for
11: $\rho_{i^\star}\leftarrow-\rho_{i^\star}$
12: $x_{i^\star}\leftarrow1-x_{i^\star}$
13: end for
14: return $\mathbf{x}$
The proof is outlined in Appendix § 10.§ 2. The strict improvement of the cut objective ensures that greedy recovery cannot continue indefinitely. The following result characterizes its termination and the condition under which the returned configuration is locally optimal. The proof is detailed in Appendix § 10.§ 3.
Theorem 2 (Finite termination and local optimality). Starting from an initial configuration , Algorithm 1 accepts at most
flips. Furthermore, if the returned configuration satisfies , then it is a one-flip local optimum of the original MAX-CUT objective.
Corollary 1 (Cut guarantee at local optimality). If is a one-flip local optimum, then
where denotes the optimal MAX-CUT value.
The proof is presented in Appendix § 10.§ 4. The above guarantee holds independently of the initial configuration and follows solely from the classical local-optimality condition. If recovery terminates upon exhausting , monotonic improvement is still guaranteed, but local optimality cannot be asserted without checking the final residues.
Limitations of Single-Vertex Recovery
Although greedy signed-residue recovery guarantees monotonic improvement, restricting updates to individual vertices can cause the algorithm to terminate at a suboptimal configuration. In particular, the absence of an improving single-vertex flip does not preclude an improvement through simultaneous changes to multiple assignments.
For example, consider the five-vertex graph illustrated in Figure 5. For the initial configuration , the cut value is , with signed residues .
Figure 5. (L) The initial configuration is a one-flip local optimum with cut value 4. (R) Simultaneously flipping vertices 2 and 3 produces the globally optimal cut of value 5. Blue and red vertices indicate the two partitions, while solid and dashed edges represent cut and uncut edges, respectively.
As shown in Table 1, every possible single-vertex flip yields a nonpositive gain. Consequently, strict greedy recovery terminates at this one-flip local optimum. However, simultaneously flipping vertices 2 and 3 produces the configuration
| Vertex | Gain | |
| 0 | 3 | |
| 1 | 2 | |
| 2 | 3 | |
| 3 | 0 | 4 |
| 4 | 0 | 4 |
Table 1. Effect of single-vertex flips on the initial configuration , with .
, increasing the cut value to . This is globally optimal, since the graph contains a triangle and hence at least one of its six edges must remain uncut.
This example illustrates that strict single-vertex ascent can become trapped at a local optimum, requiring coordinated flips wherein a subset of vertices is optimized jointly to yield a better solution. This motivates the block-based recovery strategy developed in the subsequent subsection.
Bipartite-Block Recovery via Minimum Cuts
Jointly optimising an arbitrary block (subset) of vertices while keeping the remaining assignments of the remaining vertices fixed itself can be computationally difficult, as the resulting subproblem may have the same complexity as MAX-CUT. To overcome this limitation, we construct bipartite blocks for which the conditional optimization can be transformed into an – minimum-cut problem [11]. We derive the reduction step by step below.
Construction of Bipartite Blocks.
First, we do a greedy vertex coloring of the original graph , yielding disjoint color classes
where vertices belonging to the same color class are non-adjacent. For each pair of distinct color classes, we define
This coloring remains fixed throughout recovery, providing candidate blocks that can be reused across all QPU-sampled configurations. Since every edge joining vertices in must connect the two distinct color classes, the induced graph is bipartite. This bipartite structure, as we show subsequently, provides a useful basis for simplifying the conditional optimization.
Conditional optimization.
We consider a bipartite block and its complement . Given the current configuration , we seek an assignment that maximizes the cut value of the original graph while keeping the assignments outside fixed, i.e.,
To express the above objective in terms of optimisation variables, we partition the edge set into three categories: edges internal to , edges internal to , and edges connecting the two. Since the exterior assignments remain fixed, edges entirely within contribute a constant and can be omitted from the optimization. The resulting conditional objective is
The first term in (27) captures the cut contribution of edges within the block, whereas the second term accounts for edges connecting the block to its fixed exterior. Both contributions must be considered jointly, since improving the internal cut may come at the expense of boundary edges. We next show how each term can be transformed so that their joint optimization reduces to a tractable form.
Step 1: Transforming internal interactions: We consider the first term in (27). Since is bipartite, its vertices can be assigned reference labels according to their color classes:
We do a transformation of variable,
where denotes binary XOR. This transformation complements the assignments on one side of the bipartition. To see what this variable is meant to do, consider an internal edge . Since its endpoints belong to different color classes, we have that , i.e., . Therefore,
Cutting an internal edge becomes agreeing across that edge in the transformed variables,
Summing over all internal edges yields,
Thus, after dropping the constant , maximizing the internal cut is equivalent to minimizing disagreements between the transformed variables . In particular, each internal edge now contributes a non-negative penalty whenever its endpoints receive different transformed labels.
Step 2: Transforming boundary interactions: We consider the second term in (27). Unlike internal edges, each boundary edge connects a variable vertex to a vertex whose assignment is fixed. Consequently, its contribution depends only on the chosen assignment of . For each , we define the boundary reward in terms of the transformed variable . Since assigning corresponds to the original assignment , the number of boundary edges cut is
Here, counts cut weight contributed by edges from to the fixed outside vertices. Since our objective is to maximize the boundary reward, we convert it into an equivalent non-negative minimization cost. For each vertex, we define,
The unary penalties represent the loss in boundary reward relative to the maximum reward attainable by vertex individually. Hence,
Combining the transformed internal interactions in Eq. (32) with the boundary penalties, the conditional MAX-CUT objective can be expressed as
where
Since the remaining terms are independent of , maximizing the conditional cut is equivalent to minimizing .
Step 3: Reduction to an minimum cut: In this step, we show how the minimization in (38) is solved. The pairwise penalties take the form and satisfy the binary submodularity condition, i.e., the combined cost of the two equal-label assignments must not exceed the combined cost of the two unequal-label assignments.
Together with the unary penalties, the resulting energy admits an exact minimum-cut representation [11]. We construct a flow network containing one vertex for each , together with a source and a sink . For each vertex , we introduce two directed edges with capacities,
For every internal edge , we introduce two oppositely directed edges, and , each with unit capacity. An cut partitions the vertices of the flow network into two sets, one containing the source and the other containing the sink . We associate this partition with the transformed binary variables as
Under this convention, assigning places on the source side, so the edge crosses the cut and contributes . Similarly, assigning places on the sink side, so the edge contributes .
For an internal edge , the corresponding vertices lie on opposite sides of the cut precisely when . In this case, exactly one of the two directed edges contributes unit capacity; otherwise, neither contributes. Thus, the total capacity of a cut corresponding to is
Since the cut capacity is exactly the transformed energy, finding a minimum cut yields an optimal solution to (38). To obtain this solution, we first compute a maximum flow and then identify the set of block vertices reachable from through edges with positive residual capacity. These vertices lie on the source side of a minimum cut, while the remaining vertices lie on the sink side. The optimal transformed assignment is therefore,
Finally, reversing the transformation in (29), we obtain the corresponding block assignments
The resulting maximizes the original MAX-CUT objective over the selected block, with all assignments outside held fixed.
Recovery Procedure and Guarantees
Bipartite-block recovery is applied independently to each selected QPU-sampled configuration, without requiring a preceding single-vertex greedy recovery stage (Algorithm 1). Starting from a configuration , we rank the candidate blocks according to their aggregate signed vertex residues,
where is the gain obtained by flipping vertex individually. Blocks with larger residues are examined first, as they indicate a greater aggregate tendency toward improving single-vertex assignments.
For each block , we solve the conditional optimization exactly using the minimum-cut construction described previously. The improvement in the original objective is
Since the current block assignment is feasible for the conditional optimization, . We accept an update only when . After each accepted update, the block residues are recomputed and the blocks are ranked again. The procedure terminates when a complete pass over all candidate blocks produces no improvement. Algorithm 2 Bipartite-block configuration recovery
Require: Graph , color classes , initial configuration
Ensure: Recovered configuration
repeat
improved false
for each block , do
Construct the flow network for
Compute a maximum – flow
Find the source-reachable set in the network
Set if , and otherwise
Recover for each
if then
improved true
break
end if
end for
until improved = false
return
Every accepted update strictly increases the integer-valued cut objective. Since , the number of accepted updates is bounded by
Thus, recovery terminates in finitely many updates without requiring an explicit budget. Moreover, with candidate blocks, at most conditional block optimizations are attempted. Since each minimum-cut problem is solvable in polynomial time, the overall recovery procedure also has polynomial worst-case complexity.
The final configuration is locally optimal with respect to every candidate block. In particular, it is also locally optimal under single-vertex flips, since any improving single-vertex assignment would be feasible within a block containing that vertex. Consequently, for unweighted MAX-CUT, the recovered configuration satisfies
Thus, while the procedure does not guarantee a globally optimal cut, it provides a 1/2-approximation guarantee upon convergence, in addition to monotonic improvement from the initial configuration. Finally, recovery is performed independently for each selected QPU-sampled configuration, and the best recovered solution is retained. This allows direct comparison with single-vertex greedy recovery using identical initial configurations, without additional QPU executions.
Experimental Evaluation on ibm_kingston
In this section, we evaluate the effectiveness of the proposed hybrid quantum–classical workflow for non-hardware-native MAX-CUT instances. Specifically, we investigate three aspects:
Circuit-depth reduction: The extent to which surrogate Hamiltonians reduce transpiled two-qubit depth while satisfying hardware-specific depth constraints.
Solution quality from surrogate sampling: The ability of reduced QAOA circuits to generate configurations with high cut values on the original graph.
Effectiveness of classical recovery: The improvement in solution quality achieved by refining candidate configurations against the original MAX-CUT objective.
We emphasise that our primary focus is not comparison against state-of-the-art classical optimization techniques, but to assess whether hardware-constrained surrogate execution, combined with classical recovery, enables effective QAOA-based optimization of graph instances whose full cost Hamiltonians exceed practical circuit depth budgets.
Experimental Setup: We evaluate these aspects on 120 benchmark instances from HAMLIB [12], comprising 20 instances each of 6-regular and Erdős–Rényi () graphs at each problem size . For each instance, we execute both the original QAOA circuit and its corresponding MinLA-band surrogate on ibm_kingston. The experimental configuration is summarized in Table 2.
| Setting | Configuration |
| Quantum processor | ibm_kingston |
| Graph families | 6-regular and (HAMLIB) |
| Problem sizes | |
| QPU shots | 10,000 per circuit |
| Compilation | SATMapper [7], commuting-gate routing [3]; Qiskit optimization level 3 |
| Transpiler seed | 123 |
| Noise handling | Gate and measurement twirling enabled; dynamical decoupling disabled |
| QAOA layers | |
| Depth budget | 150 (6-regular); 200 () |
| Recovery candidates | 50 distinct QPU-sampled bitstrings |
Table 2. Experimental configuration
Surrogate Selection and Depth Budgets: Vertex orderings are obtained using the weighted-aggregation MinLA heuristic [14]. For each instance, we select the lexicographically largest feasible pair , prioritizing the QAOA depth before the interaction-band radius . Feasibility requires that every vertex retains at least one incident edge and that the transpiled two-qubit depth does not exceed the prescribed budget .
The family-specific depth budgets were chosen to accommodate the minimum-bandwidth surrogates that retain at least one incident edge per vertex across all tested instances. The maximum observed transpiled two-qubit depths of these surrogates, evaluated using a single QAOA layer, were 118 for 6-regular graphs and 190 for graphs, motivating budgets of and , respectively. This provides an empirical feasibility criterion for the tested graphs and compilation setup, rather than a universal depth guarantee.
Performance Metrics: All solution qualities are evaluated on the original graph . Let denote the cut value of configuration and the optimal cut value, certified using Gurobi for every instance. We define the approximation ratio as
Recovery Evaluation: To assess the improvement due to classical recovery, we select 50 distinct starting configurations from the surrogate QAOA samples of instance . Each configuration is refined independently using recovery method . We compare the best cut values before and after recovery using
This comparison isolates the improvement obtained through classical recovery using the same 50 starting configurations. Results are reported as means and sample standard deviations over the 20 instances in each graph-family and size group.
Results on 6-Regular Graphs
Although regular graphs are sparse from a graph-theoretic perspective, they remain non-native to superconducting processors because their interaction structure differs substantially from the sparse near-linear coupling graph of the target hardware. Direct execution therefore incurs significant routing overhead, making these instances a useful testbed for evaluating whether hardware-aware surrogate Hamiltonians can preserve useful optimization information while remaining executable within realistic depth budgets.
Surrogate Construction and Circuit Depth: Each 6-regular graph contains interactions. We use the fixed-angle approach of [18], with QAOA parameters expressed in the positive- convention of our implementation. The parameter values for are in Table 3.
| 1 | ||
| 2 | ||
| 3 |
Table 3. Fixed QAOA angles for 6-regular graphs
Table 4, shows that the selected MinLA bands retain a substantial fraction of these interactions, preserving 70.5%, 49.2%, and 51.4% of the original edges for , 60, and 100, respectively. The column counts instances selected at each QAOA depth. Entries are means sample standard deviations; ranges are given in brackets.
Table 4. Selected MinLA bands for 20 6-regular instances per size.
In Figure 6, we report the resulting transpiled two-qubit depths. Despite retaining approximately half of the original interactions at the larger sizes, every surrogate circuit satisfies the hardware depth budget. Across all instances, the mean depth reduction is 31.0%, 55.8%, and 62.3% at , 60, and 100, respectively. For details on reduction in the transpiled two-qubit gate counts, readers can refer Table 7 in Appendix § 11.

Figure 6. Transpiled two-qubit depth of the full-graph and MinLA-band circuits on ibm_kingston, paired by instance and compiled at the same . Bars are means over 20 instances; error bars are sample standard deviations.
| Family | Full graph | Surrogate | Reduction (%) | |
| 6-regular | 40 | 3769.65 | 2481.15 | 34.12 |
| 6-regular | 60 | 8642.85 | 3402.15 | 59.72 |
| 6-regular | 100 | 17490.65 | 6004.95 | 57.52 |
| 40 | 1881.45 | 1876.00 | 0.28 | |
| 60 | 4344.85 | 4343.30 | 0.04 | |
| 100 | 12379.45 | 9224.65 | 25.47 |
Table 7. Transpiled two-qubit gate counts for full-graph and selected surrogate circuits at matched QAOA depth. Counts are averaged over 20 instances. The mean reduction is computed as , where and denote the corresponding two-qubit gate counts.
These results validate the surrogate-construction strategy developed in § 3. Rather than aggressively reducing the graph to a chain-like structure, MinLA ordering concentrates interactions so that a substantially richer surrogate Hamiltonian remains executable within the available hardware depth budget.
Solution Quality and Classical Recovery: We next examine the effectiveness of classical recovery in improving configurations sampled from the surrogate QAOA circuits. Figure 7 compares the best-of-50 approximation ratios before and after recovery, with all cut values evaluated on the original graphs. Both recovery strategies improve solution quality across the considered problem sizes, with bipartite-block recovery consistently achieving higher approximation ratios than signed-residue recovery.

Figure 7. Solution quality on the original graphs, over 20 instances per size. The mean AR before and after recovery, computed per instance from the same 50 MinLA-circuit samples; error bars are sample standard deviations.
At , the mean best-of-50 approximation ratio increases from 0.788 before recovery to 0.961 following signed-residue recovery and 0.997 following bipartite-block recovery. Similar improvements are observed at and , where the recovered solutions approach the optimal cut values. These findings demonstrate that configurations obtained from surrogate QAOA circuits can be effectively refined against the original MAX-CUT objective, despite the interactions omitted during quantum execution.
Classical Recovery Overhead: Figure 8 compares the computational effort of the two recovery strategies in terms of accepted updates and execution time. Signed-residue recovery performs inexpensive local updates and therefore converges quickly, whereas bipartite-block recovery repeatedly solves conditional minimum-cut subproblems that explore larger neighborhoods of the solution space. Consequently, bipartite-block recovery requires more computation per recovery run. At , the average runtime is 523 ms compared with 19 ms for signed-residue recovery. This additional computation is performed entirely classically and requires no further QPU executions. Moreover, recovery runs are independent across starting configurations and can therefore be parallelized.

Figure 8. (a) Mean accepted updates per start; whiskers extend to the maximum. (b) Mean wall time per recovery run, on a logarithmic axis. Classical recovery effort over 1,000 runs per method and size: 50 starting configurations for each of 20 instances.
Taken together, these results support the central hypothesis of this work. The 6-regular experiments demonstrate that hardware-aware surrogate construction can reduce circuit depth while retaining sufficient graph structure to support effective classical recovery. At , the complete workflow achieves a mean best-of-50 approximation ratio of 0.997 on the original graph, without additional quantum executions for recovery.
Results on Erdős–Rényi Graphs
We evaluate the workflow on the HAMLIB gnp-k_4 family, using 20 instances at each size . These graphs have non-uniform realized degrees and more edges than the corresponding 6-regular instances. Their mean degrees are approximately 14.1, 16.1, and 18.2, respectively. For each graph, we use and train the angles using a parameter scan followed by classical refinement [9, 19]. The parameters are trained once per graph and reused for its full and MinLA-band circuits. Mean training times are 9.42, 19.23, and 50.67 seconds per graph at , 60, and 100, respectively, and is completely classical.
Surrogate Construction and Circuit Depth: We prescribe a maximum transpiled two-qubit depth of , as mentioned in Table 2. Previous experiments on IBM superconducting processors have demonstrated meaningful results at comparable or greater two-qubit circuit depths [20, 21]. Table 5 summarizes the selected bands. At and , the full-graph circuits satisfy the depth constraint, allowing all interactions to be retained. At , the selected bands retain 52.2% of the original edges on average.
Table 5. Selected MinLA bands for 20 HAMLIB gnp-k_4 instances per size under . The column counts instances selected at each QAOA depth. Entries are means sample standard deviations; ranges are given in brackets.
Figure 9 reports the transpiled two-qubit depths. At and , the depths remain nearly unchanged, consistent with full interaction retention. We emphasise that full-edge retention at and is specific to the tested circuits. While we have not tested these instances for , increasing pushes the full-graph (, 60) circuits’ two-qubit depths above 200, necessitating a narrower MinLA band and dropping some edges. At , the band retains 52.2% of the edges and reduces mean two-qubit depth from 257.4 to 197.4, a paired mean reduction of 23.3%. The mean two-qubit gate count also decreases from 12,379 to 9,225, a reduction of 25.5%.

Figure 9. Transpiled two-qubit depth of the full-graph and MinLA-band circuits on ibm_kingston, paired by instance. Bars are means over 20 instances; error bars are sample standard deviations. The red dashed line marks the maximum prescribed depth .
Solution Quality and Classical Recovery: We next evaluate whether configurations obtained from the QAOA circuits can be refined to produce high-quality solutions to the original MAX-CUT instances.
Figure 10 compares the best-of-50 approximation ratios before and after recovery, with all cut values evaluated on the original graphs. Both recovery strategies improve the sampled configurations, with bipartite-block recovery achieving higher mean approximation ratios than signed-residue recovery. For and , where all interactions are retained, these improvements reflect classical refinement of full-graph QAOA samples. At , recovery additionally addresses the interactions omitted during surrogate construction, improving the resulting configurations against the complete objective.

Figure 10. Best-of-50 approximation ratios on the original graphs, over 20 instances per size for QAOA cost layers. The initial QPU sample and both recovered solutions use the same 50 starting configurations per instance. Error bars are sample standard deviations.
Classical Recovery Overhead: Figure 11 compares the computational effort of signed-residue and bipartite-block recovery in terms of accepted updates and execution time. As observed for the 6-regular instances, bipartite-block recovery achieves higher solution quality at the expense of greater classical computation. At , signed-edge recovery takes 67.6 ms per start, while bipartite-block recovery takes 3.16 s. These statistics are computed over 1,000 recovery runs per method and size, corresponding to 50 starting configurations for each of 20 graph instances. Since recovery operates independently on each configuration, the computation was parallelized without additional QPU executions.

(a) Mean accepted updates per start; whiskers extend to the maximum.

(b) Mean wall time per recovery start, on a logarithmic axis.
Figure 11. Classical recovery effort over 1,000 starts per method and size: 50 starting configurations for each of 20 instances.
Overall, these experiments demonstrate that the need for interaction reduction depends on graph size and circuit depth. While the full Hamiltonian remains executable within the prescribed budget at smaller sizes, depth-constrained surrogates become necessary at . Classical recovery further improves the sampled configurations, without increasing the quantum execution cost.
Cross-Family Comparison
Table 6 compares the edge-retention results under the family-specific depth limits. We chose the limits to target retention of approximately half of the edges in the largest instances; this led to for the 6-regular experiments and for . At , both families retain approximately half of their interactions. At smaller sizes, the bands retain all edges under , since the full circuits already satisfy that limit. The 6-regular experiments use greater QAOA depths for many instances, and consequently require edge removal to meet .
| 6-regular | Retained (%) | / Retained (%) | |||
| 40 | 0/0/20 | 150 | 70.5 3.2 | 1 | 200/100.0 |
| 60 | 0/2/18 | 150 | 49.2 5.8 | 1 | 200/100.0 |
| 100 | 6/8/6 | 150 | 51.4 15.7 | 1 | 200/52.2 2.6 |
Table 6. Edge retention and QAOA settings across the two graph families. The depth limits are family-specific.
This comparison describes two operating regimes, rather than isolating the effect of graph family: QAOA depth and the prescribed depth limit both differ. The observed retention therefore reflects graph structure, QAOA depth, and the compilation constraint together; it should not be interpreted as evidence that either family is intrinsically easier to compile. Likewise, the approximation ratios are evaluated within each family’s experiment and are not a controlled comparison of or topology.
Discussion
In this section, we highlight the scope of our experimental findings, particularly how hardware-aware circuit reduction and classical recovery contribute to the proposed workflow, and its adaptability to future quantum hardware.
Hardware-aware execution under noise constraints: The primary contribution of our work is a systematic approach to executing non-hardware-native QAOA instances within prescribed circuit-depth budgets. By heuristically selecting interactions, our framework balances the retention of graph structure against the routing overhead of quantum execution. This provides a practical means of limiting exposure to hardware noise, although circuit-depth reduction does not necessarily translate directly into improved fidelity. The chosen depth budgets represent empirical operating choices rather than universal hardware thresholds.
Interpreting solution quality: The reported approximation ratios characterize the performance of the complete hybrid workflow, comprising surrogate-based quantum sampling and classical configuration recovery. While the quantum circuit generates candidate configurations using a subset of the original interactions, classical recovery improves these configurations against the full objective. The near-optimal recovered cuts therefore establish the effectiveness of the combined procedure, without attributing the final solution quality exclusively to quantum execution. Importantly, the framework preserves the original optimization objective throughout classical recovery, even though the executed Hamiltonian is modified.
Scalability and Hardware Adaptability: Our framework separates quantum circuit complexity from classical solution refinement, allowing the computational workload to be adjusted according to available hardware resources. As processors support deeper and more reliable circuits, larger subsets of the original interactions can be retained without modifying the overall workflow. Furthermore, independent recovery across sampled configurations enables parallel classical processing without additional QPU executions. The experiments establish the feasibility of this approach for instances with up to 100 vertices, while its performance at larger scales will depend on both quantum execution requirements and classical recovery costs.
Conclusion
Sparse connectivity and noise remain major obstacles to executing QAOA on graph instances whose interaction structure differs substantially from the coupling topology of current superconducting quantum processors. In this work, we introduced a hybrid quantum-classical workflow that addresses this challenge through depth-constrained surrogate Hamiltonian construction and classical configuration recovery. By combining MinLA-based band-concentrating vertex orderings with hardware-aware interaction filtering, we construct surrogate Hamiltonians that retain all decision variables and a substantial fraction of the original graph structure while satisfying a prescribed two-qubit depth budget. We further developed signed-residue and bipartite-block recovery procedures that operate on the original graph and monotonically improve sampled solutions without requiring additional QPU executions.
Using this workflow, we demonstrated QAOA on non-hardware-native 6-regular and Erdős–Rényi graph instances with up to 100 vertices on the ibm_kingston processor. Although the full Hamiltonians of these problems incur substantial routing overhead when mapped directly to sparse superconducting hardware, the proposed surrogate circuits remained executable within realistic depth constraints and, when combined with configuration recovery, achieved approximation ratios approaching unity on the original graph. These results show that useful optimization signals can be extracted from hardware-feasible surrogate Hamiltonians and subsequently amplified through recovery on the complete objective.
More broadly, the proposed workflow provides a practical pathway toward scalability on near-term quantum hardware. The depth budget used to construct the surrogate Hamiltonian is fundamentally determined by the level of noise that current devices can tolerate. As superconducting processors continue to improve, deeper circuits will become executable, allowing larger interaction radii and therefore richer surrogate Hamiltonians that preserve an even greater fraction of the original graph. The resulting increase in retained problem information can strengthen the optimization signal available to the quantum processor, reducing the burden on subsequent recovery and extending the range of graph instances that can be addressed. In this sense, surrogate-based execution and configuration recovery offer a scalable framework for bringing increasingly large and non-hardware-native quantum optimization problems within reach of future superconducting quantum computers.
Acknowledgments
The authors acknowledge helpful discussions with Dr. Shesha Raghunathan, Dr. Kalyan Dasgupta and Dr. Sumanta Mukherjee. RM acknowledges helpful discussions with Dr. Nick Bronn.
Additional Preliminaries
QAOA Objective and Circuit Decomposition
The cost Hamiltonian in Eq. (2) satisfies
Therefore, the ground states of correspond to maximum cuts of .
The QAOA parameters are chosen to minimize the expected energy,
For fixed parameters, measurements in the computational basis yield candidate bitstrings with probabilities
from which the best observed partition can be selected.
Since the terms of commute, each cost layer decomposes, up to a global phase, as
where . Thus, a -layer QAOA circuit contains logical two-qubit interactions, whose scheduling and hardware implementation determine the resulting circuit depth.
QAOA Parameter Selection
The standard variational approach determines the QAOA parameters through classical optimization,
Evaluating this objective on quantum hardware requires repeated circuit executions, making the optimization susceptible to well-known challenges of variational quantum algorithms, including shot noise, device noise, optimization instability, and barren plateaus [22, 23]. Consequently, parameter selection methods that exploit graph structure and avoid repeated hardware-based optimization are of practical interest [9]. A useful property of QAOA is the locality of its expectation values. At depth , the expectation of an edge observable depends only on the subgraph within its -hop light cone [1]. This allows parameters to be transferred between graphs with similar local structure and motivates graph-family-specific angle selection methods [24, 25].
Regular instances
For a -regular graph, we use the fixed-angle approach of [18], which exploits QAOA locality to obtain parameters from the corresponding infinite -regular tree
For -regular graphs with girth greater than , all edge light cones have the same tree structure. The expected cut fraction therefore depends only on , , the QAOA parameters, and not on the graph size or specific instance. For regular graphs containing short cycles, these angles may also serve as transferable heuristic parameters, without requiring instance-specific quantum optimization.
Erdős–Rényi instances.
For irregular graphs, the variation in vertex degrees and local connectivity precludes a single regular-tree description. We therefore obtain instance-specific parameters at using the graph-training methodology of the QAOA training pipeline [9]. This method performs a coarse grid search followed by local refinement. The EfficientDepthOneEvaluator computes the required correlators from reduced density matrices, avoiding full statevector simulation and remaining practical for larger instances [19].
These procedures provide all variational parameters used in the subsequent hardware experiments without requiring iterative QPU-based optimization.
Connectivity-Aware Compilation of QAOA Circuits
QAOA implementation on hardware is constrained by the limited connectivity between physical qubits. Although the commuting two-qubit interactions within each cost layer can be reordered, their execution requires suitable qubit placement, routing, and gate scheduling. Consequently, the compiled circuit depth depends not only on the structure of the problem graph but also on how its interactions are mapped onto the hardware topology. We review three very useful compilation techniques: (a) SWAP strategies for routing two-qubit interactions, (b) SATMapper for optimizing the initial qubit placement, and (c) edge coloring for exploiting parallelism among commuting gates.
SWAP strategy: On sparsely connected hardware, two-qubit interactions can be executed only between adjacent physical qubits. The line-SWAP strategy [3] addresses this constraint by routing logical qubits along a path embedded in the hardware coupling graph. It alternates between two layers of disjoint SWAP operations,
These alternating layers systematically change the positions of logical qubits, allowing the required interactions to be applied when their corresponding qubits become adjacent. Since the cost-Hamiltonian terms commute, the interactions can be reordered to follow this routing sequence.
SATMapper: The number of SWAP layers required by a given strategy depends on the initial assignment of logical qubits to physical qubits. SATMapper [7] formulates this assignment as a Boolean satisfiability problem. For an initial mapping , let denote the set of logical qubit pairs that become adjacent within the first layers of the SWAP strategy. The objective is to determine
The SATMapper searches for a feasible initial mapping while minimizing the required number of SWAP layers. By placing frequently interacting logical qubits advantageously along the routing path, it substantially reduces the routing overhead relative to arbitrary initial placements.
Edge coloring and gate scheduling: The commuting interactions can be scheduled in parallel whenever they act on disjoint qubit pairs. This scheduling problem is naturally represented by an edge coloring of the interaction graph, where edges sharing a vertex receive different colors. Each color class therefore defines a set of mutually disjoint interactions. In practice, greedy edge coloring provides an efficient ordering of the gates [26]. With all these techniques combined, this ordering helps reduce the overhead of implementing QAOA cost layers on connectivity-constrained hardware while preserving the interactions specified by the problem Hamiltonian.
Detailed Proofs
Proof of Lemma 1
Proof. Let be the flipped vertex. This gives that and for every . We distinguish three cases.
Case : Using the definition of the signed vertex residue (17), we have,
Every edge incident on satisfies
The above equation can be interpreted as if is cut after flipping , then it was originally a bad/uncut edge. Consequently,
Case : Only the contribution of edge to changes. Writing , we obtain
Otherwise: Neither the assignment of nor that of any of its neighbors changes. Every contribution to its residue therefore remains unchanged, giving
Proof of Theorem 1
Proof. If vertex is selected at iteration , the acceptance condition and Eq. (18) give
The final inequality follows by summing the accepted gains, with equality when no flip is accepted.
Proof of Theorem 2
Proof. By Theorem 1, every accepted flip strictly increases the cut value. Since is integer-valued, each improvement is at least one. Moreover, for every configuration. Consequently, after accepted flips,
which establishes the bound in Eq. (22). By Eq. (18), the residue equals the change in cut value obtained by flipping vertex . Therefore, if all residues are nonpositive, no single-vertex flip can improve the objective, establishing one-flip local optimality.
Proof of Corollary 1
Proof. At a one-flip local optimum, no single-vertex flip can improve the cut. Consequently, for every , implying
Each uncut edge contributes once to the uncut-edge count of each endpoint, while each cut edge contributes similarly to the cut-edge counts. Therefore,
It follows that yielding . Since , the claimed approximation bound follows.
Transpiled Two-Qubit Gate Counts
To quantify the circuit-resource savings from graph filtering, we compare each selected surrogate with the corresponding full-graph circuit at the same QAOA depth. Table 7 reports the mean transpiled two-qubit gate counts over 20 instances per graph family and size. All two-qubit gates in the recorded compiled circuits are CZ gates.
For 6-regular graphs, the mean reductions are 34.1%, 59.7%, and 57.5% at , 60, 100, respectively. For graphs, the mean reduction is 25.5% at . Gate counts remain essentially unchanged at and , where the selected surrogates retain all original edges; the small differences arise between the compiled implementations.
References
- [1]Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014.arxiv.org/abs/1411.4028
- [2]Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Ben Chiaro, Robert Collins, William Courtney, Sean Demura, Andrew Dunsworth, Daniel Eppens, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Alan Ho, Sabrina Hong, Trent Huang, L. B. Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V. Klimov, Alexander N. Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Martin Leib, Orion Martin, John M. Martinis, Jarrod R. McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Charles Neill, Florian Neukart, Murphy Yuezhen Niu, Thomas E. O’Brien, Bryan O’Gorman, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Andrea Skolik, Vadim Smelyanskiy, Doug Strain, Michael Streif, Marco Szalay, Amit Vainsencher, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Leo Zhou, Hartmut Neven, Dave Bacon, Erik Lucero, Edward Farhi, and Ryan Babbush. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17(3):332–336, February 2021.DOI
- [3]Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner, and Daniel J. Egger. Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware. Quantum, 6:870, 2022.DOI
- [4]Stefan H. Sack and Daniel J. Egger. Large-scale quantum approximate optimization on nonplanar graphs with machine learning noise mitigation. Physical Review Research, 6:013223, 2024.DOI
- [5]Natasha Sachdeva et al. Integrated error-suppressed pipeline for quantum optimization of nontrivial binary combinatorial optimization problems on gate-model hardware at the 156-qubit scale. New Journal of Physics, 28:064506, 2026.DOI
- [6]Zixu Wang, Jack Mandell, Yangyang Xu, and Jian Shi. A depth-independent linear chain ansatz for large-scale quantum approximate optimization. arXiv preprint arXiv:2509.17296, 2025.arxiv.org/abs/2509.17296
- [7]Atsushi Matsuo, Shigeru Yamashita, and Daniel J. Egger. A sat approach to the initial mapping problem in swap gate insertion for commuting gates. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E106.A(11):1424–1431, November 2023.DOI
- [8]Jai Moondra, Phillip C. Lotshaw, Greg Mohler, and Swati Gupta. Promise of graph sparsification and decomposition for noise reduction in qaoa: Analysis for trapped-ion compilations. Quantum, 10:2185, August 2026.DOI
- [9]Qiskit-community. A pipeline and methods to generate good parameters for QAOA Ansatz circuits. https://github.com/qiskit-community/qaoa_training_pipeline/tree/main, 2026.
- [10]Javier Robledo-Moreno, Mario Motta, Holger Haas, Ali Javadi-Abhari, Petar Jurcevic, William Kirby, Simon Martiel, Kunal Sharma, Sandeep Sharma, Tomonori Shirakawa, Iskandar Sitdikov, Rong-Yang Sun, Kevin J. Sung, Maika Takita, Minh C. Tran, Seiji Yunoki, and Antonio Mezzacapo. Chemistry beyond the scale of exact diagonalization on a quantum-centric supercomputer. Science Advances, 11(25):eadu9991, 2025.DOI
- [11]V. Kolmogorov and R. Zabin. What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):147–159, 2004.
- [12]Nicolas PD Sawaya, Daniel Marti-Dafcik, Yang Ho, Daniel P Tabor, David E Bernal Neira, Alicia B Magann, Shavindra Premaratne, Pradeep Dubey, Anne Matsuura, Nathan Bishop, et al. Hamlib: A library of hamiltonians for benchmarking quantum algorithms and hardware. Quantum, 8:1559, 2024.
- [13]Josep Díaz, Jordi Petit, and Maria Serna. A survey of graph layout problems. ACM Comput. Surv., 34(3):313–356, September 2002.DOI
- [14]Ilya Safro, Dorit Ron, and Achi Brandt. Graph minimum linear arrangement by multilevel weighted edge contractions. Journal of Algorithms, 60(1):24–41, 2006.
- [15]Wai-Hung Liu and Andrew H. Sherman. Comparative analysis of the Cuthill–McKee and the reverse Cuthill–McKee ordering algorithms for sparse matrices. SIAM Journal on Numerical Analysis, 13(2):198–213, 1976.DOI
- [16]Elizabeth Cuthill and James McKee. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 24th National Conference of the ACM, pages 157–172. Association for Computing Machinery, 1969.DOI
- [17]Kalyan Dasgupta, Sumanta Mukherjee, Dhriti Verma, Surya Shravan Kumar Sajja, Abhishek Singh, Dzung Phan, and Jayant Kalagnanam. Quantum variational approaches to the maximum independent set problem at utility scale. arXiv preprint arXiv:2606.028866, 2026.
- [18]Jonathan Wurtz and Danylo Lykov. Fixed-angle conjectures for the quantum approximate optimization algorithm on regular maxcut graphs. Phys. Rev. A, 104:052419, Nov 2021.DOI
- [19]Daniel J. Egger, Jakub Mareček, and Stefan Woerner. Warm-starting quantum optimization. Quantum, 5:479, June 2021.DOI
- [20]Javier Robledo-Moreno, Mario Motta, Holger Haas, Ali Javadi-Abhari, Petar Jurcevic, William Kirby, Simon Martiel, Kunal Sharma, Sandeep Sharma, Tomonori Shirakawa, et al. Chemistry beyond the scale of exact diagonalization on a quantum-centric supercomputer. Science Advances, 11(25):eadu9991, 2025.DOI
- [21]Marco Antonio Barroca, Tanvi P. Gujarati, Vidushi Sharma, Rodrigo Neumann Barros Ferreira, Young-Hye Na, Maxwell Giammona, Antonio Mezzacapo, Benjamin Wunsch, and Mathias B. Steiner. Scaling active spaces in simulations of surface reactions through sample-based quantum diagonalization. Scientific Reports, 16(1), June 2026.DOI
- [22]McClean et al. Barren plateaus in quantum neural network training landscapes. Nature Communications, 2018.DOI
- [23]Cerezo et al. Variational quantum algorithms. Nature Reviews Physics, 2021.DOI
- [24]Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances, 2018.arxiv.org/abs/1812.04170
- [25]Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alekseev, and Ilya Safro. Transferability of optimal qaoa parameters between random graphs, 2021.arxiv.org/abs/2106.07531
- [26]Ritajit Majumdar, Dhiraj Madan, Debasmita Bhoumik, Dhinakaran Vinayagamurthy, Shesha Raghunathan, and Susmita Sur-Kolay. Optimizing ansatz design in qaoa for max-cut. arXiv preprint arXiv:2106.02812, 2021.arxiv.org/abs/2106.02812



