betaFeedback

WorksPhysics and Astronomy

Efficient XXXX Placement Strategies for Energy-Gap Enhancement in Quantum Annealing

Abstract

Quantum annealing offers the prospect of a computational advantage over classical methods for certain classes of combinatorial optimisation problems. Its performance, however, is fundamentally constrained by the minimum spectral gap between the ground state and the first excited state encountered during the annealing process. When this gap closes exponentially with problem size, the runtime required to maintain adiabatic evolution can likewise grow exponentially, severely limiting the practical efficiency of the annealer. For problems including the maximum weight independent set (MWIS), previous work has shown that introducing XXXX interactions along problem-graph edges can substantially enlarge the minimum energy-gap and thereby improve annealing performance. In practice, however, current quantum annealing hardware does not support these interactions natively and methods for implementing effective XXXX couplings come with hardware overhead and connectivity constraints. These limitations motivate the use of only a limited number of XXXX interactions. In this paper, we investigate XXXX placement strategies for MWIS instances under both resource and topological constraints, and demonstrate that careful selection of the placements can substantially increase the minimum energy-gap. We evaluate these strategies through a detailed statistical analysis of both deliberately constructed hard MWIS instances and random Erdős–Rényi graphs. Notably, these strategies are particularly effective for hard MWIS instances with initially small minimum gaps, where targeted placement yields the largest relative improvements.

Introduction

Combinatorial optimisation problems manifest practically in areas such as routing [1], resource allocation [2, 3, 4], and portfolio optimisation [5]. Rather than applying classical optimisation algorithms, quantum annealing (QA) provides a framework for solving combinatorial optimisation problems by encoding the solution to a problem instance in the ground state of a problem Hamiltonian.

By applying QA, the hope is for quantum effects, in particular tunnelling, to allow the system to move through optimisation landscapes in ways that differ from classical thermal search, therefore making the search more efficient [6]. Starting from the ground state of an initial Hamiltonian that is easy to prepare, the system is evolved continuously towards the problem Hamiltonian. Provided that the evolution is sufficiently slow, the system remains in its instantaneous ground state and therefore terminates in a state encoding the optimal solution [7, 8].

Unfortunately QA is limited by the spectral gap between the instantaneous ground state and the excited states. The runtime required for adiabatic evolution scales inversely with the square of the minimum instantaneous spectral gap during the anneal; consequently, instances for which the gap becomes exponentially small with increasing problem size can require exponentially long annealing times. Avoided level crossings associated with small gaps

therefore constitute an important bottleneck to the practical performance of QA.

One approach to mitigating this problem is to modify the annealing path by introducing additional terms into the annealing Hamiltonian. There has been a particular interest in the introduction of two-local XXXX interactions, which have been shown to substantially enlarge the minimum gap for various QA settings [9, 10, 11, 12, 13, 14]. In the context of the maximum weight independent set (MWIS) problem, previous work has demonstrated that placing XXXX interactions along edges of the problem graph can significantly improve the minimum spectral gap [15].

The unrestricted addition of XXXX interactions, however, is unlikely to be practical on near-term QA hardware. Currently, neither superconducting nor neutral-atom analogue platforms on which QA is run natively support two-local XXXX interactions. For superconducting flux qubits of the type used by D-Wave, for example, an XXXX interaction could theoretically be built directly into hardware via inductive [16] or capacitive [17] couplers. However, as Kerman has shown [18], both methods only yield a significant XXXX interaction when large local XX fields are applied to both qubits. Gadgets that implement effective XXXX terms [19, 20, 21] using available interactions come with their own hardware overhead and connectivity restrictions. This motivates a more constrained question: if only a limited number of XXXX edges can be placed, where should they be positioned in order to obtain the greatest improvement in the minimum gap?

In this work, we investigate this question for MWIS instances under both resource and connectivity constraints. Rather than assuming arbitrary native XXXX interactions, we consider specifically the constraints associated with the parity-encoding based gadget proposed in [20]. The gadget is able to implement chains of effective XXXX interactions with an overhead of one additional qubit per chain. Experimental implementation of the gadget on D-Wave hardware yielded a three order of magnitude ground-state fidelity improvement for an illustrative setting. However, in addition to being topologically restricted to chains of interactions, the gadget comes with other subtleties that encourage limiting the number of XXXX interactions to be introduced. We therefore study XXXX placement as a constrained selection problem, in which both the number and topology of the available XXXX interactions are restricted.

We compare several strategies for selecting coupling locations and evaluate their performance on both deliberately constructed hard MWIS instances and ensembles of Erdős–Rényi (ER) random graphs. Our numerical results show that strategically chosen subsets of XXXX edges can produce substantial enhancements of the minimum energy gap despite these implementation constraints. Notably, the improvement is most pronounced for instances where the original annealing paths exhibit particularly small minimum gaps, suggesting that selective coupling placement is especially useful for the hardest instances.

The remainder of this paper is organised as follows. Section II introduces the MWIS problem and its encoding as a quantum annealing Hamiltonian. Section III describes the parity-based gadget implementation of effective XXXX couplings and the topological constraints that it imposes. Section IV introduces the XXXX-interaction placement strategies. § 0.5 and VI present our numerical analysis on planted hard- and random ER-instances of the MWIS problem. We conclude in Sec. VII with a discussion of the implications of these results and possible extensions.

Quantum annealing for the MWIS problem

Let

G=(V,E)(1)G=(V,E) \tag*{(1)}

be an undirected graph with vertex set V={1,…,n}V=\{1,\ldots,n\} and edge set EE, and let each vertex i∈Vi\in V be assigned a positive weight wiw_i. An independent set is a subset S⊆VS\subseteq V such that no two vertices in SS are adjacent. The maximum weight independent set problem asks for an independent set of maximum total weight,

S⋆=arg max⁡S⊆V ∑i∈Swi.(2)S^\star=\underset{S\subseteq V}{\operatorname{arg\,max}}\ \sum_{i\in S}w_i. \tag*{(2)}

By introducing binary variables xi∈{0,1}x_i\in\{0,1\}, where xi=1x_i=1 indicates that vertex ii is included in the independent set, MWIS can be expressed as the constrained optimisation problem

max⁡x∈{0,1}n ∑i=1nwixi,(3)\underset{x\in\{0,1\}^n}{\operatorname{max}}\ \sum_{i=1}^{n}w_ix_i, \tag*{(3)}

subject to

xixj=0,(i,j)∈E.(4)x_ix_j=0,\qquad(i,j)\in E. \tag*{(4)}

To encode this as a quantum Hamiltonian, we make the standard translation

xi=1+zi2,(5)x_i=\frac{1+z_i}{2}, \tag*{(5)}

where zi=±1z_i=\pm1. So, provided the edge penalty is chosen sufficiently large, the ground state of the Hamiltonian

H^p=∑i∈V(diJzz−2wi)Zi+∑(i,j)∈EJzzZiZj(6)\hat{H}_p=\sum_{i\in V}(d_iJ_{zz}-2w_i)Z_i+\sum_{(i,j)\in E}J_{zz}Z_iZ_j \tag*{(6)}

corresponds to a maximum-weight independent set of the original graph. In Eq. (6), did_i is the degree of vertex ii, and wiw_i is its weight.

The conventional transverse-field driver Hamiltonian is

HD=−∑i=1nXi(7)H_D=-\sum_{i=1}^{n}X_i \tag*{(7)}

whose ground state is the uniform superposition of computational basis states. A standard annealing schedule interpolates between Eqs. (2.7) and (2.6),

H(s)=A(s)HD+B(s)HP,s∈[0,1],(8)H(s)=A(s)H_D+B(s)H_P,\qquad s\in[0,1], \tag*{(8)}

where A(0)≫B(0)A(0)\gg B(0) and B(1)≫A(1)B(1)\gg A(1). Furthermore, the spectral gap of the Hamiltonian is

Δ(s)=E1(s)−E0(s),(9)\Delta(s)=E_1(s)-E_0(s), \tag*{(9)}

and its minimum over the anneal is defined as

Δmin⁡=min⁡s∈[0,1]Δ(s).(10)\Delta_{\min}=\min_{s\in[0,1]}\Delta(s). \tag*{(10)}

For difficult instances, the interpolation in Eq. (8) may encounter a narrow avoided crossing and hence a small value of Δmin⁡\Delta_{\min}. It is these small gaps which we aim to mitigate through the introduction of XXXX interactions.

Parity-based gadget implementation of XX couplings

To obtain a hardware-motivated model for how such XXXX interactions might enter the anneal in practice, we consider the parity-based XXXX gadget introduced in [20]. We summarise its key concepts below and refer interested readers to that work for the full description. The purpose of the gadget is to provide an encoded logical setting that includes XXXX interactions with a physical setting that only includes fields and interactions that we have access to—i.e., XX fields, ZZ fields and ZZZZ interactions. To implement an XXXX interaction between two logical qubits, we encode each logical qubit in the parity of a pair of physical qubits, with the two pairs sharing one physical qubit. Denoting logical variables by a tilde, the encoding is defined as

z~1=z0z1,z~2=z1z2.(11)\widetilde{z}_1 = z_0z_1,\qquad\widetilde{z}_2 = z_1z_2. \tag*{(11)}

The corresponding logical Pauli-ZZ operators are therefore

Z~1=Z0Z1,Z~2=Z1Z2.(12)\widetilde{Z}_1 = Z_0Z_1,\qquad\widetilde{Z}_2 = Z_1Z_2. \tag*{(12)}

Since Z2=IZ^2 = I, a ZZZZ interaction between the two logical qubits reduces to a two-body interaction between the outer physical qubits:

Z~1Z~2=Z0Z1Z1Z2=Z0Z2.(13)\widetilde{Z}_1\widetilde{Z}_2 = Z_0Z_1Z_1Z_2 = Z_0Z_2. \tag*{(13)}

The logical transverse operators can be identified by considering how flipping each physical qubit affects the encoded parities. Flipping either outer qubit, q0q_0 or q2q_2, changes only one of the two logical parities. Thus, the individual logical XX operators can be represented as

X~1=X0,X~2=X2.(14)\widetilde{X}_1 = X_0,\qquad\widetilde{X}_2 = X_2. \tag*{(14)}

In contrast, the central physical qubit q1q_1 is shared by both parity pairs, so flipping it simultaneously reverses both logical parities. Its transverse operator therefore implements the logical XXXX interaction:

X~1X~2=X1.(15)\widetilde{X}_1\widetilde{X}_2 = X_1. \tag*{(15)}

The gadget can be extended to produce a chain of logical qubits with XXXX interactions between them through effectively chaining parity encoded qubits together. The cost is the loss of local XX driving on the internal logical qubits. This can be understood through the fact that neither of the two physical qubits encoding these internal logical qubits is associated with that logical qubit alone.

The parity-based gadget construction also imposes restrictions on the placement of the XXXX terms. Under the parity encoding, a transverse field acting on a physical qubit induces a transverse X~i\widetilde{X}_i operator on each parity variable involving that qubit. Consequently, a physical qubit belonging to a single parity variable gives rise to a one-body transverse term, whereas a qubit shared by two parity variables generates a two-body XXXX interaction. More generally, a branching point of degree kk would produce a kk-body transverse interaction in the parity-encoded description. To retain a driver Hamiltonian containing only one- and two-body transverse terms, nodes in the XXXX-interaction graph must therefore have maximum degree two. Its connected components are consequently restricted to non-branching chains or closed loops.

The gadget comes with one additional complication when embedded within a larger graph structure. The parity encoding of a logical qubit into two physical qubits means that logical ZZZZ term between an encoded qubit and a non-encoded qubit require physical three-local ZZ interactions. Similarly, a ZZZZ interaction between two encoded qubits that are not adjacent in the XXXX-interaction graph requires a physical four-local ZZ term. Such three- and four-local ZZ interactions can be emulated through standard reduction techniques at the cost of one and two additional ancillary qubits respectively per interaction [22]. This additional qubit overhead motivates limiting the number of gadget XXXX interactions that are included.

In this work we will not be considering the physical Hamiltonian associated with the gadget. Rather, we directly introducing XXXX interactions into the annealing Hamiltonian in a way that is guided by the constraints on the XXXX-interaction graph that the gadget imposes. The XXXX interactions enter the annealing Hamiltonian as part of the driver, such that the new driver can be written as

HD=HD′−∑(i,j)∈ExxnXiXj,(16)H_{\mathrm{D}} = H_{\mathrm{D}}' - \sum_{(i,j)\in E_{\mathrm{xx}}}^{n} X_iX_j, \tag*{(16)}

where ExxE_{\mathrm{xx}} denotes the set of XXXX edges and is restricted to consisting of disconnected chains and loops, and HD′H_{\mathrm{D}}' is obtained from standard driver by removing the single-qubit XX fields on qubits incident to two edges in ExxE_{\mathrm{xx}}. The practical placement problem studied in the following section can therefore be formulated schematically as

choose⁡ExxExx⊆E(17)\underset{E_{\mathrm{xx}}}{\operatorname{choose}}\quad E_{\mathrm{xx}} \subseteq E \tag*{(17)}

so as to improve

Δmin⁡(Exx),(18)\Delta_{\min}(E_{\mathrm{xx}}), \tag*{(18)}

subject simultaneously to the XXXX-budget constraint ∣Exx∣≤K|E_{\mathrm{xx}}| \leq K and the topological constraints arising from the parity-based gadget implementation. Section IV considers several strategies for making this choice, while their numerical analysis on planted hard- and ER-instances can be found in § 0.5 and Section VI.

Constrained XX placement strategies

In our investigation, we consider the following XXXX placement strategies, each inspired by some property of the MWIS problem instance. All three strategies can be created prior to running the quantum annealer, in time polynomial in the size of the graph.

Definition IV.1. (Vertex weight conflict). For MWIS, difficult competition often occurs around edges connecting two high-weight vertices, where both vertices are individually attractive, but they cannot both be selected since that would violate the independent-set constraint.

This strategy therefore ranks each problem edge (i,j)(i,j) by its score

min⁡(wi,wj),(19)\min(w_i,w_j), \tag*{(19)}

in descending order, and selects the top kk edges with the highest min⁡(wi,wj)\min(w_i,w_j).

Definition IV.2. (Field-strength ambivalence). The problem Hamiltonian expressing the MWIS problem as equation (6) encodes the tension when choosing whether to include a vertex ii in the independent-set through the term

hi=(diJzz−2wi)Zi.(20)h_i = (d_iJ_{zz} - 2w_i)Z_i. \tag*{(20)}

On the one hand, since zi=±1z_i = \pm1, including vertex ii in the set will lower the energy of the Hamiltonian by 4wi4w_i, but at the same time it raises the energy by the penalty term diJzzd_iJ_{zz}. Therefore, we reason that vertices with small hih_i values are close to being locally balanced between selected and not selected, and are likely to be sites of ambivalence. Thus, this strategy ranks each problem edge (i,j)(i,j) by its score

s=1∣hi∣+∣hj∣,(21)s = \frac{1}{\lvert h_i\rvert+ \lvert h_j\rvert}, \tag*{(21)}

in descending order, and outputs the top kk edges with the highest score ss.

Definition IV.3. (Edge-betweenness centrality). In graph theory, centrality quantifies the structural importance or influence of a vertex or edge within a graph. There are various measures of centrality, but for our purposes we will use the measure of shortest-path edge-betweenness implemented by python’s NetworkX package [23, 24].

The shortest-path edge-betweenness centrality measures how often an edge lies on shortest paths between other pairs of vertices. An edge has high betweenness if it acts as a bottleneck or bridge through which many graph paths pass. For an edge ee, is it defined as

CB(e)=∑s,t∈Vσ(s,t∣e)σ(s,t),(22)C_B(e) = \sum_{s,t\in V} \frac{\sigma(s,t\mid e)}{\sigma(s,t)}, \tag*{(22)}

where VV is the set of vertices, σ(s,t)\sigma(s,t) is the number of shortest-paths between vertex ss and tt, and σ(s,t∣e)\sigma(s,t\mid e) is the number of those paths passing through edge ee.

For a graph G=(V,E)G = (V,E), the function NetworkX.edge_betweenness_centrality(G) computes this quantity efficiently in O(∣V∣⋅∣E∣)O(\lvert V\rvert\cdot\lvert E\rvert) time using Brandes’ algorithm [25]. In this strategy, we therefore rank each problem edge (i,j)(i,j) by its edge-betweenness centrality score, in descending order. Then the strategy produces kk edges with the highest shortest-path betweenness score.

Numerical analysis on constructed small-gap instances

We follow the procedure introduced in [26] to generate 100 pseudo-random 10-vertex MWIS graphs with small minimum spectral gaps and four planted optima per graph. The vertices comprising each independent set (i.e., local optimum) are selected probabilistically, with vertices already shared by another set suppressed by a factor of 0.5.

The global optimum is assigned a total weight of 2.05, while the remaining planted optima are assigned weights drawn uniformly from the interval [1.9,2.00][1.9, 2.00], thereby enforcing a minimum weight separation of 0.05. Then the remaining weight associated with each planted optimum is distributed evenly among its constituent vertices. Edges are then introduced between pairs of vertices that do not belong to a common planted optimum.

For MWIS problem instances generated using the pseudo-random construction described above, Figure 1 shows the distribution of minimum spectral gaps, Δ\Delta, prior to the introduction of XXXX interactions. The predominance of small gaps is particularly relevant to our investigation, as these instances present the greatest potential for improvement through XXXX terms.

Distribution of minimum spectral gaps for pseudo-random MWIS instances

Figure 1. Distribution of minimum spectral gaps, Δ\Delta, for MWIS instances generated using the pseudo-random construction prior to the introduction of XXXX interactions. The histogram shows the number of instances within logarithmically spaced bins. The distribution is concentrated between 10−4<Δ≤10−210^{-4}<\Delta\leq10^{-2}, indicating that the construction predominantly generates small-gap instances.

Now we present the numerical results analysing the effect of the different XXXX placement strategies on these pseudo-random MWIS instances.

Comparison of XX placement strategies

We assume a XXXX budget of 3 (i.e., precisely 3 XXXX edges), and compare the three topology-constrained strategies in Section IV with the case without XXXX interactions. In addition, we also benchmark the results from strategic placement against the random placement of three XXXX edges for each instance. Figure 2 summarises the results. Points above the dashed line, defined by Δc=Δ\Delta_{\mathrm{c}}=\Delta, indicate an enhancement of the minimum gap. Across all strategies, the largest improvements are observed for instances with small original gaps, while the gap values with and without the additional XXXX terms approach each other as Δ\Delta increases. Random XXXX edges generally produces more modest enhancements, with most instances remaining comparatively close to the Δc=Δ\Delta_{\mathrm{c}}=\Delta line. In contrast, the topology-constrained strategies yield substantially larger improvements in the small-gap regime, with the ambivalent field-strength and high edge-betweenness strategies producing increases of more than an order of magnitude for the smaller-gap instances.

Comparison of the original minimum energy gap $\Delta$ with the minimum gap $\Delta_{\mathrm{c}}$ obtained after introducing three $XX$ terms for four edge-selection strategies

Figure 2. Comparison of the original minimum energy gap Δ\Delta with the minimum gap Δc\Delta_{\mathrm{c}} obtained after introducing three XXXX terms on 100 constructed hard MWIS instances, for the four edge-selection strategies: random edges, high weight-conflict, ambivalent field-strength, and high edge-betweenness. Both axes are logarithmic. The dashed line denotes Δc=Δ\Delta_{\mathrm{c}}=\Delta; points above this line therefore correspond to an increase in the minimum gap from the XXXX interactions. The insets show the distribution of the improvement ratio Δc/Δ\Delta_{\mathrm{c}}/\Delta, grouped according to the order of magnitude of the original gap Δ\Delta. The purple horizontal line within each box denotes the median and the green circular marker denotes the mean. The lower and upper edges of each box correspond to the first and third quartiles, respectively. Whiskers extend to the most extreme data points lying within 1.5 times the interquartile range of the corresponding quartile, while points outside this range are shown individually as outliers. In accordance with the notation in [15], an inset label 10−n10^{-n} denotes instances with 10−(n+1)<Δ≤10−n10^{-(n+1)}<\Delta\leq10^{-n}.

Scaling with the XXXX budget

To investigate how the performance scales with the XXXX budget, we fix the placement strategy to high edge-betweenness and increase the number of XXXX edges from 1 to 7. Figure 3 shows that increasing the XXXX budget generally increases the enhancement of the minimum gap, with the effect again being most pronounced for instances with small original gaps. The improvement is substantial when increasing the budget from a single XXXX to several XXXX interactions, as reflected by both the increasing number of points above the Δc=Δ\Delta_c = \Delta line and the larger values of Δc/Δ\Delta_c/\Delta in the inset distributions. However, the improvement exhibits diminishing returns. Beyond a moderate XXXX budget, increasing the number of XXXX edges further produces only marginal additional enhancement. For instances with larger original gaps, Δc/Δ\Delta_c/\Delta remains concentrated near unity, indicating that increasing the XXXX budget provides little additional benefit in this regime.

Four scatter plots comparing the original minimum energy gap $\Delta$ with the minimum gap $\Delta_c$ after introducing 1, 3, 5, and 7 $XX$ edges, with inset box plots of the improvement ratio $\Delta_c/\Delta$

Figure 3. Effect of increasing the XXXX budget for the high edge-betweenness placement strategy on 100 constructed hard MWIS instances. The panels show a comparison of the original minimum energy gap Δ\Delta with the minimum gap Δc\Delta_c obtained after introducing XXXX terms for budgets of 1, 3, 5, and 7 XXXX edges. The dashed line denotes Δc=Δ\Delta_c = \Delta, such that points above the line correspond to an enhancement of the minimum gap. Increasing the XXXX budget generally improves the minimum gap, particularly for instances with small Δ\Delta, although the additional improvement diminishes at larger budgets. The insets show the distribution of the improvement ratio Δc/Δ\Delta_c/\Delta, grouped according to the order of magnitude of the original gap Δ\Delta. The purple line and the green circular marker denote the median and mean, respectively; the box edges indicate the first and third quartiles, the whiskers extend to the most extreme non-outlier values, and orange circles denote outliers more than 1.5 times more than the inter-quartile range. An inset label 10−n10^{-n} denotes the interval 10−(n+1)<Δ≤10−n10^{-(n+1)} < \Delta\le10^{-n}.

Scaling with the length of connected XXXX terms

To assess the impact of the parity-based gadget construction constraint on the XXXX graph geometry, we fix the placement strategy to high edge-betweenness and the total XXXX budget to 7, and vary the maximum allowed length of a connected XXXX graph component. As discussed in Section III, in the parity-based gadget implementation of XXXX couplings, when several XXXX edges are connected into a single component, qubits in the interior of that component lose the ability to support independent single-XX terms. Figure 4 therefore probes the trade-off between allowing more extended XXXX graph structures and preserving local transverse-field degrees of freedom. For the smallest-gap instances, increasing the maximum component length does not lead to a monotonic improvement. While allowing short connected components can retain substantial gap enhancement, the benefit diminishes as longer components are permitted, and in some cases the performance becomes worse. This suggests that the gain obtained from introducing additional connectivity to the XXXX-interaction graph can be offset by the corresponding loss of local transverse-field degrees of freedom.

Four-panel comparison of minimum energy gaps for XX interactions with maximum connected-component lengths 1, 3, 5, and 7

Figure 4. Effect of the maximum connected-component length of the XXXX-interaction graph for the high edge-betweenness placement strategy at fixed XXXX budget 7, on 100 constructed hard MWIS instances. The four panels correspond to the cases (1, 7), (3, 7), (5, 7), and (7, 7), where the first entry denotes the maximum allowed length of a connected XXXX component and the second denotes the total number of XXXX edges included. Each panel shows a comparison of the original minimum energy gap Δ\Delta with the minimum gap. The dashed line denotes Δc=Δ\Delta_{\mathrm{c}} = \Delta, so points above the line correspond to an enhancement of the minimum gap. For the smallest-gap instances, increasing the allowed component length beyond a certain value exhibits diminishing returns and can in some cases reduce the gap enhancement, reflecting the trade-off between increased XXXX connectivity and the loss of single-XX degrees of freedom in the parity-based gadget construction. The insets show the distribution of Δc/Δ\Delta_{\mathrm{c}}/\Delta, grouped by the order of magnitude of Δ\Delta. The purple line and green circular marker denote the median and mean, respectively; the box edges indicate the first and third quartiles, whiskers extend to the most extreme non-outlier values within 1.5 times the interquartile range, while orange circles denote outliers. An inset label 10−n10^{-n} denotes the interval 10−(n+1)<Δ≤10−n10^{-(n+1)} < \Delta\le10^{-n}.

Numerical analysis on Erdős–Rényi graph-instances

Definition VI.1 (Erdős–Rényi graphs). An Erdős–Rényi graph G(n,p)G(n,p) is a simple undirected graph on the vertex set V={1,…,n}V = \{1,\ldots,n\}, in which each unordered pair of distinct vertices {i,j}⊆V\{i,j\} \subseteq V is included as an edge independently with probability pp.

Following [15], we extend our investigation to random Erdős–Rényi graph instances of the MWIS problem. We consider graphs with N=10N = 10 vertices and edge probability p=0.6p = 0.6. For each graph, the MWIS parameters are sampled independently and uniformly, according to

Jij∼U[1,2],wi∼U[0,1],(23)J_{ij} \sim\mathcal{U}[1,2], \qquad w_i \sim\mathcal{U}[0,1], \tag*{(23)}

for every (i,j)∈E(i,j) \in E and i∈Vi \in V, respectively. The choice Jij>wiJ_{ij} > w_i ensures that the energetic penalty associated with selecting adjacent vertices dominates the contribution from any individual vertex weight, so that configurations violating the independence constraint are energetically disfavoured.

Figure 5 shows the distribution of minimum spectral gaps Δ\Delta for MWIS instances generated on random Erdős–Rényi graphs prior to the introduction of XXXX interactions. Unlike the planted small-gap instances considered in the previous section, the distribution of Δ\Delta is concentrated between 10−2<Δ≤10−010^{-2} < \Delta\le10^{-0}, as these ER instances do not contain an explicitly engineered hard substructure. They therefore provide a complementary test of whether the XXXX placement strategies remain effective on generic random graph topologies.

Histogram of minimum spectral gaps for ER instances

Figure 5. Distribution of minimum spectral gaps Δ\Delta for MWIS instances on random Erdős–Rényi graphs prior to the introduction of XXXX interactions. The histogram shows the number of instances within logarithmically spaced bins. The distribution is concentrated between 10−2<Δ≤10−010^{-2} < \Delta\le10^{-0}, as they do not contain any explicitly engineered hard substructure.

