Efficient $XX$ Placement Strategies for Energy-Gap Enhancement in Quantum Annealing

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 $XX$ 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 $XX$ couplings come with hardware overhead and connectivity constraints. These limitations motivate the use of only a limited number of $XX$ interactions. In this paper, we investigate $XX$ 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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.20902
Primary Topic
Quantum Computing Algorithms and Architecture
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Efficient $XX$ Placement Strategies for Energy-Gap Enhancement in Quantum Annealing

Natasha Feinstein, P A Warburton, Jennivine Chen
arXiv (Cornell University)
Quantum Computing Algorithms and Architecture
preprint

Efficient $XX$ Placement Strategies for Energy-Gap Enhancement in Quantum Annealing

Natasha Feinstein, P A Warburton, Jennivine Chen
preprint en

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 $XX$ 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 $XX$ couplings come with hardware overhead and connectivity constraints. These limitations motivate the use of only a limited number of $XX$ interactions. In this paper, we investigate $XX$ 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.

arXiv (Cornell University)
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon