WorksPhysics and Astronomy
Efficient 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 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 couplings come with hardware overhead and connectivity constraints. These limitations motivate the use of only a limited number of interactions. In this paper, we investigate 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 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 interactions along edges of the problem graph can significantly improve the minimum spectral gap [15].
The unrestricted addition of 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 interactions. For superconducting flux qubits of the type used by D-Wave, for example, an 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 interaction when large local fields are applied to both qubits. Gadgets that implement effective 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 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 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 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 interactions to be introduced. We therefore study placement as a constrained selection problem, in which both the number and topology of the available 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 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 couplings and the topological constraints that it imposes. Section IV introduces the -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
be an undirected graph with vertex set and edge set , and let each vertex be assigned a positive weight . An independent set is a subset such that no two vertices in are adjacent. The maximum weight independent set problem asks for an independent set of maximum total weight,
By introducing binary variables , where indicates that vertex is included in the independent set, MWIS can be expressed as the constrained optimisation problem
subject to
To encode this as a quantum Hamiltonian, we make the standard translation
where . So, provided the edge penalty is chosen sufficiently large, the ground state of the Hamiltonian
corresponds to a maximum-weight independent set of the original graph. In Eq. (6), is the degree of vertex , and is its weight.
The conventional transverse-field driver Hamiltonian is
whose ground state is the uniform superposition of computational basis states. A standard annealing schedule interpolates between Eqs. (2.7) and (2.6),
where and . Furthermore, the spectral gap of the Hamiltonian is
and its minimum over the anneal is defined as
For difficult instances, the interpolation in Eq. (8) may encounter a narrow avoided crossing and hence a small value of . It is these small gaps which we aim to mitigate through the introduction of interactions.
Parity-based gadget implementation of XX couplings
To obtain a hardware-motivated model for how such interactions might enter the anneal in practice, we consider the parity-based 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 interactions with a physical setting that only includes fields and interactions that we have access to—i.e., fields, fields and interactions. To implement an 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
The corresponding logical Pauli- operators are therefore
Since , a interaction between the two logical qubits reduces to a two-body interaction between the outer physical qubits:
The logical transverse operators can be identified by considering how flipping each physical qubit affects the encoded parities. Flipping either outer qubit, or , changes only one of the two logical parities. Thus, the individual logical operators can be represented as
In contrast, the central physical qubit is shared by both parity pairs, so flipping it simultaneously reverses both logical parities. Its transverse operator therefore implements the logical interaction:
The gadget can be extended to produce a chain of logical qubits with interactions between them through effectively chaining parity encoded qubits together. The cost is the loss of local 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 terms. Under the parity encoding, a transverse field acting on a physical qubit induces a transverse 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 interaction. More generally, a branching point of degree would produce a -body transverse interaction in the parity-encoded description. To retain a driver Hamiltonian containing only one- and two-body transverse terms, nodes in the -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 term between an encoded qubit and a non-encoded qubit require physical three-local interactions. Similarly, a interaction between two encoded qubits that are not adjacent in the -interaction graph requires a physical four-local term. Such three- and four-local 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 interactions that are included.
In this work we will not be considering the physical Hamiltonian associated with the gadget. Rather, we directly introducing interactions into the annealing Hamiltonian in a way that is guided by the constraints on the -interaction graph that the gadget imposes. The interactions enter the annealing Hamiltonian as part of the driver, such that the new driver can be written as
where denotes the set of edges and is restricted to consisting of disconnected chains and loops, and is obtained from standard driver by removing the single-qubit fields on qubits incident to two edges in . The practical placement problem studied in the following section can therefore be formulated schematically as
so as to improve
subject simultaneously to the -budget constraint 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 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 by its score
in descending order, and selects the top edges with the highest .
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 in the independent-set through the term
On the one hand, since , including vertex in the set will lower the energy of the Hamiltonian by , but at the same time it raises the energy by the penalty term . Therefore, we reason that vertices with small 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 by its score
in descending order, and outputs the top edges with the highest score .
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 , is it defined as
where is the set of vertices, is the number of shortest-paths between vertex and , and is the number of those paths passing through edge .
For a graph , the function NetworkX.edge_betweenness_centrality(G) computes this quantity efficiently in time using Brandes’ algorithm [25]. In this strategy, we therefore rank each problem edge by its edge-betweenness centrality score, in descending order. Then the strategy produces 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 , 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, , prior to the introduction of interactions. The predominance of small gaps is particularly relevant to our investigation, as these instances present the greatest potential for improvement through terms.

Figure 1. Distribution of minimum spectral gaps, , for MWIS instances generated using the pseudo-random construction prior to the introduction of interactions. The histogram shows the number of instances within logarithmically spaced bins. The distribution is concentrated between , indicating that the construction predominantly generates small-gap instances.
Now we present the numerical results analysing the effect of the different placement strategies on these pseudo-random MWIS instances.
Comparison of XX placement strategies
We assume a budget of 3 (i.e., precisely 3 edges), and compare the three topology-constrained strategies in Section IV with the case without interactions. In addition, we also benchmark the results from strategic placement against the random placement of three edges for each instance. Figure 2 summarises the results. Points above the dashed line, defined by , 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 terms approach each other as increases. Random edges generally produces more modest enhancements, with most instances remaining comparatively close to the 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.

Figure 2. Comparison of the original minimum energy gap with the minimum gap obtained after introducing three 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 ; points above this line therefore correspond to an increase in the minimum gap from the interactions. The insets show the distribution of the improvement ratio , grouped according to the order of magnitude of the original gap . 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 denotes instances with .
Scaling with the budget
To investigate how the performance scales with the budget, we fix the placement strategy to high edge-betweenness and increase the number of edges from 1 to 7. Figure 3 shows that increasing the 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 to several interactions, as reflected by both the increasing number of points above the line and the larger values of in the inset distributions. However, the improvement exhibits diminishing returns. Beyond a moderate budget, increasing the number of edges further produces only marginal additional enhancement. For instances with larger original gaps, remains concentrated near unity, indicating that increasing the budget provides little additional benefit in this regime.

Figure 3. Effect of increasing the 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 with the minimum gap obtained after introducing terms for budgets of 1, 3, 5, and 7 edges. The dashed line denotes , such that points above the line correspond to an enhancement of the minimum gap. Increasing the budget generally improves the minimum gap, particularly for instances with small , although the additional improvement diminishes at larger budgets. The insets show the distribution of the improvement ratio , grouped according to the order of magnitude of the original gap . 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 denotes the interval .
Scaling with the length of connected terms
To assess the impact of the parity-based gadget construction constraint on the graph geometry, we fix the placement strategy to high edge-betweenness and the total budget to 7, and vary the maximum allowed length of a connected graph component. As discussed in Section III, in the parity-based gadget implementation of couplings, when several edges are connected into a single component, qubits in the interior of that component lose the ability to support independent single- terms. Figure 4 therefore probes the trade-off between allowing more extended 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 -interaction graph can be offset by the corresponding loss of local transverse-field degrees of freedom.

Figure 4. Effect of the maximum connected-component length of the -interaction graph for the high edge-betweenness placement strategy at fixed 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 component and the second denotes the total number of edges included. Each panel shows a comparison of the original minimum energy gap with the minimum gap. The dashed line denotes , 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 connectivity and the loss of single- degrees of freedom in the parity-based gadget construction. The insets show the distribution of , grouped by the order of magnitude of . 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 denotes the interval .
Numerical analysis on Erdős–Rényi graph-instances
Definition VI.1 (Erdős–Rényi graphs). An Erdős–Rényi graph is a simple undirected graph on the vertex set , in which each unordered pair of distinct vertices is included as an edge independently with probability .
Following [15], we extend our investigation to random Erdős–Rényi graph instances of the MWIS problem. We consider graphs with vertices and edge probability . For each graph, the MWIS parameters are sampled independently and uniformly, according to
for every and , respectively. The choice 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 for MWIS instances generated on random Erdős–Rényi graphs prior to the introduction of interactions. Unlike the planted small-gap instances considered in the previous section, the distribution of is concentrated between , as these ER instances do not contain an explicitly engineered hard substructure. They therefore provide a complementary test of whether the placement strategies remain effective on generic random graph topologies.

Figure 5. Distribution of minimum spectral gaps for MWIS instances on random Erdős–Rényi graphs prior to the introduction of interactions. The histogram shows the number of instances within logarithmically spaced bins. The distribution is concentrated between , as they do not contain any explicitly engineered hard substructure.
Comparison of placement strategies
To test whether the 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 budget to 7 and restrict each connected -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 interactions provides little improvement and can even lead to a modest reduction in the minimum gap, with 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.

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 budget is fixed to 7, with connected graph components restricted to a maximum length of 3. The box plots show the distribution of the improvement ratio , grouped according to the order of magnitude of the original minimum gap . The dashed horizontal line denotes , 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 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 denotes the interval .
Comparison with unconstrained placement
We believe another meaningful question to investigate is whether the gap enhancements reported in [15], where an 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 interactions according to a scoring criterion, we therefore seek to place 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 -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 be a simple undirected graph. A maximum 2-matching is a largest edge set such that
where denotes the number of edges in incident on .
The maximum 2-matching problem is a standard special case of -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 graph component lose their independent single- 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 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- case. In the bounded 2-matching heuristic, we restrict the connected graph components to a maximum length of three. In both panels, the strongest enhancements occur for instances with the smallest original minimum gaps, where 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 , 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 for intermediate and larger gaps. Importantly the bounded 2-matching heuristic achieves this result with consistently fewer edges. On average, the bounded 2-matching heuristic places 7.8 edges per instance, compared to 27 edges placed per instance on all problem edges.

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 interactions. In bounded 2-matching, the lengths of connected graph components are additionally constrained to be less than or equal to 3. The box plots show the distribution of the ratio , grouped according to the order of magnitude of the original minimum gap . The dashed horizontal line denotes , 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 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 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 denotes the interval .
Thus, the topology-constrained construction retains the main benefit of introducing interactions to hard instances with the need for fewer edges, albeit with increased variability relative to the unconstrained placement of terms on all problem edges.
Concluding remarks
In this work we have investigated efficient strategies for placing a limited number of 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 edges can produce substantial gap enhancements, even when the 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 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 budget and on the topology of the -interaction graph. Increasing the budget initially leads to substantial improvements, but with diminishing returns once a moderate number of interactions has been introduced. Likewise, allowing increasingly long connected graph components does not necessarily improve the minimum gap. Within the parity-based gadget construction, longer components remove independent single- degrees of freedom from interior qubits, and the resulting loss of local transverse driving can offset the benefit gained from introducing additional connectivity. This demonstrates that the effectiveness of -term placement depends not only on the number of interactions, but also on the geometry of the interaction graph.
Finally, we compared the topology-constrained construction with the unconstrained placement of 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 interactions. This suggests that much of the advantage of dense 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 -interaction graph geometries that preserve the favourable gap enhancement while minimising the occurrence of higher-order interactions and other implementation overheads introduced by the mapping. More generally, jointly optimising the choice of 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 placement strategies can be applied.
Acknowledgments
This work is supported by the QCi3 Hub, funded by EPSRC (grant ref. EP/Z53318X/1).
References
- [1]J. F. A. Sales and R. A. P. Araos, Adiabatic quantum computing for logistic transport optimization (2023), arXiv:2301.07691 [quant-ph].
- [2]E. Gabbassov, PLOS ONE 17, e0274632 (2022).
- [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]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]Á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]G. E. Santoro, R. Martoňák, E. Tosatti, and R. Car, Science 295, 2427 (2002), arXiv:cond-mat/0205820.
- [7]E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution (2000), arXiv:quant-ph/0001106 [quant-ph].DOI
- [8]T. Albash and D. A. Lidar, Reviews of Modern Physics 90, 015002 (2018).
- [9]Y. Seki and H. Nishimori, Physical Review E 85, 051112 (2012).
- [10]L. Hormozi, E. W. Brown, G. Carleo, and M. Troyer, Physical Review B 95, 184416 (2017).
- [11]T. Albash, Physical Review A 99, 042334 (2019).
- [12]V. Mehta, F. Jin, H. D. Raedt, and K. Michielsen, Physical Review A 104, 032421 (2021).
- [13]N. Feinstein, L. Fry-Bouriaux, S. Bose, and P. A. War- burton, Physical Review A 110, 042609 (2024).
- [14]R. Ghosh, L. A. Nutricati, N. Feinstein, P. A. Warburton, and S. Bose, Physical Review Research 8, 013301 (2026).
- [15]L. A. Nutricati, R. Ghosh, N. Feinstein, S. Bose, and P. A. Warburton, Quantum Science and Technology 10, 045010 (2025).
- [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]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]A. J. Kerman, New Journal of Physics 21, 073030 (2019).
- [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]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]D. Headley and N. Chancellor, Quantum Science and Technology 11, 035010 (2026).
- [22]N. Dattani, Quadratization in discrete optimization and quantum mechanics (2019), arXiv:1901.04405 [quant-ph].arxiv.org/abs/1901.04405
- [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]NetworkX Developers, Centrality Algorithms — NetworkX Documentation, NetworkX (2026), accessed: 2026-07-24.
- [25]U. Brandes, Social Networks 30, 136 (2008).
- [26]N. Feinstein, I. Shalashilin, S. Bose, and P. A. Warburton, Quantum Science and Technology 10, 025011 (2025).
- [27]A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Vol. 24 (Springer Science & Business Media, 2003).
- [28]J. Edmonds, Canadian Journal of Mathematics 17, 449–467 (1965).