Comparison of XXXX placement strategies

To test whether the XXXX placement strategies generalise beyond the planted small-gap instances, we generate 10,000 random Erdős–Rényi MWIS instances, allowing us to sample a sufficient number of instances with small minimum gaps. We consider the two topology-constrained strategies that performed best on the planted small-gap instances, namely ambivalent field-strength and high edge-betweenness. For both strategies, we fix the XXXX budget to 7 and restrict each connected XXXX-interaction graph component to have length at most 3. Figure 6 shows that both strategies retain the same qualitative behaviour observed for the planted small-gap instances. For instances with relatively large original gaps, the addition of XXXX interactions provides little improvement and can even lead to a modest reduction in the minimum gap, with Δc/Δ\Delta_c/\Delta concentrated around or slightly below unity. In contrast, the enhancement becomes increasingly pronounced as the original gap decreases. In the smallest-gap regimes, both strategies produce substantial increases in the minimum gap, often by more than an order of magnitude. This indicates that the topology-constrained placement strategies generalise to random Erdős–Rényi instances, with their principal benefit concentrated on the hardest, small-gap instances.

Performance of the ambivalent field-strength and high edge-betweenness placement strategies

Figure 6. Performance of the ambivalent field-strength and high edge-betweenness placement strategies on 10, 000 random Erdős–Rényi MWIS instances. For both strategies, the XXXX budget is fixed to 7, with connected XXXX graph components restricted to a maximum length of 3. The box plots show the distribution of the improvement ratio Δc/Δ\Delta_{\mathrm{c}}/\Delta, grouped according to the order of magnitude of the original minimum gap Δ\Delta. The dashed horizontal line denotes Δc/Δ=1\Delta_{\mathrm{c}}/\Delta= 1, corresponding to no change in the minimum gap. Both strategies yield little or slightly detrimental effect for large-gap instances, while producing increasingly strong enhancements as Δ\Delta decreases, with the largest improvements occurring for the smallest-gap instances. The purple horizontal line and green circular marker denote the median and mean, respectively; the box edges indicate the first and third quartiles, the whiskers extend to the most extreme non-outlier values, and orange circles denote outliers more than 1.5 times from the interquartile range. An axis label 10−n10^{-n} denotes the interval 10−(n+1)<Δ≤10−n10^{-(n+1)} < \Delta\le10^{-n}.

Comparison with unconstrained XXXX placement

We believe another meaningful question to investigate is whether the gap enhancements reported in [15], where an XXXX interaction is introduced for each problem edge, can be reproduced subject to the implementation constraints imposed by the parity-based gadget construction. Rather than selecting the placement of XXXX interactions according to a scoring criterion, we therefore seek to place XXXX edges on as many problem edges as possible while respecting the local topology constraints of the implementation. Since the parity-based gadget construction requires the XXXX-interaction graph to be non-branching, every vertex may have degree at most two. At first glance, the resulting optimisation problem translates nicely to the maximum-cardinality 2-matching problem.

Definition VI.2 (Maximum 2-matching). Let G=(V,E)G = (V,E) be a simple undirected graph. A maximum 2-matching is a largest edge set M⊆EM \subseteq E such that

deg⁡M(v)≤2∀v∈V.\deg_M(v) \le2 \qquad\forall v \in V.

where deg⁡M(v)\operatorname{deg}_{M}(v) denotes the number of edges in MM incident on vv.

The maximum 2-matching problem is a standard special case of bb-matching and can be reduced in polynomial time to an ordinary matching problem [27], which may then be solved using Edmonds’ blossom algorithm [28]. As this procedure is well established, we do not reproduce it here and instead refer the interested reader to these classical results. For our application, however, the degree constraint alone is insufficient. Under the parity-based gadget construction, vertices lying in the interior of a connected XXXX graph component lose their independent single-XX degree of freedom. We therefore consider a greedy bounded 2-matching heuristic that iteratively selects candidate problem edges while enforcing both the degree and component-size constraints. Specifically, the candidate edges are first ordered so that edges incident on lower-degree vertices are considered first, with ties broken randomly. The edges are then processed sequentially: an edge is accepted only if neither endpoint already has degree two and if the edge’s addition would not cause the resulting connected component to exceed the prescribed maximum number of edges. Connected components and their sizes are tracked dynamically using a union–find data structure, allowing both the merging of distinct path components and the closure of a path into a loop to be checked against the component-size bound. The resulting XXXX graph is therefore a maximal disjoint union of paths and cycles of bounded size, although the greedy construction is not guaranteed to yield a maximum-cardinality set of feasible edges.

To compare the unconstrained and topology-constrained constructions on the same footing, Figure 7 benchmarks both the all-problem-edge placement and the bounded 2-matching heuristic against the no-XXXX case. In the bounded 2-matching heuristic, we restrict the connected XXXX graph components to a maximum length of three. In both panels, the strongest enhancements occur for instances with the smallest original minimum gaps, where Δc/Δ\Delta_{\mathrm{c}}/\Delta is often well above unity and can exceed one or two orders of magnitude. This shows that both constructions are able to substantially enlarge the gap precisely in the hard-instance regime. As the original gap increases, however, the improvement decreases and the ratio concentrates around Δc/Δ≈1\Delta_{\mathrm{c}}/\Delta\approx1, indicating little effect on easier instances. Comparing the two panels, the bounded 2-matching heuristic broadly preserves the qualitative advantage of the all-problem-edge construction in the small-gap regime, while exhibiting a wider spread of outcomes and a greater number of instances with Δc/Δ<1\Delta_{\mathrm{c}}/\Delta< 1 for intermediate and larger gaps. Importantly the bounded 2-matching heuristic achieves this result with consistently fewer XXXX edges. On average, the bounded 2-matching heuristic places 7.8 XXXX edges per instance, compared to 27 XXXX edges placed per instance on all problem edges.

