betaFeedback

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 ss–tt 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 66-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 p=1p = 1 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 p=1p = 1 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 n−1n - 1 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 n−1n - 1 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-BB 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.

Principle of the proposed hybrid quantum–classical workflow

Figure 2. Principle of the proposed hybrid quantum–classical workflow. A depth-constrained surrogate reduces the quantum workload, while the top-BB 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:

  1. 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.

  1. Depth-budgeted surrogate selection: We choose the widest executable interaction band whose transpiled pp-layer circuit remains below a device-specific depth budget LL, while ensuring that every vertex retains at least one incident interaction. This directly couples surrogate-graph construction to the capabilities of the target hardware.

  1. 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 ss–tt minimum cut [11].

  1. Parallel recovery from a single QPU execution: For statistical accuracy, we perform independent recovery runs on each of the top-BB 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.

  1. 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 (G(n,p)G(n,p)) 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 G=(V,E)G=(V,E) with ∣V∣=n|V|=n vertices. The MAX-CUT problem seeks a bipartition of the vertices that maximizes the number of edges crossing the partition. Assigning a binary variable xi∈{0,1}x_i \in\{0,1\} to each vertex, the cut objective is

CG(x)=∑(i,j)∈E(xi+xj−2xixj).(1)C_G(\mathbf{x})=\sum_{(i,j)\in E}(x_i+x_j-2x_ix_j). \tag*{(1)}

Using xi=(1−zi)/2x_i=(1-z_i)/2, where zi∈{−1,+1}z_i\in\{-1,+1\}, and replacing each spin variable with the Pauli-Z operator, the corresponding cost Hamiltonian is

HC=12∑(i,j)∈E(I−ZiZj).(2)H_C=\frac{1}{2}\sum_{(i,j)\in E}(I-Z_iZ_j). \tag*{(2)}

The Quantum Approximate Optimization Algorithm (QAOA) [1] alternates evolution under the cost Hamiltonian HCH_C and the mixer Hamiltonian HM=∑i∈VXiH_M=\sum_{i\in V}X_i. The pp-layer QAOA state is

∣ψp(θ)⟩=UM(βp)UC(γp)⋯UM(β1)UC(γ1)∣+⟩⊗n,(3)\lvert\psi_p(\boldsymbol{\theta})\rangle=U_M(\beta_p)U_C(\gamma_p)\cdots U_M(\beta_1)U_C(\gamma_1)\lvert+\rangle^{\otimes n}, \tag*{(3)}

where UC(γ)=e−iγHCU_C(\gamma)=e^{-i\gamma H_C}, UM(β)=e−iβHMU_M(\beta)=e^{-i\beta H_M}, and θ=(γ,β)\boldsymbol{\theta}=(\boldsymbol{\gamma},\boldsymbol{\beta}) denotes the variational parameters. Each cost layer comprises ∣E∣|E| 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 pp-layer QAOA circuit must remain below a prescribed hardware depth budget LL. 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 AA denote the adjacency matrix of the graph G=(V,E)G = (V, E). A linear arrangement is defined as a bijection π:V→{0,…,n−1}\pi: V \to\{0, \ldots, n - 1\} that assigns each vertex a distinct position. The MinLA problem identifies an ordering that minimizes the cumulative distance between adjacent vertices,

min⁡π∑(u,v)∈E∣π(u)−π(v)∣.(4)\min_{\pi}\sum_{(u,v)\in E} \lvert\pi(u) - \pi(v) \rvert. \tag*{(4)}

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 πLA\pi_{\mathrm{LA}} denote the MinLA ordering. The corresponding adjacency matrix is obtained by applying the same permutation to its rows and columns,

(Aπ)ij=AπLA−1(i),πLA−1(j).(5)(A_{\pi})_{ij} = A_{\pi_{\mathrm{LA}}^{-1}(i),\pi_{\mathrm{LA}}^{-1}(j)}. \tag*{(5)}

As mentioned previously, the superdiagonals of AπA_{\pi} provide a natural representation of interaction span. An entry on the rrth superdiagonal represents an edge whose endpoints are separated by rr positions in the linear arrangement. Denoting the number of nonzero entries on this superdiagonal by srs_r, the arrangement cost is ∑r=1n−1r sr\sum_{r=1}^{n-1} r\,s_r. 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 G(n,p)G(n,p) 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 G(n,p)G(n,p) graph.

Depth-Constrained Selection of Interactions

For a given ordering πLA\pi_{\mathrm{LA}}, we construct a reduced interaction graph Gk=(V,Ek)G_k = (V, E_k) by retaining edges whose spans do not exceed an integer radius kk,

Ek={(u,v)∈E:∣πLA(u)−πLA(v)∣≤k}.(6)E_k = \{(u,v) \in E : |\pi_{\mathrm{LA}}(u) - \pi_{\mathrm{LA}}(v)| \le k\}. \tag*{(6)}

Equivalently, EkE_k contains the original interactions represented within the first kk superdiagonals and their symmetric subdiagonals. Since Ek⊆Ek+1E_k \subseteq E_{k+1}, increasing kk progressively restores interactions from the original graph. The choice of kk 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 GG contains no isolated vertices, the smallest radius satisfying this condition is

kcov=min⁡{k:deg⁡Gk(v)≥1, ∀v∈V}.(7)k_{\mathrm{cov}} = \min\{k : \deg_{G_k}(v) \ge1,\ \forall v \in V\}. \tag*{(7)}

Equivalently, (7) can be expressed as,

kcov=max⁡v∈Vmin⁡u∈NG(v)∣πLA(u)−πLA(v)∣,(8)k_{\mathrm{cov}} = \max_{v \in V}\min_{u \in N_G(v)} |\pi_{\mathrm{LA}}(u) - \pi_{\mathrm{LA}}(v)|, \tag*{(8)}

where NG(v)N_G(v) denotes the neighborhood of vertex vv in GG. 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 D2q(p,k)D_{2q}(p,k) denote the two-qubit depth of a pp-layer QAOA circuit constructed using GkG_k and transpiled for the target hardware under a fixed compilation configuration. Let b(πLA):=max⁡(u,v)∈E∣πLA(u)−πLA(v)∣b(\pi_{\mathrm{LA}}) := \max_{(u,v)\in E} |\pi_{\mathrm{LA}}(u) - \pi_{\mathrm{LA}}(v)| denote the maximum edge span under the chosen ordering. Then, given a prescribed depth cutoff LL, we select the radius

k⋆(p,L)=max⁡kcov≤k≤b(πLA)D2q(p,k)<Lk,(9)k^{\star}(p,L) = \max_{\substack{k_{\mathrm{cov}} \le k \le b(\pi_{\mathrm{LA})}\\ D_{2q}(p,k) < L}} k, \tag*{(9)}

The integer k⋆(p,L)k^{\star}(p,L) depends on the QAOA depth pp as well as the hardware depth limit LL. Increasing pp 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 kk 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

HC(p,L)=12∑(u,v)∈Ek⋆(p,L)(I−ZuZv).(10)H_C^{(p,L)} = \frac{1}{2}\sum_{(u,v)\in E_{k^{\star}(p,L)}} (I - Z_u Z_v). \tag*{(10)}

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,

η(p,L)=∣Ek⋆(p,L)∣∣E∣.(11)\eta(p,L) = \frac{|E_{k^{\star}(p,L)}|}{|E|}. \tag*{(11)}

To examine the influence of vertex ordering on this edge retention fraction, Figure 4 compares the cumulative retention fraction F(k)=∣Ek∣/∣E∣F(k) = |E_k|/|E| 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 k=10k = 10, 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 G(n,p)G(n,p) graph. Moreover, MinLA reaches the minimum radius required to avoid isolated vertices at smaller values of kk 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 kk.

Figure 4. Cumulative edge retention F(k)=∣Ek∣/∣E∣F(k)=|E_k|/|E| as a function of the interaction radius kk for MinLA and RCM vertex orderings of (a) a 6-regular graph and (b) a G(n,p)G(n,p) 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 EsE_s denote the set of retained interactions and Er=E\EsE_r = E \backslash E_s denote the omitted interactions. The original MAX-CUT objective can then be decomposed as

C(x)=∑(u,v)∈Eswuv(xu⊕xv)+∑(u,v)∈Erwuv(xu⊕xv),(12)C(\mathbf{x}) = \sum_{(u,v)\in E_s} w_{uv}(x_u \oplus x_v) + \sum_{(u,v)\in E_r} w_{uv}(x_u \oplus x_v), \tag*{(12)}

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 wuv=1 ∀ u,vw_{uv}=1\ \forall\ u,v.

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 CGC_G.

We rank the distinct QPU-sampled configurations by their values of CGC_G and select the BB highest-scoring configurations as recovery seeds. Let XB\mathcal{X}_B denote this set, or all distinct samples if fewer than BB are available. For a recovery procedure R\mathcal{R}, the returned assignment is

xrec∈arg⁡max⁡y∈{R(x):x∈XB}CG(y).(13)x_{\mathrm{rec}} \in\mathop{\arg\max}_{y\in\{\mathcal{R}(x):x\in\mathcal{X}_B\}} C_G(y). \tag*{(13)}

Because each trajectory retains its initial assignment unless an improvement is found,

CG(xrec)≥max⁡x∈XBCG(x).(14)C_G(x_{\mathrm{rec}}) \ge\max_{x\in\mathcal{X}_B} C_G(x). \tag*{(14)}

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 i∈Vi \in V, we define

Bi(x)=∑j∈NG(i)1[xi=xj],(15)B_i(\mathbf{x}) = \sum_{j\in N_G(i)} \mathbf{1}[x_i=x_j], \tag*{(15)}
Gi(x)=∑j∈NG(i)1[xi≠xj],(16)G_i(\mathbf{x}) = \sum_{j\in N_G(i)} \mathbf{1}[x_i\ne x_j], \tag*{(16)}

where BiB_i and GiG_i count its incident uncut (bad) and cut (good) edges, respectively. We note that the neighborhood NG(i)N_G(i) is taken in the original graph, so the gain accounts for both retained and omitted interactions. The signed vertex residue is

ρi(x)=Bi(x)−Gi(x).(17)\rho_i(\mathbf{x}) = B_i(\mathbf{x}) - G_i(\mathbf{x}). \tag*{(17)}

Since only edges incident on ii change their cut status, this residue is the gain obtained from flipping ii,

ρi(x)=CG(x⊕ei)−CG(x),(18)\rho_i(\mathbf{x}) = C_G(\mathbf{x}\mathbin{\oplus}\mathbf{e}_i) - C_G(\mathbf{x}), \tag*{(18)}

where ei\mathbf{e}_i is the binary unit vector at ii and ⊕\oplus denotes component-wise addition mod 2. Thus, ρi>0\rho_i > 0 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 ii changes only its incident edges, only the residues of ii 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 x∈{0,1}∣V∣\mathbf{x}\in\{0,1\}^{|V|} be the QPU-sampled configuration, and x′=x⊕ei\mathbf{x}'=\mathbf{x}\mathbin{\oplus}\mathbf{e}_i be the configuration obtained by flipping the assignment of vertex ii. The signed vertex residues satisfy