Comparison of the all-problem-edge construction and the topology-constrained bounded 2-matching construction

Figure 7. Comparison of the all-problem-edge construction (“All problem edges”) and the topology-constrained bounded 2-matching construction (“Bounded 2-matching”), each benchmarked against the case with no XXXX interactions. In bounded 2-matching, the lengths of connected XXXX graph components are additionally constrained to be less than or equal to 3. The box plots show the distribution of the ratio Δc/Δ\Delta_c/\Delta, grouped according to the order of magnitude of the original minimum gap Δ\Delta. The dashed horizontal line denotes Δc/Δ=1\Delta_c/\Delta= 1, corresponding to no change in the minimum gap. In both constructions, the largest gap enhancements occur for the smallest-gap instances, while the effect becomes weaker as Δ\Delta increases. The bounded 2-matching heuristic reproduces the same qualitative improvement on hard instances as the all-problem-edge construction, but on average only placed 7.8 XXXX edges per instance, compared to 27 per instance on all problem edges. The horizontal line within each box and green circular marker denote the median and mean, respectively; the box edges indicate the first and third quartiles, the whiskers extend to the most extreme non-outlier values, and individual points denote outliers more than 1.5 times from the interquartile range. An axis label 10−n10^{-n} denotes the interval 10−(n+1)<Δ≤10−n10^{-(n+1)} < \Delta\le10^{-n}.

Thus, the topology-constrained construction retains the main benefit of introducing XXXX interactions to hard instances with the need for fewer XXXX edges, albeit with increased variability relative to the unconstrained placement of XXXX terms on all problem edges.

Concluding remarks

In this work we have investigated efficient strategies for placing a limited number of XXXX edges in quantum annealing for the maximum weight independent set problem, while explicitly taking into account both resource constraints and the topological restrictions arising from an parity-based gadget implementation. We introduced three polynomial-time placement strategies based on high vertex-weight conflict, ambivalent local field-strength, and high edge-betweenness, and evaluated their ability to enhance the minimum spectral gap on both deliberately constructed small-gap instances and random Erdős–Rényi graphs.

Our numerical results show that carefully selected subsets of XXXX edges can produce substantial gap enhancements, even when the XXXX interactions are placed only on a small fraction of the problem edges. The benefit is strongly concentrated in the hardest instances: as the original minimum gap decreases, the relative enhancement obtained from XXXX placement becomes increasingly pronounced, with improvements of more than an order of magnitude observed for many of the smallest-gap instances. Among the strategies considered, ambivalent field-strength and high edge-betweenness consistently perform particularly well. These qualitative trends persist for random Erdős–Rényi instances, indicating that the observed improvement is not restricted to the particular structure of the planted small-gap instances.

We further investigated how the performance depends on the available XXXX budget and on the topology of the XXXX-interaction graph. Increasing the budget initially leads to substantial improvements, but with diminishing returns once a moderate number of XXXX interactions has been introduced. Likewise, allowing increasingly long connected XXXX graph components does not necessarily improve the minimum gap. Within the parity-based gadget construction, longer components remove independent single-XX degrees of freedom from interior qubits, and the resulting loss of local transverse driving can offset the benefit gained from introducing additional XXXX connectivity. This demonstrates that the effectiveness of XXXX-term placement depends not only on the number of XXXX interactions, but also on the geometry of the interaction graph.

Finally, we compared the topology-constrained construction with the unconstrained placement of XXXX interactions on all problem edges. A greedy bounded 2-matching construction was able to retain the principal gap enhancement observed for the hardest instances while using substantially fewer XXXX interactions. This suggests that much of the advantage of dense XXXX placement can survive under considerably more restrictive and experimentally motivated connectivity constraints.

A key advantage of the standard driver Hamiltonian is the ease with which its ground state can be prepared.

Although we have not yet addressed initialisation for the modified driver in Eq. (16), the gadget construction underlying our approach means that the anneal is initialised not in the ground state of the modified driver, but in that of the standard driver in Eq. (7), which describes the physical Hamiltonian of the system. Some of the subtleties of what this means for the initial logical state are discussed in [20]. Crucially, since the ground-state of the physical gadget Hamiltonian at the end of the anneal corresponds to the original problem ground-state, adiabatic evolution starting in the ground state of the standard driver provides a route to the optimal solution.

An important direction for future work is to refine the structure of the parity-based gadget construction itself. In particular, it would be useful to design XXXX-interaction graph geometries that preserve the favourable gap enhancement while minimising the occurrence of higher-order ZZ interactions and other implementation overheads introduced by the mapping. More generally, jointly optimising the choice of XXXX edges, connected-component geometry, and ancilla-qubit placements could provide a route towards interaction graph choices that are both spectrally effective and more compatible with realistic quantum-annealing hardware. Additionally, extending these investigations to larger problem sizes and alternative classes of optimisation problems also would further clarify how broadly such constrained XXXX placement strategies can be applied.

Acknowledgments

This work is supported by the QCi3 Hub, funded by EPSRC (grant ref. EP/Z53318X/1).

References

  1. [1]J. F. A. Sales and R. A. P. Araos, Adiabatic quantum computing for logistic transport optimization (2023), arXiv:2301.07691 [quant-ph].
  2. [2]E. Gabbassov, PLOS ONE 17, e0274632 (2022).
  3. [3]A. Witt, C. Körber, A. Kirštadter, and T. Luu, Tactile network resource allocation enabled by quantum annealing based on ilp modeling (2023), arXiv:2212.07854 [quant-ph].arxiv.org/abs/2212.07854
  4. [4]T. Otsuka, A. Li, H. Takesue, K. Inaba, K. Aihara, and M. Hasegawa, High-speed resource allocation algorithm using a coherent Ising machine for noma systems (2022), arXiv:2212.01578 [cs.IT].arxiv.org/abs/2212.01578
  5. [5]Álvaro Rubio-García, J. J. García-Ripoll, and D. Porras, Portfolio optimization with discrete simulated annealing (2022), arXiv:2210.08007 [cond-mat.stat-mech].
  6. [6]G. E. Santoro, R. Martoňák, E. Tosatti, and R. Car, Science 295, 2427 (2002), arXiv:cond-mat/0205820.
  7. [7]E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution (2000), arXiv:quant-ph/0001106 [quant-ph].DOI
  8. [8]T. Albash and D. A. Lidar, Reviews of Modern Physics 90, 015002 (2018).
  9. [9]Y. Seki and H. Nishimori, Physical Review E 85, 051112 (2012).
  10. [10]L. Hormozi, E. W. Brown, G. Carleo, and M. Troyer, Physical Review B 95, 184416 (2017).
  11. [11]T. Albash, Physical Review A 99, 042334 (2019).
  12. [12]V. Mehta, F. Jin, H. D. Raedt, and K. Michielsen, Physical Review A 104, 032421 (2021).
  13. [13]N. Feinstein, L. Fry-Bouriaux, S. Bose, and P. A. War- burton, Physical Review A 110, 042609 (2024).
  14. [14]R. Ghosh, L. A. Nutricati, N. Feinstein, P. A. Warburton, and S. Bose, Physical Review Research 8, 013301 (2026).
  15. [15]L. A. Nutricati, R. Ghosh, N. Feinstein, S. Bose, and P. A. Warburton, Quantum Science and Technology 10, 045010 (2025).
  16. [16]H. Zhang, C. Ding, D. K. Weiss, Z. Huang, Y. Ma, C. Guinn, S. Sussman, S. P. Chitta, D. Chen, A. A. Houck, J. Koch, and D. I. Schuster, Tunable inductive coupler for high fidelity gates between fluxonium qubits (2023), arXiv:2309.05720 [quant-ph].arxiv.org/abs/2309.05720
  17. [17]I. Ozfidan, C. Deng, A. Smirnov, T. Lanting, R. Harris, L. Swenson, J. Whittaker, F. Altomare, M. Babcock, C. Baron, A. Berkley, K. Boothby, H. Christiani, P. Bunyk, C. Enderud, B. Evert, M. Hager, A. Hajda, J. Hilton, S. Huang, E. Hoskinson, M. Johnson, K. Jooya, E. Ladizinsky, N. Ladizinsky, R. Li, A. MacDonald, D. Marsden, G. Marsden, T. Medina, R. Molavi, R. Neufeld, M. Nissen, M. Norouzpour, T. Oh, I. Pavlov, I. Perminov, G. Poulin-Lamarre, M. Reis, T. Prescott, C. Rich, Y. Sato, G. Sterling, N. Tsai, M. Volkmann, W. Wilkinson, J. Yao, and M. Amin, Phys. Rev. Appl. 13, 034037 (2020).
  18. [18]A. J. Kerman, New Journal of Physics 21, 073030 (2019).
  19. [19]R. J. Banks, N. Feinstein, R. Ghosh, S. Bose, and P. A. Warburton, Gadgets for simulating a non-native xx interaction in quantum annealing (2025), arXiv:2503.16663.arxiv.org/abs/2503.16663
  20. [20]R. J. Banks, N. Feinstein, R. Ghosh, S. Schulz, K. Michielsen, S. Bose, and P. A. Warburton, Enhanced analogue quantum computation with a logically-encoded xx gadget (2026), arXiv:2610.13845 [quant-ph].arxiv.org/abs/2610.13845
  21. [21]D. Headley and N. Chancellor, Quantum Science and Technology 11, 035010 (2026).
  22. [22]N. Dattani, Quadratization in discrete optimization and quantum mechanics (2019), arXiv:1901.04405 [quant-ph].arxiv.org/abs/1901.04405
  23. [23]A. A. Hagberg, D. A. Schult, and P. J. Swart, in Proceedings of the 7th Python in Science Conference (Pasadena, CA USA, 2008) pp. 11–15.DOI
  24. [24]NetworkX Developers, Centrality Algorithms — NetworkX Documentation, NetworkX (2026), accessed: 2026-07-24.
  25. [25]U. Brandes, Social Networks 30, 136 (2008).
  26. [26]N. Feinstein, I. Shalashilin, S. Bose, and P. A. Warburton, Quantum Science and Technology 10, 025011 (2025).
  27. [27]A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Vol. 24 (Springer Science & Business Media, 2003).
  28. [28]J. Edmonds, Canadian Journal of Mathematics 17, 449–467 (1965).

Paper details

vlnc:W_a6498h9f
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