ρj(x′)={−ρi(x),j=i,ρj(x)−2(1−21[xi≠xj]),j∈NG(i),ρj(x),otherwise.(19)\rho_j(\mathbf{x}') = \begin{cases} -\rho_i(\mathbf{x}), & j=i,\\ \rho_j(\mathbf{x}) - 2(1-2\mathbf{1}[x_i\ne x_j]), & j\in N_G(i),\\ \rho_j(\mathbf{x}), & \text{otherwise}. \end{cases} \tag*{(19)}

The algorithm terminates when no improving single-vertex move remains or when Fmax⁡F_{\max} flips have been accepted. This is outlined in Algorithm 1 for one seed; recovery trajectories are run independently for all x(0)∈XB\mathbf{x}^{(0)}\in\mathcal{X}_B. 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 FF flips, and let x(t)\mathbf{x}^{(t)} denote the configuration after tt accepted flips, with x(0)\mathbf{x}^{(0)} the initial configuration. Then

CG(x(t+1))>CG(x(t)),t=0,…,F−1.(20)C_G(\mathbf{x}^{(t+1)}) > C_G(\mathbf{x}^{(t)}), \qquad t=0,\ldots,F-1. \tag*{(20)}

Consequently, the returned configuration satisfies

CG(x(F))≥CG(x(0)),(21)C_G(\mathbf{x}^{(F)}) \ge C_G(\mathbf{x}^{(0)}), \tag*{(21)}

with equality if and only if F=0F=0, 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 x(0)\mathbf{x}^{(0)}, Algorithm 1 accepts at most

F≤min⁡{Fmax⁡,∣E∣−CG(x(0))}(22)F \le\min\left\{F_{\max}, |E|-C_G(\mathbf{x}^{(0)})\right\} \tag*{(22)}

flips. Furthermore, if the returned configuration x^\widehat{\mathbf{x}} satisfies max⁡i∈Vρi(x^)≤0\max_{i\in V}\rho_i(\widehat{\mathbf{x}})\le0, then it is a one-flip local optimum of the original MAX-CUT objective.

Corollary 1 (Cut guarantee at local optimality). If x^\widehat{\mathbf{x}} is a one-flip local optimum, then

CG(x^)≥∣E∣2≥CG⋆2,(23)C_G(\widehat{\mathbf{x}})\ge\frac{|E|}{2}\ge\frac{C_G^\star}{2}, \tag*{(23)}

where CG⋆C_G^\star 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 Fmax⁡F_{\max}, 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 x=(0,1,0,1,1)\mathbf{x}=(0,1,0,1,1), the cut value is CG(x)=4C_G(\mathbf{x})=4, with signed residues ρ(x)=(−1,−2,−1,0,0)\boldsymbol{\rho}(\mathbf{x})=(-1,-2,-1,0,0).

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 iiGain ρi\rho_iCG(x⊕ei)C_G(\mathbf{x}\oplus\mathbf{e}_i)
0−1-13
1−2-22
2−1-13
304
404

Table 1. Effect of single-vertex flips on the initial configuration x=(0,1,0,1,1)\mathbf{x}=(0,1,0,1,1), with CG(x)=4C_G(\mathbf{x})=4.

x′=(0,1,1,0,1)x' = (0,1,1,0,1), increasing the cut value to CG(x′)=5C_G(x') = 5. 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 ss–tt 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 GG, yielding qq disjoint color classes

V=C1∪⋯∪Cq,(24)V = C_1 \cup\cdots\cup C_q, \tag*{(24)}

where vertices belonging to the same color class are non-adjacent. For each pair of distinct color classes, we define

Sab≔Ca∪Cb,1≤a<b≤q.(25)S_{ab} \coloneqq C_a \cup C_b,\qquad1 \leq a < b \leq q. \tag*{(25)}

This coloring remains fixed throughout recovery, providing Q=(q2)Q = \binom{q}{2} candidate blocks that can be reused across all QPU-sampled configurations. Since every edge joining vertices in SabS_{ab} must connect the two distinct color classes, the induced graph G[Sab]G[S_{ab}] 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 S:=Sab=Ca∪CbS := S_{ab} = C_a \cup C_b and its complement S‾=V∖S\overline{S} = V \setminus S. Given the current configuration x\mathbf{x}, we seek an assignment yS\mathbf{y}_S that maximizes the cut value of the original graph while keeping the assignments outside SS fixed, i.e.,

yS⋆∈arg⁡max⁡yS∈{0,1}∣S∣  CG(yS,xS‾).(26)\mathbf{y}_S^\star\in\underset{\mathbf{y}_S \in\{0,1\}^{|S|}}{\arg\max}\; C_G(\mathbf{y}_S,\mathbf{x}_{\overline{S}}). \tag*{(26)}

To express the above objective in terms of optimisation variables, we partition the edge set into three categories: edges internal to SS, edges internal to S‾\overline{S}, and edges connecting the two. Since the exterior assignments remain fixed, edges entirely within S‾\overline{S} contribute a constant and can be omitted from the optimization. The resulting conditional objective is

FS(yS;xS‾)=∑(u,v)∈E[S]1[yu≠yv]+∑u∈S∑v∈N(u)∩S‾1[yu≠xv].(27)F_S(\mathbf{y}_S;\mathbf{x}_{\overline{S}}) = \sum_{(u,v)\in E[S]} \mathbb{1}[y_u \ne y_v] + \sum_{u\in S}\sum_{v\in N(u)\cap\overline{S}} \mathbb{1}[y_u \ne x_v]. \tag*{(27)}

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 G[S]G[S] is bipartite, its vertices can be assigned reference labels according to their color classes:

cu={0,u∈Ca,1,u∈Cb.(28)c_u = \begin{cases} 0, & u \in C_a,\\ 1, & u \in C_b. \end{cases} \tag*{(28)}

We do a transformation of variable,

tu=yu⊕cu,u∈S,(29)t_u = y_u \oplus c_u,\qquad u \in S, \tag*{(29)}

where ⊕\oplus 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 (u,v)∈E[S](u,v) \in E[S]. Since its endpoints belong to different color classes, we have that cu≠cvc_u \ne c_v, i.e., cu⊕cv=1c_u \oplus c_v = 1. Therefore,

yu⊕yv=(tu⊕cu)⊕(tv⊕cv)=tu⊕tv⊕1.(30)y_u \oplus y_v = (t_u \oplus c_u) \oplus(t_v \oplus c_v) = t_u \oplus t_v \oplus1. \tag*{(30)}

Cutting an internal edge (u,v)∈E[S](u,v) \in E[S] becomes agreeing across that edge in the transformed variables,

1[yu≠yv]=1−1[tu≠tv].(31)\mathbf{1}[y_u \ne y_v] = 1 - \mathbf{1}[t_u \ne t_v]. \tag*{(31)}

Summing over all internal edges yields,

∑(u,v)∈E[S]1[yu≠yv]=∣E[S]∣−∑(u,v)∈E[S]1[tu≠tv].(32)\sum_{(u,v)\in E[S]} \mathbf{1}[y_u \ne y_v] = |E[S]| - \sum_{(u,v)\in E[S]} \mathbf{1}[t_u \ne t_v]. \tag*{(32)}

Thus, after dropping the constant ∣E[S]∣|E[S]|, maximizing the internal cut is equivalent to minimizing disagreements between the transformed variables ∑(u,v)∈E[S]1[tu≠tv]\sum_{(u,v)\in E[S]} \mathbf{1}[t_u \ne t_v]. 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 u∈Su \in S to a vertex v∈Sˉv \in\bar{S} whose assignment xvx_v is fixed. Consequently, its contribution depends only on the chosen assignment of uu. For each u∈Su \in S, we define the boundary reward in terms of the transformed variable tut_u. Since assigning tu=rt_u = r corresponds to the original assignment yu=r⊕cuy_u = r \oplus c_u, the number of boundary edges cut is

Hu(r)=∑v∈NG(u)∩Sˉ1[r⊕cu≠xv],r∈{0,1}.(33)H_u(r) = \sum_{v\in N_G(u)\cap\bar{S}} \mathbf{1}[r \oplus c_u \ne x_v],\qquad r \in\{0,1\}. \tag*{(33)}

Here, Hu(r)H_u(r) counts cut weight contributed by edges from uu 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,

Ku:=max⁡{Hu(0),Hu(1)},(34)K_u := \max\{H_u(0), H_u(1)\}, \tag*{(34)}
Du(r):=Ku−Hu(r).(35)D_u(r) := K_u - H_u(r). \tag*{(35)}

The unary penalties Du(r)≥0D_u(r) \ge0 represent the loss in boundary reward relative to the maximum reward attainable by vertex uu individually. Hence,

∑u∈SHu(tu)=∑u∈SKu−∑u∈SDu(tu).(36)\sum_{u\in S} H_u(t_u) = \sum_{u\in S} K_u - \sum_{u\in S} D_u(t_u). \tag*{(36)}

Combining the transformed internal interactions in Eq. (32) with the boundary penalties, the conditional MAX-CUT objective can be expressed as

FS(yS;xSˉ)=∣E[S]∣+∑u∈SKu−ES(t),(37)F_S(y_S; x_{\bar{S}}) = |E[S]| + \sum_{u\in S} K_u - \mathcal{E}_S(t), \tag*{(37)}

where

ES(t)=∑(u,v)∈E[S]1[tu≠tv]+∑u∈SDu(tu).(38)\mathcal{E}_S(t) = \sum_{(u,v)\in E[S]} \mathbf{1}[t_u \ne t_v] + \sum_{u\in S} D_u(t_u). \tag*{(38)}

Since the remaining terms are independent of tt, maximizing the conditional cut is equivalent to minimizing ES(t)\mathcal{E}_S(t).

Step 3: Reduction to an s−ts-t minimum cut: In this step, we show how the minimization in (38) is solved. The pairwise penalties take the form V(tu,tv)=1[tu≠tv]V(t_u,t_v)=\mathbf{1}[t_u\ne t_v] 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.

V(0,0)+V(1,1)≤V(0,1)+V(1,0),(39)V(0,0)+V(1,1)\le V(0,1)+V(1,0), \tag*{(39)}

Together with the unary penalties, the resulting energy admits an exact s−ts-t minimum-cut representation [11]. We construct a flow network containing one vertex for each u∈Su\in S, together with a source ss and a sink tt. For each vertex u∈Su\in S, we introduce two directed edges with capacities,

cap⁡(s,u)=Du(1),cap⁡(u,t)=Du(0).(40)\operatorname{cap}(s,u)=D_u(1),\qquad\operatorname{cap}(u,t)=D_u(0). \tag*{(40)}

For every internal edge (u,v)∈E[S](u,v)\in E[S], we introduce two oppositely directed edges, (u,v)(u,v) and (v,u)(v,u), each with unit capacity. An s−ts-t cut partitions the vertices of the flow network into two sets, one containing the source ss and the other containing the sink tt. We associate this partition with the transformed binary variables as

tu={0,u belongs to the source side,1,u belongs to the sink side.(41)t_u= \begin{cases} 0, & u\text{ belongs to the source side},\\ 1, & u\text{ belongs to the sink side}. \end{cases} \tag*{(41)}

Under this convention, assigning tu=0t_u=0 places uu on the source side, so the edge (u,t)(u,t) crosses the cut and contributes Du(0)D_u(0). Similarly, assigning tu=1t_u=1 places uu on the sink side, so the edge (s,u)(s,u) contributes Du(1)D_u(1).

For an internal edge (u,v)∈E[S](u,v)\in E[S], the corresponding vertices lie on opposite sides of the cut precisely when tu≠tvt_u\ne t_v. 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 tt is

CutCap⁡(t)=∑u∈SDu(tu)+∑(u,v)∈E[S]1[tu≠tv]=ES(t).(42)\operatorname{CutCap}(t)=\sum_{u\in S}D_u(t_u)+\sum_{(u,v)\in E[S]}\mathbf{1}[t_u\ne t_v]=\mathcal{E}_S(t). \tag*{(42)}

Since the cut capacity is exactly the transformed energy, finding a minimum s−ts-t cut yields an optimal solution to (38). To obtain this solution, we first compute a maximum s−ts-t flow and then identify the set UU of block vertices reachable from ss 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,

tu⋆={0,u∈U,1,u∈S∖U.(43)t_u^\star= \begin{cases} 0, & u\in U,\\ 1, & u\in S\setminus U. \end{cases} \tag*{(43)}

Finally, reversing the transformation in (29), we obtain the corresponding block assignments

yu⋆=tu⋆⊕cu,u∈S.(44)y_u^\star=t_u^\star\oplus c_u,\qquad u\in S. \tag*{(44)}

The resulting yS⋆\mathbf{y}_S^\star maximizes the original MAX-CUT objective over the selected block, with all assignments outside SS 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 x\mathbf{x}, we rank the candidate blocks according to their aggregate signed vertex residues,

Rab(x)=∑u∈Sabρu(x),(45)R_{ab}(\mathbf{x})=\sum_{u\in S_{ab}}\rho_u(\mathbf{x}), \tag*{(45)}

where ρu(x)\rho_u(\mathbf{x}) is the gain obtained by flipping vertex uu individually. Blocks with larger residues are examined first, as they indicate a greater aggregate tendency toward improving single-vertex assignments.

For each block SS, we solve the conditional optimization exactly using the s−ts-t minimum-cut construction described previously. The improvement in the original objective is

ΔS⋆(x)=CG(yS⋆,xS‾)−CG(x).(46)\Delta_S^\star(\mathbf{x})=C_G(\mathbf{y}_S^\star,\mathbf{x}_{\overline{S}})-C_G(\mathbf{x}). \tag*{(46)}

Since the current block assignment is feasible for the conditional optimization, ΔS⋆(x)≥0\Delta_S^\star(\mathbf{x})\ge0. We accept an update only when ΔS⋆(x)>0\Delta_S^\star(\mathbf{x})>0. 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 G=(V,E)G=(V,E), color classes {Ca}a=1q\{C_a\}_{a=1}^{q}, initial configuration x(0)\mathbf{x}^{(0)}

Ensure: Recovered configuration x\mathbf{x}

  1. x←x(0)\mathbf{x} \gets\mathbf{x}^{(0)}

  2. repeat

  3. improved ←\gets false

  4. for each block S=Ca∪CbS=C_a\cup C_b, a<ba<b do

  5. Construct the flow network for SS

  6. Compute a maximum ss–tt flow

  7. Find the source-reachable set UU in the network

  8. Set tu∗=0t_u^*=0 if u∈Uu\in U, and tu∗=1t_u^*=1 otherwise

  9. Recover yu∗=tu∗⊕cuy_u^*=t_u^*\oplus c_u for each u∈Su\in S

  10. if CG(yS∗,xSˉ)>CG(x)C_G(y_S^*,x_{\bar S})>C_G(\mathbf{x}) then

  11. xS←yS∗\mathbf{x}_S\gets y_S^*

  12. improved ←\gets true

  13. break

  14. end if

  15. end for

  16. until improved = false

  17. return x\mathbf{x}

Every accepted update strictly increases the integer-valued cut objective. Since CG(x)≤∣E∣C_G(\mathbf{x})\leq|E|, the number of accepted updates is bounded by

A≤∣E∣−CG(x(0)).(47)A\leq|E|-C_G(\mathbf{x}^{(0)}). \tag*{(47)}

Thus, recovery terminates in finitely many updates without requiring an explicit budget. Moreover, with Q=(q2)Q=\binom{q}{2} candidate blocks, at most Q(A+1)Q(A+1) 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

CG(xfinal)≥∣E∣2≥CG∗2.(48)C_G(\mathbf{x}_{\mathrm{final}})\geq\frac{|E|}{2}\geq\frac{C_G^*}{2}. \tag*{(48)}

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:

  1. Circuit-depth reduction: The extent to which surrogate Hamiltonians reduce transpiled two-qubit depth while satisfying hardware-specific depth constraints.

  2. Solution quality from surrogate sampling: The ability of reduced QAOA circuits to generate configurations with high cut values on the original graph.

  3. 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 HAML​​IB [12], comprising 20 instances each of 6-regular and Erdős–Rényi (G(n,p)G(n,p)) graphs at each problem size n∈40,60,100n \in40, 60, 100. 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.

SettingConfiguration
Quantum processoribm_kingston
Graph families6-regular and G(n,p)G(n,p) (HAML​​IB)
Problem sizesn=40,60,100n = 40, 60, 100
QPU shots10,000 per circuit
CompilationSATMapper [7], commuting-gate routing [3]; Qiskit optimization level 3
Transpiler seed123
Noise handlingGate and measurement twirling enabled; dynamical decoupling disabled
QAOA layersp∈{1,2,3}p \in\{1, 2, 3\}
Depth budget LL150 (6-regular); 200 (G(n,p)G(n,p))
Recovery candidates50 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 (p,k)(p,k), prioritizing the QAOA depth p∈{1,2,3}p \in\{1,2,3\} before the interaction-band radius kk. Feasibility requires that every vertex retains at least one incident edge and that the transpiled two-qubit depth does not exceed the prescribed budget LL.

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 G(n,p)G(n,p) graphs, motivating budgets of L=150L=150 and L=200L=200, 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 GG. Let CG(x)C_G(x) denote the cut value of configuration xx and CG∗C_G^* the optimal cut value, certified using Gurobi for every instance. We define the approximation ratio as

AR⁡(x)=CG(x)CG∗.(49)\operatorname{AR}(x)=\frac{C_G(x)}{C_G^*}. \tag*{(49)}

Recovery Evaluation: To assess the improvement due to classical recovery, we select 50 distinct starting configurations Si50S_i^{50} from the surrogate QAOA samples of instance ii. Each configuration is refined independently using recovery method RR. We compare the best cut values before and after recovery using

AR⁡i,raw(50)=max⁡x∈Si50AR⁡(x),(50)\operatorname{AR}_{i,\mathrm{raw}}^{(50)}=\max_{x\in S_i^{50}}\operatorname{AR}(x), \tag*{(50)}
AR⁡i,R(50)=max⁡x∈Si50AR⁡(R(x)).(51)\operatorname{AR}_{i,R}^{(50)}=\max_{x\in S_i^{50}}\operatorname{AR}(R(x)). \tag*{(51)}

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 ∣E∣=3n|E|=3n interactions. We use the fixed-angle approach of [18], with QAOA parameters expressed in the positive-ZZZZ convention of our implementation. The parameter values for p=1,2,3p=1,2,3 are in Table 3.

ppβ\betaγ\gamma
1(0.39270)(0.39270)(−0.42055)(-0.42055)
2(0.51825,0.27656)(0.51825, 0.27656)(−0.32421,−0.57977)(-0.32421, -0.57977)
3(0.57265,0.39892,0.21694)(0.57265, 0.39892, 0.21694)(−0.28142,−0.50403,−0.57681)(-0.28142, -0.50403, -0.57681)

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 n=40n = 40, 60, and 100, respectively. The p⋆p^\star column counts instances selected at each QAOA depth. Entries are means ±\pm sample standard deviations; ranges are given in brackets.

nnCG⋆‾\overline{C^\star_G}p⋆=1/2/3p^\star= 1/2/3k⋆‾\overline{k^\star} [range]Retained (%)
4092.3±1.292.3 \pm1.20/0/208.5±1.18.5 \pm1.1 [6, 10]70.5±3.270.5 \pm3.2
60140.1±1.8140.1 \pm1.80/2/184.7±1.64.7 \pm1.6 [3, 10]49.2±5.849.2 \pm5.8
100237.4±1.9237.4 \pm1.96/8/610.2±8.610.2 \pm8.6 [3, 25]51.4±15.751.4 \pm15.7

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 n=40n = 40, 60, and 100, respectively. For details on reduction in the transpiled two-qubit gate counts, readers can refer Table 7 in Appendix § 11.

Transpiled two-qubit depth of the full-graph and MinLA-band circuits on ibm_kingston

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 pp. Bars are means over 20 instances; error bars are sample standard deviations.

FamilynnFull graphSurrogateReduction (%)
6-regular403769.652481.1534.12
6-regular608642.853402.1559.72
6-regular10017490.656004.9557.52
G(n,p)G(n,p)401881.451876.000.28
G(n,p)G(n,p)604344.854343.300.04
G(n,p)G(n,p)10012379.459224.6525.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 10020∑i=120(1−Nsur,i/Nfull,i)\frac{100}{20}\sum_{i=1}^{20}(1-N_{\mathrm{sur},i}/N_{\mathrm{full},i}), where Nfull,iN_{\mathrm{full},i} and Nsur,iN_{\mathrm{sur},i} 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.

Bar chart of solution quality on the original graphs for 40, 60, and 100 vertices, comparing initial QPU samples, signed-edge recovery, and bipartite-block 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 n=100n = 100, 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 n=40n = 40 and n=60n = 60, 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 n=100n = 100, 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.

Two-panel bar chart of classical recovery effort, showing mean accepted updates per start and mean wall time per recovery run for signed-edge and bipartite-block recovery at 40, 60, and 100 vertices

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 n=100n = 100, 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 n∈{40,60,100}n \in\{40, 60, 100\}. 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 p=1p = 1 and train the angles using a 15×1515 \times15 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 n=40n = 40, 60, and 100, respectively, and is completely classical.

Surrogate Construction and Circuit Depth: We prescribe a maximum transpiled two-qubit depth of L=200L = 200, 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 n=40n = 40 and n=60n = 60, the full-graph circuits satisfy the depth constraint, allowing all interactions to be retained. At n=100n = 100, the selected bands retain 52.2% of the original edges on average.

nn∣E∣|E|CG⋆C_G^\starp⋆=1/2/3p^\star= 1/2/3k⋆k^\star [range]Retained (%)
40283.0±10.7283.0 \pm10.7186.3±6.8186.3 \pm6.820/0/036.2±1.536.2 \pm1.5 [33, 39]100.0±0.0100.0 \pm0.0
60483.9±17.4483.9 \pm17.4318.9±10.3318.9 \pm10.320/0/055.1±1.955.1 \pm1.9 [51, 58]100.0±0.0100.0 \pm0.0
100910.7±32.5910.7 \pm32.5600.1±18.1600.1 \pm18.120/0/019.0±1.219.0 \pm1.2 [16, 21]52.2±2.652.2 \pm2.6

Table 5. Selected MinLA bands for 20 HAMLIB gnp-k_4 instances per size under L=200L = 200. The p⋆p^\star column counts instances selected at each QAOA depth. Entries are means ±\pm sample standard deviations; ranges are given in brackets.

Figure 9 reports the transpiled two-qubit depths. At n=40n = 40 and n=60n = 60, the depths remain nearly unchanged, consistent with full interaction retention. We emphasise that full-edge retention at n=40n = 40 and n=60n = 60 is specific to the tested p=1p = 1 circuits. While we have not tested these instances for p>1p > 1, increasing pp pushes the full-graph (n=40n = 40, 60) circuits’ two-qubit depths above 200, necessitating a narrower MinLA band and dropping some edges. At n=100n = 100, 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%.

Transpiled two-qubit depth of the full-graph and MinLA-band circuits

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 L=200L = 200.

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 n=40n = 40 and n=60n = 60, where all interactions are retained, these improvements reflect classical refinement of full-graph QAOA samples. At n=100n = 100, recovery additionally addresses the interactions omitted during surrogate construction, improving the resulting configurations against the complete objective.

Best-of-50 approximation ratios for initial and recovered solutions

Figure 10. Best-of-50 approximation ratios on the original G(n,p)G(n,p) graphs, over 20 instances per size for p=1p = 1 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 n=100n = 100, 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.

Mean accepted updates per recovery start

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

Mean wall time per recovery start

(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 p=1p = 1 Hamiltonian remains executable within the prescribed budget at smaller sizes, depth-constrained surrogates become necessary at n=100n = 100. 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 L=150L = 150 for the 6-regular experiments and L=200L = 200 for G(n,p)G(n,p). At n=100n = 100, both families retain approximately half of their interactions. At smaller sizes, the G(n,p)G(n,p) bands retain all edges under L=200L = 200, since the full p=1p = 1 circuits already satisfy that limit. The 6-regular experiments use greater QAOA depths for many instances, and consequently require edge removal to meet L=150L = 150.

nn6-regular p⋆=1/2/3p^{\star} = 1/2/3LLRetained (%)G(n,p)G(n,p) ppLL / Retained (%)
400/0/2015070.5 ±\pm 3.21200/100.0
600/2/1815049.2 ±\pm 5.81200/100.0
1006/8/615051.4 ±\pm 15.71200/52.2 ±\pm 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 pp 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

⟨x∣HC∣x⟩=CG(x).(52)\langle x|H_C|x\rangle= C_G(x). \tag*{(52)}

Therefore, the ground states of −HC-H_C correspond to maximum cuts of GG.

The QAOA parameters are chosen to minimize the expected energy,

Ep(θ)=⟨ψp(θ)∣−HC∣ψp(θ)⟩.(53)E_p(\boldsymbol{\theta}) = \langle\psi_p(\boldsymbol{\theta})| -H_C |\psi_p(\boldsymbol{\theta})\rangle. \tag*{(53)}

For fixed parameters, measurements in the computational basis yield candidate bitstrings with probabilities

Pθ(x)=∣⟨x∣ψp(θ)⟩∣2,(54)P_{\boldsymbol{\theta}}(x) = |\langle x|\psi_p(\boldsymbol{\theta})\rangle|^2, \tag*{(54)}

from which the best observed partition can be selected.

Since the terms of HCH_C commute, each cost layer decomposes, up to a global phase, as

UC(γ)≐∏(u,v)∈ERZZ(u,v)(−γ),(55)U_C(\gamma) \doteq\prod_{(u,v)\in E} R_{ZZ}^{(u,v)}(-\gamma), \tag*{(55)}

where RZZ(ϕ)=e−iϕZ⊗Z/2R_{ZZ}(\phi) = e^{-i\phi Z\otimes Z/2}. Thus, a pp-layer QAOA circuit contains p∣E∣p|E| 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,

θ⋆=arg min⁡θ Ep(θ).(56)\boldsymbol{\theta}^{\star} = \underset{\boldsymbol{\theta}}{\operatorname{arg\,min}}\ E_p(\boldsymbol{\theta}). \tag*{(56)}

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 pp, the expectation of an edge observable ZuZvZ_uZ_v depends only on the subgraph within its pp-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 dd-regular graph, we use the fixed-angle approach of [18], which exploits QAOA locality to obtain parameters from the corresponding infinite dd-regular tree

(γFA,βFA)=AFA(d,p).(57)(\gamma^{\mathrm{FA}},\beta^{\mathrm{FA}}) = A_{\mathrm{FA}}(d,p). \tag*{(57)}

For dd-regular graphs with girth greater than 2p+12p+1, all edge light cones have the same tree structure. The expected cut fraction therefore depends only on dd, pp, 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 p=1p=1 using the graph-training methodology of the QAOA training pipeline [9]. This method performs a coarse (β,γ)(\beta,\gamma) grid search followed by local refinement. The EfficientDepthOneEvaluator computes the required correlators from reduced 4×44 \times4 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 (q0,…,qn−1)(q_0,\ldots,q_{n-1}) embedded in the hardware coupling graph. It alternates between two layers of disjoint SWAP operations,

Seven={(q0,q1),(q2,q3),…},Sodd={(q1,q2),(q3,q4),…}.(58)\mathcal{S}_{\mathrm{even}} = \{(q_0,q_1),(q_2,q_3),\ldots\}, \quad \mathcal{S}_{\mathrm{odd}} = \{(q_1,q_2),(q_3,q_4),\ldots\}. \tag*{(58)}

These alternating layers systematically change the positions of logical qubits, allowing the required RZZR_{ZZ} 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 μ\mu, let AL(μ)\mathcal{A}_L(\mu) denote the set of logical qubit pairs that become adjacent within the first LL layers of the SWAP strategy. The objective is to determine

L⋆=min⁡μ,L{L:E(G)⊆AL(μ)}.(59)L^\star= \min_{\mu,L}\{L : E(G) \subseteq\mathcal{A}_L(\mu)\}. \tag*{(59)}

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 RZZR_{ZZ} 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 RZZR_{ZZ} 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 ii be the flipped vertex. This gives that xi′=1−xix'_i = 1 - x_i and xj′=xjx'_j = x_j for every j≠ij \ne i. We distinguish three cases.

Case j=ij=i: Using the definition of the signed vertex residue (17), we have,

ρi(x)=∑j∈NG(i)(1−21[xi≠xj]).(60)\rho_i(\mathbf{x}) = \sum_{j \in N_G(i)} (1 - 2\mathbb{1}[x_i \ne x_j]). \tag*{(60)}

Every edge incident on ii satisfies

1[xi′≠xj′]=1−1[xi≠xj].(61)\mathbb{1}[x'_i \ne x'_j] = 1 - \mathbb{1}[x_i \ne x_j]. \tag*{(61)}

The above equation can be interpreted as if (i,j)(i,j) is cut after flipping ii, then it was originally a bad/uncut edge. Consequently,

ρi(x′)=∑j∈NG(i)(1−2(1−1[xi≠xj]))=−ρi(x).(62)\rho_i(\mathbf{x}') = \sum_{j \in N_G(i)} (1 - 2(1 - \mathbb{1}[x_i \ne x_j])) = -\rho_i(\mathbf{x}). \tag*{(62)}

Case j∈NG(i)j \in N_G(i): Only the contribution of edge (i,j)(i,j) to ρj\rho_j changes. Writing aij=1[xi≠xj]a_{ij} = \mathbb{1}[x_i \ne x_j], we obtain

ρj(x′)−ρj(x)=(1−2(1−aij))−(1−2aij)=−2(1−2aij).(63)\rho_j(\mathbf{x}') - \rho_j(\mathbf{x}) = (1 - 2(1-a_{ij})) - (1 - 2a_{ij}) = -2(1 - 2a_{ij}). \tag*{(63)}

Otherwise: Neither the assignment of jj nor that of any of its neighbors changes. Every contribution to its residue therefore remains unchanged, giving

ρj(x′)=ρj(x).(64)\rho_j(\mathbf{x}') = \rho_j(\mathbf{x}). \tag*{(64)}

Proof of Theorem 1

Proof. If vertex iti_t is selected at iteration tt, the acceptance condition and Eq. (18) give

CG(x(t+1))−CG(x(t))=ρit(x(t))>0.(65)C_G\left(x^{(t+1)}\right) - C_G\left(x^{(t)}\right) = \rho_{i_t}\left(x^{(t)}\right) > 0. \tag*{(65)}

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 CGC_G is integer-valued, each improvement is at least one. Moreover, CG(x)≤∣E∣C_G(x) \leq\lvert E\rvert for every configuration. Consequently, after FF accepted flips,

CG(x(0))+F≤CG(x(F))≤∣E∣,(66)C_G\left(x^{(0)}\right) + F \leq C_G\left(x^{(F)}\right) \leq\lvert E\rvert, \tag*{(66)}

which establishes the bound in Eq. (22). By Eq. (18), the residue ρi(x)\rho_i(x) equals the change in cut value obtained by flipping vertex ii. 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, ρi(x^)≤0\rho_i(\widehat{x}) \leq0 for every i∈Vi \in V, implying

∑i∈VBi(x^)≤∑i∈VGi(x^).(67)\sum_{i\in V} B_i(\widehat{x}) \leq\sum_{i\in V} G_i(\widehat{x}). \tag*{(67)}

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,

∑i∈VBi(x^)=2(∣E∣−CG(x^)),∑i∈VGi(x^)=2CG(x^).(68)\sum_{i\in V} B_i(\widehat{x}) = 2\left(\lvert E\rvert- C_G(\widehat{x})\right), \qquad\sum_{i\in V} G_i(\widehat{x}) = 2C_G(\widehat{x}). \tag*{(68)}

It follows that 2(∣E∣−CG(x^))≤2CG(x^)2(\lvert E\rvert- C_G(\widehat{x})) \leq2C_G(\widehat{x}) yielding CG(x^)≥∣E∣/2C_G(\widehat{x}) \geq\lvert E\rvert/2. Since CG⋆≤∣E∣C_G^\star\leq\lvert E\rvert, 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 n=40n = 40, 60, 100, respectively. For G(n,p)G(n,p) graphs, the mean reduction is 25.5% at n=100n = 100. Gate counts remain essentially unchanged at n=40n = 40 and n=60n = 60, where the selected surrogates retain all original edges; the small differences arise between the compiled implementations.

References

  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [19]Daniel J. Egger, Jakub Mareček, and Stefan Woerner. Warm-starting quantum optimization. Quantum, 5:479, June 2021.DOI
  20. [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. [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. [22]McClean et al. Barren plateaus in quantum neural network training landscapes. Nature Communications, 2018.DOI
  23. [23]Cerezo et al. Variational quantum algorithms. Nature Reviews Physics, 2021.DOI
  24. [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. [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. [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

Paper details

vlnc:W_credfn97
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents